Computational complexity of the quantum separability problem

Lawrence M. Ioannou

REVIEW 3 major objections 2 minor 1 cited by

Computational complexity of the quantum separability problem

T0 review · 3 major / 2 minor · reviewed 2026-08-28 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The approximate quantum separability problem is Turing-NP-complete, and weak separation is strongly NP-hard

desk verdict Useful survey and a solid QSEP membership result, but the headline strong-NP-hardness theorem is not supported: Eq. (57) is false as written. read the letter →

arxiv quant-ph/0603199 v7 pith:IR4KNOW3 submitted 2006-03-22 quant-ph cs.CC

Lawrence M. Ioannou This is my paper · ORCID

classification quant-phcs.CC MSC 68Q1781P4081P68 PACS 03.67.Mn

keywords quantumseparabilityNP-completenessTuringreductionweakmembershipproblementanglementwitnesssemidefiniteprogrammingdeFinettitheoremdensitymatrix

topics The Hierarchy Problem

open problems The Hierarchy Problem

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to establish where the bipartite quantum separability problem sits in classical complexity theory: given a density matrix on $\mathbb{C}^M \otimes \mathbb{C}^N$, can one efficiently decide whether it is separable or entangled? Its main claim is that the natural approximate decision version, QSEP, is in NP and NP-hard under Turing reductions, hence Turing-NP-complete, and that the weak separation problem, which must output an approximate entanglement witness, is strongly NP-hard whenever $2 \le N \le M$. This matters because the approximate, error-tolerant formulation is the one used in experiments and in convex-optimization practice, while the exact formulation is either unwieldy for rational inputs or runs into undecidability at boundary points for arbitrary real inputs. If the classification is right, no deterministic polynomial-time algorithm for approximate separability exists unless $P = NP$, and QSEP may be the first natural problem that is Turing- but not Karp-NP-complete.

What carries the argument

The argument is carried by a chain of polynomial reductions: CLIQUE to weak maximization over the simplex, to robust semidefinite feasibility, to weak validity for the separable set, and then by oracle reductions to weak membership, with a second branch reaching weak separation. The decisive algebraic object is identity (57), $$\max_{\$\sigma$ \in S_{M,N}} \mathrm{tr}(B\$\sigma$) = \max_{\|x\|_2=1} \sum_{i=1}^{M-1} (x^T B_i x)^2,$$ which rewrites the maximum of a block matrix over separable states as a sum of squared quadratic forms and links clique-like hardness to the existence of entanglement witnesses. A finite de Finetti bound supplies the upper bound on the symmetric-extension search, and the weak-optimization subroutine with optimal sphere coverings supplies the best known upper bound on the witness-search algorithm.

What would settle it

Compute both sides of identity (57) for a small explicit block matrix, for instance $M = N = 2$ with a rational $B_1$, where the right-hand side is an eigenvalue-type maximization and the left-hand side can be bounded by a converging hierarchy; a single mismatch between the two maxima would refute the strong-NP-hardness derivation.

Watch

Extended reading notes

Core claim

The central discovery is a complexity classification: the approximate separability decision problem QSEP is Turing-NP-complete. QSEP asks whether a rational density matrix is within a specified Euclidean tolerance of a separable state, with the candidate decomposition restricted to finite precision; the certified decomposition is a short certificate, so the problem is in NP, and a Karp reduction from the weak membership problem transfers known NP-hardness. The second main claim is that WSEP, the weak separation problem that must either certify near-separability or return an approximate entanglement witness, is strongly NP-hard in the regime $2 \le N \le M$. The strong hardness follows from a new reduction chain starting from CLIQUE and passing through quadratic-form and robust-feasibility problems, upgraded to polynomial accuracy by a cutting-plane reduction. The paper leaves open whether QSEP is Karp-NP-complete and suggests it might be the first natural problem separating Turing from Karp completeness within NP.

Load-bearing premise

The strong NP-hardness result rests on the unproved equality (57) between the maximum of a block matrix over separable states and the maximum of a sum of squared quadratic forms over unit vectors; if that equality has any counterexample, the strong-hardness conclusion collapses.

