Source-linked AI summary
A quasipolynomial-time algorithm for the quantum separability problem
Fernando G. S. L. Brandao, Matthias Christandl, Jon Yard
TL;DR
The paper addresses the computational difficulty of deciding separability and optimizing over separable bipartite states. It uses semidefinite programming with symmetric extensions and an improved de Finetti bound. The resulting algorithms run in quasipolynomial time, while the techniques also yield QMA characterizations and related entanglement results.
Problem
The paper studies how to decide whether a bipartite density matrix is separable or ε-away from the separable states, and how to optimize over that convex set.
Source: §1 · p. 1Method
The algorithm searches for symmetric extensions using semidefinite programming and relies on an improved de Finetti-type bound derived from conditional mutual information.
Source: §2 · pp. 2, 3, 5Results
WSEP for the Euclidean and LOCC norms is solvable in quasipolynomial time, and the work also gives improved BSS algorithms and new QMA characterizations.
Source: §2 · pp. 2–3Takeaways & Limitations
Multiple unentangled proofs do not increase QMA power when verification uses suitable LOCC protocols, yielding a characterization of QMA.
Source: §2 · p. 3Whether a comparable hardness result holds for LOCC measurements remains open, so optimality of the algorithm under exponential-time SAT assumptions is unresolved.
Source: §2 · p. 3
Abstract
from arXiv · showhide
We present a quasipolynomial-time algorithm for solving the weak membership problem for the convex set of separable, i.e. non-entangled, bipartite density matrices. The algorithm decides whether a density matrix is separable or whether it is eps-away from the set of the separable states in time exp(O(eps^-2 log |A| log |B|)), where |A| and |B| are the local dimensions, and the distance is measured with either the Euclidean norm, or with the so-called LOCC norm. The latter is an operationally motivated norm giving the optimal probability of distinguishing two bipartite quantum states, each shared by two parties, using any protocol formed by quantum local operations and classical communication (LOCC) between the parties. We also obtain improved algorithms for optimizing over the set of separable states and for computing the ground-state energy of mean-field Hamiltonians. The techniques we develop are also applied to quantum Merlin-Arthur games, where we show that multiple provers are not more powerful than a single prover when the verifier is restricted to LOCC protocols, or when the verification procedure is formed by a measurement of small Euclidean norm. This answers a question posed by Aaronson et al (Theory of Computing 5, 1, 2009) and provides two new characterizations of the complexity class QMA, a quantum analog of NP. Our algorithm uses semidefinite programming to search for a symmetric extension, as first proposed by Doherty, Parrilo and Spedialieri (Phys. Rev. A, 69, 022308, 2004). The bound on the runtime follows from an improved de Finetti-type bound quantifying the monogamy of quantum entanglement, proved in (arXiv:1010.1750). This result, in turn, follows from a new lower bound on the quantum conditional mutual information and the entanglement measure squashed entanglement.
1. INTRODUCTION
The introduction frames separability testing and optimization as central computational problems in quantum information, connecting them to entanglement theory and quantum complexity.
Entanglement background
- The introduction situates separability as a convex-geometric problem over normalized Hermitian matrices, with entanglement characterized by failure to decompose into product states.Entanglement witnesses provide Hermitian operators that separate an entangled state from all separable states.Source: §1 · pp. 1–2
Separability and weak membership
- Weak membership asks whether a bipartite density matrix is separable or at least ε-distant from the separable-state set under a chosen norm.Separable states are convex combinations of product states and contain only classical correlations, whereas nonseparable states are entangled.Source: §1 · p. 1
- The problem is studied using the Euclidean and trace norms, with prior algorithms having worst-case exponential complexity.The trace norm and Euclidean norm are related by dimension-dependent inequalities, so results for one can inform the other.Source: §1 · pp. 1–2
Optimization over separable states
- Best Separable State optimization estimates the maximum of tr(Mσ) over separable states and is equivalent to weak membership up to polynomial losses in accuracy.Its applications include entanglement-witness optimization, mean-field ground-state energies, and minimum channel min-entropy.Source: §1 · p. 2
Quantum complexity
- BSS is also connected to QMA(2), because the optimal acceptance probability of a two-proof quantum protocol can be expressed as a BSS instance.QMA is the quantum analogue of NP, while QMA(2) supplies two proofs that are not entangled with one another.Source: §1 · p. 2
2. RESULTS
The paper develops quasipolynomial algorithms for separability and related optimization problems, then applies the same techniques to characterize QMA under restricted verification measurements.
Separability algorithms
- WSEP(ε, ∥*∥2) and WSEP(ε, ∥*∥LOCC) admit quasipolynomial-time algorithms, with LOCC distance reflecting distinguishability by local operations and classical communication.The LOCC norm is operationally motivated and is relevant to applications such as Bell-inequality violation and teleportation.Source: §2 · p. 2
- The separability algorithm uses semidefinite programming to search for symmetric extensions, building on an improved de Finetti-type bound.The bound quantifies how monogamy limits entanglement in highly extendible states.Source: §2 · pp. 2–3
Optimization applications
- The same method yields a quasipolynomial-time algorithm for Best Separable State and an algorithm for the ground-state energy of mean-field Hamiltonians.Mean-field ground-state computation is equivalent to minimizing tr(σK) over separable states.Source: §2 · pp. 2–3
Limitations and open questions
- For LOCC measurements, matching hardness is unknown, so optimality of the algorithm would require a corresponding hardness result.The paper notes that the available hardness construction uses operators that need not be implementable by LOCC.Source: §2 · p. 3
Entanglement structure
- Highly extendible states that remain far from separable states in trace norm must be data-hiding states, nearly indistinguishable from separable states by LOCC measurements.This connects the improved de Finetti bound to operational limitations of LOCC protocols.Source: §2 · p. 3
Quantum Merlin-Arthur games
- QMA equals the class using polynomially many unentangled proofs verified by polynomial-time implementable LOCC measurements, answering an open question of Aaronson et al. [1].The paper also gives a QMA characterization using measurements whose no-instance operators have polynomially bounded Euclidean norm.Source: §2 · pp. 3–4
- The LOCC characterization remains bounded to constant numbers of proofs because recursive reductions incur quadratic proof-size blowup.Whether the results extend to nonconstant k, such as k = O(poly(n)), remains open.Source: §2 · p. 4
Entanglement structure
- The new conditional-mutual-information bound implies that squashed entanglement is faithful, being strictly positive for every entangled state.The result resolves a longstanding conjecture in entanglement theory.Source: §2 · p. 5
3. PROOFS
The proofs reduce separability testing and related optimization problems to semidefinite programs over symmetric extensions. Improved entanglement bounds establish soundness, while recursive simulations derive the complexity-theoretic consequences.
Theorem 3
- Theorem 3 combines new entanglement inequalities, including a squashed-entanglement monogamy relation, to control how close k-extendible states can be to separable states.Its proof chains inequalities involving conditional mutual information, hypothesis-testing distinguishability, and one-way LOCC distance.Source: §3 · pp. 5–7
Theorem 1
- Separability testing is formulated as an SDP searching for a positive semidefinite symmetric extension whose marginals are bounded by a regularized input state.The input is mixed with the maximally mixed state before solving the program.Source: §3 · p. 5
- If the input is separable, convexity supplies a symmetric extension and the SDP value remains near one; if it is ε-away, the entanglement bound forces the value below one by Ω(ε).The algorithm uses an approximate feasible region and ellipsoid optimization with k = O(ε^-2 log |A|) in the soundness analysis.Source: §3 · p. 5
Theorem 2
- Choosing k = O(ε^-2 log |A|) lets an SDP over k-extendible states approximate Best Separable State within additive ε.The same framework handles LOCC measurements and, via Cauchy–Schwarz, general Hermitian operators.Source: §3 · p. 6
Quantum Merlin–Arthur applications
- The LOCC proof converts multi-prover protocols into single-prover QMA protocols by requesting a symmetric extension, preserving completeness while increasing soundness by at most ℓε.Each reduction step causes a quadratic proof-size blowup, so recursive application is limited to a constant number of rounds before standard QMA amplification.Source: §3 · p. 6
- The small-Euclidean-norm verification result uses the same symmetric-extension strategy, while the converse QMA inclusion follows from Marriott–Watrous error reduction.The resulting measurement has exponentially small Euclidean norm on no-instances.Source: §3 · p. 6