A quasipolynomial-time algorithm for the quantum separability problem

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.

9 pages, no figures; to appear in proceedings STOC '11

References in corpus (16)

• Quantum entanglement
• Quantifying Entanglement
• Monogamy of entanglement and other correlations
• "Squashed Entanglement" - An Additive Entanglement Measure
• A complete family of separability criteria
• Aspects of generic entanglement
• Quantum Data Hiding
• Randomizing quantum states: Constructions and applications
• N-representability is QMA-complete
• One-and-a-half quantum de Finetti theorems
• Hiding classical data in multi-partite quantum states
• Optimal quantum source coding with quantum information at the encoder and decoder
• A Generalization of Quantum Stein's Lemma
• Hiding Quantum Data
• Testing product states, quantum Merlin-Arthur games and tensor optimisation
• Finite size mean-field models

Cited by in corpus (16)

• Quantum Resource Theories
• Computing quantum discord is NP-complete
• Hypercontractivity, Sum-of-Squares Proofs, and their Applications
• A Separability-Entanglement Classifier via Machine Learning
• 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
• Approximate quantum Markov chains
• Testing symmetry on quantum computers
• The Complexity of the Separable Hamiltonian Problem
• Large-$d$ phase transitions in holographic mutual information
• Two-message quantum interactive proofs and the quantum separability problem
• Dvoretzky's Theorem and the Complexity of Entanglement Detection
• Probabilistic state synthesis based on optimal convex approximation
• De Finetti Theorems for Braided Parafermions
• A de Finetti theorem for quantum causal structures
• Local Purity Distillation in Quantum Systems: Exploring the Complementarity Between Purity and Entanglement