Editorial extensions

If this is right

If QSEP is Turing-NP-complete as claimed, no classical polynomial-time algorithm can solve approximate separability for all dimensions unless $P = NP$.
Strong NP-hardness of WSEP means that producing an approximate entanglement witness is intractable as well, not merely deciding whether a state is near-separable.
The quantum de Finetti bound turns the symmetric-extension hierarchy into a concrete algorithm: checking extensions up to $k = \lceil 4M/\delta \rceil$ copies suffices for weak membership with accuracy $\delta$.
The entanglement-witness search with optimally chosen sphere coverings gives the best currently known worst-case complexity, dominated by the covering size times a polynomial factor.
If QSEP is not Karp-NP-complete, it would be the first natural decision problem whose Turing and Karp completeness notions differ.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the strong hardness classification holds, the same reduction strategy should transfer to neighbouring convex-set problems whose extreme points have tensor-product structure, so multipartite separability and separability with marginal constraints are natural places to look for similar strong hardness.
The open Turing-versus-Karp gap suggests a concrete research target: either find a direct Karp reduction from CLIQUE to QSEP that bypasses the ellipsoid-method weak-membership step, or find a reason why such a reduction cannot exist.
The de Finetti bound $k = \lceil 4M/\delta \rceil$ implies that in fixed small dimensions the symmetric-extension SDP is a finite algorithm with explicit running time; the intractability statement binds only as both dimensions and the reciprocal accuracy grow together.
A testable benchmark suggested by the analysis is to compare the witness-search and symmetric-extension algorithms on random high-dimensional states; the theory says witness-search cost is governed by sphere-covering size, so better coverings should translate directly into speed.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: this is a useful survey with one solid new result and one headline hardness result that is not supported as written. The stress-test note is right: Eq. (57) is false, and Fact 5 falls with it.

What's good: the QSEP formulation is careful, and the proof that QSEP is in NP, with explicit truncation-error bounds in Propositions 1 and 2, is a real contribution. The discussion of why weak membership formulations do not sit naturally in NP, and the relationship to co-NP, entanglement witnesses, and the Karp-versus-Turing open problem, is clear and well organized. The survey of algorithms (symmetric extensions, entanglement-witness search, and the rest) is genuinely useful, and the complexity comparison is a service to the community. The author is also honest about what comes from Gurvits' private communication and what is his own.

The soft spot is not minor. Eq. (57) claims max_{σ∈S} tr(Bσ) = max_{||x||=1} Σ_i (x^T B_i x)^2. For a product state, the expectation of B is 2 Σ_i Re(u_0^* u_i) v^T B_i v, and maximizing over u gives sqrt(Σ_i (v^T B_i v)^2), not Σ_i (...)^2. So the identity is off by a square. Concretely, with M=N=2 and B1=diag(2,1), the LHS is 2 and the RHS is 4. Since the third link in the CLIQUE→WMQS→RSDF→WVAL chain uses this identity directly, Fact 5, the strong NP-hardness of WSEP, is not established by this preprint. Eq. (55) also has a factor-2 slip: (x^T B_ij x)^2 = 4 A_ij x_i^2 x_j^2, so the sum over i

Will the theorem survive? Possibly. Replacing Eq. (57) by the square-root version and absorbing the factor 2, the CLIQUE gap remains Θ(n^{-2}), so a corrected reduction with γ=sqrt(ζ) and suitable ε should go through. But that corrected argument is not in the paper, and the current text leans on a private communication and an unproved identity for a load-bearing step.

Who this is for: anyone working on separability algorithms or on the complexity of convex membership in quantum information. The survey half deserves a wide read even if the hardness result needs repair. I would send it to a referee, because the QSEP membership result and the survey are worth publishing and the flaw is specific and repairable. I would not cite Fact 5 as it stands.

Recommendation: engage with the paper, but ask for a full public proof of the corrected reduction chain before accepting the strong-hardness claim.

Referee Report

3 major / 2 minor

