For every constant ε>0, we give an exp(Õ(∞n))-time algorithm for the 1 vs 1 - ε Best Separable State (BSS) problem of distinguishing, given an n2 x n2 matrix ℳ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state ρ that ℳ accepts with probability 1, and the case that every separable state is accepted with probability at most 1 - ε. Equivalently, our algorithm takes the description of a subspace 𝒲 ⊆ 𝔽n2 (where 𝔽 can be either the real or complex field) and distinguishes between the case that contains a rank one matrix, and the case that every rank one matrix is at least ε far (in 𝓁2 distance) from 𝒲.
For every constant ε>0, we give an exp(Õ(∞n))-time algorithm for the 1 vs 1 - ε Best Separable State (BSS) problem of distinguishing, given an n2 x n2 matrix ℳ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state ρ that ℳ accepts with probability 1, and the case that every separable state is accepted with probability at most 1 - ε. Equivalently, our algorithm takes the description of a subspace 𝒲 ⊆ 𝔽n2 (where 𝔽 can be either the real or complex field) and distinguishes between the case that contains a rank one matrix, and the case that every rank one matrix is at least ε far (in 𝓁2 distance) from 𝒲.
We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states. In classical terms, the goal is to maximize ⟨(x⊗y),M(x⊗y)⟩ over unit vectors x,y where 0⪯M⪯I; we call this value BSS(M). We study BSS in the "perfect completeness" regime, where given M such that BSS(M)=1 the goal is to find the best possible solution x,y -- this generalizes the problem of finding a rank-one matrix as close as possible to a given subspace of Rn×n guaranteed to contain a rank-one matrix. The strongest known algorithmic guarantees for this problem are: (1) an algorithm which finds a solution with value 1−ε in time exp(n(logn)O(1)/ε2), due to Barak, Kothari, and Steurer, and (2) an algorithm which finds a solution with value q/n in time roughly nO(q), due to Bhattiprolu, Ghosh, Guruswami, Lee, and Tulsiani. We give a much simpler approach to rounding the SoS relaxation, generalizing the canonical "global correlation rounding" technique, and obtain a better running time. Given M with BSS(M)=1, our algorithm finds a solution with value 1−ε in time nO(n/ε), and a solution of value q/n in time nO(q). Using the same techniques, we prove a new variant of the "pinning lemma", a measure-decomposition theorem widely used in LP/SDP rounding, high-dimensional probability, and statistical physics, which we believe is of independent interest.
For every ε>0, we give an exp(O~(n/ε2))-time algorithm for the 1 vs 1−ε \emph{Best Separable State (BSS)} problem of distinguishing, given an n2×n2 matrix M corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state ρ that M accepts with probability 1, and the case that every separable state is accepted with probability at most 1−ε. Equivalently, our algorithm takes the description of a subspace W⊆Fn2 (where F can be either the real or complex field) and distinguishes between the case that W contains a rank one matrix, and the case that every rank one matrix is at least ε far (in ℓ2 distance) from W. To the best of our knowledge, this is the first improvement over the brute-force exp(n)-time algorithm for this problem. Our algorithm is based on the \emph{sum-of-squares} hierarchy and its analysis is inspired by Lovett's proof (STOC '14, JACM '16) that the communication complexity of every rank-n Boolean matrix is bounded by O~(n).
The quantum separability problem asks whether a bipartite density matrix is separable or is η-far from every separable state. We give a randomized polynomial-time algorithm for this problem for every fixed constant gap η>0, when distance is measured in the Euclidean norm.
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.
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 ε-away from the set of the separable states in time exp(O(ε-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.
A key concept in quantum information theory is the notion of separable states; states for which there is no quantum entanglement.Determining if a given state is entangled has been shown to be NP-hard, and so no deterministic and efficient algorithm will likely be created for this purpose.Current tests are either computationally intensive , return false positives or worsen as the dimension of the problem grows larger.These large dimensions arise naturally in quantum computing.It is therefore necessary to develop a reliable test that is naturally scalable to higher dimensions if one wishes to create efficient quantum computers.Using random matrix theory, a new algorithm has been developed that, with high probability, can determine if a quantum state is separable or entangled.The purpose of this research is to implement this algorithm, checking its efficiency through numerical tests, as well as testing the limitations of the theory behind it.