Formalize Open Quantum Problem #44: Complexity of the separability problem

[MarioKrenn6240]

What is the conjecture

This is problem #44 in the Open Quantum Problems collection, a later addition to Reinhard F. Werner’s original open-problems project.

This is one of the OQP items that is most naturally phrased as an open complexity-classification problem rather than a single yes/no conjecture.

Problem (Open Quantum Problem #44: “Complexity of the separability problem”).
Let Sep(d,d) denote the set of separable density matrices on ℂ^d ⊗ ℂ^d.
Given a bipartite mixed state ρ, promised either that ρ ∈ Sep(d,d) or that ρ is at least ε away in trace distance from every separable state, determine the computational complexity of deciding which case holds as a function of d and ε.

A standard formalization is as an ε-weak membership problem for the convex set of separable states:

• Fix the bipartite Hilbert space ℂ^d ⊗ ℂ^d.
• Let D(d,d) be the set of density operators on ℂ^d ⊗ ℂ^d (positive semidefinite, trace 1).
• Let
  Sep(d,d) = conv { α ⊗ β : α, β are density operators on ℂ^d }.
• Define the trace-distance-to-separable-set by
  dist_tr(ρ, Sep(d,d)) := inf_{σ ∈ Sep(d,d)} (1/2) * ||ρ - σ||_1.

Then the promise problem is:

• Input: a density matrix ρ ∈ D(d,d) (given classically by its d^2 × d^2 matrix entries) and a parameter ε > 0.
• YES case: ρ ∈ Sep(d,d).
• NO case: dist_tr(ρ, Sep(d,d)) ≥ ε.
• Promise: one of the two cases above holds.

The main open problem is:

• Complexity question: determine the computational complexity of this promise problem as a function of the local dimension d and the accuracy parameter ε.

The OQP page also highlights why this matters:

• The separability problem is tightly connected to quantum proof systems with unentangled witnesses, especially QMA(2).
• If for some constant ε > 0 there were a quasipolynomial-time algorithm (roughly d^{O(log d)}) for this trace-norm weak membership problem, then QMA(2) ⊆ EXP.
• If such an algorithm also admitted a sufficiently parallel implementation, then QMA(2) ⊆ PSPACE.

The OQP page also records benchmark partial results / nearby relaxations:

• ε-weak membership for Sep(d,d) is NP-hard for inverse-polynomial ε.
• There is a quasipolynomial-time algorithm for related weak-membership formulations where distance is measured in LOCC norm (and also Euclidean norm), rather than trace norm.
• A related optimization problem,
  max_{σ ∈ Sep(d,d)} Tr(Qσ),
  admits algorithms whose runtime can depend exponentially on the Frobenius norm ||Q||_F.

Where to find the details / references

Primary sources:

• Open Quantum Problems site (Problem #44)
• Open Quantum Problems master list (for numbering/metadata)
• For background on the original OQP project (note that the 2005 snapshot only covers Problems 1–29):
  O. Krüger & R. F. Werner, “Some Open Problems in Quantum Information Theory”:
  https://arxiv.org/abs/quant-ph/0504166

Key related references (as listed on the OQP page):

• H. Blier & A. Tapp, “All languages in NP have very short quantum proofs” (2009; arXiv:0709.0738)
• S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor, “The power of unentanglement” (Theory Comput. 5 (2009); arXiv:0804.0802)
• J. Chen & A. Drucker, “Short multi-prover quantum proofs for SAT without entangled measurements” (arXiv:1011.0716)
• A. W. Harrow & A. Montanaro, “Testing product states, quantum Merlin-Arthur games and tensor optimisation” (J. ACM 60(1), 2013; arXiv:1001.0017)
• L. Gurvits, “Classical deterministic complexity of Edmonds’ problem and quantum entanglement” (STOC 2003; arXiv:quant-ph/0303055)
• S. Gharibian, “Strong NP-hardness of the quantum separability problem” (Quantum Inf. Comput. 10, 343–360 (2010); arXiv:0810.4507)
• F. G. S. L. Brandão, M. Christandl, and J. Yard, “A quasipolynomial-time algorithm for the quantum separability problem” (STOC 2011; arXiv:1011.2751)
• Y. Shi & X. Wu, “Epsilon-net method for optimizations over separable states” (Theor. Comput. Sci. 598, 51–63 (2015); arXiv:1112.0808)

(Useful background survey, not explicitly listed on the OQP page but very helpful for formalization context:)

• L. M. Ioannou, “Computational complexity of the quantum separability problem” (Quantum Inf. Comput. 7(4), 335–370 (2007); arXiv:quant-ph/0603199)

Prerequisites needed

• Finite-dimensional quantum mechanics: density matrices, tensor products, partial traces
• Separability vs entanglement; convex decompositions into product states
• Matrix analysis: positivity, trace norm / Schatten 1-norm, Frobenius norm
• Convex geometry / optimization: convex hulls, distance to a convex set, weak membership vs weak optimization
• Classical complexity theory: decision and promise problems, polynomial vs quasipolynomial time, NP-hardness
• Quantum complexity theory: QMA, QMA(2), unentangled witnesses, LOCC measurements
• (Optional) Semidefinite programming and symmetric-extension hierarchies

AMS categories

• ams-81 (Quantum theory)
• ams-68 (Computer science)
• ams-52 (Convex and discrete geometry)
• ams-94 (Information and communication theory)

Choose either option

• I plan on adding this conjecture to the repository
• This issue is up for grabs: I would like to see this conjecture added by somebody else