Summary. The paper studies the computational complexity of the bipartite quantum separability problem in its approximate, weak-membership formulations. It defines a decision problem QSEP, argues that QSEP is in NP via an explicit certificate and is NP-hard under Turing reductions by a Karp reduction from the weak membership problem WMEM(S_M,N), and then discusses non-membership in co-NP. The paper further claims strong NP-hardness of the weak separation problem WSEP(S_M,N) through a reduction chain from CLIQUE via WMQS, RSDF, and WVAL(S_M,N). The second half surveys deterministic algorithms for separability, including symmetric-extension SDP hierarchies and entanglement-witness search, and compares their asymptotic complexities.

Significance. The paper provides a useful systematic survey and gives explicit error analyses for the certificate-based reduction behind Fact 3. If the main results were correct, QSEP would be a rare natural problem that is Turing-NP-complete without a known Karp completeness, and the strong hardness of WSEP would be a notable strengthening of Gurvits' theorem. The survey portion, with its explicit complexity estimates and discussion of promise formulations, is also valuable. However, the load-bearing identity in the strong-hardness reduction is false as stated, and a norm bound in the NP-containment reduction is also invalid, so the paper's central new claims are not established in the present form.

major comments (3)

[§2.2.5, Eq. (57)] Equation (57) is false as stated, and it is the load-bearing link in the reduction chain (50) for Fact 5. For M=N=2 and B_1=diag(2,1), the block matrix (56) has eigenvalues ±2 and ±1, and the product state |+⟩|e_1⟩ attains expectation 2, so the left-hand side equals 2; the right-hand side equals max_{||x||=1}(x^T B_1 x)^2 = 4. Re-deriving from the product-state expression gives max_{σ∈S_{M,N}} tr(Bσ) = (max_{||x||=1} Σ_i (x^T B_i x)^2)^{1/2}, i.e., the right-hand side of (57) is the square of the left-hand side. Consequently the threshold mapping (γ,ε):=(ζ,η) does not preserve the WMQS/RSDF yes/no distinction, and Fact 5 is not established as written. The argument may be repairable by using the square-root identity and adjusting γ and ε, but the corrected reduction is not present in the manuscript.
[§2.2.5, Eq. (55)] The chain of equalities in (55) also contains a factor-of-2 error. With B_ij defined to have √A_ij in positions (i,j) and (j,i), one has (x^T B_ij x)^2 = 4 A_ij x_i^2 x_j^2, so Σ_{i<j}(x^T B_ij x)^2 = 2 Σ_{i,j} A_ij x_i^2 x_j^2 when A_ii=0, not Σ_{i,j} A_ij x_i^2 x_j^2. Thus the RSDF instance produced from a WMQS instance is not equivalent to the WMQS instance unless the objective or the matrices are rescaled. This is a separate numerical error in the reduction chain, and it should be corrected consistently with the corrected Eq. (57).
[§2.2.2, Proposition 1] The proof of Proposition 1 contains an invalid norm bound. From the fact that each element of the MN×MN matrix γ_i is at most 2^{-(p-7)} in absolute value, it does not follow that (tr(γ_i^2))^{1/2} ≤ √(MN) 2^{-(p-7.5)}; an m×m matrix with entries bounded by ε can have Frobenius norm as large as mε. The subsequent sum would then yield M^3N^3 2^{-(p-7)} rather than the stated M^3N^3 2^{-(p-7.5)}, so the chosen value δ' = M^3N^3 2^{-(p-8)} may be too small. The reduction from WMEM to QSEP can almost certainly be repaired by increasing p, but the argument as printed needs correction.

minor comments (2)

[§3.2, Eq. (68)] The approximation leading to Eq. (68) drops a factor of (1+δ/4)^{\bar{k}} ≈ e^M when \bar{k}=4M/δ, so the displayed asymptotic d_{S_{\bar{k}}} ≈ (4/δ)^M is missing an e^M factor. This does not change the ranking of algorithms for small δ, but it affects the claimed comparison and should be corrected.
[§2.2.5, line after Eq. (59)] The chain WV AL(SM,N) ≤K WVIOL(SM,N) calls a reduction from a decision problem to a search problem a Karp reduction; please clarify the formal reduction notion used for search problems or rephrase the claim.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: hardness reductions are external and the author's own algorithms are not premises.

