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 ε-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.
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.
We give algorithms for the optimization problem: $\max_ρ\ip{Q}ρ$, where Q is a Hermitian matrix, and the variable ρ is a bipartite {\em separable} quantum state. This problem lies at the heart of several problems in quantum computation and information, such as the complexity of QMA(2). While the problem is NP-hard, our algorithms are better than brute force for several instances of interest. In particular, they give PSPACE upper bounds on promise problems admitting a QMA(2) protocol in which the verifier performs only logarithmic number of elementary gate on both proofs, as well as the promise problem of deciding if a bipartite local Hamiltonian has large or small ground energy. For Q≥0, our algorithm runs in time exponential in ∥Q∥F. While the existence of such an algorithm was first proved recently by Brand{ã}o, Christandl and Yard [{\em Proceedings of the 43rd annual ACM Symposium on Theory of Computation}, 343--352, 2011], our algorithm is conceptually simpler.
We study a multilinear optimization problem for tensors with bounded Frobenius norm, where each of the k local factors of dimension d is chosen from a convex set. We give a deterministic algorithm running in time dO(k) for constant additive approximations. As applications, we obtain the first polynomial-time algorithms at constant accuracy for weak membership in the nuclear-norm unit ball of high-order tensors and for multipartite quantum separability in Frobenius norm. Our approach views tensor optimization as a cooperative multiprover game and combines this perspective with a recursive spectral compression procedure. We then show that related ideas admit a quantum implementation when the input state is given through copies, rather than an explicit classical description. In these settings we obtain an algorithm to solve Frobenius-norm separability testing using poly(k) copies and poly(klogd) time.
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.