A quasipolynomial-time algorithm for the quantum separability problem
From MaRDI portal
Abstract: 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.
Recommendations
Cited in
(27)- Optimal separation in exact query complexities for Simon's problem
- Limitations of semidefinite programs for separable states and entangled games
- Deterministic polynomial-time quantum algorithms for Simon's problem
- Classical complexity and quantum entanglement
- Schur-Weyl duality for the Clifford group with applications: property testing, a robust Hudson theorem, and de Finetti representations
- The sum-of-squares hierarchy on the sphere and applications in quantum information theory
- De Finetti theorems for braided parafermions
- Quantum de Finetti theorems under local measurements with applications
- A successive approximation method for quantum separability
- Exponential decay of correlations implies area law
- Epsilon-net method for optimizations over separable states
- Quantum interactive proofs and the complexity of separability testing
- Strong NP-hardness of the quantum separability problem
- Computational complexity of the quantum separability problem
- scientific article; zbMATH DE number 1303028 (Why is no real title available?)
- scientific article; zbMATH DE number 1748602 (Why is no real title available?)
- Linear-Time Algorithm for Quantum 2SAT
- Dvoretzky's theorem and the complexity of entanglement detection
- Epsilon-net method for optimizations over separable states
- Quantum entanglement, sum of squares, and the log rank conjecture
- Computing quantum discord is NP-complete
- An improved semidefinite programming hierarchy for testing entanglement
- scientific article; zbMATH DE number 6789292 (Why is no real title available?)
- Quantum free games
- Faithful squashed entanglement
- Optimizing entanglement manipulation via algebraic-geometric decompositions and semi-definite programming hierarchies
- Large-d phase transitions in holographic mutual information
This page was built for publication: A quasipolynomial-time algorithm for the quantum separability problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419104)