full rationale

The central claims (Fact 3: QSEP is in NPCT; Fact 4: QSEP is not in co-NP unless NP equals co-NP; Fact 5: WSEP(SM,N) is strongly NP-hard) are established by Karp and Turing reductions from CLIQUE and PARTITION and by cited external theorems (Gurvits [51], Motzkin and Straus [63], Groetschel-Lovasz-Schrijver [50]). The author's own prior work [4,5] and thesis [68] appear only in the survey and complexity estimates of algorithms, not as premises of the new hardness results. No parameter is fitted to data and then renamed a prediction, and no formulation defines the target quantity in terms of the conclusion. The unproved identity quoted as Eq. (57) from Gurvits is an external cited mathematical assertion; if that identity were false, the defect would be a correctness or validity risk, not a circularity, because the paper does not derive Eq. (57) from the conclusion it is used to prove. Therefore no circular step is present.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The new claims are built on standard complexity-theoretic reductions plus a handful of nontrivial theorems. No data are fitted, so the free-parameter list is empty. The most fragile input is the quoted Gurvits identity (57), which is necessary for strong NP-hardness of weak separation.

assumptions (6)

standard math Carathéodory's theorem, Fact 1: separable states are convex combinations of M^2 N^2 pure product states
Used to bound the size of guessed decompositions in QSEP.
domain assumption Quantum de Finetti theorem bound of Christandl et al. (Theorem 2): if ρ has a Bose-symmetric extension to k copies of A then tr|ρ−σ| ≤ 4M/k for some separable σ
Load-bearing for the bounded symmetric-extension algorithm complexity (Corollary 1).
standard math Motzkin-Straus theorem (Theorem 1): max_{y∈Δ_n} y^T A_G y = 1 − 1/κ
First link in the strong NP-hardness reduction chain.
domain assumption Gurvits identity (57) relating separable-state optimization to unit-sphere quadratic forms
Third link in the strong NP-hardness chain; quoted from [51] without proof.
standard math Existence of asymptotically optimal Euclidean δ-nets on the sphere with size ≤ (1+2/δ)^(2M)
Used for all algorithm complexity estimates in Section 3.
domain assumption NP ≠ co-NP (conjectured)
Fact 4's conclusion that QSEP is not in co-NP is conditional on this conjecture.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Computational complexity of the quantum separability problem." pith.science (2026). https://pith.science/paper/IR4KNOW3

@misc{pith2026quant-ph0603199,
  author       = {Pith},
  title        = {Pith review of: Computational complexity of the quantum separability problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IR4KNOW3}},
  note         = {Machine review of arXiv:quant-ph/0603199}
}

read the original abstract

Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or separable, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with the complexity classes NP, NP-complete, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem; and the entanglement-witness search (via interior-point algorithms and global optimization). These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.

Figures

Figures reproduced from arXiv: quant-ph/0603199 by the authors.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Quantum Separability and Entanglement Detection via Entanglement-Witness Search and Global Optimization
quant-ph 2006-02 conditional novelty 5.0 of 10

Separability can be decided from a partial set of observable expectations by reducing the weak separation problem to global optimization, and the set of separable states is shown not to be a polytope.

Reference graph

Works this paper leans on

82 extracted references · 77 canonical work pages · cited by 1 Pith paper

[1]

A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri. Distinguishing se parable and entangled states. Phys. Rev. Lett. , 88:187904, 2002

2002
[2]

A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri. Complete family o f separability criteria. Phys. Rev. A , 69:022308, 2004

2004
[3]

One-and-a-half quantum de Finetti theorems

M. Christandl, R. K¨ onig, G. Mitchison, and R. Renner. One-and- a-half quantum de ﬁnetti theorems, 2006. quant-ph/0602130

work page Pith review arXiv 2006
[4]

L. M. Ioannou, B. C. Travaglione, D. C. Cheung, and A. K. Ekert . Improved algorithm for quantum separability and entanglement detection. Phys. Rev. A , 70:060303(R), 2004

