Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1011.2751 · ACM Symposium on Theory of Computing (STOC)

A quasipolynomial-time algorithm for the quantum separability problem

Fernando G. S. L. Brandão, Matthias Christandl, Jon Yard

Published Jun 6, 2011• 62 citations
arXivHTMLPDF

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 ε-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.

DOI
10.1145/1993636.1993683

Related papers

A subexponential-time algorithm for the quantum separability problem

Fernando G. S. L. Brandão, Matthias Christandl, Jon Yard

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.

•Nov 11, 2010•1 citation

Quantum proof systems and entanglement theory

Salman Abolfathe Beikidezfuli

Quantum complexity theory is important from the point of view of not only theory of computation but also quantum information theory. In particular, quantum multi-prover interactive proof systems are defined based on complexity theory notions, while their characterization can be formulated using LOCC operations. On the other hand, the main resource in quantum information theory is entanglement, which can be considered as a monotonic decreasing quantity under LOCC maps. Indeed, any result in quantum proof systems can be translated to entanglement theory, and vice versa. In this thesis I mostly focus on quantum Merlin-Arthur games as a proof system in quantum complexity theory. I present a new complete problem for the complexity class QMA. I also show that computing both the Holevo capacity and the minimum output entropy of quantum channels are NP-hard. Then I move to the multiple-Merlin-Arthur games and show that assuming some additivity conjecture for entanglement of formation, we can amplify the gap in QMA(2) protocols. Based on the same assumption, I show that the QMA(k)-hierarchy collapses to QMA(2). I also prove that QMAlog(2), which is defined the same as QMA(2) except that the size of witnesses is logarithmic, with the gap n-(3+e) contains NP. Finally, motivated by the previous results, I show that the positive partial transpose test gives no bound on the trace distance of a given bipartite state from the set of separable states.

•Jan 1, 2009•0 citations

On the Hardness of the Quantum Separability Problem and the Global Power of Locally Invariant Unitary Operations

Sevag Gharibian

Given a bipartite density matrix ρ of a quantum state, the Quantum Separability \nproblem (QUSEP) asks — is ρ entangled, or separable? In this thesis, we first \nstrengthen Gurvits’ 2003 NP-hardness result for QUSEP by showing that the Weak \nMembership problem over the set of separable bipartite quantum states is strongly \nNP-hard, meaning it is NP-hard even when the error margin is as large as inverse \npolynomial in the dimension, i.e. is “moderately large”. Previously, this NP-hardness was known only to hold in the case of inverse exponential error. We observe \nthe immediate implication of NP-hardness of the Weak Membership problem over the set of entanglement-breaking maps, as well as lower bounds on the maximum (Euclidean) distance possible between a bound entangled state and the separable set of quantum states (assuming P ≠ NP). \n \nWe next investigate the entanglement-detecting capabilities of locally invariant \nunitary operations, as proposed by Fu in 2006. Denoting the subsystems of ρ as \nA and B, such that ρ_B = Tr_A(ρ), a locally invariant unitary operation U^B is one \nwith the property U^B ρ_B (U^B)^† = ρ_B. We investigate the maximum shift (in Euclidean \ndistance) inducible in ρ by applying I⊗U^B, over all locally invariant choices of U^B. \nWe derive closed formulae for this quantity for three cases of interest: (pseudo)pure \nquantum states of arbitrary dimension, Werner states of arbitrary dimension, and \ntwo-qubit states. Surprisingly, similar to recent anomalies detected for non-locality \nmeasures, the first of these formulae demonstrates the existence of non-maximally \nentangled states attaining shifts as large as maximally entangled ones. Using the latter of these formulae, we demonstrate for certain classes of two-qubit states an equivalence between the Fu criterion and the CHSH inequality. Among other results, we investigate the ability of locally invariant unitary operations to detect bound entanglement.

•Sep 18, 2008•0 citations

Quantum State Local Distinguishability via Convex Optimization

Alessandro Cosentino

