Physics – Quantum Physics
Scientific paper
2010-11-11
Proceedings of ACM Symposium on Theory of Computation (STOC'11), June 2011, p. 343-351
Physics
Quantum Physics
9 pages, no figures; to appear in proceedings STOC '11
Scientific paper
10.1145/1993636.1993683
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.
Brandao Fernando G. S. L.
Christandl Matthias
Yard Jon
No associations
LandOfFree
A quasipolynomial-time algorithm for the quantum separability problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A quasipolynomial-time algorithm for the quantum separability problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A quasipolynomial-time algorithm for the quantum separability problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-202875