work page 2004
[5]

L. M. Ioannou and B. C. Travaglione. Quantum separability and en tanglement detection via entanglement-witness search and global optimization. Phys. Rev. A , 73:052314, 2006

work page 2006
[6]

Horodecki

P. Horodecki. Separability criterion and inseparable mixed states with positive partial transposition. Phys. Lett. A , 232:333, 1997

1997
[7]

Characterizing entanglement

Dagmar Bruß. Characterizing entanglement. J. Math. Phys. , 43:4237, 2002

work page 2002
[8]

B. M. Terhal. Detecting quantum entanglement. Journal Theoretical Computer Science , 287(1):313–335, 2002

work page 2002

Show all 82 references

[9]

Sen De, U

A. Sen De, U. Sen, M. Lewenstein, and A. Sanpera. The separab ility versus entanglement problem, 2005. quant-ph/0508032

2005 arXiv
[10]

A. Peres. Separability criterion for density matrices. Phys. Rev. Lett. , 77:1413–1415, 1996

1996
[11]

Horodecki and P

M. Horodecki and P. Horodecki. Reduction criterion of separa bility and limits for a class of distillation protocols. Phys. Rev. A , 59:4206, 1999

1999
[12]

Horodecki, P

R. Horodecki, P. Horodecki, and M. Horodecki. Quantum α-entropy inequalities: inde- pendent condition for local realism? Phys. Lett. A , 210:377–381, 1996

1996
[13]

Nielsen and J

M. Nielsen and J. Kempe. Separable states are more disordered globally than locally. Phys. Rev. Lett. , 86:5184–7, 2001

2001
[14]

O. Rudolph. Further results on the cross norm criterion for se parability, 2002. quant-ph/0202121

2002 arXiv
[15]

Chen and L.-A

K. Chen and L.-A. Wu. A matrix realignment method for recognizin g entanglement. Quant. Inf. Comp. , 3:193, 2003

2003
[16]

S eparability of mixed quan- tum states: linear contractions approach, 2002

Michal Horodecki, Pawel Horodecki, and Ryszard Horodecki. S eparability of mixed quan- tum states: linear contractions approach, 2002. quant-ph/020 6008

2002
[17]

S. L. Braunstein, C. M. Caves, R. Jozsa, N. Linden, S. Popesc u, and R. Schack. Separa- bility of very noisy mixed states and implications for NMR quantum comp uting. Phys. Rev. Lett., 83:1054, 1999. LA WRENCE M. IOANNOU 33

1999
[18]

Gurvits and H

L. Gurvits and H. Barnum. Largest separable balls around the m aximally mixed bipartite quantum state. Phys. Rev. A , 66:062311, 2002

2002
[19]

Zyczkowski, P

K. Zyczkowski, P. Horodecki, A. Sanpera, and M. Lewenstein. Volume of the set of separable states. Phys.Rev. A , 58:883, 1998

1998
[20]

Vidal and R

G. Vidal and R. Tarrach. Robustness of entanglement. Phys. Rev. A , 59:141, 1999

1999
[21]

Kraus, J

B. Kraus, J. I. Cirac, S. Karnas, and M. Lewenstein. Separab ility in 2 ×n composite quantum systems. Phys. Rev. A , 61:062302, 2000

2000
[22]

Horodecki, P

M. Horodecki, P. Horodecki, and R. Horodecki. Separability of m ixed states: necessary and suﬃcient conditions. Phys. Lett. A , 223:1–8, 1996

1996
[23]

Horodecki, M

P. Horodecki, M. Lewenstein, G. Vidal, and I. Cirac. Operationa l criterion and construc- tive checks for the separabilty of low-rank density matrices. Phys. Rev. A , 62:032310, 2000

2000
[24]

Albeverio, Shao-Ming Fei, and Debashish Goswami

S. Albeverio, Shao-Ming Fei, and Debashish Goswami. Separability of rank two quantum states. Phys. Lett. A , 286:91–96, 2001

2001
[25]

J. H. Wilkinson and C. Reinsch. Linear Algebra, Handbook for Automatic Computation Vol. II. Springer-Verlag, Berlin, 1971