Entanglement and nonlocality play a fundamental role in quantum computing. To understand the interplay between these phenomena, researchers have considered the model of local operations and classical communication, or LOCC for short, which is a restricted subset of all possible operations that can be performed on a multipartite quantum system. The task of distinguishing states from a set that is known a priori to all parties is one of the most basic problems among those used to test the power of LOCC protocols, and it has direct applications to quantum data hiding, secret sharing and quantum channel capacity. The focus of this thesis is on state distinguishability problems for classes of quantum operations that are more powerful than LOCC, yet more restricted than global operations, namely the classes of separable and positive-partial-transpose (PPT) measurements. We \nbuild a framework based on convex optimization (on cone programming, in particular) to study such problems. Compared to previous approaches to the problem, the method described in this thesis provides precise numerical bounds and quantitative analytic results. By combining the duality theory of cone programming with the channel-state duality, we also establish a novel connection between the state distinguishability problem and the study of positive linear maps, which is a topic of independent interest in quantum information theory. \n \nWe apply our framework to several questions that were left open in previous works regarding the distinguishability of maximally entangled states and unextendable product sets. First, we exhibit small sets of orthogonal maximally entangled states in that are not perfectly distinguishable by LOCC. As a consequence of this, we show a gap between the power of PPT and separable measurements for the task of distinguishing sets consisting only of maximally entangled states. Furthermore, we prove tight bounds on the entanglement cost that is necessary to distinguish any sets of Bell states, thus showing that quantum teleportation is optimal for this task. Finally, we provide an easily checkable characterization of when an unextendable product set is perfectly discriminated by separable measurements, along with the first known example of an unextendable product set that cannot be perfectly discriminated by separable measurements.

•Aug 24, 2015•0 citations

Quantum Separability in Polynomial Time

Giulio Malavolta

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.

quant-pharXiv:2607.23773•Jul 28, 2026•3 citations

Quantum de finetti theorems under local measurements with applications

Fernando G. S. L. Brandão, Aram W. Harrow

Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements in each of the subsystems one can get a much improved error dependence on the dimension of the subsystems. We also obtain similar results for non-signaling probability distributions. We give the following applications of the results to quantum complexity theory, polynomial optimization, and quantum information theory: We prove the optimality of the Chen-Drucker protocol for 3-SAT, under the assumption there is no subexponential-time algorithm for SAT. In the protocol a prover sends to a verifier √n polylog(n) unentangled quantum states, each composed of O(log(n)) qubits, as a proof of the satisfiability of a 3-SAT instance with n variables and O(n) clauses. The quantum verifier checks the validity of the proof by performing local measurements on each of the proofs and classically processing the outcomes. We show that any similar protocol with O(n1/2 - ε) qubits would imply a exp (n1 - 2ε polylog(n))-time algorithm for 3-SAT. We show that the maximum winning probability of free games (in which the questions to each prover are chosen independently) can be estimated by linear programming in time exp(O(log|Q| + log2|A|/ε2) ), with |Q| and |A| the question and answer alphabet sizes, respectively, matching the performance of a previously known algorithm due to Aaronson, Impagliazzo, Moshkovitz, and Shor. This result follows from a new monogamy relation for non-locality, showing that k-extendible non-signaling distributions give at most a O(k-1/2) advantage over classical strategies for free games. We also show that 3-SAT with n variables can be reduced to obtaining a constant error approximation of the maximum winning probability under entangled strategies of O(√n)-player one-round non-local games, in which only two players are selected to send O(√n)-bit messages. We show that the optimization of certain polynomials over the complex hypersphere can be performed in quasipolynomial time in the number of variables $n$ by considering O(log(n)) rounds of the Sum-of-Squares (Parrilo/Lasserre) hierarchy of semidefinite programs. This can be considered an analogue to the hypersphere of a similar known results for the simplex. As an application to entanglement theory, we find a quasipolynomial-time algorithm for deciding multipartite separability. We consider a quantum tomography result due to Aaronson -- showing that given an unknown n-qubit state one can perform tomography that works well for most observables by measuring only O(n) independent and identically distributed (i.i.d.) copies of the state -- and relax the assumption of having i.i.d copies of the state to merely the ability to select subsystems at random from a quantum multipartite state. The proofs of the new quantum de Finetti theorems are based on information theory, in particular on the chain rule of mutual information. The results constitute improvements and generalizations of a recent de Finetti theorem due to Brandao, Christandl and Yard.

