Open quantum systems are harder to track than open
classical systems
Prahlad Warszawski
1
and Howard M. Wiseman
2
1
Centre of Excellence in Engineered Quantum Systems (Australian Research Council),
School of Physics, The University of Sydney, Sydney, New South Wales 2006, Australia
2
Centre for Quantum Computation and Communication Technology (Australian Research Council),
Centre for Quantum Dynamics, Griffith University, Brisbane, Queensland 4111, Australia
October 4, 2019
For a Markovian (in the strongest sense) open quantum system it is possi-
ble, by continuously monitoring the environment, to perfectly track the system;
that is, to know the stochastically evolving pure state of the system without
altering the master equation. In general, even for a system with a finite Hilbert
space dimension D, the pure state trajectory will explore an infinite number
of points in Hilbert space, meaning that the dimension K of the classical mem-
ory required for the tracking is infinite. However, Karasik and Wiseman [Phys.
Rev. Lett., 106(2):020406, 2011] showed that tracking of a qubit (D
= 2
) is al-
ways possible with a bit (K
= 2
), and gave a heuristic argument implying that
a finite K should be sufficient for any D, although beyond D
= 2
it would be
necessary to have K > D. Our paper is concerned with rigorously investigat-
ing the relationship between D and K
min
, the smallest feasible K. We confirm
the long-standing conjecture of Karasik and Wiseman that, for generic systems
with D >
2
, K
min
> D, by a computational proof (via Hilbert Nullstellensatz
certificates of infeasibility). That is, beyond D
= 2
, D-dimensional open quan-
tum systems are provably harder to track than D-dimensional open classical
systems. We stress that this result allows complete freedom in choice of mon-
itoring scheme, including adaptive monitoring which is, in general, necessary
to implement a physically realizable ensemble (as it is known) of just K pure
states. Moreover, we develop, and better justify, a new heuristic to guide our
expectation of K
min
as a function of D, taking into account the number L of
Lindblad operators as well as symmetries in the problem. The use of invari-
ant subspace and Wigner symmetries (that we recently introduced elsewhere,
[New J. Phys. https://doi.org/10.1088/1367-2630/ab14b2]) makes it tractable
to conduct a numerical search, using the method of polynomial homotopy con-
tinuation, to find finite physically realizable ensembles in D
= 3
. The results of
this search support our heuristic. We thus have confidence in the most interest-
ing feature of our heuristic: in the absence of symmetries, K
min
D
2
, implying
a quadratic gap between the classical and quantum tracking problems. Explicit
adaptive monitoring schemes that realize the discovered finite ensembles are
obtained numerically, thus facilitating future experimental investigations.
Prahlad Warszawski: prahladw@gmail.com
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 1
arXiv:1905.10935v2 [quant-ph] 4 Oct 2019
1 Introduction
Tracking an open quantum system requires measuring the environment to which the system
is coupled. In this way, the experimentalist gains knowledge of the quantum trajectory [1]
followed by the system of interest. For the case of perfect detector efficiency, no system
information is lost into the environment and the system trajectory maps the path of a
pure quantum state. It is of interest to ask, how much memory is required to track a pure
state trajectory of open quantum system? The answer is typically that an infinite memory
is required, due to the fact that generic monitoring schemes will result in a continuous
quantum state trajectory that occupies a non-zero dimensional manifold of pure states.
Remarkably, this is not always the case: it has been shown [26] that, via the implemen-
tation of especially chosen system-dependent adaptive measurement schemes, quantum
trajectories of some systems can be constrained to a finite number, K, of pure quantum
states. This has profound consequences for the memory requirements of tracking an open
quantum system, as a classical device with only K states (a ‘finite state machine’ [7]) is
sufficient to follow the quantum evolution. In this paper, we will investigate the minimum
ensemble size, K
min
, that is achievable, given complete freedom of measurement scheme.
In particular, we compare and contrast K
min
with the dimension, D, of the quantum
system and so address some long-standing open questions of interest raised in Refs. [3, 4].
To elaborate further, we begin by discussing the tracking of an open quantum system
that is
classical
in the sense that the finite ensemble of quantum states that form the system
trajectory are mutually orthogonal. This will serve to benchmark our considerations of
generic open quantum systems. A canonical ‘classical’ example is Einstein’s original model
of stimulated and spontaneous jumps, which, in modern language, describes an open
quantum system weakly coupled to a bath. In equilibrium, Einstein’s theory involves
jumps between energy eigenstates (for example, Bohr’s stationary atomic and molecular
states [8]) that could in principle be monitored, so that the system could be tracked just
by specifying which of these states the system occupies. Implicit in this early model is that
the ensemble size is equal to the number of accessible energy eigenstates, D. Clearly, a D-
state finite, resettable, classical memory is capable of tracking the state of the (effectively)
classical system. Additionally, there is only a single way to monitor the environment that
provides complete information as to the transitions (for the atomic model this would be
the photon number basis).
In contrast to the effectively classical case just discussed, the choice of monitoring of
a generic open quantum system can have a profound effect upon its evolution. The sys-
tem, by definition, is interacting with the environment and, for suitable initial conditions,
becomes entangled with it. The measurement of the environment by an experimentalist
effects ‘quantum steering’ [9] upon the system. In this paper we are concerned with the
case of continuous Markovian dynamics induced by the bath, also known as quantum
white noise (QWN) coupling; the system will then,
in the absence of measurement
, obey
a Lindblad-form master equation (ME) for the density matrix [1]:
˙ρ = Lρ i[
ˆ
H
eff
ρ ρ
ˆ
H
eff
] +
L
X
l=1
ˆc
l
ρˆc
l
, (1)
where
ˆ
H
eff
ˆ
H i
P
l
ˆc
l
ˆc
l
/
2
and
ˆ
H is the Hermitian Hamiltonian. The purpose of
separating Eq. (1) into terms that involve
ˆ
H
eff
and those comprising ˆc
l
ρˆc
l
is that they can
be associated with a purity-preserving unraveling of the ME, as would arise from perfectly
efficient monitoring of the decoherence channels (that are indexed by l). Assuming an
initially pure system state, if a detection in channel l is observed at time t then the system
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 2
jumps from the pre-jump state |ψ(t
)i to the post-jump state |ψ(t)i ˆc
l
|ψ(t
)i. After
the jump, the quantum state evolves under the no-jump evolution operator
ˆ
H
eff
and will
typically not remain stationary unless it happens to be an eigenstate of
ˆ
H
eff
.
The stochastic path followed by the state is known as a quantum trajectory, and
different monitoring schemes will lead to different types of quantum trajectories [1, 10].
In fact, there are an infinite number of ways to measure the environment that maintains
a pure quantum state for the system. This follows from the invariance of Eq. (1) under
the following joint transformations [3, 11]
ˆc
l
(
ˆc
0
m
=
L
X
l=1
S
ml
ˆc
l
+ β
m
)
(2)
ˆ
H
(
ˆ
H
0
=
ˆ
H
i
2
M
X
m=1
(β
m
ˆc
0
m
β
m
ˆc
0†
m
)
)
, (3)
where, with M L,
~
β is an arbitrary complex M-vector and S is an arbitrary M × L
semi-unitary matrix; that is,
P
M
m=1
S
ml
S
ml
0
=
δ
l,l
0
. By unraveling Eq. (1) with {ˆc
0
m
} as the
jump and
ˆ
H
0
eff
=
ˆ
H
0
i
P
M
m=1
ˆc
0
m
ˆc
0
m
/
2
as the no-jump operators, different
~
β and S thus
correspond to different measurement schemes [1, 10]. See endnote [12] for more details.
Monitoring schemes can be divided into those that lead to jumps in the quantum state
[1315] and those that lead to quantum diffusion [10, 16, 17]. The distinction is that,
in an infinitesimal interval of duration time dt, the former involves detector ‘clicks’ that
occur with a probability proportional to dt and deliver a finite amount of new system
information, whereas the latter always deliver an infinitesimal amount of information in
this infinitesimal interval. Here, we are concerned with quantum jumps, rather than
diffusion, as this allows transitions analogous to those contained in the Einstein model.
However, there is typically still a large distinction between classical and quantum jump
trajectories: in between the quantum jumps the experimentalist is continuously updating
the system state in a non-trivial way, as the ‘no-click’ results also carry information, albeit
an amount that scales with dt. This information affects the state even when it is a state
of maximal information (i.e. pure), unlike the classical case, leading to smooth but non-
unitary evolution between jumps. Thus, it is clear that the system generically explores a
continuum of states in Hilbert space.
Whilst a non-zero dimensional manifold of states is therefore typically associated
with continuous measurement, the Schr¨odinger-Hughston-Jozsa-Wootters (S-HJW) the-
orem [1820], by contrast, gives physical meaning to any pure state ensemble representing
a mixed state matrix (also called a density matrix) ρ. In particular, for finite D
=
rank
(
ρ
)
,
one may consider ensembles,
ρ =
K
X
k=1
k
|φ
k
i hφ
k
| , (4)
for any choice of K, provided that D K < . The S-HJW theorem states that if there
exists physically a purification, in a higher dimensional Hilbert space, of a system in a
mixed state ρ, then for any ensemble that represents ρ, there is a way to measure the
environment(s) that is, make measurements in the larger Hilbert space that act as the
identity on the system Hilbert space — such as to collapse the system into one of the pure
states |φ
k
i with the appropriate probability
k
. Note that in general these states are not
mutually orthogonal, even for K = D, and this must be so for K > D.
The S-HJW theorem applies to a measurement on the environment at a particular time.
If this is a time remote from the initial conditions, and the system obeys Eq. (1) with a
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 3
unique stationary solution ρ
ss
of rank D [21], then in Eq. (4), ρ
=
ρ
ss
. An obvious question
is: can the finite ensembles representing ρ
ss
allowed by the S-HJW theorem also pertain,
at remote times, to continuous monitoring? To address this we make the additional
assumption, mentioned above, that the ME has been derived from a QWN coupling. Then
we can ask whether a given pure state ensemble can be realised continuously by the
experimentalist via a carefully chosen measurement scheme. That is, is it possible, merely
by obtaining information from the bath in the right way, to force a quantum system,
obeying a given ME, to behave like a discrete classical system, in the sense of jumping
between a given finite set of pure states? It was shown in Ref. [2] that this question is
equivalent to asking whether the following finite set of algebraic constraints can be satisfied
k, L |φ
k
i hφ
k
| =
K
X
j=1
κ
jk
(|φ
j
i hφ
j
| |φ
k
i hφ
k
|) (5)
for some ensemble {
k
, |φ
k
i} of size K. The real-valued transition rates, κ
jk
0
, naturally
determine the occupation probabilities
k
. A valid solution is known as a
physically
realisable ensemble
(PRE) [2], because there exists some measurement procedure that will
realize the ensemble in the sense described above, even if that procedure may by difficult
to implement in practice. In particular, it is known that the measurement scheme required
to achieve a PRE is generally adaptive in nature [3]. In general, a ME will allow multiple
solutions to Eq. (5) via the experimental freedom described by Eqs. (2)–(3). Most of the
difficulty of our research program arises due to the system of non-linear constraints defined
by Eq. (5) being difficult to solve, even numerically, when D > 2.
It was also shown in Ref. [2] that there are ensembles that represent ρ
ss
but that are
not PREs (this was referred to as the “preferred ensemble fact”). A fundamental question
for open quantum systems is whether, for a given master equation, there exist any finite
PREs. It was found in Ref. [3] that for D
= 2
it always possible to find at least one K
= 2
PRE. For D >
2
, a heuristic argument, using free parameter and constraint counting,
was made in Ref. [3] predicting that one can expect a PRE to exist if K
(
D
1)
2
+ 1
.
This separation from the classical case (where K
=
D is necessary and sufficient) for
D >
2
would indicate a profound difference between quantum and classical open systems.
However, the heuristic argument of Ref. [3] was not tested against numerical evidence,
and both the quantum–classical gap, and the very existence of finite quantum ensembles
in general, remained conjectural. The question of whether ME symmetries can alter our
expectations regarding the minimal size of PREs was treated in [6]. There it was found
that a commonly employed invariant subspace symmetry can reduce the heuristic ensemble
size to K
1
2
D
2
D + 2
, which is still larger than D for D > 2.
In this paper we address the three most important open questions raised by Ref. [3].
We answer the first two definitively, and provide strong numerical evidence to support our
conjectures regarding the third. The first question (Q1) is:
are there MEs for which the
minimally sized PRE is larger than
D
?
We answer this in the positive by exhibiting a ME
for which there are provably no PREs of size D. In this sense we can state (consistent
with our title) that open quantum systems can be harder to track than open classical
systems. The second question (Q2) is as follows:
is an ensemble size of
K
= (
D
1)
2
+ 1
always sufficient for a PRE to be found?
This time we will answer in the negative by
exhibiting a ME for which there are provably no PREs of size
(
D
1)
2
+ 1
or smaller.
This proof requires the refining of the counting arguments from Ref. [3], which also leads
us to a modified heuristic for the minimum sufficient K, containing a dependence upon
the number of decoherence channels modeled by the ME. The third question (Q3) is:
does
this refined form of the argument in Ref. [
3
] reliably predict whether PREs are feasible for
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 4
a ME of a given form.
For clarity, we partition Q3 into its natural sub-questions (Q3a, Q3b, Q3c), arising from
the heuristic’s comparison of the number of free parameters and constraints that constitute
the algebraic formulation of PREs. Q3a asks whether the heuristic’s prediction of ruling
out PREs for ensembles smaller than the determined threshold is accurate, while Q3b
assesses its utility when the number of parameters and constraints are equal and, finally,
Q3c concerns scenarios where there are more parameters than constraints. The heuristic
can make predictions for MEs and PREs in particular classes, so we take the prediction of
the heuristic to be as follows: only in a measure-zero set of MEs will PREs exist contrary
to expectation, whilst when PREs
are
feasible according to the heuristic, they will exist
for a finite fraction of randomly drawn MEs. The numeric results that we obtain strongly
support the conjecture that the counting heuristic makes accurate predictions for Q3a and
Q3b, in the sense described. At the same time, the numerics undermine the unreasonably
strong hypothesis that the heuristic is a necessary and sufficient condition for the existence
of PREs. Some discussion of Q3c is provided in our concluding remarks, but a systemic
investigation is left for future work due to its somewhat divergent focus from Q1-2 and,
also, its computational difficulty.
It is worth highlighting the reasons why Q1-Q3 have not been previously answered
and, in turn, why we are now in a position to answer them. The most relevant point is
that PREs, in D >
2
, are
hard
to investigate. There are no known analytic expressions for
their construction and, more importantly, even numerically their discovery is extremely
difficult. To find a PRE, the set of nonlinear polynomial constraints given by Eq. (5)
must be solved. The difficulty of this task becomes exponentially more difficult as the
number of equations and variables increases. In fact, the problem is known to fall into the
NP-complete complexity class [22]. This alone does not prohibit the constraints’ solution;
it just places low practical bounds on the system size that can be solved. Thus, with
regards to Q1-Q3, it becomes an issue of how large a system can be numerically processed
in comparison to how small a system is minimally sufficient for investigation. In this paper
we utilise the recent work regarding symmetries for PREs that was carried out in [6]. This
allows us to search, with meaningful expectation, for PREs possessing symmetry that are
of a smaller size than that expected based on the heuristic of [3]. Computationally, the
effect of this is to reduce the size of the relevant polynomial system to only 24 constraint
equations, as compared to the 45 constraint equations that are relevant when simplifying
symmetries are not considered. In terms of enlarging the size of the polynomial systems
that we can address, we newly apply two powerful software packages (MAGMA [23] and
PHCpack [24]) to PREs that respectively take advantage of Gr¨obner basis [25] and polyno-
mial homotopy continuation [26] techniques. In this way, by applying symmetry and more
powerful numerics, we are able to cross into the regime where Q1-Q3 can be answered.
The paper is organised as follows. Firstly, in Sec. 2, a brief description of the sym-
metries introduced in [6] is provided. In Sec. 3 we then develop a more sophisticated
heuristic than that found in Ref. [3] to guide when PREs are expected to exist and when
not to exist. This provides a pathway to follow in order to answer the research questions
Q1–Q3 introduced above. In Sec. 4, the mathematical task of solving Eq. (5) is discussed.
In Sec. 5, we address Q1–Q3 using state-of-the-art numerical, and computational algebra,
solvers for various classes of MEs and PREs. Finally, we conclude with a summary and a
discussion of future research directions in Sec. 6.
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 5
2 Symmetry and PREs
In prior work, the role of various types of symmetry in the structure of PREs was ex-
plored [6]. It was found that symmetries of the ME can be used to simplify the task of
finding PREs and, also, to relate discovered PREs. That is, PREs can inherit ME symme-
tries in a well defined way. In this current paper, we will utilise symmetry for systems of
dimension D
= 3
, in order to facilitate obtaining answers to the research questions posed
in the introduction. For completeness, we now provide a brief simplified description of the
symmetry tools that were developed in [6].
2.1 Invariant subspaces of L
We label the space of density matrices for a D-dimensional complex Hilbert space H as
D (H). We say that a ME, ˙ρ
=
Lρ, has an invariant subspace symmetry iff there exists some
non-trivial subregion, D
I
, of D (H), to which dynamics is confined, given an initialisation
within that subregion. Additionally, we require that the subregion be an interesting one,
in the sense that it has the potential to support PREs for the specified ME. This latter
point requires that it contain at least D pure states, in order to form pure-state ensembles
of rank D we have stipulated that ρ
ss
be of rank D. An example of such an invariant
subspace, provided in [6] and of relevance here, is that of real-valued density matrices
otherwise known as ‘redit’ states.
The reason for considering such invariant subspaces is that one can then look for
solutions to Eq. (5) that lie entirely in this subspace. That is,
k, |φ
k
i hφ
k
| D
I
. (6)
One can consider Eq. (5) as effectively enforcing constraints relating to the different re-
gions of D (H): given that |φ
k
i hφ
k
| does not have support on all such regions, some portion
of the constraints are automatically satisfied. The reduction in the number of non-trivial
constraints upon |φ
k
i hφ
k
| means that the polynomial system that must be solved in order
to find PREs (of the form Eq. (6)) is smaller than if an invariant subspace was not con-
sidered. Additionally, there is a potential reduction in the expected minimum PRE size.
This will be discussed further from a theoretical perspective in Sec. 3 and be utilised in
Sec. 5, where we find new PREs. Note that in performing a limited search for PREs, one
is excluding the possibility of finding the fraction (which may be zero, one or in between)
of PREs that have support outside D
I
.
2.2 Wigner symmetries
The second ME symmetry discussed in [6] that is of direct relevance, is that of Wigner
symmetry. Wigner transformations act on Hilbert space rays in a way that preserves
the Hilbert space inner product, | hψ
1
|ψ
2
i |. Their action is consequently well defined
upon pure state projectors, and we denote this as T |ψihψ|. Wigner showed that such
transformations are either unitary (and so linear in their action on Hilbert space) or
antiunitary (and so antilinear) [27, 28]. In this subsection, we are concerned with those
Wigner transformations that leave the Lindbladian, L, invariant:
T
1
L T = L, (7)
and term these ‘Wigner symmetries’.
Given a ME whose Lindbladian satisfies Eq. (7) for some T , we can then posit the
existence of PREs that possess the Wigner symmetry, which we define in the following
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 6
way. Let P be a permutation of {
1
...K} with k
0
=
P
(
k
)
. Then we define a PRE as having
the Wigner symmetry T iff permutation P such that
k, T |φ
k
i hφ
k
| = |φ
k
0
i hφ
k
0
| and (8)
κ
j
0
k
0
= κ
jk
. (9)
The consequence of both the ME (through L) and the PRE possessing the Wigner sym-
metry [Eq. (7) and Eqs. (8)–(9), respectively] is that some portion of the constraints of
Eq. (5) are redundant [6]. Specifically, given an equivalence relation, , amongst ensemble
members in the presence of the symmetry T as
|φ
k
i |φ
k
0
i iff T : |φ
k
0
i hφ
k
0
| = T |φ
k
i hφ
k
| , (10)
then the constraints on only one element of each equivalence class,
[
|φ
k
i
]
, need to be
tested as the remainder are implied. Once again, the benefit is a smaller polynomial
system that must be solved in order to find PREs. Similarly to the invariant subspace
symmetry, Wigner symmetry will be used in Sec. 5 to find new PREs.
3 Heuristics for the existence of PREs
Previous work [3] argued heuristically, via the counting of free parameters and constraints
of Eq. (5), that typically K
(
D
1)
2
+ 1
ensemble states are required for a PRE
to be possible. More recently [6], consideration was given to the minimum PRE size
in the presence of the invariant subspace symmetry D
I
=
R
D×D
D (H) (real-valued
density matrices), and an analogous heuristic, K
1
2
D
2
D + 2
, was derived. Such
a D
I
, containing redit states, provides an example of a subregion that has the minimal
dimensionality (when considered as a convex linear space) able to support ρ
ss
having
Rank(ρ
ss
) = D, as is appropriate for the minimisation of K.
The existence of free parameters in Eq. (5) is due to there being no preference (at least
none relevant to our current discussion) as to the nature of the states, |φ
k
i, comprise the
PRE, nor of the transition rates, κ
jk
, between them. The constraints obviously enforce
the properties intrinsic to the PRE. That larger K makes it more likely for a PRE to
exist, all other things being equal, arises due to the number of free parameters (we will
often omit the modifier ‘free’ going forward) depending quadratically upon K while the
number of constraints only depends on it linearly. (The origin of these dependences will
be discussed in detail later.)
An important piece of evidence supporting the argument in [3] for K
(
D
1)
2
+ 1
is
the fact (proven in [3]) that every system obeying a Lindblad-form master equation has at
least one PRE with K
= 2
for D
= 2
. For D, K
= 2
it is indeed the case that the number of
parameters and constraints involved in Eq. (5) are equal (we term this a ‘square’ system).
Moreover, the solution set in that case typically consists of isolated solutions (termed a
‘zero-dimensional solution set’), consistent with the equality portion of K
(
D
1)
2
+ 1
holding. Similar remarks apply in the case of a minimally dimensioned invariant subspace,
such as that of rebit states [(D 1)
2
+ 1 =
1
2
D
2
D + 2
for D = 2].
In this section a more sophisticated heuristic for the required ensemble size K is de-
veloped that has dependence not only upon D but also upon the number of decoherence
channels, L in Eq. (1). There is, of course, no guarantee that a physical solution (repre-
senting a PRE) can be found when the number of constraints is less than or equal to the
number of parameters but it serves as a heuristic for when one is likely to find PREs. This
heuristic is important even for a computational approach to the existence problem, given
the computational complexity of finding PREs (discussed in detail in Sec. 4).
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 7
Figure 1: Each node represents a member state of a PRE and directed edges are transitions in the
direction of the arrow. (a) A 4 member fully connected graph. (b) A graph that traps the state in nodes
3 and 4 so is not a feasible PRE. (c) Maximum number of transitions for a
D
= 3
, L
= 1 ME for a
K = 4 PRE. (d) Maximum number of transitions for a D = 3, L = 1 ME for a K = 6 PRE.
The description of a PRE consists of a set of states and their occupation probabilities,
but when investigating their existence it is more more beneficial to think about the transi-
tion rates, κ
jk
, rather than
k
. This is because the structure of the ME can (in a way that
is defined in Sec. 3.1) place constraints on the allowed κ
jk
, which can simplify Eq. (5). To
aid these arguments it is useful to form a graph representation of the ensemble in which
each member (state) is a node and allowed transitions are illustrated by directed edges.
An example is shown in Fig. 1(a) for 4 ensemble members with all transitions allowed
(termed ‘fully connected’). It is possible that some of the allowed transitions are, in fact,
not utilized (κ
jk
= 0 for some j, k) by a particular ensemble.
3.1 Parameter and constraint counting
In this subsection we first form counting arguments for the arrangement and number of
transitions that can exist, given the ME defining the system dynamics. At the end of
the subsection the more straightforward task of describing the number of state vector
parameters, and the number of constraints upon them, is performed.
It is of interest to maximise the number of graph transitions as this will give the
greatest chance of PRE existence, at least according to our heuristic criterion for which the
transitions exist as free parameters. The graph that maximises the number of transitions is
obviously the fully connected one but, as will be shown, this will not always be consistent
with the ME in question. Perhaps the most obvious requirement of a graph and
one that the fully connected graph satisfies is that all the nodes must be repeatedly
explored in the long time limit. That is, the state cannot become trapped in a sub-graph.
An example of a graph that is ruled out by this consideration is Fig. 1(b). We note that
freedom in choosing the measurement scheme is assumed; in particular a sufficient number
of detectors, M, is provided to avoid unnecessarily limiting the number of possible different
post-jump states.
Let us now discuss the circumstances under which we can rule out the fully connected
graph. To do so in a simple manner, we will consider Hilbert subspaces,
˜
H, as opposed
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 8
to subregions of D (H). That is H
=
˜
H H
R
(with, R being the remainder space). In
the case that H
R
is non-trivial, then dim
(
˜
H
)
< D. In this subsection, we will often refer
to the dimension of an ensemble of pure states, by which we mean the dimension of the
Hilbert subspace,
˜
H that contains the entire ensemble. Each directed connection (with
rate κ
jk
) references the transition from the kth to the jth state, which will occur when a
detection event is registered at a, possibly non-unique, detector, m such that f
(
m, k
) =
j.
The function f takes as inputs the clicking detector, m, and the pre-click system state
k, to give a post-click state j (see App. E for more details concerning PRE measurement
schemes). We are interested in the case j 6
=
k, so that the detection causes a finite change
in the state, from |φ
k
i to ˆc
k
m
|φ
k
i
φ
f(m,k)
E
, where ˆc
k
m
is mth jump operator when the
system is known (or, rather, believed) to be in the kth state. Although there can be
many different possible post-jump states j from a particular state k, the dimension of the
post-jump Hilbert subspace (which plays the role of the previously defined
˜
H) is restricted
in size to be min{L
+1
, D}. This is because the ˆc
k
m
are formed from linear combinations
of ˆc
l
(of which there are L) together with the identity (see Eq. (3) and App. E), while D
is the dimensionality of the system. In the case where this restriction is saturated, the
pre-jump state, |φ
k
i, also belongs to
˜
H.
The importance of this restriction can be seen by examining a K
= 4
ensemble. First
we assume that the rank of ρ
ss
is D
= 3
and that the number of Linblad operators is
L
= 1
. For any state in the ensemble, the Hilbert subspace comprising this state and the
post-jump state(s), say
˜
H
0
, must be of dimension 2. If all the transition rates were non-
zero then
˜
H
0
would contain the entire ensemble, which is a contradiction as dim(
˜
H
0
)
< D.
Thus, the fully connected graph of Fig. 1(a) is ruled out as a possibility for L
= 1
and
the number of free parameters corresponding to transition rates is less than the expected
K
(
K
1) = 12
. By contrast, if the rank of ρ
ss
is kept at 3 but L
= 2
then dim
(
˜
H
0
)
can
be 3 and the fully connected graph is not ruled out on these grounds.
Coming back to Rank
(
ρ
ss
) = 3
and L
= 1
, the obvious question is: what is the largest
number of transitions allowed? An example optimal configuration is given in Fig. 1(c),
where 6 rates are possible. Nodes
1
,
2
,
3
do span a 2-dimensional Hilbert subspace but
there is asymmetry as node
4
is only accessed via node 3’s single outward connection.
This conspires to allow node
4
to be outside the node
1
,
2
,
3
subspace and increase the
Hilbert space dimension of the ensemble to 3 as required. That only 6 rates are possible
represents a large reduction from the fully connected graph. It will be shown that K
= 4
PREs are not generically allowed for D
= 3
for any L. However, MEs possessing certain
types of symmetry can render some of the constraints of Eq. (5) redundant. Together with
introducing such symmetries, if we take L
2
(so that fully connected graphs are not
ruled out by the considerations of dim
(
˜
H
0
)
that are discussed above), then the resultant
system of polynomial constraints becomes ‘square’ and thus PREs may be searched for
with significant expectation of their existence.
Another example (K
= 6
, L
= 1
, D
= 3
) that will prove relevant and that also serves
to illustrate the optimal technique for ‘rate packing’ is shown in Fig. 1(d). The idea is that
there is as large a group of highly connected nodes as possible (nodes
1
4
in Fig. 1(d)),
because this allows the number of connections to grow as the square of the group size.
As the dimension of the ensemble is required to reach D, there is an outward connector
node that breaks the symmetry, here node 5. Node 5 cannot be connected to anything
in addition to 6 as, if it were, this would constrain node 6 to be in the same subspace as
nodes 1–4. Node 6 further breaks the symmetry by connecting to one (and only one) of
the nodes 1–4. A single connection from 6 to 5 is not allowed as this would trap the system
in nodes 5,6. If, instead of K
= 6
, the ensemble size was K
= 7
, the extra node would be
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 9
optimally added to the highly connected group, with then
9
more transitions possible. If
it was added anywhere else fewer connections would be possible. As a different extension,
if D
= 4
then one of the highly connected nodes would have to be moved to the lowly
connected chain that serves to increase the Hilbert space dimension of the ensemble; for
example, in between nodes 5 and 6.
We now have enough intuition to give the general case, describing how the maximal
number of transition rates can be packed for arbitrary K, D, L. The schematic for the
configuration is given in Fig. 2 and is based on the principle of a highly connected group
(of dimension L
+ 1
) that contains most of the transitions and a lowly connected group
whose purpose is to fill out the ensemble dimension to match Rank(ρ
ss
). There are a few
generalisations to the L
= 1
examples above. Firstly, the node which connects the upper
to lower groups is also connected internally within the upper group, but less so than the
other upper members. As long as it has no more than L connections, there is no effect
on the upper and lower dimensionalities. For the case L
= 1
there is only one connection
so this is consistent with the analysis above. The second major difference is that the
lower group is also internally connected up to a maximum of L connections, by the same
reasoning as just given. The total number of transition rates for arbitrary K, D, L can
easily be counted from Fig. 2 to give
(
K D
+
L
)
2
+
L
(
D L
)
. This expression applies
when L < D
1
. If L D
1
there is no need for a lowly connected group of nodes and
the graph can be fully connected, with K(K 1) rates.
Before comparing the
total
number of parameters and constraints, in Sec. 3.2, we first
give the number of parameters in Eq. (5) that arise from the specification of the K ensemble
members. A generic D-dimensional pure state can be described by a state vector with D
complex numbers or
2
D real numbers, but this is before normalisation and removing an
overall phase. Thus,
2
D
2
real parameters per state are sufficient, or
2
K
(
D
1)
in total.
Finally, to compare against the number of parameters, we need the number of constraint
equations. To find this, we note that both sides of Eq. (5) are, by construction, Hermitian
and traceless, which leads to D
2
1 constraints for each k.
Finally in this subsubsection, we comment on the special case of the invariant subspace
symmetry D
I
=
R
D×D
D (H), which we use extensively in the latter parts of this paper.
In this case, only D
1
parameters are required to describe each state vector. Any
smaller invariant subspace would not support rank
(
ρ
ss
) =
D. The number of non-trivial
constraint equations is also reduced in number, to
(
D
2
+
D
)
/
2
per ensemble member,
as any constraints relating to the imaginary components of the state vector are trivially
satisfied.
3.1.1 Ambiguity in the counting of state parameters
As Eq. (5) is a matrix equation it would be natural to consider forming the ensemble
members as state
matrices
rather than state vectors. If this approach is taken, then the
counting is different as follows. A D-dimensional Hermitian matrix with unit trace is
given by D
2
1
real parameters. To ensure that the state is pure and is positive, the
additional (real) constraints Tr
ρ
2
=
Tr
ρ
3
= 1
need to be applied [29]. On the face of
it this removes 2 free parameters. However, we quickly run into difficulties. For example,
if D
2
3
real parameters are used for a pure state matrix then this gives 6 free parameters
for D
= 3
rather than 4 via a state vector approach. Thus, the state matrix description
is not minimalistic in the number of parameters and only becomes equivalent to the state
vector description with the highly non-linear cubic constraints imposed by Tr
ρ
3
= 1
. We
posit that the parameter and constraint counting
should
be conducted in a minimal way
and consequently proceed in that direction. Evidence for the correctness of this approach
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 10
Figure 2: Schematically shown is the heuristic for optimal rate packing in a PRE. The ensemble states
are divided into two classes, the first of which (upper panel) is highly connected and the second (lower
panel) is less connected and serves to increase the ensemble dimension. The highly connected nodes are
fully intra-connected with the exception of the symmetry breaking node that connects to the less highly
connected nodes. The dimension of the highly connected nodes is
L
+ 1. The lowly connected nodes
fill out the dimension of the ensemble to
D
, with each node increasing the dimension by one. This is
achieved by having no more than
L
connections from any one node. Finally, the system state must not
be trapped in the lower sub-section, so there is at least one connection from lower to upper.
is subsequently found and described further in Sec. 5.1, where we establish that no PREs
are possible for specific MEs when the number of parameters is less than constraints as
determined by the state vector approach but the number of parameters is larger than
constraints with the matrix method.
3.2 Comparing the number of parameters and constraints
As a reminder to the reader, we have adopted the following heuristic when searching for the
PREs: the total number of free parameters should be greater than or equal to the number
of constraints as described by Eq. (5). Requiring this to hold for a K-sized ensemble in
D dimensions with L < D
1
Lindblad operators (in the absence of invariant subspace
symmetry) thus gives
(K D + L)
2
+ L(D L) + 2K(D 1) K(D
2
1). (11)
Here we have not simplified the inequality so that the number of transitions (terms one
and two), the number of state parameters (term three) and the number of constraints
(RHS) can be clearly identified. If L D
1
then the relevant inequality is that obtained
in Ref. [3]: K
(
D
1)
2
+ 1
. The minimum ensemble size, K
min
, can be found from
Eq. (11) for fixed D, L by taking the smallest integer value of K that satisfies it. The
integer rounding associated with K
min
simplifies the quadratic solution in such a way that
we can summarise our knowledge of the minimum expected PRE size, for all D, L, as:
K
min
= (D 1)
2
+ 1 + 1
{L<D1}
× (2D 2L 1) , (12)
where 1
{A}
is the indicator function, which is 1 if A is true and 0 otherwise. That is,
if L D
1
then we reproduce the minimum ensemble size suggested in Ref. [3]. But
if L < D
1
, the minimum ensemble size is larger by
2
D
2
L
1
, making it equal to
K
min
=
D
2
2
L
+ 1
. For all values of L, K
min
D
2
and in the ‘worst’ case, of L
= 1
,
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 11
we find K
min
=
D
2
1
(for D >
2
). The values of K
min
for small values of D, L are
summarized in Table 1.
Equipped with the expected ensemble size, K
min
, required for a PRE to exist, we can
assess which classes of MEs are appropriate in order to address the targetted research
questions (Q1-3) that were raised in Sec. 1. Firstly, we consider when an ensemble of size
K
min
> D is required, which relates to Q1. From Table 1, we expect that this will be
when D
3
and will be minimally satisfied with K
min
= 5
for L
2
and D
= 3
. Secondly,
to answer Q2 we consider whether K
= (
D
1)
2
+ 1
is always sufficient to find a PRE.
We have shown that, at least in terms of parameter and constraint counting, it is not (for
D >
2
), as MEs with L < D
1
are expected to require an additional
2
D
2
L
1
ensemble
members. For example, a D
= 3
ME with a single decoherence channel has K
min
= 8
.
Whether we can actually consistently find PREs of size K
min
(which relates to Q3b) and
rule them out for K < K
min
(Q3a) will provide evidence as to the quality of the heuristic
and thus constitute our response to Q3.
3.2.1 K
min
for a minimally sized invariant subspace
The analogous expressions to Eqs. (11)–(12) can be found when the invariant subspace
symmetry is considered, specifically the space of real-valued density matrices. That is, we
find the minimum PRE size, given that it is restricted to the subspace and that the ME
maps real-valued density matrices to real-valued density matrices. Comparing the sum
of the transition parameters and state parameters with the number of constraints gives,
when L < D 1,
(K D + L)
2
+ L(D L) + K(D 1)
1
2
K(D
2
+ D 2), (13)
while for L D
1
it is K
(
K
1) +
K
(
D
1)
1
2
K
(
D
2
+
D
+ 2)
. Solving this latter
expression, for smallest integer K, one obtains K
min
=
1
2
D
2
D + 2
. The minimum
PRE size for arbitrary D, L can thus be written as
K
min
=
1
2
D
2
D + 2
+ 1
{L<D1}
× (2D 2L 1) 1
{g(D , L)}
, (14)
with g
(
D, L
)
being a Boolean function, whose dependence upon D and L is not particularly
important as it only influences K
min
by one unit. More interesting is the fact that, to within
one unit, the addition to the ensemble size necessitated by small L is precisely the same
as in the generic (non-invariant subspace) case of Eq. (12):
2
D
2
L
1
. Moreover, the
threshold for when this addition applies is also the same: L < D
1
. Example values for
K
min
, for small D, L, are given in Table 2.
From Table 2, we expect that the minimal ensemble size, K
min
, will be larger than
D for D
3
. The lowest dimensioned such example is D
= 3
which has K
min
= 4
when
L
2
. With regards to whether K
= (
D
1)
2
+ 1
is always sufficient to find a PRE
(research Q2), we see that even when an invariant subspace symmetry is applicable it is
not expected to be sufficient for small L (for example, K
min
= 6
for D
= 3
and L
= 1
). In
Sec. 5 we will confirm the practical relevance of Table 2.
In this subsection we have considered how K
min
is modified for small L when the
invariant subspace symmetry is taken into account. In App. A, we provide some brief
comments as to how another symmetry Wigner symmetry can impact on viable
PRE graphs. This will, in turn, effect the minimum size of PREs that possess the Wigner
symmetry.
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 12
Lindblads
Dim. 1 2 3 4 5
2 2 2 2 2 2
3 8 5 5 5 5
4 15 13 10 10 10
5 24 22 20 17 17
Table 1: The minimum number of PRE mem-
bers,
K
min
, required for the number of param-
eters to equal or exceed the number of con-
straints is provided for a variety of
D, L
. Our
heuristic suggest that a soln of Eq. (5) may be
possible for
K
=
K
min
. Generic MEs are being
considered. The shaded cells highlight values
of
K
min
that are made larger than (
D
1)
2
+ 1
(the ensemble size suggested in Ref. [
3
]) due
to the restrictions on allowed graphs described
in Sec. 3.1 (which apply when L < D 1).
Lindblads
Dim. 1 2 3 4 5
2 2 2 2 2 2
3 6 4 4 4 4
4 11 10 7 7 7
5 17 15 14 11 11
Table 2: The difference from Table 1 is that
MEs with
L
having the redit as an invariant sub-
space are considered, as described in Sec. 2.1.
PRE states are restricted to being redits, which
reduces the size of
K
min
necessary for the num-
ber of constraints imposed by Eq. (5) to be less
than, or equal to, the number of parameters.
4 Analysing polynomial constraints in order to find or rule out
PREs
In our introductory comments, and also in previous work [6], we have commented on the
difficulty of finding PREs. In this section we provide further details, and also introduce the
newly applied technique of polynomial homotopy continuation. Additionally, the related
task of definitively ruling out the existence of PREs of a particular size, for a specified
ME, is discussed.
To progress beyond the heuristic arguments of Sec. 3, example PREs need to be found
for explicit MEs. That is, the set of matrix equations specified by Eq. (5) needs to be
solved. On the LHS of Eq. (5), there is a quadratic dependence upon the pure state vector
parameterization (see Sec. 3.1.1). The L Lindbladian superoperator provides known co-
efficients (the ME is fixed) to the quadratic monomials. Note that we take the state vector
to be unnormalised, with the normalisation included as an additional quadratic constraint.
The RHS of Eq. (5) consists of cubic monomials arising from the state vectors (quadratic)
multiplied by the transition rate parameters. Assuming we are working with a minimally
sized ensemble and a completely generic ME for which invariant subspace symmetries
are not relevant the set of matrix equations (one for each ensemble member) forms a
polynomial system containing
K
min
D
2
(15)
equations and as many (or slightly more) parameters. The lowest dimensional generic
ME that has a PRE with K
min
> D is for D
= 3
, for which we expect K
min
= 5
(when
L
2
, allowing a fully connected PRE graph). Finding a PRE for such a case involves
solving a square (it turns out there are no excess free parameters in this case) system of
45 polynomial constraints. The simplest generic ME for which K
= (
D
1)
2
+ 1
is not
expected to be sufficient is for D
= 3
, L
= 1
, for which K
min
= 8
(see Table 1). Finding a
PRE for such a case involves solving a system with 72 polynomial constraints. In the case
that the ME possesses an optimal invariant subspace symmetry, the polynomial system
has fewer constraints:
1
2
K
min
(D
2
+ D). (16)
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 13
For the ‘re3it’ (D
= 3
, real valued state vectors), the invariant subspace that we choose
for our detailed PRE search, K
min
= 4
(provided L
2
) and the polynomial system has
24 constraints. If L
= 1
, D
= 3
then K
min
= 6
(see Table 2) and 36 constraint equations
are obtained. The question of whether it is feasible to solve such large systems, in order
to find PREs, is now considered in some detail.
The most conceptually straightforward approach to solving such systems is via pro-
gressively eliminating variables, for example by calculating a
lex
Gr¨obner basis [25] (a
discussion of Gr¨obner bases in the context of PREs can also be found in an appendix
of [4]). However, even if the Gr¨obner basis can be found, the elimination process typically
rapidly increases the degree of the remaining monomials. Unfortunately there are no gen-
eral formulas for solving polynomial equations in a single variable of degree
5
in a way
that expresses the roots of that polynomial in terms of radicals. This removes the possibil-
ity of finding PREs algebraically in these cases, so a numeric approach is essential. Even
numerically, it is still a very difficult problem and, in fact, it falls into the NP-complete
complexity class [22]. It is important to realize that this difficulty extends to the decision
problem of determining whether a solution exists [30]. This is relevant as we will often
be satisfied with finding an
example
PRE, and not all, PREs that exist for a given ME.
To illustrate, finding an example PRE for a specific ME with K
min
> D and also proving
that no PREs are possible for K < K
min
(for the same ME) would provide evidence for
Q3 and an answer to Q1.
Despite the computational complexity, polynomial systems
can
be numerically solved
up to a moderate size. Where is the boundary that separates the tractable from in-
tractable? Obviously it depends on the details of the polynomials and the applied solution
methods, but for the purposes of this discussion the reader is provided with some circum-
stantial evidence from the literature as well as our direct experience. In [22] it is suggested
that even when using the highly efficient Gr¨obner basis Faug`ere F4 algorithm [31] (a vari-
ant on the Buchberger algorithm [32]) quadratic systems of size larger than 15 equations
are very difficult. The constraints of Eq. (5) are cubic (except for K
min
quadratic normal-
isation constraints) and are resultantly more difficult. Our experience with Gr¨obner basis
techniques using MAGMA was that an example system of 16 equations was soluble in
about 13hrs [33] whereas size 20 systems were out of reach (limitations of 200Gb of Ram
were exceeded after several days runtime).
The above discussion relates to cases in which we expect a solution to exist, rather
than over-determined systems (number of variables less than number of constraints), for
which no solution is expected. In the latter circumstance, there is a remarkably useful
result due to Hilbert that can allow a proof (analytically, via the obtaining of a Hilbert
Nullstellensatz certificate of infeasibility) that no PREs of a particular size are possible.
In App. B we provide some more technical details of the procedure that we briefly outline
here. The algorithm [34] is as follows: Eq. (5) provides a set of polynomial constraints
that generate an ideal for which we calculate a Gr¨obner basis. If the basis contains {
1
}
then the polynomials have no common zero in C
n
(n being the number of parameters).
Unfortunately it is not straightforward to computationally extend this to a statement
about common zeroes in R
n
as the real numbers are not an algebraically closed field.
Thus, our technique will be to rule out complex solutions so that real solutions are also
infeasible. Despite this being heavy handed, it will allow several results to be established
regarding PRE non-existence.
Although obtaining a Hilbert Nullstellensatz certificate of infeasibility possesses the
highlighted difficulty of finding a Gr¨obner basis there are two reasons why we find
the task simpler for ruling out PREs. Firstly, it is simply the fact that the PREs that
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 14
we wish to rule out are typically smaller than K
min
, so a smaller polynomial system is
relevant. Secondly, even for large systems, the presence of {
1
} in the Gr¨obner basis can
quickly collapse the computation; we find that Gr¨obner bases for such over-determined
systems are typically easier to obtain. The possibility of proving by these methods that
there exist no PREs of a certain size positions us to directly tackle research questions
Q1-Q2, and provide evidence for Q3a.
Coming back to the difficulty of actually finding solutions to polynomial systems, when
they exist, we were clearly motivated to explore different (beyond Gr¨obner basis) numerical
techniques. Further success was had with the method of polynomial homotopy continua-
tion, in which the problem is cast into an ‘embarrassingly parallel’ [24] form. As a brief
explanation, solutions of a simple ‘start system’ (a polynomial system that possesses the
desired features) are tracked (see endnote [35]) as the system is homotopically continued
(transformed) to the target polynomial system, with each solution path able to be treated
independently (a more in-depth discussion is provided in App. C). This is particularly
suited to our goal of finding example PREs as we can stop tracking paths once a single
PRE solution is found. That is, the entire search space does not have to be be explored.
This is by no means a panacea as the number of paths can be enormous and a large
number may have to be followed before either a solution is found or it is decided that re-
sources are better spent exploring a different ME. For example, the ezout bound for the
maximum number of solutions to a system is the product of the largest degree of the poly-
nomial equations; admittedly this is typically much larger than than the tightest available
bounds for sparse systems containing relatively few monomials compared to parameters.
The ezout bound for K
= 5
, D
= 3
system evaluates to
3
.
9
×
10
20
potential solutions
and that for the K
= 8
, D
= 3
system is
8
.
8
×
10
32
. A particularly useful extension to the
polynomial continuation approach is the very recently developed Monodromy method [36],
which reduces the number of paths that have to be tracked and, importantly, eliminates
the necessity of doing a costly pre-computation to obtain a bound tighter than that of
B´ezout. This is also described further in App. C.
Utilising the polynomial homotopy continuation numerical approach as well as the
monodromy extension, PREs were extracted from systems of 24 polynomial equations.
Despite this being less than that required to investigate generic K
= 5
, D
= 3
PREs, it
is
sufficient to find PREs that possess the invariant subspace symmetry, for which K
min
= 4
for D
= 3
. The result is that, by combining symmetry considerations and newly applied
numeric methods, we are now capable of investigating research question Q3b described in
the introduction.
5 Results
In this section the previously developed counting arguments and symmetry techniques are
used to guide the finding of PREs or to rule out their existence for a large number of
example MEs. The examples are chosen from classes (specified by D, L) that allow us to
answer the following two existential questions raised in the introduction (following [3]):
are there MEs for which the minimally sized PRE is larger than
D
?
(Q1) and
is an
ensemble size of
K
= (
D
1)
2
+ 1 always sufficient for a PRE to be found?
(Q2). Evidence
is also accumulated as to the validity of parameter and constraint counting being used
to rule out PREs (Q3a) or determine that they are feasible (Q3b). The existence of an
explicit measurement scheme that realizes each identified PRE is confirmed to ensure that
the PRE is not merely a mathematical construction.
When we prove that no PRE can exist, the proof consists of a Hilbert Nullstellensatz
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 15
Class
Symm.
Type K L Graph
PRE
exists? Method Purpose
I N 3 2,3 FC N Gr¨obner Q1&Q3a
II N 3,4,5 1 R N Gr¨obner Q1&Q3a,Q1&Q3a,Q2&Q3a
III S 3,4 3 FC N,Y Gr¨obner,PHC Q1&Q3a,Q3b
IV SW 3,4 2 FC N,Y Gr¨obner,PHC Q1&Q3a,Q3b
Table 3: Classes of
D
= 3 MEs for which we obtained major results are labeled and described. The
second column describes the symmetry (there can be more than one) of the ME: either (N)one, invariant
(S)ubspace symmetry (Sec. 2.1) or (W)igner symmetry (Sec. 2.2). The third column gives the considered
ensemble size, while the fourth column states the number of decoherence channels. The ‘Graph’ column
states whether the graph of the ensemble was fully connected (FC) or was necessarily (R)estricted by
the rate counting arguments of Sec. 3.1. The sixth column indicates what type of PRE existence proof
was obtained: N indicates that a Nullstellensatz proved that no PRE exists, while Y indicates that a
PRE exists, with the proof made by example. The ‘Method’ column indicates how the computation
was performed: either via Gr
¨
obner basis with MAGMA or polynomial homotopy continuation (PHCpack
and monodromy extension). The final column indicates the significance of the result by referring the
to the research question that it addressed. Comma separated values in columns 3 or 4 (never both)
indicate multiple investigations. In subsequent columns, if different values apply respectively to each
investigation then these are also indicated by comma separated values.
certificate of infeasibility (see Sec. 4 and App. B). To numerically search for example PREs
in cases where they are expected to exist, we use the technique of polynomial homotopy
continuation (see Sec. 4 and App. C). The software that we used was PHCpack [24] together
with a recently developed monodromy package [36] that extends its capability.
To aid the reader, a summary of our results is provided in Table 3, to which we will
refer.
5.1 Are open quantum systems harder to track than open classical systems?
In order to answer this central question in the affirmative, it needs to be proven that there
exists a ME such that K
=
D states are not sufficient for a PRE to be formed (Q1). This
is because a classical system can always be tracked with K
=
D states as the occupation
(
1
or
0
) of each state could, in principle, always be known by monitoring the environment.
It is also of interest to look for a generic difference in difficulty of tracking quantum and
classical systems. That is, we ask whether K
=
D is insufficient
in general
, for randomly
drawn MEs. By addressing this, in a manner guided by our heuristic, we will also gather
evidence regarding to Q3a.
For the moment, we delay the task of actually finding a PRE and concentrate on
disproving their existence for K < K
min
, with K
min
determined utilising our (L and
symmetry dependent) knowledge of parameter and constraint counting. In D
= 2
it was
shown in Ref. [3] that K
=
D
= 2
is always sufficient to find a PRE, so the search for
an example system for which K is necessarily larger than D is extended to D
= 3
. (All
the results we obtain in this paper for specific example MEs apply to D
= 3
.) In Sec. 3
we found that for a
generic
ME (no symmetry considerations), described by a sufficiently
large number of linearly independent decoherence channels (L
2
for D
= 3
), the number
of parameters equals (or exceeds) the number of constraints for a minimum sized ensemble
K
min
= 5
(a summary for K
min
in terms of L, D was provided in Table 1). Thus, it is
logical to attempt to rule out PREs by Hilbert Nullstellensatz for K
= 3
,
4
. For completely
generic D
= 3
MEs (which we label as class I, see Table 3), it
is
within our computational
ability to obtain the K
= 3
certificates of infeasibility, but, unfortunately, K
= 4
proved
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 16
too difficult. However, it should be remembered that our current goal is only to find
example MEs that require K > D ensemble members to form a PRE, so ruling out K
= 3
is sufficient in this respect.
To select generic MEs, the D
= 3
Hamiltonian and Lindblad terms were parameterised
according to
ˆ
H = i
1
2
(α
1
α
1
) α
2
α
3
α
2
1
2
(α
4
α
4
) α
5
α
3
α
5
1
2
(α
6
α
6
)
, ˆc
l
=
γ
l
1
γ
l
2
γ
l
3
γ
l
4
γ
l
5
γ
l
6
γ
l
7
γ
l
8
γ
l
1
γ
l
5
, (17)
with l
=
1, ..., L. Note that the Lindblad’s are taken as traceless without loss of gener-
ality [37]. The complex values ~α,~γ
l
were chosen randomly from a uniform distribution
covering some rectangular range
[
a ia, a
+
ia
]
, with a being some arbitrarily chosen
cutoff (we took a
= 3
). That is,
6 + 8
L complex random values were generated in order to
specify an example ME from class I, with L chosen sufficiently large (for convenience we
focused on L
= 2
,
3
), so that there was no rate counting restriction on the graph being fully
connected. Once
ˆ
H and ˆc
l
have been specified, the constraints that must be satisfied by a
potential PRE were formed. These are found in Eq. (5) (see Eq. (1) for the Lindbladian
definition), with 3 sets (remembering that we are investigating K
= 3
) of 9 equations (27
total) compared with 21 state vector and transition rate parameters. These polynomial
systems were fed into MAGMA for 20 different example class I MEs, with a Hilbert Null-
stellensatz achieved for each system. It is curious that there was a large range of difficulty
in obtaining the computational proofs: around half completed in about 8 seconds but the
rest took from hours up to
2
.
5
days in the hardest case. Having found MEs for which
K
=
D ensemble members are not sufficient to form a PRE (and therefore answered Q1),
we then state that open quantum systems
are
harder to track than open classical systems.
Indeed, we believe them to be generically so. That is, we conjecture that the proportion of
generically selected class I MEs that possess K
= 3
PREs will be vanishingly small. That
the heuristic predicted no K
= 3
PREs would exist, for the selected MEs, is evidence for
its accuracy (and addresses Q3a). To ensure that our results can be reproduced, a specific
example of every class of ME that we obtain a result for is given in App. D.
5.1.1 L = 1 MEs are harder to track
We have shown that open quantum systems are harder to track than open classical systems,
but only in a minimal sense. That is, we proved that K
=
D
= 3
PREs do not exist for
randomly generated MEs without providing evidence for how large K must be to find a
PRE. As mentioned earlier, K
= 4
, D
= 3
Nullstellens¨atze for generic MEs are currently
beyond us, but we can make progress for the particular case of L
= 1
. This is because
the number of parameters is limited in this instance by our rate-counting arguments,
resulting in a more highly over-determined system of constraints. This conspires to make
a computational Nullstellensatz less demanding to achieve in the systems we investigated.
In the case when L
2
, there are 36 constraint equations and 32 parameters for a K
= 4
PRE, but when L
= 1
the number of parameters reduces to 26. This is despite the optimal
‘rate packing’ graph being chosen, see Sec. 3.1. If the graph is non-optimal, then fewer
than 26 parameters are present. This allowed us to obtain K
= 4
Nullstellens¨atze for all
30 example MEs that we chose according to the method above (but now with L
= 1
). To
distinguish this result we define the generic L = 1 MEs as belonging to class II.
Somewhat surprisingly, the same technique was also successful in ruling out K
= 5
PREs in all 30 class II examples. In this case, there are 45 constraints with a maximum
of 36 parameters. It is perhaps the relatively large ratio of constraints to parameters that
Accepted in Quantum 2019-09-27, click title to verify. Published under CC-BY 4.0. 17
allows us to obtain a Nullstellensatz in this case, while the 36 constraint and 32 parameter
scenario for generic K
= 4
, L
2
MEs was out of reach. We provide a brief discussion of
further difficulties of this L
= 1
computational proof in endnote [38]. To be clear: there
is no surprise surrounding the non-existence of K
= 5
PREs for L
= 1
as they are not
expected according to Table 1 (K
min
= 8
). Rather, the surprise is that we were able to
prove it via Nullstellensatz. The implication of the L
= 1
result is that we have proved,
for some example MEs, that K
= (
D
1)
2
+ 1
states are
not
sufficient to form a PRE.
This answers an open question of Ref. [3] that was raised as Q2 in the introduction. We
leave the task of attempting to obtain Nullstellens¨atze for K
= 6
,
7
PREs belonging to
generic L = 1 MEs for future work.
Note that if a state
matrix
parameterization of ensemble members had been used, as
discussed in Sec. 3.1.1, then it would be concluded that K
= 5
states are sufficient for
the number of parameters to exceed constraints in a class II ME. The fact that a K
= 5
Nullstellensatz is obtained for specific MEs is then evidence supporting the state vector
parameterization, which gives a minimal parameterization of pure states. That is, as
is worth emphasizing, the results of this subsection are completely consistent with our
parameter and constraint counting arguments we have been able to rule out PREs in
many cases when our heuristics would not expect them to exist, thus providing strong
evidence for an affirmative answer to Q3a. In particular, our heuristics say that L
= 1
MEs are generically harder to track than would have been expected in the absence of
consideration of L, and our numerics strongly support that conclusion.
5.2 Applying symmetry in order to find PREs
In the previous subsection we showed that open quantum systems are harder to track
than open classical systems, with the minimal K
=
D
= 3
PREs ruled out generically and
K
5
PREs typically ruled out for L
= 1
. Notably, we have not as yet actually found
any PREs! To do so would place an upper bound on how difficult example MEs are to
track and potentially provide confidence in our heuristic arguments as to when PREs are
expected (which forms Q3b). For D
= 3
, PREs are only expected to exist for generic
class I MEs (with L
2
) when K
5
. However, as discussed in Sec. 4, this leads to
polynomial systems of at least 45 equations and 45 parameters that are very difficult to
solve, even numerically. In this subsection we do find PREs, but only after the application
of symmetry makes the task tractable.
5.2.1 Invariant subspace symmetry
The first strategy we use is to introduce the inv