1971
[26]

Golub and Charles F

Gene H. Golub and Charles F. van Loan. Matrix Computations . The Johns Hopkins University Press, Baltimore, 1996

1996
[27]

Stoer and R

J. Stoer and R. Bulirsch. Introduction to numerical analysis . Springer-Verlag, New York, 2002

2002
[28]

J. H. Wilkinson. Global convergence of tridiagonal QR algorithm w ith origin shifts. Lin. Alg. Appl. , 1:409–420, 1968

1968
[29]

Lewenstein and A

M. Lewenstein and A. Sanpera. Separability and entanglement o f composite quantum systems. Phys. Rev. Lett. , 80:2261, 1998

1998
[30]

R. T. Thew, K. Nemoto, A. G. White, and W. J. Munro. Qudit quan tum-state tomog- raphy. Phys. Rev. A , 66:012303, 2002

2002
[31]

Semideﬁnite program ming

Lieven Vandenberghe and Stephen Boyd. Semideﬁnite program ming. SIAM Review , 38(1):49–95, 1996

1996
[32]

Fannes, J

M. Fannes, J. T. Lewis, and A. Verbeure. Symmetric states of composite systems. Lett. Math. Phys. , 15:255, 1988

1988
[33]

C. M. Caves, C. A. Fuchs, and R. Schack. Unknown quantum st ates: The quantum de ﬁnetti representation. J. Math. Phys. , 43:4537, 2002

2002
[34]

C omplete hierarchies of eﬃcient approximations to problems in entanglement theory

Jens Eisert, Philipp Hyllus, Otfried G¨ uhne, and Marcos Curty. C omplete hierarchies of eﬃcient approximations to problems in entanglement theory. Phys. Rev. A , 70:062317, 2004. 34 COMPUTATIONAL COMPLEXITY OF THE QUANTUM SEPARABILITY PROB LEM

2004
[35]

Lasserre

Jean B. Lasserre. Global optimization with polynomials and the pr oblem of moments. SIAM J. Optim. , 11(3):796–817, 2001

2001
[36]

GloptiPoly: Global o ptimization over poly- nomials with Matlab and SeDuMi

Didier Henrion and Jean-Bernard Lasserre. GloptiPoly: Global o ptimization over poly- nomials with Matlab and SeDuMi. ACM Transactions on Mathematical Software , 29(2): 165–194, 2003

2003
[37]

Vedral, M

V. Vedral, M. Plenio, M. A. Rippin, and P. L. Knight. Quantifying en tanglement. Phys. Rev. Lett., 78:2275–2279, 1997

1997
[38]

Bipartite Entanglement: A Cryptographic point of view

Matthias Christandl. Bipartite Entanglement: A Cryptographic point of view . PhD thesis, University of Cambridge, 2005

2005
[39]

C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootter s. Mixed state entanglementand quantum error correction. Phys. Rev. A , 54(5):3824–3851, 1996

1996
[40]

Optimizing entropy relative to a channel or a suba lgebra

Armin Uhlmann. Optimizing entropy relative to a channel or a suba lgebra. OPEN SYS.AND INF.DYN. , 5:209, 1998. URL http://arxiv.org/abs/quant-ph/9701014

1998 arXiv
[41]

Fernando G. S. L. Brand˜ ao and Reinaldo O. Vianna. Robust sem ideﬁnite programming approach to the separability problem. Phys. Rev. A , 70:062309(R), 2004

2004
[42]

Fernando G. S. L. Brand˜ ao and Reinaldo O. Vianna. Separable m ultipartite mixed states: Operational asymptotically necessary and suﬃcient cond itions. Phys. Rev. Lett. , 93:220503, 2004

2004
[43]

Woerdeman

Hugo J. Woerdeman. Checking 2 ×m quantum separability via semideﬁnite programming. Phys. Rev. A , 67:010303(R), 2003

2003
[44]

Horodecki and A

P. Horodecki and A. Ekert. Method for direct detection of qu antum entanglement. Phys. Rev. Lett., 89:127902, 2002

2002
[45]