arXiv:1210.6367•ACM Symposium on Theory of Computing (STOC)•May 28, 2013•74 citations
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.
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.
Quantum complexity theory is important from the point of view of not only theory of computation but also quantum information theory. In particular, quantum multi-prover interactive proof systems are defined based on complexity theory notions, while their characterization can be formulated using LOCC operations. On the other hand, the main resource in quantum information theory is entanglement, which can be considered as a monotonic decreasing quantity under LOCC maps. Indeed, any result in quantum proof systems can be translated to entanglement theory, and vice versa. In this thesis I mostly focus on quantum Merlin-Arthur games as a proof system in quantum complexity theory. I present a new complete problem for the complexity class QMA. I also show that computing both the Holevo capacity and the minimum output entropy of quantum channels are NP-hard. Then I move to the multiple-Merlin-Arthur games and show that assuming some additivity conjecture for entanglement of formation, we can amplify the gap in QMA(2) protocols. Based on the same assumption, I show that the QMA(k)-hierarchy collapses to QMA(2). I also prove that QMAlog(2), which is defined the same as QMA(2) except that the size of witnesses is logarithmic, with the gap n-(3+e) contains NP. Finally, motivated by the previous results, I show that the positive partial transpose test gives no bound on the trace distance of a given bipartite state from the set of separable states.
Given a bipartite density matrix ρ of a quantum state, the Quantum Separability \nproblem (QUSEP) asks — is ρ entangled, or separable? In this thesis, we first \nstrengthen Gurvits’ 2003 NP-hardness result for QUSEP by showing that the Weak \nMembership problem over the set of separable bipartite quantum states is strongly \nNP-hard, meaning it is NP-hard even when the error margin is as large as inverse \npolynomial in the dimension, i.e. is “moderately large”. Previously, this NP-hardness was known only to hold in the case of inverse exponential error. We observe \nthe immediate implication of NP-hardness of the Weak Membership problem over the set of entanglement-breaking maps, as well as lower bounds on the maximum (Euclidean) distance possible between a bound entangled state and the separable set of quantum states (assuming P ≠ NP). \n \nWe next investigate the entanglement-detecting capabilities of locally invariant \nunitary operations, as proposed by Fu in 2006. Denoting the subsystems of ρ as \nA and B, such that ρ_B = Tr_A(ρ), a locally invariant unitary operation U^B is one \nwith the property U^B ρ_B (U^B)^† = ρ_B. We investigate the maximum shift (in Euclidean \ndistance) inducible in ρ by applying I⊗U^B, over all locally invariant choices of U^B. \nWe derive closed formulae for this quantity for three cases of interest: (pseudo)pure \nquantum states of arbitrary dimension, Werner states of arbitrary dimension, and \ntwo-qubit states. Surprisingly, similar to recent anomalies detected for non-locality \nmeasures, the first of these formulae demonstrates the existence of non-maximally \nentangled states attaining shifts as large as maximally entangled ones. Using the latter of these formulae, we demonstrate for certain classes of two-qubit states an equivalence between the Fu criterion and the CHSH inequality. Among other results, we investigate the ability of locally invariant unitary operations to detect bound entanglement.
Entanglement and nonlocality play a fundamental role in quantum computing. To understand the interplay between these phenomena, researchers have considered the model of local operations and classical communication, or LOCC for short, which is a restricted subset of all possible operations that can be performed on a multipartite quantum system. The task of distinguishing states from a set that is known a priori to all parties is one of the most basic problems among those used to test the power of LOCC protocols, and it has direct applications to quantum data hiding, secret sharing and quantum channel capacity. The focus of this thesis is on state distinguishability problems for classes of quantum operations that are more powerful than LOCC, yet more restricted than global operations, namely the classes of separable and positive-partial-transpose (PPT) measurements. We \nbuild a framework based on convex optimization (on cone programming, in particular) to study such problems. Compared to previous approaches to the problem, the method described in this thesis provides precise numerical bounds and quantitative analytic results. By combining the duality theory of cone programming with the channel-state duality, we also establish a novel connection between the state distinguishability problem and the study of positive linear maps, which is a topic of independent interest in quantum information theory. \n \nWe apply our framework to several questions that were left open in previous works regarding the distinguishability of maximally entangled states and unextendable product sets. First, we exhibit small sets of orthogonal maximally entangled states in that are not perfectly distinguishable by LOCC. As a consequence of this, we show a gap between the power of PPT and separable measurements for the task of distinguishing sets consisting only of maximally entangled states. Furthermore, we prove tight bounds on the entanglement cost that is necessary to distinguish any sets of Bell states, thus showing that quantum teleportation is optimal for this task. Finally, we provide an easily checkable characterization of when an unextendable product set is perfectly discriminated by separable measurements, along with the first known example of an unextendable product set that cannot be perfectly discriminated by separable measurements.
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η>0η>0, when distance is measured in the Euclidean norm.
Quantum de Finetti theorems are a useful tool in the study of correlations in quantum multipartite states. In this paper we prove two new quantum de Finetti theorems, both showing that under tests formed by local measurements in each of the subsystems one can get a much improved error dependence on the dimension of the subsystems. We also obtain similar results for non-signaling probability distributions. We give the following applications of the results to quantum complexity theory, polynomial optimization, and quantum information theory: We prove the optimality of the Chen-Drucker protocol for 3-SAT, under the assumption there is no subexponential-time algorithm for SAT. In the protocol a prover sends to a verifier √n polylog(n) unentangled quantum states, each composed of O(log(n)) qubits, as a proof of the satisfiability of a 3-SAT instance with n variables and O(n) clauses. The quantum verifier checks the validity of the proof by performing local measurements on each of the proofs and classically processing the outcomes. We show that any similar protocol with O(n1/2 - ε) qubits would imply a exp (n1 - 2ε polylog(n))-time algorithm for 3-SAT. We show that the maximum winning probability of free games (in which the questions to each prover are chosen independently) can be estimated by linear programming in time exp(O(log|Q| + log2|A|/ε2) ), with |Q| and |A| the question and answer alphabet sizes, respectively, matching the performance of a previously known algorithm due to Aaronson, Impagliazzo, Moshkovitz, and Shor. This result follows from a new monogamy relation for non-locality, showing that k-extendible non-signaling distributions give at most a O(k-1/2) advantage over classical strategies for free games. We also show that 3-SAT with n variables can be reduced to obtaining a constant error approximation of the maximum winning probability under entangled strategies of O(√n)-player one-round non-local games, in which only two players are selected to send O(√n)-bit messages. We show that the optimization of certain polynomials over the complex hypersphere can be performed in quasipolynomial time in the number of variables nnn by considering O(log(n)) rounds of the Sum-of-Squares (Parrilo/Lasserre) hierarchy of semidefinite programs. This can be considered an analogue to the hypersphere of a similar known results for the simplex. As an application to entanglement theory, we find a quasipolynomial-time algorithm for deciding multipartite separability. We consider a quantum tomography result due to Aaronson -- showing that given an unknown n-qubit state one can perform tomography that works well for most observables by measuring only O(n) independent and identically distributed (i.i.d.) copies of the state -- and relax the assumption of having i.i.d copies of the state to merely the ability to select subsystems at random from a quantum multipartite state. The proofs of the new quantum de Finetti theorems are based on information theory, in particular on the chain rule of mutual information. The results constitute improvements and generalizations of a recent de Finetti theorem due to Brandao, Christandl and Yard.