Authors Gus Gutoski, Patrick Hayden, Kevin Milner, Mark M. Wilde,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103
www.theoryofcomputing.org
Quantum Interactive Proofs and
the Complexity of Separability Testing
Gus Gutoski∗ Patrick Hayden† Kevin Milner‡ Mark M. Wilde§
Received September 8, 2013; Revised January 27, 2015; Published March 26, 2015
Abstract: We identify a formal connection between physical problems related to the
detection of separable (unentangled) quantum states and complexity classes in theoretical
computer science. In particular, we show that to nearly every quantum interactive proof
complexity class (including BQP, QMA, QMA(2), and QSZK), there corresponds a natural
separability testing problem that is complete for that class. Of particular interest is the fact that
the problem of determining whether an isometry can be made to produce a separable state is
either QMA-complete or QMA(2)-complete, depending upon whether the distance between
quantum states is measured by the one-way LOCC norm or the trace norm. We obtain
strong hardness results by employing prior work on entanglement purification protocols to
prove that for each n-qubit maximally entangled state there exists a fixed one-way LOCC
measurement that distinguishes it from any separable state with error probability that decays
exponentially in n.
ACM Classification: F.1.3
AMS Classification: 68Q10, 68Q15, 68Q17, 81P68
Key words and phrases: quantum entanglement, quantum complexity theory, quantum interactive
proofs, quantum statistical zero knowledge, BQP, QMA, QSZK, QIP, separability testing
∗ Supported by Government of Canada through Industry Canada, the Province of Ontario through the Ministry of Research
and Innovation, NSERC, DTO-ARO, CIFAR, and QuantumWorks.
† Supported by Canada Research Chairs program, the Perimeter Institute, CIFAR, NSERC and ONR through grant
N000140811249. The Perimeter Institute is supported by the Government of Canada through Industry Canada and by the
Province of Ontario through the Ministry of Research and Innovation.
‡ Supported by NSERC.
§ Supported by Centre de Recherches Mathématiques.
© 2015 Gus Gutoski, Patrick Hayden, Kevin Milner, and Mark M. Wilde
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2015.v011a003
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
1 Introduction
Certain families of decision problems have proven to be particularly versatile and expressive in complexity
theory, in the sense that slightly varying their formulation can tune the difficulty of the problems through a
wide range of complexity classes. Adding quantifiers to the problem of evaluating a Boolean formula, for
example, brings the venerable satisfiability problem up through the levels of the polynomial hierarchy [68]
all the way up to PSPACE [67], at each level providing a decision problem complete for the associated
complexity class. Moreover, adding limitations to the format of the Boolean satisfiability problem gives
decision problems complete for a variety of more limited classes.1 Likewise, in the domain of interactive
proofs [4, 38, 5, 71, 54, 73], problems based on distinguishing probability distributions or quantum states,
depending on the setting, arise very naturally.
In the domain of quantum information theory, quantum mechanical entanglement is responsible
for many of the most surprising and, not coincidentally, useful potential applications of quantum infor-
mation [49], including quantum teleportation [9], super-dense coding [13], enhanced communication
capacities [11, 12, 28], device-independent quantum key distribution [35, 69], and communication com-
plexity [25]. Thus, deciding whether a given quantum state is separable (unentangled) or entangled is a
prominent and long-standing question that frequently resurfaces in different forms. The complexity of
determining whether a given mixed quantum state is separable or entangled therefore arose early and
was resolved: the problem is NP-complete with respect to Cook reductions when the state is specified
as a density matrix and one demands an error tolerance no smaller than an inverse polynomial in the
dimension of the matrix [39, 37].
From a physics or engineering perspective, however, it is often more natural to specify a quantum
state as arising from a sequence of specified operations (as in a quantum circuit) or the application of a
local Hamiltonian [59, 14]. This formulation of the quantum separability problem was studied by three of
us [46], wherein it was shown that the problem is hard for both QSZK and NP, even when one demands
that no-instances be far from separable in the so-called “one-way LOCC distance” (and not merely in
trace distance). It was also shown that this one-way LOCC variant of the problem admits a two-message
quantum interactive proof, putting it in QIP(2). The exact complexity of this problem is still open.
Informally, the one-way LOCC distance is an operationally motivated distance measure for bipartite
quantum states [62]. Given two states ρ, ξ of registers AB, the one-way LOCC norm kρ − ξ k1- LOCC
dictates the maximum probability with which ρ could be distinguished from ξ by two parties acting locally
on registers A, B and endowed with classical communication from A to B. It is clear that the one-way
LOCC distance is no larger than the trace distance, and it can sometimes be much smaller [34, 29, 30, 62].
In one of the earliest examples [34], it was found that maximally mixed states on the symmetric and
antisymmetric subspace of two systems of dimension d have a 1-LOCC distance no larger than O(1/d)
while their trace distance is maximal, given that these states are orthogonal. See Section 2.4 for details.
In this paper, we explore several variations on the complexity of determining whether a state specified
by a quantum circuit is separable, or whether a channel specified by a quantum circuit can be made to
produce a separable output state. The properties we vary include the following:
1 For example, it is known that if clauses of the Boolean satisfiability problem are limited to two variables each, the resulting
problem (2SAT) is NL-complete [64, Ch. 4.2, Theorem 16.3], while if one allows only Horn clauses the resulting problem
(HORNSAT) is P-complete [27], and if one removes any such limitations on clauses the problem (SAT) is NP-complete [26].
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 60
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
1. Allowing arbitrary mixed states versus restricting attention to pure states.
2. Allowing arbitrary channels versus restricting attention to isometric channels.
3. We compare the difficulty of deciding whether entanglement is present (separable versus entangled
states) with the difficulty of identifying any correlation whatsoever (product versus non-product
states).
4. Measuring distance between quantum states using the trace norm or the so-called “one-way LOCC
norm” of [62].
We study seven different combinations of these properties, obtaining problems that are complete for four
different complexity classes based on quantum interactive proofs: BQP, QMA, QMA(2), and QSZK. Our
study applies to multipartite states and channels, though only bipartite states and channels are required
for the hardness results. We obtain strong hardness results as a corollary of a theorem establishing
the existence of a fixed one-way LOCC measurement that successfully distinguishes a given n-qubit
maximally entangled state from any separable state with error probability that decays exponentially in
n. (Theorem 3.1 of Section 3.) It appears that this observation has not yet been made explicitly in the
literature, though it is implied by prior results on entanglement purification protocols [10, 7, 3, 43]. We
provide a new proof.
Outline of paper. A detailed list of our complexity theoretic results is given in Figure 1 of Section 1.1.
A summary of relevant concepts such as the one-way LOCC distance, various complexity classes, the
permutation and swap tests is given in Section 2. Our strong lower bound on the one-way LOCC distance
between maximally entangled and separable states is proven in Section 3. The completeness results are
presented in Sections 4–7. In Section 9 we discuss how these completeness results provide operational
interpretations for several geometric measures of entanglement discussed in [75, 23] and references
therein. Finally, we conclude in Section 11 with a summary of our results and a discussion of directions
for future research.
1.1 Overview of results
Figure 1 gives a brief description of each problem and provides a concise summary of our results. Below
we give more details of our results along with their relation to prior results in the literature:
1. P URE P RODUCT S TATE is BQP-complete, as is the one-way LOCC version of the problem.
(Theorem 4.2 of Section 4.) Membership in BQP follows from the soundness of the “product
test” [44]. Hardness of the one-way LOCC version follows from an application of Theorem 3.1.
2. The one-way LOCC version of S EPARABLE I SOMETRY O UTPUT is QMA-complete. (Theorem 5.2
of Section 5.) Membership in QMA follows from the existence of succinct k-extendible witnesses
for separability [17]. (A similar approach was used in previous work by three of us to place the
one-way LOCC version of S EPARABLE S TATE inside QIP(2) [?, 46].) Hardness follows from
another application of Theorem 3.1.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 61
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
3. P URE P RODUCT I SOMETRY O UTPUT, P RODUCT I SOMETRY O UTPUT, and S EPARABLE I SOME -
TRY O UTPUT are QMA(2)-complete. (Theorem 6.2 and Corollary 6.9 of Section 6.) Membership
of P URE P RODUCT I SOMETRY O UTPUT in QMA(2) follows from a simple application of the swap
test combined with the collapse QMA(k) = QMA(2) [44]. Hardness is the result of a novel circuit
gadget (Figure 4). Completeness for the other two problems follows by an equivalence to P URE
P RODUCT I SOMETRY (Section 6.3).
4. P RODUCT S TATE is QSZK-complete. (Theorem 7.2 of Section 7.) The result follows by an
equivalence with the QSZK-complete problem Q UANTUM S TATE S IMILARITY [70, 74].
5. The one-way LOCC version of S EPARABLE S TATE is in SQG, a competing-provers class known to
coincide with PSPACE [41]. (Proposition 8.2 of Section 8.) As mentioned previously, this problem
is already known to be contained in QIP(2) [46], which is a subset of PSPACE [51, 50]. Thus, this
new bound is not a complexity-theoretic improvement over prior work.
However, it is interesting that this problem admits a succinct quantum witness in support of
separability, provided that the verifier is granted the additional ability to query a second, competing
prover in his effort to check the veracity of the first prover’s purported witness. By contrast, the
two-message single-prover quantum interactive proof of [46] depends critically upon the ability of
the prover to apply a channel in support of separability.
2 Preliminaries
This section summarizes some facts about quantum information and complexity theory relevant for the
rest of the paper. Familiarity with both fields of study is assumed; our primary goal here is to establish
notation and terminology. Some references giving background on these topics are [63, 78, 79] and [73, 1].
2.1 Registers, states, separable states
A register is a finite-level quantum system, which is implicitly identified with a finite-dimensional
complex Euclidean space. Registers are denoted with Roman capital letters A, B, . . . . The state of a
register is described by a density matrix, which is a positive semidefinite matrix ρ with Tr(ρ) = 1. A pure
state is a rank-one density matrix. Pure states can be written in standard bra-ket notation ρ = |ψihψ| for
some unit vector |ψi. It is common practice to refer to unit vectors |ψi as pure states. The Greek letters
φ , ψ are reserved for pure states and we often abbreviate |ψihψ| to ψ.
A multipartite state ρA1 ···Al is a product state if ρA1 ···Al = ρA1 ⊗ · · · ⊗ ρAl for states ρA1 , . . . , ρAl of
registers A1 , . . . , Al , respectively. A state is separable if it can be written as a probabilistic mixture of
product states [77]. That is, a multipartite state ρA1 ···Al is said to be separable if it admits a decomposition
of the following form:
ρA1 ···Al = ∑ pY (y) σA1,y
1
⊗ · · · ⊗ σAl,yl , (2.1)
y∈Y
for collections {σA1,y
1
}, . . . , {σAl,yl } of quantum states and some probability distribution pY (y) over an
alphabet Y [77]. By applying the spectral theorem to each density operator, we can always find a
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 62
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
Problem name Description Complexity Circuit
A
• P URE P RODUCT S TATE Is the state generated by the
• P URE P RODUCT S TATE, one- pure-state quantum circuit BQP-complete |0⟩ U
way LOCC version close to a product state? B
Is there an input to the isom-
etry such that the output is
close to a separable state in
• S EPARABLE I SOMETRY O UT-
trace distance, or does every QMA-complete
PUT , one-way LOCC version
input lead to an output that
A
is far from separable in one- Circuit
Input
way LOCC distance? U
• P URE P RODUCT I SOMETRY |0⟩ B
O UTPUT Is there an input to the isom-
• P RODUCT I SOMETRY O UT- etry such that the output is QMA(2)-
PUT close to a product/separable complete
• S EPARABLE I SOMETRY O UT- state?
PUT
Is the state generated by the
• P RODUCT S TATE mixed-state circuit close to a QSZK-complete
product state? R
In QIP(2). A
Is the state generated by the |0⟩ U
• S EPARABLE S TATE, one-way QSZK-hard,
mixed-state circuit close to a B
LOCC version NP-hard.
separable state?
[46]
Is there an input to the chan-
nel such that the output is R
Channel
close to a separable state in Input
• S EPARABLE C HANNEL O UT- QIP-complete U A
trace distance or does every
PUT , one-way LOCC version [46] |0⟩
input lead to an output that B
is far from separable in one-
way LOCC distance?
Figure 1: The collected results of separability testing problems and their complexity. A “one-way LOCC
version” of a problem means that distances for yes-instances are measured by the trace norm, but distances
for no-instances are measured by the one-way LOCC norm.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 63
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
decomposition of any separable state in terms of pure product states:
ρA1 ···A` = ∑ pZ (z) |ψ 1,z ihψ 1,z |A1 ⊗ · · · ⊗ |ψ `,z ihψ `,z |A` . (2.2)
z∈Z
A state is entangled if it is not separable.
In the multipartite case it is often necessary to specify the cut or partition of the registers relative to
which ρ is product or separable. For example, a state ρ of registers ABCD could be a bipartite product
state with respect to the cut AB : CD, yet it may not be a product state with respect to the tripartite cut
A : B : CD or the bipartite cut AC : BD. We let S denote the set of all separable states with respect to
a given cut. Whenever the cut is not immediately clear from the context, we make it explicit with an
argument—for example, S(A : B : CD).
2.2 Trace distance, fidelity
The Schatten 1-norm kX k1 of a matrix X is defined as the sum of the singular values of X. (Hereafter we
refer to this norm as simply the 1-norm. This norm is sometimes called the trace norm and is alternately
denoted kX kTr .) The 1-norm characterizes the physically observable difference between two quantum
states ρ, ξ in the following sense: given a quantum register prepared in one of {ρ, ξ } chosen uniformly at
random, the maximum probability with which one can correctly identify the given state by a two-outcome
measurement of that register is equal to 1/2 + kρ − ξ k1 /4. The measurement that achieves this maximal
probability is known as the Helstrom measurement [48].
The quantity kρ − ξ k1 is sometimes called the trace distance between ρ, ξ . The trace distance
between two quantum states ρ, ξ is given by the following variational characterization:
kρ − ξ k1 = 2 max Tr(Π(ρ − ξ )) , (2.3)
0ΠI
where the maximizing Π? leads to the Helstrom measurement {Π? , I − Π? }. A straightforward conse-
quence of (2.3) is that if two states are close in trace distance then they must have similar measurement
statistics. In particular, for all measurement operators 0 Π I it holds that
1
Tr(Πρ) ≥ Tr(Πξ ) − kρ − ξ k1 . (2.4)
2
The trace distance kψ − φ k1 between two pure states |ψi, |φ i is related to the inner product hψ|φ i
by the formula
|hφ |ψi|2 = 1 − kψ − φ k21 /4 . (2.5)
The following implication holds for any pure states φ , ψ and any ε ∈ [0, 1]:
√
|hφ |ψi|2 ≥ 1 − ε =⇒ kφ − ψ k1 ≤ 2 ε . (2.6)
The fidelity is a pseudodistance measure for quantum states given by
√ p 2
F(ρ, ξ ) = ρ ξ (2.7)
1
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 64
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
for all density matrices ρ, ξ . Uhlmann’s Theorem asserts that the fidelity between two states ρ, ξ is the
optimal squared overlap between purifications of ρ, ξ :
F(ρ, ξ ) = max |hφρ |φσ i|2 . (2.8)
|φρ i,|φσ i
Uhlmann’s Theorem gives the fidelity an operational interpretation as the maximum probability with
which a purification of ρ would pass a test for being a purification of σ . The fidelity and trace distance
are related by the Fuchs-van-de-Graaf inequalities [36]:
p 1 p
1− F(ρ, ξ ) ≤ kρ − ξ k1 ≤ 1 − F(ρ, ξ ) . (2.9)
2
2.3 Permutation test, swap test
The permutation test is a quantum circuit applied to a multi-register system A1 , . . . , An with the property
that the probability of passing is equal to the shadow of the state on the symmetric subspace of the complex
sym
Euclidean space associated with A1 , . . . , An (i. e., Tr(ΠA1 ,...,An ρ)) [53] (see also [6, 52]). Furthermore, if
the test passes, then the resulting state of those registers is supported on the symmetric subspace. The test
consists of the following steps:
1. Prepare an n!-dimensional ancillary register W in a uniform superposition of all n! computational
basis states. (This is accomplished by applying the quantum Fourier transform to the all-zeros state
|0i of W .)
2. Apply a controlled-permutation unitary that permutes registers A1 , . . . , An according to the permu-
tation indexed in register W .
3. Invert the quantum Fourier transform on W and measure that register in the computational basis.
Accept if and only if the measurement outcome is all zeros.
A special case of the permutation test for n = 2 is known as the swap test [20]. (In this case the
ancillary register W is just a single qubit and the quantum Fourier transform is just the standard Hadamard
gate.) The swap test has the powerful property that if registers A1 A2 are prepared in a pure product state
|ψi|φ i then the swap test passes with probability
1 1 1
+ |hψ|φ i|2 = 1 − kψ − φ k21 . (2.10)
2 2 8
Thus, with repetition, the swap test can be used to estimate the distance between any two unknown pure
states.
2.4 One-way LOCC distance
In this paper we are sometimes interested in the distinguishability of multipartite quantum states under
the restriction that the distinguishing measurement must be implementable by local operations with
unidirectional classical communication. This class of measurements induces a matrix norm called the
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 65
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
one-way LOCC norm [62]. For each matrix X acting on the complex Euclidean space associated with
registers AB, the one-way LOCC norm kX k1- LOCC of X is defined by
kX k1- LOCC = max k(IA ⊗ ΛB→M )(X)k1 , (2.11)
ΛB→M
where the maximization is over all quantum-to-classical channels ΛB→M . These are the channels that
measure the contents of register B and store the classical outcome in a new register M. Every such channel
has the form
ΛB→M (ρ) = ∑ Tr(Λm ρ)|mihm| , (2.12)
m
where {|mi} is an orthonormal basis and {Λm } forms a quantum measurement, meaning that each Λm is
positive semidefinite and ∑m Λm = I.
This definition of the one-way LOCC norm is asymmetric: one could define another norm as a
maximization over measurements of register A, and these norms are distinct. It is clear from the definition
that
kX k1- LOCC ≤ kX k1 , (2.13)
because the one-way LOCC measurements are a subset of all measurements.
The one-way LOCC norm extends naturally to multi-register systems [56, 16, 19]. In particular, for
each matrix X acting on the complex Euclidean space associated with registers A1 · · · A` , the `-partite
one-way LOCC norm of X is given by
kX k1- LOCC = max k(IA1 ⊗ ΛA2 ⊗ · · · ⊗ ΛA` )(X)k1 , (2.14)
ΛA2 ,...,ΛA`
where the maximization is now over quantum-to-classical channels ΛA2 , . . . , ΛAl . The interpretation
here when X is a difference of two density matrices is that the last ` − 1 parties each perform a local
measurement on their systems and communicate the results to the first party, who then attempts to
distinguish the two states.
2.5 Quantum interactive proofs
A quantum interactive proof consists of a conversation between a polynomial-time quantum verifier and
a computationally unbounded quantum prover regarding some binary input string x. The prover attempts
to convince the verifier to accept x and the verifier attempts to judge the veracity of the prover’s argument.
A promise problem L is said to admit a quantum interactive proof with completeness c and soundness s if
there exists c, s ∈ [0, 1] such that c > s and a verifier who meets the following conditions:
Completeness condition. If x is a yes-instance of L, then the prover can convince the verifier to accept
with probability at least c.
Soundness condition. If x is a no-instance of L, then no prover can convince the verifier to accept with
probability higher than s.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 66
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
The completeness and soundness parameters c, s need not be fixed constants but may instead vary as a
function of the input length |x|. If these parameters are not specified then it is assumed that L admits a
quantum interactive proof for some choice of c(|x|), s(|x|) for which there exists a polynomial-bounded
function p(|x|) such that c − s ≥ 1/p. The complexity class QIP consists of all promise problems that
admit quantum interactive proofs and is known to coincide with PSPACE [50].
Often in the study of interactive proofs the precise values of c, s are immaterial because error-reduction
procedures can be used to transform any verifier for which c − s ≥ 1/p into another verifier for which
c tends toward one and s tends toward zero exponentially quickly in the bit length of x. (For example,
sequential repetition followed by a majority vote can be used to reduce error for QIP.) For this reason, it is
typical to assume without loss of generality that c, s are constants such as 2/3, 1/3 or that c is exponentially
close to one and s is exponentially close to zero whenever it is convenient to do so. However, it is not
always clear that a given complexity class is robust with respect to the choice of c, s so it is good practice
to be as inclusive as possible when defining these classes.
Interesting subclasses of QIP are obtained by restricting the number of messages in the interaction
between the verifier and prover. For each positive integer m, the class QIP(m) consists of those problems
that admit a quantum interactive proof in which the verifier exchanges no more than m messages with the
prover. It is known that three messages suffice for any quantum interactive proof, so that QIP = QIP(3)
[54], leaving a hierarchy of four classes defined by quantum interactive proofs. Fundamental complexity
classes such as BQP and QMA can be written in this notation as QIP(0) and QIP(1), respectively. This
hierarchy, along with other complexity classes considered in this paper (other than QMIPne ), is depicted
in Figure 2. QMIPne is a class defined in [55]—it allows for multiple prover interactive proofs with
provers who do not share entanglement (clearly, this contains both QMA(2) and QIP).
A quantum interactive proof for a promise problem L is said to be statistical zero knowledge if for
each yes-instance x of L the verifier learns nothing from the prover beyond the veracity of the claim “x
is a yes-instance of L.” This property is formalized via a simulation-based definition of “knowledge.”
The complexity class of promise problems that admit statistical zero knowledge quantum interactive
proofs is called QSZK. We need not concern ourselves with a precise definition of this class, since our
completeness results are established by equivalence to another QSZK-complete problem. The reader is
referred to the seminal works in [70, 74] for more information on statistical zero knowledge quantum
interactive proofs.
Other interesting variations of the quantum interactive proof model are obtained by considering
multiple cooperating or competing provers. For example, one can consider a variant of QMA in which
k distinct and unentangled provers cooperate in order to convince the verifier to accept. The resulting
complexity class is called QMA(k) and is known to satisfy QMA(k) = QMA(2) for all integers k ≥ 2 [44].
The only known bounds for QMA(2) are the trivial bounds QMA ⊆ QMA(2) ⊆ NEXP. Lower bounds
for QMA(2) are presented in references [2, 15, 8, 22, 57, 24]; upper bounds in references [18, 66].
Despite the lack of any decent upper bound on QMA(2), we are aware of only two problems in
QMA(2) that are not also known to be in QMA: the pure-state N-representability problem [58] and the
separable sparse Hamiltonian problem [21]. Of these, only the latter is known to be QMA(2)-complete.
The present paper gives another QMA(2)-complete problem in Section 6.
Alternately, one could consider quantum interactive proofs with two competing provers: one prover—
the yes-prover—tries to convince the verifier to accept x while the other prover—the no-prover—tries
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 67
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
QMIPne
QIP(3) = PSPACE = SQG
QMA(2) QIP(2)
QIP(1) = QMA QSZK
QIP(0) = BQP
NP
P
Figure 2: The quantum interactive proof hierarchy and related classes discussed in this paper. A line
denotes inclusion of the lower class in the higher class. (For example, P is a subset of NP.) Classes for
which a separability testing problem is known to be complete are in bold type.
to convince the verifier to reject x. As before, interesting complexity classes are obtained by restricting
the number and timing of messages in the interaction between the verifier and provers. In Section 8 we
exhibit a protocol in which the verifier receives a single message from the yes-prover and then exchanges
two messages with the no-prover. The complexity class of promise problems that admit such proofs is
called SQG (for “short quantum games”) and is known to coincide with PSPACE [41].
Each of the aforementioned complexity classes is known to be robust with respect to the choice of
completeness and soundness parameters c, s, meaning that any protocol for which c is larger than s plus an
inverse polynomial in the input length can be amplified into a new protocol with c exponentially close to
one and s exponentially close to zero. Error reduction for BQP follows immediately from Chernoff-type
bounds via sequential repetition followed by a majority vote. Error-reduction results for QIP, QIP(2),
QMA, QSZK, QMA(2), and SQG were established in [54, 51, 61, 70, 44, 41], respectively.2
2 That SQG is robust with respect to error follows from the containments SQG(c, s) ⊆ PSPACE for any c − s > 1/poly [41]
and PSPACE ⊆ SQG(1 − ε, ε) for any desired exponentially small ε [40]. However, the “error reduction procedure” induced
here is very circuitous: a high-error short quantum game must be simulated in polynomial space, and then that polynomial-space
computation must be converted back into a low-error short quantum game via proofs of IP = PSPACE [60, 65]. It is not known
whether a more straightforward transformation such as parallel repetition followed by a majority vote could be used to reduce
error for SQG.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 68
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
3 One-way LOCC distance to a separable state
In this section we prove a theorem that enables us to establish strong hardness results for various
separability testing problems appearing later in the paper.
If |φ i is any maximally entangled pure state of two n-qubit registers AB then
max F(φ , σ ) = 2−n . (3.1)
σ ∈S(A:B)
A concise proof of the above equality can be found in [72, Lecture 17]. Applying the above relation and
(2.9), we find the following result for the trace distance:
min kφ − σ k1 ≥ 2 1 − 2−2n .
(3.2)
σ ∈S(A:B)
In fact, a much stronger statement holds: every maximally entangled state is exponentially far from
separable not only in trace distance, but also in one-way LOCC distance. It appears that this observation
has not yet been made explicitly in the literature, though it is implied by prior results on entanglement
purification protocols [10, 7, 3, 43]. We provide a new proof.
Theorem 3.1 (Minimum one-way LOCC distance to separable). For all maximally entangled pure states
|φ i of two n-qubit registers AB it holds that
min kφ − σ k1- LOCC ≥ 2(1 − (2/3)n ) . (3.3)
σ ∈S(A:B)
Moreover, this bound is witnessed by a fixed one-way LOCC measurement that depends only on |φ i.
Proof. Let An := A1 · · · An denote Alice’s n qubits, and let Bn := B1 · · · Bn denote Bob’s. By the local uni-
tary equivalence of maximally entangled states, it suffices to exhibit a fixed one-way LOCC measurement
that successfully distinguishes any separable state σAn :Bn from n singlets
n
ψ − Ai Bi ,
O
(3.4)
i=1
√
each in the state |ψ − i := (|01i − |10i)/ 2. One such scheme is as follows:
1. (Twirling) Bob selects n 2 × 2 unitaries {U1 , . . . ,Un } at random according to the Haar measure and
applies unitary Ui to his ith qubit. He reports to Alice which unitaries he selected and she applies
Ui to her ith qubit. This “twirling” step has the effect of symmetrizing their state so that it is a
mixture of Bell states.
2. For i ∈ {1, . . . , n}, Bob picks one of the following three Pauli operators
0 1 1 0
X := , Z := , Y = iXZ (3.5)
1 0 0 −1
at random. Let Pi denote the ith choice. He measures Pi on his ith qubit. After performing the last
measurement, he sends all measurement choices and outcomes to Alice.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 69
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
3. For i ∈ {1, . . . , n}, Alice measures Pi on her ith qubit.
4. She accepts that the state is n singlets if and only if all measurement outcomes are different.
The main reason that this 1-LOCC distinguishing protocol works is as follows: the singlet is the
only state having the property that measurement outcomes are different when performing the same von
Neumann measurement on each qubit (for any von Neumann measurement). Furthermore, the maximum
probability with which a separable state can pass this test is equal to 2/3, so that performing n of these
tests on a separable state σAn :Bn reduces the probability of passing the “singlet test” to (2/3)n .
We now analyze this protocol in more detail. Due to the fact that (U ⊗U)|ψ − i = |ψ − i for any 2 × 2
unitary U, the first step has no effect on the singlets. Furthermore, the rest of the protocol succeeds
with probability one if the state is equal to n singlets, due to the property mentioned in the previous
paragraph. So we turn to analyzing the probability of accepting if the state is in fact separable. We begin
by analyzing the first “Pauli test” in steps 2-4 and find a bound on its acceptance probability. When doing
so, it suffices to consider the reduced state of σAn :Bn on systems A1 and B1 , which is separable across this
cut because the original state is separable across the An : Bn cut. The initial twirling procedure transforms
this separable state to the following “Werner” state:
1− p +
p ψ− ψ− A B + ψ ψ+ A B + φ + φ + A B + φ − φ − A B , (3.6)
1 1 3 1 1 1 1 1 1
such that the maximal value of p is 1/2 [49, Section VI-B-9]. (The states |ψ + iA1 B1 , |φ + iA1 B1 , and
|φ − iA1 B1 are the other Bell states orthogonal to |ψ − iA1 B1 .) One can check that the probability with which
each of the three other Bell states besides |ψ − iA1 B1 passes the “Pauli test” on the ith qubit (in steps 2-4
above) is equal to 1/3. So this implies that the maximum probability with which this Pauli test can pass
is 1/2 · 1 + 1/6 · (1/3 + 1/3 + 1/3) = 2/3. The analysis is the same for the other n − 1 Pauli tests: the
only property that we use is that the reduced states on systems Ai : Bi is separable across this cut, so that
entanglement (or any correlation whatsoever) in the systems A1 · · · An or B1 · · · Bn (but not across the cut
An : Bn ) cannot help in passing this test. This property follows from the facts that (i) the initial state is
separable across the An : Bn cut, (ii) the scheme is LOCC with respect to this cut, and (iii) separability is
preserved under LOCC. The result is that (2/3)n is a universal bound on the maximum probability with
which any separable state σAn :Bn can pass the overall test. By the discussion in Sections 2.2 and 2.4, the
statement in the theorem follows.
4 P URE P RODUCT S TATE is BQP-complete
We begin with the simplest of our separability testing promise problems—that of determining whether
the state prepared by a given quantum circuit is close to a pure product state. We propose two variants of
this problem, one easier than the other. We prove that the harder variant is in BQP and we prove that the
easier variant is BQP-hard, establishing BQP-completeness for both problems.
Problem 4.1 ((α, β , `)-P URE P RODUCT S TATE3 ).
3 If ` = 2 then the problem is called (α, β )-B IPARTITE P URE P RODUCT S TATE . This convention applies to other problem
names throughout the paper.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 70
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
Input: A description of a quantum circuit that prepares an `-partite pure state |ψi.
Yes: |ψi is α-close to a pure product state:
min kψ − φ1 ⊗ · · · ⊗ φ` k1 ≤ α . (4.1)
|φ1 i,...,|φ` i
No: |ψi is β -far from any pure product state:
min kψ − φ1 ⊗ · · · ⊗ φ` k1 ≥ β . (4.2)
|φ1 i,...,|φ` i
We define the one-way LOCC version of (α, β , `)-P URE P RODUCT S TATE similarly except that the
trace norm in the specification of a no-instance is replaced with the one-way LOCC norm. The one-way
LOCC version of P URE P RODUCT S TATE trivially reduces to the trace distance version by virtue of the
inequality kX k1 ≥ kX k1- LOCC . The main result of this section is the following theorem:
Theorem 4.2 (P URE P RODUCT S TATE is BQP-complete). The following hold:
√
1. The trace distance version of (α, β , `)-P URE P RODUCT S TATE4 is in BQP for all ` and α < β 3211 .
2. The one-way LOCC version of (ε, 2 − ε)-B IPARTITE P URE P RODUCT S TATE is BQP-hard, even
when ε decays exponentially in the input length.
√
Thus, both problems are BQP-complete for all ` ≥ 2 and all (α, β ) with 0 < α < β 3211 and β < 2.
4.1 Membership in BQP
Our efficient quantum algorithm for the P URE P RODUCT S TATE problem employs the product test. The
product test is a boolean test that takes as input two copies of an arbitrary multipartite pure state |ψi.
The closer |ψi is to a product state, the higher the probability with which the product test passes. A
specification of the product test is as follows:
1. Given are two copies of an arbitrary `-partite pure state |ψi. One of these copies is contained in
registers A1 , . . . , A` and the other in B1 , . . . , B` .
2. Perform ` swap tests—one for each pair of registers (Ai , Bi ) for i = 1, . . . , `. Accept if and only if
all the swap tests pass.
The relationship between the distance from |ψi to the nearest product state and the success probability of
the product test was established in [44].
Theorem 4.3 ([44]). For each `-partite pure state |ψi let Ptest (ψ) denote the probability with which the
product test passes when applied to |ψi and let
1−ε = max |hψ|φ1 ⊗ · · · ⊗ φ` i|2 . (4.3)
|φ1 i,...,|φ` i
√
4 It is implicit here and throughout the rest of the paper that the gap between α and β 11
32 is larger than an inverse polynomial
in the input length.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 71
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
It holds that
11
1 − 2ε ≤ Ptest (ψ) ≤ 1 − ε. (4.4)
512
The bounds of Theorem 4.3 are easily written in terms of the trace distance t between |ψi and the
nearest product state via (2.5):
11 2
1 − t 2 /2 ≤ Ptest (ψ) ≤ 1 − t . (4.5)
2048
Armed with the product test, we now present our quantum algorithm for the P URE P RODUCT S TATE
problem.
√
Proposition 4.4. (α, β , `)-P URE P RODUCT S TATE is in BQP for all ` and all α < β 3211 .
Proof. The efficient quantum algorithm for (α, β , `)-P URE P RODUCT S TATE is as follows: use the input
circuit to prepare two copies of |ψi, perform the product test, and accept if and only if the product test
passes.
If |ψi is a yes-instance then (4.5) tells us that the product test passes with probability at least 1 − α 2 /2.
On the other hand, if |ψi is a no-instance then (4.5) tells us that the product test passes with probability
at most 1 − (11/2048)β 2 . The algorithm witnesses membership
√ in BQP whenever the former quantity is
larger than the latter, which occurs whenever α < β · 11/32.
4.2 Hardness for BQP
Proposition 4.5. The one-way LOCC version of (ε, 2 − ε)-B IPARTITE P URE P RODUCT S TATE is BQP-
hard, even when ε decays exponentially in the input length.
Proof. Let L be any promise problem in BQP and let {|νix }x be a family of efficiently preparable pure
states witnessing membership of L in BQP. By this we mean the following: for each instance x of L the
state |νx i is held in two registers DG. Register D is a decision qubit indicating acceptance or rejection
of x and register G is a garbage register that is a purifying system for D.
Suppose that the family {|νix }x has completeness 1 − δ and soundness δ . In this proof we reduce the
arbitrary problem L to the one-way LOCC version of (α, β )-B IPARTITE P URE P RODUCT S TATE where
√
α =2 δ, (4.6)
√
β = 2 − 22−n/2 − 2 δ , (4.7)
for any desired n. The desired hardness result then follows by an appropriate choice of δ , n, given that
BQP(c, s) ⊆ BQP(δ , 1 − δ ) for any δ exponentially small in the input length.
The reduction is as follows. Given an instance x of L we produce a description of the following circuit
for preparing a pure state |ψi of registers AA0 BDG:
1. Prepare registers AA0 in a 2n-qubit maximally entangled state such as n EPR pairs, which we denote
by |φ + i. Prepare register B in the n-qubit |0i state. Prepare registers DG in state |νx i.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 72
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
2. Perform a controlled swap gate that swaps registers A0 and B when D is in the reject state |noi and
acts as the identity otherwise.
A graphical depiction of this state preparation circuit appears later in the paper as a special case of
Figure 3.
If x is a yes-instance of L then |νx i has squared overlap at least 1 − √δ with |yesiD |ζ iG for some
state |ζ i of register G. It follows that the constructed state |ψi is 2 δ -close in trace distance to
|φ + iAA0 |0iB |yesiD |ζ iG , which is a product with respect to the cut AA0 : BDG. So |ψi is a yes-instance of
the one-way LOCC version of (α, β )-B IPARTITE P URE P RODUCT S TATE.
Next, suppose that x is a no-instance of L. In this case |νx i has√squared overlap at least 1 − δ with
|noiD |ηiG for some state |ηi of register G. It follows that |ψi is 2 δ -close in trace distance to a state
which is in tensor product with the 2n-qubit maximally entangled state |φ + i on registers AB. By contrast,
for any product state |φ i of registers AA0 : BDG the reduced state TrA0 DG (φ ) of registers AB must also
be a product state. Thus, it suffices to exhibit a fixed one-way LOCC measurement that successfully
distinguishes any product state of registers AB from n EPR pairs with high probability. The existence of
such a measurement was proved in Theorem 3.1.
We therefore have the following for any product state |φ i of registers AA0 : BDG:
+ +
kψ − φ k1- LOCC ≥ TrA0 DG (φ ) − φAB − φAB − TrA0 DG (ψ) 1- LOCC (4.8)
√ 1- LOCC
≥ 2 − 22−n/2 − 2 δ , (4.9)
from which it follows that |ψi is a no-instance of the one-way LOCC version of (α, β )-B IPARTITE P URE
P RODUCT S TATE.
5 S EPARABLE I SOMETRY O UTPUT (one-way LOCC version) is QMA-
complete
In this section we prove QMA-completeness of the problem of deciding whether the isometry implemented
by a given quantum circuit can be made to produce a state that is close to separable in trace distance or
far from separable in one-way LOCC distance.
Problem 5.1 ((α, β , `)-S EPARABLE I SOMETRY O UTPUT, one-way LOCC version).
Input: A description of a quantum circuit that implements an isometry U with an `-partite output
system A1 · · · A` .
Yes: There is an input state ρ such that UρU ∗ is α-close in trace distance to separable:
min min kUρU ∗ − σ k1 ≤ α . (5.1)
ρ σ ∈S(A1 :···:A` )
No: For all input states ρ it holds that UρU ∗ is β -far in one-way LOCC distance from separable:
min min kUρU ∗ − σ k1- LOCC ≥ β . (5.2)
ρ σ ∈S(A1 :···:A` )
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 73
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
The main result of this section is the following theorem:
Theorem 5.2 (S EPARABLE I SOMETRY O UTPUT, one-way LOCC version is QMA-complete). The
following hold:
1. The one-way LOCC version of (α, β , `)-S EPARABLE I SOMETRY O UTPUT is in QMA for all ` and
all α < β 4 /16.
2. The one-way LOCC version of (ε, 2 − ε)-B IPARTITE S EPARABLE I SOMETRY O UTPUT is QMA-
hard, even when ε decays exponentially in the input length.
Thus, the problem is QMA-complete for all ` ≥ 2, all 0 < α < β 4 /16, and all β < 2.
5.1 Containment in QMA
Our quantum witness for separability invokes the notion of k-extendibility of separable states [76]. We
therefore begin with a brief summary of k-extendibility.
Let AB be any two registers and let B1 , . . . , Bk be registers each of the same size as B. A bipartite
state ρ of registers AB is k-extendible if there exists a state ω of registers AB1 · · · Bk that is invariant under
permutations of registers B1 , . . . , Bk and consistent with ρ, meaning that TrB2 ···Bk (ω) = ρ.
The set of all k-extendible states (with respect to a given cut of the registers) is denoted Ek . It is a
basic fact that every separable state is k-extendible for all k, so that S ⊆ Ek . To see this, let
ρ = ∑ pi |ψ i ihψ i |A ⊗ |φ i ihφ i |B (5.3)
i
be any separable state of registers AB and observe that
∑ pi |ψ i ihψ i |A ⊗ |φ i ihφ i |⊗k
B (5.4)
i
is a k-extension of ρ. It is known that if ρ is not separable then there exists some k0 for which ρ is not
k0 -extendible. Moreover, it is known that Ek+1 ⊆ Ek for all k, from which it follows that the sets Ek form
a containment hierarchy that converges to the set S of separable states in the limit k → ∞ [31, 32].
The notion of k-extendibility extends naturally to multi-register systems A1 · · · A` by imposing the
extendibility condition on each individual register [33, 19], though the notation is cumbersome. Formally,
let Ai,1 , . . . , Ai,k be registers of the same size as Ai . A state ρ of registers A1 · · · A` is k-extendible with
respect to A1 : · · · : A` if there exists a global state ω of all ` k registers Ai, j that is consistent with ρ on
A1 · · · A` and invariant under permutations of registers Ai,1 , . . . , Ai,k for all i = 1, . . . , `. (Observe that there
are ` · k! such permutations.)
Brandão and Harrow have shown that if ρ is close to k-extendible in trace distance for not-too-large
k then ρ is also close to separable in one-way LOCC distance [19]. The following is a straightforward
consequence of their result.
Theorem 5.3. Let A1 , . . . , A` be registers whose total combined dimension is D. Let ρ be ε-far from
separable in one-way LOCC distance, so that
min kρ − σ k1- LOCC ≥ ε. (5.5)
σ ∈S(A1 :···:A` )
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 74
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
Then for any δ < ε it holds that ρ is δ -far from k-extendible in trace distance, so that
min kρ − σ 0 k1 ≥ δ , (5.6)
σ 0 ∈Ek (A1 :···:A` )
provided
4`2 log D
k ≥ `+ . (5.7)
(ε − δ )2
Proof. Let σ 0 be any k-extendible state with k > `. We know from [19, Theorem 2 and Corollary 8] that
there is a separable state σ 00 ∈ S such that
s
4`2 log D
σ 0 − σ 00 1- LOCC ≤ . (5.8)
k−`
So we use this in the following chain of inequalities:
ε≤ min kρ − σ k1- LOCC (5.9)
σ ∈S(A1 :···:A` )
≤ kρ − σ 00 k1- LOCC (5.10)
≤ kρ − σ 0 k1- LOCC + kσ 0 − σ 00 k1- LOCC (5.11)
s
4`2 log D
≤ kρ − σ 0 k1 + . (5.12)
k−`
Since this bound holds for any k-extendible state, we can conclude that
s
4`2 log D
ε− ≤ min kρ − σ 0 k1 . (5.13)
k−` σ 0 ∈Ek (A1 :···:A` )
The statement of the theorem then follows by picking k large enough so that
s
4`2 log D
ε− ≥δ.
k−`
We now present our succinct quantum witness for the one-way LOCC version of the S EPARABLE
I SOMETRY O UTPUT problem.
Proposition 5.4. The one-way LOCC version of (α, β , `)-S EPARABLE I SOMETRY O UTPUT is in QMA
for all ` and all α < β 4 /16.
Proof. For convenience we write A := A1 · · · A` where the combined register A has dimension
√ D. It is
helpful to label the input and output registers of U as U : S → A. Let ε > 0 be such that α < (β − ε)2 /4.
The verifier witnessing membership of the problem in QMA is as follows:
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 75
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
1. Receive k ` + 1 registers from the prover labeled S and Aij where Aij has the same size as Ai for
i = 1, . . . , ` and j = 1, . . . , k and
4`2 log D
k = `+ . (5.14)
ε2
Apply U to register S to obtain register A := A1 , . . . , A` .
2. Perform ` permutation tests: one for each group (Ai , A1i , . . . , Aki ) of k + 1 registers. Accept if and
only if all permutation tests pass.
In what follows we use the shorthand A j := A1j · · · A`j for each j ∈ {1, . . . , k}.
Suppose first that U is a yes-instance of the problem. We show that there exists a state √ ρSA1 ···Ak of the
k ` + 1 registers SA1 · · · Ak that causes the verifier to accept with probability at least 1 − α. To this end
we define the following symbols:
1. Let σA be a separable state and ρS be a state of register S such that
kUρSU ∗ − σA k1 ≤ α , (5.15)
as promised in (5.1).
2. Let σAA1 ···Ak be a (k + 1)-extension of σA in registers AA1 · · · Ak . It is important that this (k + 1)-
extension be taken as a convex combination of pure states as in (5.4), so that it would be accepted
by the permutation test with probability one.
3. Let Û : SW → A denote the unitary circuit that implements U when the workspace register W is
initialized to |0i.
By the preservation of subsystem fidelity [51, Lemma 7.2] there exists a state ρSA1 ···Ak of registers
SA1 · · · Ak consistent with ρS such that
F (Û ∗ ⊗ IA1 ···Ak )σAA1 ···Ak (Û ⊗ IA1 ···Ak ), ρSA1 ···Ak ⊗ |0ih0|W = F Û ∗ σAÛ, ρS ⊗ |0ih0|W .
(5.16)
Let us argue that this state ρSA1 ···Ak is our desired state. It follows from (2.9), (5.15), and unitary invariance
of fidelity that
1 − α ≤ F σA , Û(ρS ⊗ |0ih0|W )Û ∗
(5.17)
∗
= F Û σAÛ, ρS ⊗ |0ih0|W . (5.18)
Applying the above and (2.9) to the right side of (5.16), we find that the quantity in (5.16) is at least
1 − Û ∗ σAÛ − ρS ⊗ |0ih0|W 1
≥ 1−α . (5.19)
Applying (2.9) to the left side of (5.16), we find that the quantity in (5.16) is at most
1 2
1− (Û ∗ ⊗ IA1 ···Ak )σAA1 ···Ak (Û ⊗ IA1 ···Ak ) − ρSA1 ···Ak ⊗ |0ih0|W 1
. (5.20)
4
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 76
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
Combining (5.19) and (5.20) leads to the following bound:
√
kσAA1 ···Ak − (U ⊗ IA1 ···Ak )ρSA1 ···Ak (U ∗ ⊗ IA1 ···Ak )k1 ≤ 2 α . (5.21)
√
Thus, ρSA1 ···Ak is 2 α-close in trace distance to a state that is accepted by the verifier
√ with certainty. It
then follows from (2.4) that the verifier accepts ρSA1 ···Ak with probability at least 1 − α as desired.
Now suppose that U is a no-instance of the problem. By Theorem 5.3 and our choice of k we have
that
min min kUρSU ∗ − σA k1 ≥ β − ε . (5.22)
ρS σA ∈Ek (A1 :···:A` )
We claim that an upper bound on the probability with which all the permutation tests pass is given by the
maximum fidelity of UρSU ∗ with a k-extendible state:
Pr[all pass] ≤ max max F(UρSU ∗ , σA ) . (5.23)
ρS σA ∈Ek
It follows
√ from (2.9) that this probability is at most 1 − (β − ε)2 /4. We chose ε so that the completeness
1 − α is larger than the soundness 1 − (β − ε)2 /4, from which it follows that the problem is in QMA.
We now justify the claim in (5.23) using a method similar to that in [46, Section 4]. In order to
implement the permutation tests in step 2 the verifier prepares a control register C in state
1
|permiC := √ ∑ |πiC , (5.24)
k! π∈Sk
which is a uniform superposition over all possible permutations of k elements resulting from an application
of the quantum Fourier transform [63] to the state |0iC , so that the C register requires dlog2 (k!)e qubits.
The verifier then applies the following controlled-permutation operation:
π
(UΠ )AA1 ···AkC := ∑ WAA1 ···Ak ⊗ |πihπ|C , (5.25)
π∈Sk
where WAA π
1 ···Ak is a unitary operation corresponding to permutation π. The verifier finally applies an
inverse quantum Fourier transform to C, measures it in the computational basis, and accepts if the
measurement outcomes are all zeros. Letting |ψiRSA1 ···Ak be a purification of the prover’s input, we can
write the maximum acceptance probability of this proof system as follows:
2
max h0|C QFTC−1 (UΠ )AA1 ···AkCUS→A |ψiRSA1 ···Ak |permiC 2
|ψiRSA1 ···Ak
2
= max h0|C hφ |RAA1 ···Ak QFTC−1 (UΠ )AA1 ···AkCUS→A |ψiRSA1 ···Ak |permiC 2 . (5.26)
|ψiRSA1 ···Ak ,|φ iRAA1 ···Ak
We can define a channel generated by the inverse of the verifier’s circuit conditioned on accepting as
follows:
MAA1 ···Ak →AC (σAA1 ···Ak ) := TrA1 ···Ak {(UΠ )AA1 ···AkC (σAA1 ···Ak ⊗ |permihperm|C )(UΠ∗ )AA1 ···AkC } . (5.27)
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 77
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
After doing so, we can apply Uhlmann’s theorem to (5.26) to rewrite the maximum acceptance probability
as follows:
∗
max F(US→A ρSUS→A ⊗ |permihperm|C , MAA1 ···Ak →AC (σAA1 ···Ak )) . (5.28)
ρS ,σAA1 ···Ak
Since the fidelity can only increase under the discarding of the control register C,5 the maximum
acceptance probability is upper bounded by the following quantity:
∗
max F(US→A ρSUS→A , MAA1 ···Ak →A (σAA1 ···Ak )) , (5.29)
ρS ,σAA1 ···Ak
where
MAA1 ···Ak →A (σAA1 ···Ak ) = TrC {MAA1 ···Ak →AC (σAA1 ···Ak )} (5.30)
1 π π
∗
= ∑ TrA1 ···Ak WAA1 ···Ak σAA1 ···Ak WAA1 ···Ak ,
k! π∈Sk
The equation above reveals that MAA1 ···Ak →A is just the channel that applies a random permutation of
the AA1 · · · Ak systems and discards the last k systems A1 · · · Ak . Clearly, since the channel MAA1 ···Ak →A
symmetrizes the state of the systems AA1 · · · Ak , the maximum in (5.29) is achieved by a state σAA1 ···Ak for
which systems AA1 · · · Ak are permutation symmetric. Thus, by recalling the definition of k-extendibility,
we can rewrite (5.29) as the maximum k-extendible fidelity of US→A ρSUS→A ∗ :
∗ ∗
max F(US→A ρSUS→A , MAA1 ···Ak →A (σAA1 ···Ak )) = max F(US→A ρSUS→A , σA ) . (5.31)
ρS ,σAA1 ···Ak ρS ,σA ∈Ek (A1 :···:A` )
This demonstrates that the maximum k-extendible fidelity is an upper bound on the maximum acceptance
probability and completes our proof of the claim in (5.23).
5.2 Hardness for QMA
Proposition 5.5. The one-way LOCC version of (ε, 2 − ε)-B IPARTITE S EPARABLE I SOMETRY O UTPUT
is QMA-hard, even when ε decays exponentially in the input length.
Proof. This proof is almost exactly the same as the proof of Proposition 4.5. The only difference is that
here we must quantify over all states of a new input register P for each circuit. Nonetheless, we include a
full proof for completeness.
Let L be any promise problem in QMA and let {Vx }x be a family of isometric verifier circuits
witnessing this fact with completeness 1 − δ and soundness δ for sufficiently small δ to be chosen later.
Circuits in this family take the form Vx : P → DG. The input register P is supplied by the prover. The
output register D is a decision qubit indicating acceptance or rejection of x and the output register G is a
garbage register that holds the purification of D.
5 We can interpret discarding the control register as actually giving it to the prover, so that the resulting fidelity corresponds
to the maximum acceptance probability in a modified protocol in which the prover controls the inputs to C.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 78
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
In this proof we reduce the arbitrary problem L to the one-way LOCC version of (α, β )-B IPARTITE
S EPARABLE I SOMETRY O UTPUT where
√
α =2 δ, (5.32)
√
2−n/2
β = 2−2 −2 δ , (5.33)
for any desired n. The desired hardness result then follows by an appropriate choice of δ , n.
The reduction is as follows. Given an instance x of L we produce a description of the following
isometric circuit U : P → AA0 BDG:
1. Given the input register P apply the verifier circuit Vx to obtain registers DG.
2. Prepare registers AA0 in a 2n-qubit maximally entangled state such as n EPR pairs, which we denote
by |φ + i. Prepare register B in the n-qubit |0i state.
3. Perform a unitary conditional swap gate that swaps registers A0 and B when D is in the reject state
|noi and acts as the identity otherwise.
See Figure 3 for a graphical depiction of this circuit.
A'
|Φ+⟩
A
|0⟩
B
D
Prover
Input Vx
G
Figure 3: The circuit U produced by our reduction from an arbitrary problem L ∈ QMA to the one-way
LOCC version of (ε, 2 − ε)-B IPARTITE S EPARABLE I SOMETRY O UTPUT. The dashed line indicates that
the output registers are to be divided along the bipartite cut AA0 : BDG. This construction also appears in
the proof of Proposition 4.5 in the special case where the prover’s input is empty.
Suppose x is a yes-instance of L and let |ϖi be a pure state of register P that causes the verifier
to accept with high probability, meaning that the state Vx |ϖi has squared √ overlap at least 1 − δ with
|yesiD |ζ iG for some state |ζ i of register G. It follows that U|ϖi is 2 δ -close in trace distance to
|φ + iAA0 |0iB |yesiD |ζ iG , which is a product with respect to the cut AA0 : BDG, and so U is a yes-instance
of the one-way LOCC version of (α, β )-B IPARTITE S EPARABLE I SOMETRY O UTPUT.
Next, suppose that x is a no-instance √ of L. In this case for all input states ρ of register P the output
state UρU ∗ of registers AA0 BDG is 2 δ -close to a state which is in tensor product with the 2n-qubit
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 79
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
maximally entangled state |φ + i on registers AB. By contrast, for any separable state σ of registers
AA0 : BDG the reduced state TrA0 DG (σ ) of registers AB must also be separable. Thus, it suffices to exhibit
a fixed one-way LOCC measurement that successfully distinguishes any separable state of registers AB
from n EPR pairs with high probability. The existence of such a measurement was proved in Theorem 3.1.
We therefore have the following for any input state ρ of register P and any separable state σ of
registers AA0 : BDG:
kUρU ∗ − σ k1- LOCC ≥ TrA0 DG (σ ) − φAB
+ +
− φAB − TrA0 DG (UρU ∗ ) 1- LOCC (5.34)
√ 1- LOCC
≥ 2 − 22−n/2 − 2 δ , (5.35)
from which it follows that U is a no-instance of the one-way LOCC version of (α, β )-B IPARTITE
S EPARABLE I SOMETRY O UTPUT.
6 S EPARABLE I SOMETRY O UTPUT is QMA(2)-complete
In Section 5 we showed that the one-way LOCC version of the S EPARABLE I SOMETRY O UTPUT problem
is QMA-complete. By contrast, in this section we show that the trace distance version of this problem
(and some closely related variants of it) are QMA(2)-complete.
We begin by restricting attention to the problem of determining whether an isometry U described by
a quantum circuit can be made to produce a pure product output state from a pure input state.
Problem 6.1 ((α, β , `)-P URE P RODUCT I SOMETRY O UTPUT).
Input: A description of a quantum circuit that implements an isometry U with an `-partite output
system A1 · · · A` .
Yes: There is an input state |ψi such that U|ψi is α-close to a pure product state:
min min kUψU ∗ − φ1 ⊗ · · · ⊗ φ` k1 ≤ α . (6.1)
|ψi |φ1 i,...,|φ` i
No: For all input states |ψi it holds that U|ψi is β -far from a pure product state:
min min kUψU ∗ − φ1 ⊗ · · · ⊗ φ` k1 ≥ β . (6.2)
|ψi |φ1 i,...,|φ` i
The main result of this section is the following theorem:
Theorem 6.2 (P URE P RODUCT I SOMETRY O UTPUT is QMA(2)-complete). The following hold:
1. (α, β , `)-P URE P RODUCT I SOMETRY O UTPUT is in QMA(2) for all ` and all α < β .
2. (ε, 2 − ε)-B IPARTITE P URE P RODUCT I SOMETRY O UTPUT is QMA(2)-hard, even when ε decays
exponentially in the input length.
Thus, the problem is QMA(2)-complete for all ` ≥ 2 and all 0 < α < β < 2.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 80
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
6.1 Containment in QMA(2)
Proposition 6.3. (α, β , `)-P URE P RODUCT I SOMETRY O UTPUT is in QMA(2) for all ` and all α < β .
Proof. We prove that the problem is in QMA(` + 1), from which it follows that the problem is also in
QMA(2) via the main result of [44]. The verifier witnessing membership of the problem in QMA(` + 1)
is as follows:
1. Receive an input state |ψi from one of the provers and a candidate product state |φ1 i ⊗ · · · ⊗ |φ` i
from the remaining ` provers.
2. Apply U to the input. Perform a swap test between U|ψi and |φ1 i ⊗ · · · ⊗ |φ` i. Accept if and only
if the swap test passes.
If U is a yes-instance then the provers can cause the verifier to accept with probability at least 1 − α 2 /8
by an appropriate choice of states |ψi, |φ1 i, . . . , |φ` i. It follows from a standard convexity argument that
the provers achieve their maximum probability of success for the swap test when they each send the
verifier a pure state, so we assume that they do so without loss of generality. So if U is a no-instance then
the verifier will accept with probability at most 1 − β 2 /8 regardless of which states the provers send to
the verifier. As α < β , there is a gap between completeness and soundness for this verifier.
6.2 Hardness for QMA(2)
Proposition 6.4. (ε, 2 − ε)-B IPARTITE P URE P RODUCT I SOMETRY O UTPUT is QMA(2)-hard, even
when ε decays exponentially in the input length.
Proof. Let L be any promise problem in QMA(2) and let {Vx }x be a family of unitary verifier circuits
(indexed by instances x of L) witnessing this fact with completeness 1 − δ and soundness δ for sufficiently
small δ to be chosen later. Circuits in this family take the form Vx : ABW → DG. Such a verifier circuit Vx
is depicted in Figure 4(a). The input registers A, B are supplied by the two provers and the input register
W is a workspace register initialized to the |0i state. The output register D is a decision qubit indicating
acceptance or rejection of x and the output register G is a garbage register that consists of the remaining
qubits upon which Vx acts.
In this proof we reduce the arbitrary problem L to (α, β )-B IPARTITE P URE P RODUCT I SOMETRY
O UTPUT where
√
α =2 δ, (6.3)
r √ 2
β = 2 1− δ + 2−n/2 , (6.4)
for any desired n. The desired hardness result then follows by an appropriate choice of δ , n.
The reduction is as follows. Given an instance x of L we produce a description of the following
isometric circuit U : G → ABCC0W :
1. Given the input register G, prepare a qubit D in the accept state |yesi and apply the inverse circuit
Vx∗ to obtain registers ABW .
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 81
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
C
|Φ+⟩
C'
Prover 1 A D |1⟩ D A
Input
Prover 2 B Vx Vx† B
Input
G W
G
|0⟩ W
(a) A QMA(2) verifier. (b) The circuit produced by our reduction.
Figure 4: (a) A unitary verifier circuit Vx for an arbitrary verifier witnessing membership of L in QMA(2)
on input x. (b) The circuit U produced by our reduction. Dashed lines indicate that the output registers
are to be divided along the bipartite cut A : BCC0W .
2. Prepare registers CC0 in a 2n-qubit maximally entangled state such as n EPR pairs, which we
denote by |φ + i.
3. Perform a unitary conditional swap gate that swaps registers A and C when W is orthogonal to the
|0i state and acts as the identity otherwise. (Here we implicitly pad the register A with |0i qubits so
as to have the same size as C.)
See Figure 4(b) for a graphical depiction of this circuit.
Let us argue that this construction has the claimed properties. Suppose first that x is a yes-instance
of L and let |φ iA |ϕiB be a pure product state of registers AB that causes the verifier to accept with high
probability. That is, the state Vx |φ iA |ϕiB |0i
√ W has squared overlap at least 1 − δ with |yesi|ψi for some
state |ψi of register G. Thus U|ψi is 2 δ -close in trace distance to |φ iA |ϕiB |φ + iCC0 |0iW , which is
a product with respect to the cut A : BCC0W , and so U is a yes-instance of (α, β )-B IPARTITE P URE
P RODUCT I SOMETRY O UTPUT.
Next, suppose that x is a no-instance of L. Fix any pure input state |ψi for register G and observe that
U|ψi = Π0U|ψi + (I − Π0 )U|ψi (6.5)
where Π0 = |0ih0|W denotes the projection onto the |0i state for register W . From the definition of the
circuit U it is clear that we may write
Π0U|ψi = Π0 (Vx∗ |yesi|ψi) ⊗ |φ + iCC0 (6.6)
+
= |ζAB i|0iW |φ iCC0 (6.7)
(I − Π0 )U|ψi = SwapAC0 (I − Π0 )(Vx∗ |yesi|ψi) ⊗ |φ + iCC0
(6.8)
= |ξBC0W i|φ + iAC (6.9)
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 82
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
for some choice of subnormalized pure states |ζAB i and |ξBC0W i of registers AB and BC0W , respectively.
Then for any pure product state |φ i of registers A : BCC0W it holds that
|hφ |U|ψi| ≤ max hφ 0 |Π0U|ψi + max hφ 00 |(I − Π0 )U|ψi (6.10)
|φ 0 i |φ 00 i
where the maxima on the right side are also over product states |φ 0 i, |φ 00 i of registers A : BCC0W .
First, let us bound the maximum over |φ 0 i. It is clear from (6.7) that this maximum is achieved by
some |φ 0 i of the form
|φ 0 i = |φ iA |ϕiB |0iW |φ + iCC0 , (6.11)
in which case we have
√
hφ 0 |Π0U|ψi = |hφ |A hϕ|B h0|W Vx∗ |yesi|ψi| ≤ δ (6.12)
where the inequality follows from the assumption that x is a no-instance of L.
Next, let us bound the maximum over |φ 00 i. Since (I − Π0 )U|ψi is maximally entangled on registers
AC, its squared inner product with any product state |φ 00 i is at most 2−n as observed in (3.1) of Section 3.
We have thus shown that
√ 2
max max |hφ |U|ψi|2 ≤ δ + 2−n/2 (6.13)
|ψi product |φ i
and consequently r √ 2
∗ −n/2
min min kUψU − φ k1 ≥ 2 1− δ +2 . (6.14)
|ψi product |φ i
We have thus shown that U is a no-instance of (α, β )-B IPARTITE P URE P RODUCT I SOMETRY O UTPUT.
6.3 Equivalence of separability testing problems
We also consider two variants of P URE P RODUCT I SOMETRY O UTPUT (Problem 6.1) in which the task
is to determine whether an isometry U can be made to produce a (not necessarily pure) product state or a
separable state. Whereas Problem 6.1 restricts attention only to pure input states, in the following variants
of the problem we also allow arbitrary mixed state inputs. Formal specifications of these two variants of
Problem 6.1 are given below.
Problem 6.5 ((α, β , `)-P RODUCT I SOMETRY O UTPUT).
Input: A description of a quantum circuit that implements an isometry U with an `-partite output
system A1 · · · A` .
Yes: There is an input state ρ such that UρU ∗ is α-close to a product state:
min min kUρU ∗ − σ1 ⊗ · · · ⊗ σ` k1 ≤ α . (6.15)
ρ σ1 ,...,σ`
No: For all input states ρ it holds that UρU ∗ is β -far from a product state:
min min kUρU ∗ − σ1 ⊗ · · · ⊗ σ` k1 ≥ β . (6.16)
ρ σ1 ,...,σ`
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 83
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
Problem 6.6 ((α, β , `)-S EPARABLE I SOMETRY O UTPUT).
Input: A description of a quantum circuit that implements an isometry U with an `-partite output
system A1 · · · A` .
Yes: There is an input state ρ such that UρU ∗ is α-close to a separable state:
min min kUρU ∗ − σ k1 ≤ α . (6.17)
ρ σ ∈S(A1 :···:A` )
No: For all input states ρ it holds that UρU ∗ is β -far from separable:
min min kUρU ∗ − σ k1 ≥ β . (6.18)
ρ σ ∈S(A1 :···:A` )
We now argue that, for each `, these problems are equivalent to one another for a wide range of
choices of (α, β ). These equivalences are corollaries of the following proposition, which relates minimal
distance from separable to minimal distance from pure product.
Proposition 6.7 (Separable-to-pure product reduction). Let U be an isometry with an `-partite output
system A1 · · · A` and suppose that there is an input state ρ such that UρU ∗ is δ -close to some separable
state σ ∈ S(A1 : · · · : A` ):
kUρU ∗ − σ k1 ≤ δ . (6.19)
√
Then there is a pure input state |ψi such that UψU ∗ is 4 δ -close to some pure product state |φ1 i ⊗ · · · ⊗
|φ` i: √
kUψU ∗ − φ1 ⊗ · · · ⊗ φ` k1 ≤ 4 δ . (6.20)
Proof. Let
σ = ∑ px φ1x ⊗ · · · ⊗ φ`x (6.21)
x
be a decomposition of σ as a probabilistic mixture of pure product states and let
√
|ζ i = ∑ px |xiR ⊗ |φ1x i ⊗ · · · ⊗ |φ`x i (6.22)
x
be a purification of σ on registers RA1 · · · A` .
Let S denote the input register for U. It follows from (2.9) and Uhlmann’s Theorem that there is a
purification |ψi of ρ on registers RS with
√
kUψU ∗ − ζ k1 ≤ 2 δ . (6.23)
Write |ψi as
√
|ψi = ∑ qx |xiR ⊗ |ψ x i (6.24)
x
for some probability vector q and states {|ψ x i}x (not necessarily orthogonal). Apply a dephasing channel
in the basis {|xi}x on register R and use contractivity of trace norm under quantum channels to obtain
kUψU ∗ − ζ k1 ≥ ∑ qx |xihx| ⊗Uψ xU ∗ − ∑ px |xihx| ⊗ φ1x ⊗ · · · ⊗ φ`x . (6.25)
x x 1
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 84
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
Combining this bound with the triangle inequality, we have
∑ px kUψ xU ∗ − φ1x ⊗ · · · ⊗ φ`x k1 (6.26)
x
= ∑ px |xihx| ⊗ (Uψ xU ∗ − φ1x ⊗ · · · ⊗ φ`x ) (6.27)
x 1
≤ ∑ qx |xihx| ⊗Uψ xU ∗ − ∑ px |xihx| ⊗Uψ xU ∗ (6.28)
x x 1
+ ∑ qx |xihx| ⊗Uψ xU ∗ − ∑ px |xihx| ⊗ φ1x ⊗ · · · ⊗ φ`x (6.29)
x x 1
√
≤ 4 δ. (6.30)
Since this inequality holds for a convex combination over terms indexed by x, it must also hold for at
least one choice of ψ x , φ1x , . . . , φ`x .
Corollary 6.8 (Equivalence of problems). The following hold for all ` and all α < β :
1. Both (α, β , `)-P RODUCT
√ I SOMETRY O UTPUT and (α, β , `)-S EPARABLE I SOMETRY O UTPUT
trivially reduce to (4 α, β , `)-P URE P RODUCT I SOMETRY O UTPUT.
2. Conversely, (α, β , `)-P URE P RODUCT I SOMETRY O UTPUT trivially reduces to both (α, β 2 /16, `)-
P RODUCT I SOMETRY O UTPUT and (α, β 2 /16, `)-S EPARABLE I SOMETRY O UTPUT.
Proof. By definition, no-instances of both (α, β , `)-P RODUCT
√ I SOMETRY O UTPUT and (α, β , `)-S EP -
ARABLE I SOMETRY O UTPUT are also no-instances of (4 α, β , `)-P URE P RODUCT I SOMETRY O UT-
PUT . By Proposition 6.7, yes-instances of both (α, β , `)-P RODUCT I SOMETRY O UTPUT and (α, β , `)-
√
S EPARABLE I SOMETRY O UTPUT are also yes-instances of (4 α, β , `)-P URE P RODUCT I SOMETRY
O UTPUT.
By definition, yes-instances of (α, β , `)-P URE P RODUCT I SOMETRY O UTPUT are also yes-instances
of both (α, β 2 /16, `)-P RODUCT I SOMETRY O UTPUT and (α, β 2 /16, `)-S EPARABLE I SOMETRY O UT-
PUT . By the contrapositive of Proposition 6.7, no-instances of (α, β , `)-P URE P RODUCT I SOMETRY
O UTPUT are also no-instances of both (α, β 2 /16, `)-P RODUCT I SOMETRY O UTPUT and (α, β 2 /16, `)-
S EPARABLE I SOMETRY O UTPUT.
Corollary 6.9 (QMA(2)-completeness of equivalent problems). The following hold:
1. Problems 6.5 and 6.6 are in QMA(2) for all ` and all α < β 2 /16.
2. These two problems are QMA(2)-hard for all ` ≥ 2 and all (α, β ) = (ε, 1/4 − ε), even when ε
decays exponentially in the input length.
Thus, these two problems are QMA(2)-complete for all ` ≥ 2 if both 0 < α < β 2 /16 and β < 1/4.
Remark 6.10. The fact that Problems 6.5 and 6.6 are QMA(2)-hard only for (α, β ) = (ε, 1/4 − ε)
instead of the best possible (ε, 2 − ε) is an artifact of Proposition 6.7. The best possible
√hardness
√ result
would be obtained if the bound in Proposition 6.7 could somehow be improved from 4 δ to 2δ .
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 85
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
7 P RODUCT S TATE is QSZK-complete
In this section we prove QSZK-completeness of the problem of determining whether the state prepared
by a given quantum circuit is close to a product state.
Problem 7.1 ((α, β )-P RODUCT S TATE).
Input: A description of a quantum circuit that prepares an `-partite mixed state ρ.
Yes: ρ is α-close to a product state:
min min kρ − σ1 ⊗ · · · ⊗ σ` k1 ≤ α. (7.1)
ρ σ1 ,...,σ`
No: ρ is β -far from product:
min min kρ − σ1 ⊗ · · · ⊗ σ` k1 ≥ β . (7.2)
ρ σ1 ,...,σ`
The main result of this section is the following theorem:
Theorem 7.2 (P RODUCT S TATE is QSZK-complete). The following hold:
1. (α, β , `)-P RODUCT S TATE is in QSZK for all ` and all α < β 2 /(` + 1).
2. (ε, 2 − ε)-B IPARTITE P RODUCT S TATE is QSZK-hard, even when ε decays exponentially in the
input length.
Thus, the problem is QSZK-complete for all ` ≥ 2 and all 0 < α < β 2 /(` + 1) and β < 2.
This result is proven by establishing equivalence between the P RODUCT S TATE problem and the
Q UANTUM S TATE S IMILARITY problem, which is defined as follows:
Problem 7.3 ((α, β )-Q UANTUM S TATE S IMILARITY).
Input: Descriptions of two quantum circuits that prepare mixed states ρ0 , ρ1 .
Yes: ρ0 and ρ1 are α-close: kρ0 − ρ1 k1 ≤ α.
No: ρ0 and ρ1 are β -far apart: kρ0 − ρ1 k1 ≥ β .
Problem 7.3 is known to be QSZK-complete. Specifically, (α, β )-Q UANTUM S TATE S IMILARITY is
contained in QSZK for all α < β 2 and (ε, 2 − ε)-Q UANTUM S TATE S IMILARITY is QSZK-hard, even
when ε decays exponentially in the input length [70, 74]. Thus, Theorem 7.2 can be proved by reducing
Problems 7.1 and 7.3 to each other.
7.1 Containment in QSZK
Our reduction from P RODUCT S TATE to Q UANTUM S TATE S IMILARITY employs the fact that if ρ is
close to a product state then ρ is also close to the product of its reduced states. We are not aware of an
explicit proof of this fact in the literature, so we provide a proof.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 86
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
Lemma 7.4 (Approximation by a product of reduced states). Let ρ be a state of registers A1 , . . . , A` and
suppose there is a product state σ1 ⊗ · · · ⊗ σ` with
kρ − σ1 ⊗ · · · ⊗ σ` k1 ≤ α . (7.3)
Then it follows that
kρ − ρA1 ⊗ · · · ⊗ ρA` k1 ≤ (` + 1)α (7.4)
where ρAi denotes the reduced state of ρ on register Ai for i = 1, . . . , `.
Proof. By the triangle inequality we have
kρ − ρA1 ⊗ · · · ⊗ ρA` k1 ≤ kρ − σ1 ⊗ · · · ⊗ σ` k1 + kσ1 ⊗ · · · ⊗ σ` − ρA1 ⊗ · · · ⊗ ρA` k1 . (7.5)
By assumption the first term on the right is no larger than α. For the second term, another application of
the triangle inequality yields
kσ1 ⊗ · · · ⊗ σ` − ρA1 ⊗ · · · ⊗ ρA` k1 (7.6)
≤ kσ1 ⊗ · · · ⊗ σ` − ρA1 ⊗ σ2 ⊗ · · · ⊗ σ` k1 + kρA1 ⊗ σ2 ⊗ · · · ⊗ σ` − ρA1 ⊗ · · · ⊗ ρA` k1 (7.7)
= kσ1 − ρA1 k1 + kσ2 ⊗ · · · ⊗ σ` − ρA2 ⊗ · · · ⊗ ρA` k1 . (7.8)
By the contractivity of the trace norm under partial trace we have
kσi − ρAi k1 ≤ kσ1 ⊗ · · · ⊗ σ` − ρ k1 ≤ α (7.9)
for each i = 1, . . . , `. The lemma then follows by applying (7.6)-(7.8) inductively.
We are now ready to reduce P RODUCT S TATE to Q UANTUM S TATE S IMILARITY.
Proposition 7.5. (α, β , `)-P RODUCT S TATE is in QSZK for all ` and all α < β 2 /(` + 1).
Proof. We reduce (α, β , `)-P RODUCT S TATE to ((` + 1)α, β )-Q UANTUM S TATE S IMILARITY. It then
follows that (α, β , `)-P RODUCT S TATE is in QSZK whenever α < β 2 /(` + 1) as desired.
The reduction is as follows: given an instance ρ of (α, β , `)-P RODUCT S TATE, one can construct
circuits that prepare states
ρ0 = ρ , (7.10)
ρ1 = ρA1 ⊗ · · · ⊗ ρA` . (7.11)
Specifically, we use the original circuit to make ρ0 = ρ, and we use the original circuit ` times to make
` copies of ρ and then trace over the appropriate subsystems to make ρ1 = ρA1 ⊗ · · · ⊗ ρA` . If ρ is a
yes-instance of (α, β , `)-P RODUCT S TATE then by Lemma 7.4 we have that kρ0 − ρ1 k1 ≤ (` + 1)α.
Conversely, if ρ is a no-instance of (α, β , `)-P RODUCT S TATE then it must be that kρ0 − ρ1 k1 ≥ β .
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 87
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
7.2 Hardness for QSZK
Proposition 7.6. (ε, 2 − ε)-B IPARTITE P RODUCT S TATE is QSZK-hard, even when ε decays exponen-
tially in the input length.
Proof. We reduce (δ , 2 − δ )-Q UANTUM S TATE S IMILARITY to (α, β )-B IPARTITE P RODUCT S TATE for
α = nδ /2 , (7.12)
β = 2 − 2−Ω(n) , (7.13)
for any desired n. The desired hardness result then follows by an appropriate choice of δ , n.
The reduction is as follows. Given an instance (ρ0 , ρ1 ) of Q UANTUM S TATE S IMILARITY we
construct a circuit that prepares n copies of the bipartite state ωA:S of registers AS given by
1 1
ωA:S = |0ih0|A ⊗ ρ0 + |1ih1|A ⊗ ρ1 . (7.14)
2 2
Figure 5 illustrates an isometric circuit for preparing (a purification of) a single copy of ωA:S .
A
|Φ+⟩
B
R
|0⟩ Uρ i
S
Figure 5: The isometric circuit that prepares a purification of ωA:S . This circuit is produced by our
reduction from Q UANTUM S TATE S IMILARITY to B IPARTITE P RODUCT S TATE. Here Uρi are the unitary
circuits that prepare ρi = TrR (Uρi |0ih0|Uρ∗i ) in register S for i ∈ {0, 1}. This same circuit is also produced
by the reduction of [46] from Q UANTUM S TATE D ISTINGUISHABILITY to the one-way LOCC version
of S EPARABLE S TATE, except that reduction discards register S instead of R.
If (ρ0 , ρ1 ) is a yes-instance of (δ , 2 − δ )-Q UANTUM S TATE S IMILARITY then the trace distance
between ωA:S and the product state
1
σA:S = (|0ih0| + |1ih1|)A ⊗ ρ0 (7.15)
2
is at most (1/2)kρ0 − ρ1 k1 ≤ δ /2. It then follows from [70, Lemma 8] that
⊗n ⊗n
ωA:S − σA:S 1
≤ nδ /2 . (7.16)
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 88
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
⊗n ⊗n
As σA:S is a product relative to the bipartite cut A1 · · · An : S1 · · · Sn it must be that ωA:S is a yes-instance of
(α, β )-B IPARTITE P RODUCT S TATE relative to this cut.
By contrast, if (ρ0 , ρ1 ) is a no-instance of (δ , 2 − δ )-Q UANTUM S TATE S IMILARITY then ωA:S is
almost perfectly correlated on A : S and hence far from a product. Recall that trace distance is equal to
the maximum probability of distinguishing states over all possible measurements, so we can lower bound
the distance to the nearest product state by considering a particular protocol to distinguish ωA:S from any
product state. In this protocol, we begin by measuring the first qubit (register A) in the computational
basis and by performing the Helstrom measurement {Π0 , Π1 } on the second system, storing the two
measurement outcomes in classical registers.
It is straightforward to calculate the state ωA:S 0
0 that results after applying the protocol above to the
state ωA:S :
0 1 1 1 1
ωA:S 0 = Tr{Π0 ρ0 }|00ih00| + Tr{Π1 ρ1 }|11ih11| + Tr{Π0 ρ1 }|10ih10| + Tr{Π1 ρ0 }|01ih01| .
2 2 2 2
(7.17)
Recall that the Helstrom measurement distinguishes two states ρ0 and ρ1 with the following success
probability:
1 1 1 1
Tr{Π0 ρ0 } + Tr{Π1 ρ1 } = 1 + kρ0 − ρ1 k1 , (7.18)
2 2 2 2
and the following error probability:
1 1 1 1
Tr{Π0 ρ1 } + Tr{Π1 ρ0 } = 1 − kρ0 − ρ1 k1 . (7.19)
2 2 2 2
0
Using this fact, it is straightforward to establish that the trace distance between ωA:S 0 and the perfectly
correlated state ΦA:S0 , defined as
1
ΦA:S0 := (|00ih00| + |11ih11|) , (7.20)
2
is no larger than
1 δ
1 − kρ0 − ρ1 k1 ≤ . (7.21)
2 2
For a product state, the two measurement outcomes must be uncorrelated, and so we can write the
result of applying the above protocol to any product state using the probability p of measuring |0ih0| and
the probability q of measuring Π0 :
σ p,q = pq|00ih00| + p(1 − q)|01ih01| + q(1 − p)|10ih10| + (1 − p)(1 − q)|11ih11| . (7.22)
From the monotonicity of trace distance under quantum operations, it follows that
0
min kσ0 ⊗ σ1 − ωA:S k1 ≥ minkσ p,q − ωA:S k1 . (7.23)
σ0 ,σ1 p,q
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 89
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
Due to symmetry, we can take p ≤ 1/2 without loss of generality. We can then bound the minimum
0 :
distance of σ p,q to ωA:S
0 0
minkσ p,q − ωA:S k1 ≥ minkσ p,q − ΦA:S k1 − kΦA:S − ωA:S k1 (7.24)
p,q p,q
δ
≥ kσ p,q − ΦA:S k1 − (7.25)
2
1 1 δ
= − pq + − (1 − p)(1 − q) + |p(1 − q)| + |q(1 − p)| − (7.26)
2 2 2
1 1 δ
= − pq + − (1 − p)(1 − q) + p(1 − q) + q(1 − p) − (7.27)
2 2 2
1 δ
≥ − pq + p(1 − q) + q(1 − p) − (7.28)
2 2
1 δ
≥ + p(1 − q) − (7.29)
2 2
1−δ
≥ , (7.30)
2
where the first line follows from the triangle inequality, and the fourth through last lines follow from
the fact that 0 ≤ p ≤ 1/2 and 0 ≤ q ≤ 1. It then follows from [70, Lemma 8] that for suitably high n
⊗n
we have that ωA:S is at least 2 − 2−Ω(n) -far from any product state and so this state is a no-instance of
(α, β )-B IPARTITE P RODUCT S TATE as desired.
Remark 7.7. Theorem 7.2 provides a different proof that the promise problem E RROR C ORRECTABILITY
of [42] is QSZK-complete (with a proof preceding this one given in [47]). Indeed, E RROR C ORRECTABIL -
ITY is the task of deciding whether it is possible to decode a maximally entangled state from systems R
and B when a unitary specified as a quantum circuit acts on systems R, B, and E, such that systems R and
B are initialized to the maximally entangled state and system E is initialized to the all-zero state. In this
problem, there is a promise that it is either possible to decode maximal entanglement (approximately) or
impossible to do so. Due to the “decoupling theorem” often used in quantum information theory [45], the
question of whether it is possible to decode maximal entanglement between systems R and B is equivalent
to the question of whether systems R and E are in a product state. Thus, it follows from Theorem 7.2
that E RROR C ORRECTABILITY and P RODUCT S TATE are reducible to each another and that E RROR
C ORRECTABILITY is QSZK-complete.
8 A short quantum game for the one-way LOCC version of S EPARABLE
S TATE
In [46] it was shown that the one-way LOCC version of the S EPARABLE S TATE problem admits a
two-message quantum interactive proof, so that the problem lies inside QIP(2). In this section we
show that this problem also admits a short quantum game, putting it inside SQG, too. As mentioned in
Section 1.1, this result is not a complexity-theoretic improvement over prior work. But it is interesting
that the one-way LOCC version of S EPARABLE S TATE admits a natural, single-message quantum proof
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 90
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
provided that the verifier has help from a second competing prover. Recall the definition of the one-way
LOCC version of the S EPARABLE S TATE problem [46]:
Problem 8.1 ((α, β , `)-S EPARABLE S TATE, one-way LOCC version).
Input: A description of a quantum circuit that prepares a state ρ of registers A1 · · · A` .
Yes: ρ is α-close in trace distance to a separable state:
min kρ − σ k1 ≤ α . (8.1)
σ ∈S(A1 :···:A` )
No: ρ is β -far in one-way LOCC distance from separable:
min kρ − σ k1- LOCC ≥ β . (8.2)
σ ∈S(A1 :···:A` )
The main result of this section is the following proposition:
Proposition 8.2. The one-way LOCC version of (α, β , `)-S EPARABLE S TATE is in SQG for all ` and all
α < β.
Proof. Suppose that registers A1 · · · A` have combined total dimension D. The verifier witnessing mem-
bership of the problem in SQG is described as follows:
1. Receive k ` registers from the yes-prover labeled Aij for i = 1, . . . , ` and j = 1, . . . , k where
16`2 log D
k = `+ . (8.3)
(β − α)2
(Intuitively, these registers contain a purported k-extension of ρ.)
2. Perform ` permutation tests: one for each group (A1i , . . . , Aki ) of k registers. Reject immediately if
any test fails. Discard all registers except A11 , . . . , A1` , letting σ denote the reduced state of these
remaining registers.
3. Prepare a copy of ρ using the input circuit and choose a random bit b ∈ {0, 1}. If b = 0 then send
ρ to the no-prover. Otherwise, send σ to the no-prover. (Intuitively, the no-prover is challenged to
identify whether the state he receives from the verifier is ρ or σ .)
4. Receive a single bit b0 from the no-prover. Reject if and only if b0 = b.
Let us argue that this protocol is correct. For yes-instances an optimal strategy for the yes-prover is to
select a separable state σ that is α-close in trace distance to ρ and send the verifier a k-extension of σ .
As σ is separable, such an extension must exist for every choice of k and so the permutation test passes
with certainty. The no-prover is then faced with the task of distinguishing σ from ρ, which he can do
with probability no larger than 1/2 + α/4, implying that the verifier accepts with probability at least
1/2 − α/4.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 91
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
For no-instances an optimal strategy for the no-prover is to perform a measurement that distinguishes
ρ from the convex set Ek of k-extendible states with probability at least
1 1
+ min kρ − σ k1 . (8.4)
2 4 σ ∈Ek
(The existence of such a measurement was first shown in [40] and a simple proof can be found in Yu,
Duan, and Xu [80].)
To see that the yes-prover cannot win, observe that if the permutation test of step 2 passes then the
state of all k ` registers Aij received from the yes-prover is projected into the symmetric subspaces of
(A1i , . . . , Aki ) for each i = 1, . . . , `. The set of such states is contained in the set Ek of k-extendible states,
and we know from Theorem 5.3 and our choice of k that
β +α
min kρ − σ k1 ≥ . (8.5)
σ ∈Ek 2
Thus, the no-prover convinces the verifier to reject with probability at least 1/2 + (β + α)/8, implying
that the verifier accepts with probability at most 1/2 − (β + α)/8. This protocol witnesses membership
in SQG whenever 1/2 − α/4 > 1/2 − (β + α)/8, which occurs whenever α < β .
9 Operational interpretations of geometric measures of entanglement
Our work has a close connection to several entanglement measures known collectively as the geometric
measure of entanglement—see [75, 23] and references therein. This is also the case with the work
in [44] and we comment briefly on this connection. The original definition of the geometric measure of
entanglement for a pure state |ψi of registers AB is defined as the maximum squared overlap with a pure
product state:
max |hφ ⊗ ϕ|ψi|2 . (9.1)
|φ iA ,|ϕiB
This quantity has an operational interpretation as the maximum probability with which the state |ψi
would pass a test for being a pure product state. By taking the negative logarithm one obtains an entropic-
like quantity that is equal to the geometric measure of entanglement and satisfies a list of desirable
requirements that any entanglement measure ought to meet.
If one has a promise that the quantity (9.1) is larger than 1 − ε or smaller than ε (as in the definition
of the P URE P RODUCT S TATE problem, Problem 4.1) then the product test can be used to determine
which is the case. However, this observation does not directly give an operational interpretation of the
quantity in (9.1). Rather, an operational interpretation of (9.1) is given by the quantum interactive proof
in [46] for S EPARABLE S TATE, whose maximum acceptance probability for a given state ρ of registers
AB is given by
max F(ρAB , σAB ) , (9.2)
σ ∈S(A:B)
of which (9.1) is a special case when ρAB is pure. (This bound holds in the limit of large k, the number of
registers sent by the prover in a purported k-extension of ρ.) The operational interpretation for (9.2) is
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 92
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
that it is the maximum probability with which a prover could convince a verifier that a state ρ is separable
by acting on a purification of ρ.
Our work has also unveiled and provided operational interpretations for other quantifiers of entangle-
ment that fall within the geometric class. Indeed, the maximum acceptance probability of our quantum
witness for the one-way LOCC version of S EPARABLE I SOMETRY O UTPUT is bounded by
max F(U(ρS ⊗ |0ih0|)U † , σAB ) , (9.3)
ρ, σAB ∈S
again a bound that holds in the large k limit. Clearly, this quantity is related to the so-called “entangling
power” of the unitary U [81], that is, its ability to take a product state input to an entangled output no
matter what the input is. Furthermore, the quantum interactive proof for the one-way LOCC version of
S EPARABLE C HANNEL O UTPUT given in [46] has the following upper bound on its maximum acceptance
probability:
max F(NS→AB (ρS ), σAB ) , (9.4)
ρ, σAB ∈S
where NS→AB is a quantum channel with input system S and output systems AB. Again, this bound holds
in the limit of large k. The above measure is related to the entangling capabilities of a quantum channel
no matter what the input is, and the quantum interactive proof provides an operational interpretation for
the above quantity as well.
10 Discussion: Does nondeterminism trump one-way LOCC distance?
An interesting and surprising comparison emerges in light of the combined results of the present paper
with those of [46]. For isometric channels, it is no surprise that detecting product outputs is easier than
detecting separable outputs when no-instances in the former problem are promised to be far from a
product in one-way LOCC distance instead of trace distance: these problems are complete for QMA and
QMA(2), respectively. For states, however, detecting separability is harder than detecting productness,
even when no-instances in the former problem are promised to be far from separable in one-way LOCC
distance: the former is both QSZK- and NP-hard while the latter is QSZK-complete.
An anonymous reviewer suggests one possible explanation for this phenomenon: the added difficulty
of nondeterminism trumps the reduced difficulty of the one-way LOCC promise. Specifically, detecting
entangled or correlated isometry outputs is inherently “nondeterministic,” as one must guess the proper
input to the isometry. Similarly, detecting separable states is also “nondeterministic,” as one must guess a
mixture of product states. By contrast, product states have no nondeterminism of this form and so we can
expect the corresponding detection problem to be easier, even when one demands a lower error tolerance
via the trace distance.
This explanation is interesting and intuitive. To this explanation we add the following observation:
even product states contain “nondeterminism” in the sense that we must also recognize products of mixed
states, not just pure states, and that the P URE P RODUCT S TATE problems (both one-way LOCC and trace
distance versions) are even easier (BQP-complete).
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 93
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
11 Conclusion
We have proved that several separability testing problems are complete for BQP, QMA, QMA(2), and
QSZK. These completeness results build upon the work of [46], which exhibits a separability testing
problem in QIP(2) and another problem complete for QIP. The completeness of these problems for a
wide range of complexity classes illustrates an important connection between entanglement and quantum
computational complexity theory. In hindsight, it is perhaps natural that these entanglement-related
problems capture the expressive power of these classes, since entanglement seems to be the most
prominent feature which distinguishes classical from quantum computational complexity theory.
It is interesting to note the connection between these problems and the differences that give rise to
problems complete for different interactive proof classes. Some patterns emerge: it seems as though
mixed state separability requires two messages to be added onto a proof for pure state separability so
that the prover may act upon the purification of the mixed state, as is the case for both the “state” and
“channel” versions of these problems.
Two-message quantum interactive proofs continue to be somewhat mysterious. Extrapolating from
our results, the one-way LOCC version of S EPARABLE S TATE has the qualities that one would intuitively
expect of a QIP(2)-complete problem. Despite this intuition, we do not know whether it is QIP(2)-
complete or even QMA-hard. However, our work here provides some intuition for why the problem
should not be either QSZK- or QMA-complete—there are other problems very different from it that are
complete for these classes.
Our work can be extended in a number of directions. The trace distance version of S EPARABLE
C HANNEL O UTPUT may help to understand the relation between multi-prover quantum interactive proofs
with and without entanglement among the provers (QMIP versus QMIP∗ ). Similarly, the trace distance
version of S EPARABLE S TATE may provide further insights. It would also be worthwhile to characterize
the channel version of P RODUCT S TATE in order to map out more of the space of separability testing
problems. Such an extension may also help to provide a tighter characterization of classes that rely on
“unentanglement,” such as QMA(2).
It is satisfying that each of the separability testing problems (with the possible exception of the
one-way LOCC version of S EPARABLE S TATE) is complete for a different complexity class. Perhaps
by studying the remaining related problems and their variants (trace norm versus one-way LOCC norm,
separable states versus product states, etc.) one may find two different separability testing problems that
are nontrivially reducible to each other.
Acknowledgements
We thank Claude Crépeau, Brian Swingle, and John Watrous for helpful conversations and the anonymous
referees for many helpful suggestions. Some of this research was conducted while GG was a visitor at
the School of Computer Science at McGill University, at which time GG’s primary affiliation was the
Institute for Quantum Computing and School of Computer Science, University of Waterloo, Waterloo,
Ontario, Canada. MMW began this project while affiliated with the School of Computer Science, McGill
University.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 94
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
References
[1] S COTT A ARONSON: Quantum Computing since Democritus. Cambridge Univ. Press, 2013. 62
[2] S COTT A ARONSON , S ALMAN B EIGI , A NDREW D RUCKER , B ILL F EFFERMAN , AND P ETER
S HOR: The power of unentanglement. Theory of Computing, 5(1):1–42, 2009. Preliminary version
in CCC’08. [doi:10.4086/toc.2009.v005a001] 67
[3] A NDRIS A MBAINIS , A DAM S MITH , AND K E YANG: Extracting quantum entanglement (general
entanglement purification protocols). In Proc. 17th IEEE Conf. on Computational Complexity
(CCC’02), pp. 82–91, 2002. [doi:10.1109/CCC.2002.1004345, arXiv:quant-ph/0110011] 61, 69
[4] L ÁSZLÓ BABAI: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM
Press, 1985. [doi:10.1145/22145.22192] 60
[5] L ÁSZLÓ BABAI AND S HLOMO M ORAN: Arthur-Merlin games: a randomized proof system, and a
hierarchy of complexity classes. J. Comput. System Sci., 36(2):254–276, 1988. [doi:10.1016/0022-
0000(88)90028-1] 60
[6] A DRIANO BARENCO , A NDRE B ERTHIAUME , DAVID D EUTSCH , A RTUR E KERT, R ICHARD
J OZSA , AND C HIARA M ACCHIAVELLO: Stabilization of quantum computations by symmetriza-
tion. SIAM J. Comput., 26(5):1541–1557, 1997. [doi:10.1137/S0097539796302452, arXiv:quant-
ph/9604028] 65
[7] H OWARD BARNUM , C LAUDE C RÉPEAU , DANIEL G OTTESMAN , A DAM S MITH , AND A LAIN
TAPP: Authentication of quantum messages. In Proc. 43rd FOCS, pp. 449–458. IEEE Comp. Soc.
Press, 2002. [doi:10.1109/SFCS.2002.1181969, arXiv:quant-ph/0205128] 61, 69
[8] S ALMAN B EIGI: NP vs QMAlog (2). Quantum Inf. Comput., 10(1&2):141–151, 2010.
[arXiv:0810.5109] 67
[9] C HARLES H. B ENNETT, G ILLES B RASSARD , C LAUDE C RÉPEAU , R ICHARD J OZSA , A SHER
P ERES , AND W ILLIAM K. W OOTTERS: Teleporting an unknown quantum state via dual clas-
sical and Einstein-Podolsky-Rosen channels. Physical Review Letters, 70(13):1895–1899, 1993.
[doi:10.1103/PhysRevLett.70.1895] 60
[10] C HARLES H. B ENNETT, DAVID P. D I V INCENZO , J OHN A. S MOLIN , AND W ILLIAM K. W OOT-
TERS: Mixed state entanglement and quantum error correction. Physical Review A, 54(5):3824–3851,
1996. [doi:10.1103/PhysRevA.54.3824, arXiv:quant-ph/9604024] 61, 69
[11] C HARLES H. B ENNETT, P ETER W. S HOR , J OHN A. S MOLIN , AND A SHISH V. T HAPLIYAL:
Entanglement-assisted classical capacity of noisy quantum channels. Physical Review Letters,
83(15):3081–3084, 1999. [doi:10.1103/PhysRevLett.83.3081, arXiv:quant-ph/9904023] 60
[12] C HARLES H. B ENNETT, P ETER W. S HOR , J OHN A. S MOLIN , AND A SHISH V. T HAPLIYAL:
Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem. IEEE Trans.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 95
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
Inform. Theory, 48(10):2637–2655, 2002. [doi:10.1109/TIT.2002.802612, arXiv:quant-ph/0106052]
60
[13] C HARLES H. B ENNETT AND S TEPHEN J. W IESNER: Communication via one- and two-particle
operators on Einstein-Podolsky-Rosen states. Physical Review Letters, 69(20):2881–2884, 1992.
[doi:10.1103/PhysRevLett.69.2881] 60
[14] D OMINIC W. B ERRY, G RAEME A HOKAS , R ICHARD C LEVE , AND BARRY C. S ANDERS: Efficient
quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics,
270(2):359–371, 2007. [doi:10.1007/s00220-006-0150-x, arXiv:quant-ph/0508139] 60
[15] H UGUE B LIER AND A LAIN TAPP: All languages in NP have very short quantum proofs. In Third
International Conference on Quantum, Nano and Micro Technologies, 2009. ICQNM ’09., pp.
34–37, 2009. [doi:10.1109/ICQNM.2009.21, arXiv:0709.0738] 67
[16] F ERNANDO G. S. L. B RANDÃO AND M ATTHIAS C HRISTANDL: Detection of multiparticle entan-
glement: Quantifying the search for symmetric extensions. Physical Review Letters, 109(16):160502,
2012. [doi:10.1103/PhysRevLett.109.160502, arXiv:1105.5720] 66
[17] F ERNANDO G. S. L. B RANDÃO , M ATTHIAS C HRISTANDL , AND J ON YARD: Faithful squashed en-
tanglement. Communications in Mathematical Physics, 306(3):805–830, 2011. [doi:10.1007/s00220-
011-1302-1, arXiv:1010.1750] 61
[18] F ERNANDO G. S. L. B RANDÃO , M ATTHIAS C HRISTANDL , AND J ON YARD: A quasipolynomial-
time algorithm for the quantum separability problem. In Proc. 43rd STOC, pp. 343–351. ACM
Press, 2011. [doi:10.1145/1993636.1993683, arXiv:1011.2751] 67
[19] F ERNANDO G. S. L. B RANDÃO AND A RAM W ETTROTH H ARROW: Quantum de Finetti theorems
under local measurements with applications. In Proc. 45th STOC, pp. 861–870. ACM Press, 2013.
[doi:10.1145/2488608.2488718, arXiv:1210.6367] 66, 74, 75
[20] H ARRY B UHRMAN , R ICHARD C LEVE , J OHN WATROUS , AND RONALD DE W OLF: Quantum
fingerprinting. Physical Review Letters, 87(16):167902, 2001. [doi:10.1103/PhysRevLett.87.167902,
arXiv:quant-ph/0102001] 65
[21] A NDRÉ C HAILLOUX AND O R S ATTATH: The complexity of the separable Hamiltonian prob-
lem. In Proc. 27th IEEE Conf. on Computational Complexity (CCC’12), pp. 32–41, 2012.
[doi:10.1109/CCC.2012.42, arXiv:1111.5247] 67
[22] J ING C HEN AND A NDREW D RUCKER: Short multi-prover quantum proofs for SAT without
entangled measurements. 2010. [arXiv:1011.0716] 67
[23] L IN C HEN , M ARTIN AULBACH , AND M ICHAL H AJDUSEK: Comparison of different defi-
nitions of the geometric measure of entanglement. Physical Review A, 89(4):042305, 2014.
[doi:10.1103/PhysRevA.89.042305, arXiv:1308.0806] 61, 92
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 96
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
[24] A LESSANDRO C HIESA AND M ICHAEL A. F ORBES: Improved soundness for QMA with
multiple provers. Chicago Journal of Theoretical Computer Science, 2013, Article 1.
[doi:10.4086/cjtcs.2013.001] 67
[25] R ICHARD C LEVE AND H ARRY B UHRMAN: Substituting quantum entanglement for communica-
tion. Physical Review A, 56(2):1201–1204, 1997. [doi:10.1103/PhysRevA.56.1201, arXiv:quant-
ph/9704026] 60
[26] S TEPHEN A. C OOK: The complexity of theorem proving procedures. In Proc. 3rd STOC, pp.
151–158. ACM Press, 1971. [doi:10.1145/800157.805047] 60
[27] S TEPHEN A. C OOK AND P HUONG N GUYEN: Logical Foundations of Proof Complexity. Cambridge
Univ. Press, 2010. [doi:10.1017/CBO9780511676277] 60
[28] T OBY S. C UBITT, D EBBIE L EUNG , W ILLIAM M ATTHEWS , AND A NDREAS W INTER: Improving
zero-error classical communication with entanglement. Physical Review Letters, 104(23):230503,
2010. [doi:10.1103/PhysRevLett.104.230503, arXiv:0911.5300] 60
[29] DAVID P. D I V INCENZO , PATRICK H AYDEN , AND BARBARA M. T ERHAL: Hiding quantum data.
Foundations of Physics, 33(11):1629–1647, 2003. [doi:10.1023/a:1026013201376, arXiv:quant-
ph/0207147] 60
[30] DAVID P. D I V INCENZO , D EBBIE W. L EUNG , AND BARBARA M. T ERHAL: Quantum data hiding.
IEEE Trans. Inform. Theory, 48(3):580–598, March 2002. [doi:10.1109/18.985948, arXiv:quant-
ph/0103098] 60
[31] A NDREW C. D OHERTY, PABLO A. PARRILO , AND F EDERICO M. S PEDALIERI: Distin-
guishing separable and entangled states. Physical Review Letters, 88(18):187904, 2002.
[doi:10.1103/PhysRevLett.88.187904, arXiv:quant-ph/0112007] 74
[32] A NDREW C. D OHERTY, PABLO A. PARRILO , AND F EDERICO M. S PEDALIERI: Complete family
of separability criteria. Physical Review A, 69(2):022308, 2004. [doi:10.1103/PhysRevA.69.022308,
arXiv:quant-ph/0308032] 74
[33] A NDREW C. D OHERTY, PABLO A. PARRILO , AND F EDERICO M. S PEDALIERI: Detecting multi-
partite entanglement. Physical Review A, 71(3):032333, 2005. [doi:10.1103/PhysRevA.71.032333]
74
[34] T ILO E GGELING AND R EINHARD F. W ERNER: Hiding classical data in multipartite quantum states.
Physical Review Letters, 89(9):097905, 2002. [doi:10.1103/physrevlett.89.097905, arXiv:0203004]
60
[35] A RTUR K. E KERT: Quantum cryptography based on Bell’s theorem. Physical Review Letters,
67(6):661–663, 1991. [doi:10.1103/PhysRevLett.67.661] 60
[36] C HRISTOPHER A. F UCHS AND J EROEN VAN DE G RAAF: Cryptographic distinguishability
measures for quantum-mechanical states. IEEE Trans. Inform. Theory, 45(4):1216, 1999.
[doi:10.1109/18.761271, arXiv:quant-ph/9712042] 65
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 97
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
[37] S EVAG G HARIBIAN: Strong NP-hardness of the quantum separability problem. Quantum Inf.
Comput., 10(3):343–360, 2010. [arXiv:0810.4507] 60
[38] S HAFI G OLDWASSER , S ILVIO M ICALI , AND C HARLES R ACKOFF: The knowledge complexity of
interactive proof systems. SIAM J. Comput., 18(1):186–208, 1989. Preliminary version in STOC’85.
[doi:10.1137/0218012] 60
[39] L EONID G URVITS: Classical deterministic complexity of Edmonds’ problem and quantum en-
tanglement. In Proc. 35th STOC, pp. 10–19. ACM Press, 2003. [doi:10.1145/780542.780545,
arXiv:quant-ph/0303055] 60
[40] G US G UTOSKI AND J OHN WATROUS: Quantum interactive proofs with competing provers. In Proc.
22nd Symp. Theoretical Aspects of Comp. Sci. (STACS’05), volume 3404 of LNCS, pp. 605–616.
Springer, 2005. [doi:10.1007/978-3-540-31856-9_50, arXiv:cs/0412102] 68, 92
[41] G US G UTOSKI AND X IAODI W U: Parallel approximation of min-max problems. Comput. Com-
plexity, 22(2):385–428, 2013. Preliminary version in CCC’12. [doi:10.1007/s00037-013-0065-9,
arXiv:1011.2787] 62, 68
[42] DANIEL H ARLOW AND PATRICK H AYDEN: Quantum computation vs. firewalls. Journal of High
Energy Physics, 2013(6):85, 2013. [doi:10.1007/JHEP06(2013)085, arXiv:1301.4504] 90
[43] A RAM W ETTROTH H ARROW AND D EBBIE L EUNG: A communication-efficient nonlocal mea-
surement with application to communication complexity and bipartite gate capacities. IEEE Trans.
Inform. Theory, 57(8):5504–5508, 2011. [doi:10.1109/TIT.2011.2158468, arXiv:0803.3066] 61, 69
[44] A RAM W ETTROTH H ARROW AND A SHLEY M ONTANARO: An efficient test for product states
with applications to quantum Merlin-Arthur games. In Proc. 51st FOCS, pp. 633–642. IEEE Comp.
Soc. Press, 2010. [doi:10.1109/FOCS.2010.66, arXiv:1001.0017] 61, 62, 67, 68, 71, 81, 92
[45] PATRICK H AYDEN , M ICHAL H ORODECKI , A NDREAS W INTER , AND J ON YARD: A decoupling
approach to the quantum capacity. Open Systems & Information Dynamics, 15(1):7–19, 2008.
[doi:10.1142/S1230161208000043, arXiv:quant-ph/0702005] 90
[46] PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE: Two-message quantum interactive
proofs and the quantum separability problem. Quantum Inf. Comput., 14(5 & 6):384–416, 2014.
Preliminary version at CCC’13. [arXiv:1211.6120] 60, 61, 62, 63, 77, 88, 90, 91, 92, 93, 94
[47] PATRICK H AYDEN AND B RIAN S WINGLE: Quantum error correction and QSZK. unpublished,
2012. 90
[48] C ARL W. H ELSTROM: Quantum detection and estimation theory. Journal of Statistical Physics,
1(2):231–252, 1969. [doi:10.1007/BF01007479] 64
[49] RYSZARD H ORODECKI , PAWEŁ H ORODECKI , M ICHAŁ H ORODECKI , AND K AROL
H ORODECKI: Quantum entanglement. Reviews of Modern Physics, 81(2):865–942, 2009.
[doi:10.1103/RevModPhys.81.865, arXiv:quant-ph/0702225] 60, 70
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 98
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
[50] R AHUL JAIN , Z HENGFENG J I , S ARVAGYA U PADHYAY, AND J OHN WATROUS: QIP = PSPACE. J.
ACM, 58(6):30, 2011. Preliminary version in STOC’10. [doi:10.1145/2049697.2049704] 62, 67
[51] R AHUL JAIN , S ARVAGYA U PADHYAY, AND J OHN WATROUS: Two-message quantum interac-
tive proofs are in PSPACE. In Proc. 50th FOCS, pp. 534–543. IEEE Comp. Soc. Press, 2009.
[doi:10.1109/FOCS.2009.30, arXiv:0905.1300] 62, 68, 76
[52] M ASARU K ADA , H ARUMICHI N ISHIMURA , AND T OMOYUKI YAMAKAMI: The efficiency of
quantum identity testing of multiple states. Journal of Physics A: Mathematical and Theoretical,
41(39):395309, 2008. [doi:10.1088/1751-8113/41/39/395309, arXiv:0809.2037] 65
[53] A LEXEI Y U . K ITAEV: Quantum measurements and the Abelian Stabilizer Problem. ECCC,
TR96-003, 1995. [arXiv:quant-ph/9511026] 65
[54] A LEXEI Y U . K ITAEV AND J OHN WATROUS: Parallelization, amplification, and exponential time
simulation of quantum interactive proof systems. In Proc. 32nd STOC, pp. 608–617. ACM Press,
2000. [doi:10.1145/335305.335387] 60, 67, 68
[55] H IROTADA KOBAYASHI AND K EIJI M ATSUMOTO: Quantum multi-prover interactive proof systems
with limited prior entanglement. J. Comput. System Sci., 66(3):429–450, May 2003. Preliminary
version in ISAAC’02. [doi:10.1016/s0022-0000(03)00035-7, arXiv:cs/0102013] 67
[56] C ÉCILIA L ANCIEN AND A NDREAS W INTER: Distinguishing multi-partite states by local measure-
ments. Communications in Mathematical Physics, 323(2):555–573, 2013. [doi:10.1007/s00220-
013-1779-x, arXiv:1206.2884] 66
[57] F RANÇOIS L E G ALL , S HOTA NAKAGAWA , AND H ARUMICHI N ISHIMURA: On QMA protocols
with two short quantum proofs. Quantum Inf. Comput., 12(7&8):589–600, 2012. [arXiv:1108.4306]
67
[58] Y I -K AI L IU , M ATTHIAS C HRISTANDL , AND F RANK V ERSTRAETE: Quantum computational com-
plexity of the N-representability problem: QMA complete. Physical Review Letters, 98(11):110503,
2007. [doi:10.1103/PhysRevLett.98.110503, arXiv:quant-ph/0609125] 67
[59] S ETH L LOYD: Universal quantum simulators. Science, 273(5278):1073–1078, 1996.
[doi:10.1126/science.273.5278.1073] 60
[60] C ARSTEN L UND , L ANCE F ORTNOW, H OWARD K ARLOFF , AND N OAM N ISAN: Algebraic meth-
ods for interactive proof systems. J. ACM, 39(4):859–868, 1992. Preliminary version in FOCS’90.
[doi:10.1145/146585.146605] 68
[61] C HRIS M ARRIOTT AND J OHN WATROUS: Quantum Arthur-Merlin games. Comput. Complex-
ity, 14(2):122–152, 2005. Preliminary version in CCC’04. [doi:10.1007/s00037-005-0194-x,
arXiv:cs/0506068] 68
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 99
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
[62] W ILLIAM M ATTHEWS , S TEPHANIE W EHNER , AND A NDREAS W INTER: Distinguishability of
quantum states under restricted families of measurements with an application to quantum data
hiding. Communications in Mathematical Physics, 291(3):813–843, 2009. [doi:10.1007/s00220-
009-0890-5, arXiv:0810.2327] 60, 61, 66
[63] M ICHAEL A. N IELSEN AND I SAAC L. C HUANG: Quantum Computation and Quantum Information.
Cambridge Univ. Press, 2000. 62, 77
[64] C HRISTOS H. PAPADIMITRIOU: Computational Complexity. Addison-Wesley, 1994. 60
[65] A DI S HAMIR: IP = PSPACE. J. ACM, 39(4):869–877, 1992. Preliminary version in FOCS’90.
[doi:10.1145/146585.146609] 68
[66] YAOYUN S HI AND X IAODI W U: Epsilon-net method for optimizations over separable states. In
Proc. 39th Internat. Colloq. on Automata, Languages and Programming (ICALP’12), volume 7391
of LNCS, pp. 798–809. Springer, 2012. [doi:10.1007/978-3-642-31594-7_67, arXiv:1112.0808] 67
[67] M ICHAEL S IPSER: Introduction to the Theory of Computation. International Thomson Publishing,
1996. 60
[68] L ARRY J. S TOCKMEYER: The polynomial-time hierarchy. Theoret. Comput. Sci., 3(1):1–22, 1976.
[doi:10.1016/0304-3975(76)90061-X] 60
[69] U MESH VAZIRANI AND T HOMAS V IDICK: Fully device independent quantum key distribu-
tion. Physical Review Letters, 113(14)(14):140501, 2014. [doi:10.1103/PhysRevLett.113.140501,
arXiv:1210.1810] 60
[70] J OHN WATROUS: Limits on the power of quantum statistical zero-knowledge. In Proc. 43rd
FOCS, pp. 459–468. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181970, arXiv:quant-
ph/0202111] 62, 67, 68, 86, 88, 90
[71] J OHN WATROUS: PSPACE has constant-round quantum interactive proof systems. Theoret. Comput.
Sci., 292(3):575–588, 2003. Preliminary version in FOCS’99. [doi:10.1016/S0304-3975(01)00375-
9] 60
[72] J OHN WATROUS: Theory of Quantum Information (course lecture notes). 2004. 69
[73] J OHN WATROUS: Quantum computational complexity. Encyclopedia of Complexity and System
Science, pp. 7174–7201, 2009. [doi:10.1007/978-0-387-30440-3_428, arXiv:0804.3401] 60, 62
[74] J OHN WATROUS: Zero-knowledge against quantum attacks. SIAM J. Comput., 39(1):25–58, 2009.
Preliminary version in STOC’06. [doi:10.1137/060670997, arXiv:quant-ph/0511020] 62, 67, 86
[75] T ZU -C HIEH W EI AND PAUL M. G OLDBART: Geometric measure of entanglement and appli-
cations to bipartite and multipartite quantum states. Physical Review A, 68(4)(4):042307, 2003.
[doi:10.1103/PhysRevA.68.042307, arXiv:quant-ph/0307219] 61, 92
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 100
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
[76] R EINHARD F. W ERNER: An application of Bell’s inequalities to a quantum state extension problem.
Letters in Mathematical Physics, 17(4):359–363, 1989. [doi:10.1007/BF00399761] 74
[77] R EINHARD F. W ERNER: Quantum states with Einstein-Podolsky-Rosen correlations
admitting a hidden-variable model. Physical Review A, 40(8):4277–4281, 1989.
[doi:10.1103/PhysRevA.40.4277] 62
[78] M ARK M. W ILDE: From Classical to Quantum Shannon Theory. 2011. Published in [79].
[arXiv:1106.1445] 62
[79] M ARK M. W ILDE: Quantum Information Theory. Cambridge Univ. Press, 2013. 62, 101
[80] N ENGKUN Y U , RUNYAO D UAN , AND Q UANHUA X U: Bounds on the distance between a unital
quantum channel and the convex hull of unitary channels, with applications to the asymptotic
quantum Birkhoff conjecture. 2012. [arXiv:1201.1172] 92
[81] PAOLO Z ANARDI , C HRISTOF Z ALKA , AND L ARA FAORO: Entangling power of quantum evolu-
tions. Physical Review A, 62(3):030301, 2000. [doi:10.1103/PhysRevA.62.030301, arXiv:quant-
ph/0005031] 93
AUTHORS
Gus Gutoski
Postdoctoral Scholar
Perimeter Institute for Theoretical Physics, Waterloo, Ontario, Canada
ggutoski perimeterinstitute ca
http://www.perimeterinstitute.ca/personal/ggutoski/
Patrick Hayden
Professor of Physics
Department of Physics, Stanford University, Stanford, California, USA
phayden stanford edu
http://web.stanford.edu/~phayden
Kevin Milner
Ph. D. student
University of Oxford, Oxford, UK
kamilner kamilner ca
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 101
G US G UTOSKI , PATRICK H AYDEN , K EVIN M ILNER , AND M ARK M. W ILDE
Mark M. Wilde
Assistant Professor
Hearne Institute for Theoretical Physics, Department of Physics and Astronomy, Center for
Computation and Technology, Louisiana State University, Baton Rouge, Louisiana, USA
mwilde lsu edu
http://www.markwilde.com
ABOUT THE AUTHORS
G US G UTOSKI was born in Kitchener, Ontario, twin city of Waterloo, Ontario. After
completing a BMath at the University of Waterloo he briefly escaped the Region of
Waterloo for a MSc at the University of Calgary in Calgary, Alberta. Unfortunately,
his graduate advisor, John Watrous, subsequently took a position at the University of
Waterloo. Gus reluctantly followed his advisor back to his hometown and completed a
Ph. D. in Computer Science at the University of Waterloo. He is currently a postdoctoral
researcher at the Perimeter Institute for Theoretical Physics in Waterloo and he cannot
get enough of Waterloo. Gus’s research interests include quantum complexity theory,
quantum cryptography, and, lately, Bitcoin.
PATRICK H AYDEN received his D. Phil. in Physics from the University of Oxford in 2001
under the supervision of Artur Ekert. Subsequently he was a postdoc at Caltech before
joining the faculty at McGill University, where he spent nine happy years before moving
to Stanford in 2013. Like many computer scientists, Hayden developed an interest in
complexity theory because of its possible relevance to black hole physics. His other
research interests include skiing and backcountry camping. Outside of work, Hayden
enjoys proving theorems in quantum communication theory and studying the emergence
of spacetime.
K EVIN M ILNER did his undergraduate studies at the University of Alberta where he devel-
oped an interest in complexity theory before joining McGill University to study quantum
information for his M. Sc., under the supervision of Patrick Hayden. His hobbies include
breaking and fixing the Internet, which he now studies as a D. Phil. student supervised by
Cas Cremers at the University of Oxford, and not worrying about the Internet, which he
now studies whenever he can.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 102
Q UANTUM I NTERACTIVE P ROOFS AND THE C OMPLEXITY OF S EPARABILITY T ESTING
M ARK M. W ILDE was born in Metairie, Louisiana, USA. He received the Ph. D. in electrical
engineering from the University of Southern California, Los Angeles, in 2008, and
was advised by Todd Brun. He is an Assistant Professor in the Department of Physics
and Astronomy and the Center for Computation and Technology at Louisiana State
University. His current research interests are in quantum Shannon theory, quantum
optical communication, quantum computational complexity theory, and quantum error
correction. He has elected not to include any humor in his bio because he finds the above
three bios to be about as unfunny as “unfunny” can be and fears that any attempt of his
would be worse. He also recognizes that this is the first time he has roasted his coauthors
in the second-to-last sentence of a published scientific paper.
T HEORY OF C OMPUTING, Volume 11 (3), 2015, pp. 59–103 103