W. C. Myrvold. The decision problem for entanglement. In R. S. C ohen, M. Horne, and J. Stachel, editors, Potentiality, entanglement and passion-at-a-distance , pages 177–190. Kluwer Academic Publishers, 1997

1997
[46]

Weihrauch

K. Weihrauch. Computability. Springer-Verlag, Berlin, 1987

1987
[47]

Seidenberg

A. Seidenberg. A new decision method for elementary algebra. Annals of Mathematics , 60(2):365–374, 1954

1954
[48]

A decision method for elementary algebra and geo metry

Alfred Tarski. A decision method for elementary algebra and geo metry. Technical report, University of California, Berkeley, 1951

1951
[49]

On t he combinatorial and algebraic complexity of quantiﬁer elimination

Saugata Basu, Richard Pollack, and Marie-Fran¸ coise Roy. On t he combinatorial and algebraic complexity of quantiﬁer elimination. Journal of the ACM , 43(6):1002–1045, 1996

1996
[50]

Gr¨ otschel, L

M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver. Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin, 1988. ISBN 038713624x. LA WRENCE M. IOANNOU 35

1988
[51]

L. Gurvits. Classical deterministic complexity of Edmonds’ prob lem and quantum en- tanglement. In Proceedings of the thirty-ﬁfth ACM symposium on Theory of co mputing, pages 10–19, New York, 2003. ACM Press

2003
[52]

The complexity of separability testing

Kristopher Luttmer. The complexity of separability testing. Ma ster’s thesis, University of Calgary, 2005

2005
[53]

Garey and David S

Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the theory of NP-completeness . W.H. Freeman and Company, New York, 1979

1979
[54]

C. H. Papadimitriou, editor. Computational complexity . Addison Wesley Longman, Reading, Massachusetts, 1994

1994
[55]

Nielsen and I

M. Nielsen and I. Chuang. Quantum Computation and Quantum Information . Cambridge University Press, Cambridge, 2000

2000
[56]

Ladner, N

R. Ladner, N. Lynch, and A. Selman. Comparison of polynomial-t ime reducibilities. Theoretical Computer Science , 1:103–123, 1975

1975
[57]

A two-way algorithm for the ent anglement problem

Florian Hulpke and Dagmar Bruß. A two-way algorithm for the ent anglement problem. J. Phys. A: Math. Gen. , 38:5573, 2005

2005
[58]

Nonlinear entanglement witnesses

Otfried G¨ uhne and Norbert L¨ utkenhaus. Nonlinear entanglement witnesses. Phys. Rev. Lett., 96:170502, 2006

2006
[59]

Aaronson

S. Aaronson. Private communication. 2005

2005
[60]

Ben-Tal and A

A. Ben-Tal and A. Nemirovskii. Robust convex optimization. Mathematics of Operational Research, 23(4):769–805, 1998

1998
[61]

L. Gurvits. Private communication. 2006

2006
[62]

Gurvits and H

L. Gurvits and H. Barnum. Better bound on the exponent of th e radius of the multipartite separable ball. Phys. Rev. A , 72:032322, 2005

2005
[63]

T. S. Motzkin and E. G. Straus. Maxima for graphs and a new pro of of a theorem of tur´ an.Canadian J. Math. , 17:533–540, 1965

1965
[64]

Atkinson and Pravin M

David S. Atkinson and Pravin M. Vaidya. A cutting plane algorithm f or convex pro- gramming that uses analytic centers. Mathematical Programming, 69:1–43, 1995

1995
[65]

Pavan and Alan L

A. Pavan and Alan L. Selman. Separation of NP-completeness no tions. SIAM J. Comput. , 31(3):906–918, 2001

2001
[66]

A. Pavan. Comparison of reductions and completeness notions . SIGACT News, 40, 2003

2003
[67]

Geometry of separable states

Ingemar Bengtsson and Karol Zyczkowski. Geometry of separable states . Cambridge University Press, Cambridge, 2006

2006
[68]

L. M. Ioannou. Computing ﬁnite-dimensional bipartite quantum separability, 2005. PhD thesis, available at http://arXiv.org/abs/cs/0504110. 36 COMPUTATIONAL COMPLEXITY OF THE QUANTUM SEPARABILITY PROB LEM

