An improved semidefinite programming hierarchy for testing entanglement
From MaRDI portal
Publication:529619
DOI10.1007/S00220-017-2859-0zbMATH Open1364.81041arXiv1506.08834OpenAlexW3105588021MaRDI QIDQ529619FDOQ529619
Authors: Aram W. Harrow, Anand Natarajan, Xiaodi Wu 
Publication date: 19 May 2017
Published in: Communications in Mathematical Physics (Search for Journal in Brave)
Abstract: We present a stronger version of the Doherty-Parrilo-Spedalieri (DPS) hierarchy of approximations for the set of separable states. Unlike DPS, our hierarchy converges exactly at a finite number of rounds for any fixed input dimension. This yields an algorithm for separability testing which is singly exponential in dimension and polylogarithmic in accuracy. Our analysis makes use of tools from algebraic geometry, but our algorithm is elementary and differs from DPS only by one simple additional collection of constraints.
Full work available at URL: https://arxiv.org/abs/1506.08834
Recommendations
- A quasipolynomial-time algorithm for the quantum separability problem
- Limitations of semidefinite programs for separable states and entangled games
- A two-way algorithm for the entanglement problem
- Distinguishing separable and entangled states
- Computational complexity of the quantum separability problem
Algorithms for approximation of functions (65D15) Quantum coherence, entanglement, quantum correlations (81P40)
Cites Work
- Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
- Geometric algorithms and combinatorial optimization.
- Which problems have strongly exponential complexity?
- Relative entropy and squashed entanglement
- Near-optimal and explicit Bell inequality violations
- Sums of squares, moment matrices and optimization over polynomials
- Title not available (Why is that?)
- Sum-of-squares proofs and the quest toward optimal algorithms
- Strong duality conditions in semidefinite programming
- Title not available (Why is that?)
- Faithful squashed entanglement
- Title not available (Why is that?)
- Pre- and Post-Processing Sum-of-Squares Programs in Practice
- Undecidability of the Spectral Gap
- Quantum de finetti theorems under local measurements with applications
- An exact Jacobian SDP relaxation for polynomial optimization
- First and second order analysis of nonlinear semidefinite programs
- Classical deterministic complexity of Edmonds' Problem and quantum entanglement
- Algebraic degree of polynomial optimization
- On the combinatorial and algebraic complexity of quantifier elimination
- Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems
- Strong NP-hardness of the quantum separability problem
- On the Equivalence of Algebraic Approaches to the Minimization of Forms on the Simplex
- The power of unentanglement
- On QMA protocols with two short quantum proofs
- Testing product states, quantum Merlin-Arthur games and tensor optimization
- Improved soundness for QMA with multiple provers
- Quantum interactive proofs with weak error bounds
- Epsilon-net method for optimizations over separable states
- Degree bounds for Gröbner bases of low-dimensional polynomial ideals
- On the Power of the PPT Constraint in the Symmetric Extensions Test for Separability
- Approximating the set of separable states using the positive partial transpose test
- On quantum interactive proofs with short messages
- Hypercontractivity, sum-of-squares proofs, and their applications
- Strong duality in lasserre's hierarchy for polynomial optimization
Cited In (11)
- Entanglement meter: estimation of entanglement with single copy in interferometer
- Dimension-free entanglement detection in multipartite Werner states
- Limitations of semidefinite programs for separable states and entangled games
- Entanglement diagnostics for efficient VQA optimization
- Bounding the separable rank via polynomial optimization
- Title not available (Why is that?)
- Finite convergence of sum-of-squares hierarchies for the stability number of a graph
- \texttt{libCreme}: an optimization library for evaluating convex-roof entanglement measures
- Epsilon-net method for optimizations over separable states
- Relating an entanglement measure with statistical correlators for two-qudit mixed states using only a pair of complementary observables
- The power of unentangled quantum proofs with non-negative amplitudes
Uses Software
This page was built for publication: An improved semidefinite programming hierarchy for testing entanglement
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q529619)
