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 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 the density matrix ρ of a bipartite quantum state, the quantum separability problem asks whether ρ is entangled or separable. In 2003, Gurvits showed that this problem is NP-hard if ρ 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 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.
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or separable, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper’s main focus. I then give a thorough treatment of the problem’s relationship with NP, NP-completeness, and co-NP. I also discuss extensions of Gurvits ’ NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem [1, 2, 3]; and the entanglement-witness search (via interior-point algorithms and global optimization) [4, 5]. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or \emph{separable}, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with NP, NP-completeness, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem \cite{DPS02,DPS04,qphCKMR06}; and the entanglement-witness search (via interior-point algorithms and global optimization) \cite{ITCE04,IT06}. These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.
Ever since entanglement was identified as a computational and cryptographic resource, researchers have sought efficient ways to tell whether a given density matrix represents an unentangled, or separable, state. This paper gives the first systematic and comprehensive treatment of this (bipartite) quantum separability problem, focusing on its deterministic (as opposed to randomized) computational complexity. First, I review the one-sided tests for separability, paying particular attention to the semidefinite programming methods. Then, I discuss various ways of formulating the quantum separability problem, from exact to approximate formulations, the latter of which are the paper's main focus. I then give a thorough treatment of the problem's relationship with the complexity classes NP, NP-complete, and co-NP. I also discuss extensions of Gurvits' NP-hardness result to strong NP-hardness of certain related problems. A major open question is whether the NP-contained formulation (QSEP) of the quantum separability problem is Karp-NP-complete; QSEP may be the first natural example of a problem that is Turing-NP-complete but not Karp-NP-complete. Finally, I survey all the proposed (deterministic) algorithms for the quantum separability problem, including the bounded search for symmetric extensions (via semidefinite programming), based on the recent quantum de Finetti theorem; and the entanglement-witness search (via interior-point algorithms and global optimization). These two algorithms have the lowest complexity, with the latter being the best under advice of asymptotically optimal point-coverings of the sphere.