2005 arXiv
[69]

Pisier, editor

G. Pisier, editor. The volume of convex bodies and Banach space geometry . Cambridge University Press, Cambridge, 1989

1989
[70]

A de Finetti representatio n for ﬁnite symmetric quantum states

Robert K¨ onig and Renato Renner. A de Finetti representatio n for ﬁnite symmetric quantum states. J. Math. Phys. , 46:122102, 2005

2005
[71]

P´ erez-Garcia and I

D. P´ erez-Garcia and I. Cirac. Private communication. 2006

2006
[72]

Horn and Charles R

Roger A. Horn and Charles R. Johnson. Matrix Analysis . Cambridge University Press, Cambridge, 1985

1985
[73]

A separability criterion for density operators

Oliver Rudolph. A separability criterion for density operators. J. Phys. A , 33:3951–3955, 2000

2000
[74]

Deciding sepability with a ﬁxed error

David P´ erez-Garcia. Deciding sepability with a ﬁxed error. Phys. Lett. A , 330:149–154, 2004

2004
[75]

Y. Ye. Interior Point Algorithms: Theory and Analysis . John Wiley and Sons, Inc., New York, 1997

1997
[76]

Zapatrin

Rom` an R. Zapatrin. An asymptotical separability criterion for bipartite density opera- tors, 2005. quant-ph/0504169

2005 arXiv
[77]

Zapatrin

Rom` an R. Zapatrin. A note on continuous ensemble expansions of quantum states, 2004. quant-ph/0403105

2004 arXiv
[78]

Zapatrin

Rom` an R. Zapatrin. Continuous optimal ensembles i: A geometr ical characterization of robustly separable quantum states, 2005. quant-ph/0503173

2005 arXiv
[79]

Zapatrin

Rom` an R. Zapatrin. Continuous optimal ensembles ii: Reducing t he separability condi- tion to numerical equations, 2005. quant-ph/0504034

2005 arXiv
[80]

R. H. Hardin, N. J. A. Sloane, and W. D. Smith. Spherical Codes. In preparation, see http://www.research.att.com/∼njas/coverings/index.html
[81]

Horst and P

R. Horst and P. Pardalos, editors. Handbook of Global Optimization . Kluwer Academic Publishers, Dordrecht, 1995

1995
[82]

E. Hansen. Global Optimization Using Interval Analysis . Marcel Dekker Incorporated, Boston, 1992. ISBN 0824786963

1992

Pith tools

Reviewed August 28, 2026 · model on record in the stance chip above.

[1] [1]

A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri. Distinguishing se parable and entangled states. Phys. Rev. Lett. , 88:187904, 2002

2002

[2] [2]

A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri. Complete family o f separability criteria. Phys. Rev. A , 69:022308, 2004

2004

[3] [3]

One-and-a-half quantum de Finetti theorems

M. Christandl, R. K¨ onig, G. Mitchison, and R. Renner. One-and- a-half quantum de ﬁnetti theorems, 2006. quant-ph/0602130

work page Pith review arXiv 2006

[4] [4]

L. M. Ioannou, B. C. Travaglione, D. C. Cheung, and A. K. Ekert . Improved algorithm for quantum separability and entanglement detection. Phys. Rev. A , 70:060303(R), 2004

work page 2004

[5] [5]

L. M. Ioannou and B. C. Travaglione. Quantum separability and en tanglement detection via entanglement-witness search and global optimization. Phys. Rev. A , 73:052314, 2006

work page 2006

[6] [6]

Horodecki

P. Horodecki. Separability criterion and inseparable mixed states with positive partial transposition. Phys. Lett. A , 232:333, 1997

1997

[7] [7]

Characterizing entanglement

Dagmar Bruß. Characterizing entanglement. J. Math. Phys. , 43:4237, 2002

work page 2002

[8] [8]

B. M. Terhal. Detecting quantum entanglement. Journal Theoretical Computer Science , 287(1):313–335, 2002

work page 2002