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

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

Sevag Gharibian

Published Sep 18, 2008• 0 citations
OpenAlex

Abstract

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.

Related papers

Strong NP-hardness of the quantum separability problem

Sevag Gharibian

Given the density matrix $\rho$ of a bipartite quantum state, the quantum separability problem asks whether $\rho$ is entangled or separable. In 2003, Gurvits showed that this problem is NP-hard if $\rho$ is located within an inverse exponential (with respect to dimension) distance from the border of the set of separable quantum states. In this paper, we extend this NP-hardness to an inverse polynomial distance from the separable set. The result follows from a simple combination of works by Gurvits, Ioannou, and Liu. We apply our result to show (1) an immediate lower bound on the maximum distance between a bound entangled state and the separable set (assuming $\rm{P}\neq\rm{ NP}$), and (2) NP-hardness for the problem of determining whether a completely positive trace-preserving linear map is entanglement-breaking.

Quantum Information and Computation•Mar 1, 2010•236 citations

Strong NP-Hardness of the Quantum Separability Problem

Sevag Gharibian

Given the density matrix rho of a bipartite quantum state, the quantum separability problem asks whether rho is entangled or separable. In 2003, Gurvits showed that this problem is NP-hard if rho is located within an inverse exponential (with respect to dimension) distance from the border of the set of separable quantum states. In this paper, we extend this NP-hardness to an inverse polynomial distance from the separable set. The result follows from a simple combination of works by Gurvits, Ioannou, and Liu. We apply our result to show (1) an immediate lower bound on the maximum distance between a bound entangled state and the separable set (assuming P != NP), and (2) NP-hardness for the problem of determining whether a completely positive trace-preserving linear map is entanglement-breaking.

arXiv:0810.4507•Oct 24, 2008•15 citations

Strong NP-hardness of the quantum separability problem

GharibianSevag

Given the density matrix ρ of a bipartite quantum state, the quantum separability prob-lem asks whether ρ is entangled or separable. In 2003, Gurvits showed that this problemis NP-hard if ρ is loca...

Quantum Information and Computation•Mar 1, 2010•42 citations

On global effects caused by locally noneffective unitary operations

Sevag Gharibian, Hermann Kampermann, D. Bruss

Given a bipartite quantum state $\rho$ with subsystems $A$ and $B$ of arbitrary dimensions, we study the entanglement detecting capabilities of locally noneffective, or cyclic, unitary operations [Fu, Europhys. Lett., vol. 75]. Local cyclic unitaries have the special property that they leave their target subsystem invariant. We investigate the distance between $\rho$ and the global state after local application of such unitaries as a possible indicator of entanglement. To this end, we derive and discuss closed formulae for the maximal such distance achievable for three cases of interest: (pseudo)pure quantum states, Werner states, and two-qubit states. What makes this criterion interesting, as we show here, is that it surprisingly displays behavior similar to recent anomalies observed for non-locality measures in higher dimensions, as well as demonstrates an equivalence to the CHSH inequality for certain classes of two-qubit states. Yet, despite these similarities, the criterion is not itself a non-locality measure. We also consider entanglement detection in bound entangled states.

arXiv:0809.4469•Quantum Information and Computation•Nov 1, 2009•15 citations

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

Complete entanglement detection using polynomial invariants

Thomas C. Fraser, Vjosa Blakaj, Roberto Rubboli +2 more

Existing methods for deciding whether a bipartite quantum state is separable or entangled typically fall into one of two categories: they are either complete but require access to an explicit density matrix followed by numerical optimization, or they can be evaluated directly by measuring the quantum system but are incomplete, in the sense that they cannot detect all forms of entanglement. In this work, we overcome both limitations in a unified framework. First, we bypass numerical optimization by deriving separability criteria in the form of universal bounds on tensor powers of separable states. We prove that these bounds are complete: every entangled state violates them for sufficiently large tensor powers. Second, we explicitly construct a corresponding complete family of nonlinear entanglement witnesses, which can detect all forms of entanglement without requiring an explicit density matrix. The witnesses we construct are moreover basis-independent, in the sense that they are invariant under conjugation by local unitaries. Altogether, our results expand the toolbox for entanglement detection in arbitrary local dimensions in a manifestly invariant way.

quant-pharXiv:2606.16712•Jun 16, 2026•0 citations
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.
Given the density matrix ρ\rhoρ of a bipartite quantum state, the quantum separability problem asks whether ρ\rhoρ is entangled or separable. In 2003, Gurvits showed that this problem is NP-hard if ρ\rhoρ is located within an inverse exponential (with respect to dimension) distance from the border of the set of separable quantum states. In this paper, we extend this NP-hardness to an inverse polynomial distance from the separable set. The result follows from a simple combination of works by Gurvits, Ioannou, and Liu. We apply our result to show (1) an immediate lower bound on the maximum distance between a bound entangled state and the separable set (assuming P≠NP\rm{P}\neq\rm{ NP}P=NP), and (2) NP-hardness for the problem of determining whether a completely positive trace-preserving linear map is entanglement-breaking.
Given the density matrix rho of a bipartite quantum state, the quantum separability problem asks whether rho is entangled or separable. In 2003, Gurvits showed that this problem is NP-hard if rho is located within an inverse exponential (with respect to dimension) distance from the border of the set of separable quantum states. In this paper, we extend this NP-hardness to an inverse polynomial distance from the separable set. The result follows from a simple combination of works by Gurvits, Ioannou, and Liu. We apply our result to show (1) an immediate lower bound on the maximum distance between a bound entangled state and the separable set (assuming P != NP), and (2) NP-hardness for the problem of determining whether a completely positive trace-preserving linear map is entanglement-breaking.
Given a bipartite quantum state ρ\rhoρ with subsystems AAA and BBB of arbitrary dimensions, we study the entanglement detecting capabilities of locally noneffective, or cyclic, unitary operations [Fu, Europhys. Lett., vol. 75]. Local cyclic unitaries have the special property that they leave their target subsystem invariant. We investigate the distance between ρ\rhoρ and the global state after local application of such unitaries as a possible indicator of entanglement. To this end, we derive and discuss closed formulae for the maximal such distance achievable for three cases of interest: (pseudo)pure quantum states, Werner states, and two-qubit states. What makes this criterion interesting, as we show here, is that it surprisingly displays behavior similar to recent anomalies observed for non-locality measures in higher dimensions, as well as demonstrates an equivalence to the CHSH inequality for certain classes of two-qubit states. Yet, despite these similarities, the criterion is not itself a non-locality measure. We also consider entanglement detection in bound entangled states.
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.
Existing methods for deciding whether a bipartite quantum state is separable or entangled typically fall into one of two categories: they are either complete but require access to an explicit density matrix followed by numerical optimization, or they can be evaluated directly by measuring the quantum system but are incomplete, in the sense that they cannot detect all forms of entanglement. In this work, we overcome both limitations in a unified framework. First, we bypass numerical optimization by deriving separability criteria in the form of universal bounds on tensor powers of separable states. We prove that these bounds are complete: every entangled state violates them for sufficiently large tensor powers. Second, we explicitly construct a corresponding complete family of nonlinear entanglement witnesses, which can detect all forms of entanglement without requiring an explicit density matrix. The witnesses we construct are moreover basis-independent, in the sense that they are invariant under conjugation by local unitaries. Altogether, our results expand the toolbox for entanglement detection in arbitrary local dimensions in a manifestly invariant way.