Dvoretzky's theorem and the complexity of entanglement detection

DOI10.19086/DA.1242zbMATH Open1404.81039arXiv1510.00578OpenAlexW2196383449MaRDI QIDQ4645006FDOQ4645006

Authors: G. Aubrun, Stanislaw J. Szarek 

Publication date: 9 January 2019

Published in: Discrete Analysis (Search for Journal in Brave)

Abstract: The well-known Horodecki criterion asserts that a state $ho$ on $mathbf{C}^{d}otimesmathbf{C}^d$ is entangled if and only if there exists a positive map $Phi:mathsf{M}_{d}omathsf{M}_d$ such that the operator $(PhiotimesmathrmId)(ho)$ is not positive semi-definite. We show that the number of such maps needed to detect all the robustly entangled states (i.e., states $ho$ which remain entangled even in the presence of substantial randomizing noise) exceeds $exp(c{d}^3/logd)$. The proof is based on the 1977 inequality of Figiel--Lindenstrauss--Milman, which ultimately relies on Dvoretzky's theorem about almost spherical sections of convex bodies. We interpret that inequality as a statement about approximability of convex bodies by polytopes with few vertices or with few faces and apply it to the study of fine properties of the set of quantum states and that of separable states. Our results can be thought of as geometrical manifestations of the complexity of entanglement detection.

Full work available at URL: https://arxiv.org/abs/1510.00578

Recommendations

• Dimension-free entanglement detection in multipartite Werner states
• A characterization of positive linear maps and criteria of entanglement for quantum states
• On the reduction criterion for random quantum states
• General SIC measurement-based entanglement detection
• Random and free positive maps with applications to entanglement detection

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07) Quantum coherence, entanglement, quantum correlations (81P40)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• User-friendly tail bounds for sums of random matrices
• Title not available (Why is that?)
• Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model
• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
• The dimension of almost spherical sections of convex bodies
• Separability of mixed states: necessary and sufficient conditions.
• Separability criterion and inseparable mixed states with positive partial transposition.
• Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
• Separability Criterion for Density Matrices
• Title not available (Why is that?)
• Entanglement thresholds for random induced states
• Title not available (Why is that?)
• Quantum interactive proofs and the complexity of separability testing
• Classical deterministic complexity of Edmonds' Problem and quantum entanglement
• Title not available (Why is that?)
• A note on coverings
• Geometry of sets of quantum maps: A generic positive map acting on a high-dimensional system is not completely positive
• Covering a sphere with spheres
• Entanglement witnesses arising from exposed positive linear maps
• Positive linear maps of operator algebras
• Approximation of convex sets by polytopes
• Strong NP-hardness of the quantum separability problem
• Hastings's additivity counterexample via Dvoretzky's theorem
• Title not available (Why is that?)
• Thrifty approximations of convex bodies by polytopes
• On approximation by projections of polytopes with few facets
• Title not available (Why is that?)
• Computational complexity of the quantum separability problem
• Testing product states, quantum Merlin-Arthur games and tensor optimization
• A quasipolynomial-time algorithm for the quantum separability problem
• Alice and Bob Meet Banach
• \(k\)-extendibility of high-dimensional bipartite quantum states
• Limitations of semidefinite programs for separable states and entangled games
• There is no direct generalization of positive partial transpose criterion to the three-by-three case

Cited In (8)

• The set of separable states has no finite semidefinite representation except in dimension \(3\times 2\)
• Limitations of semidefinite programs for separable states and entangled games
• Tensor products of quantum mappings
• On Polyhedral Approximations of the Positive Semidefinite Cone
• Random matrix techniques in quantum information theory
• Entanglement Detection: Complexity and Shannon Entropic Criteria
• On approximations of the PSD cone by a polynomial number of smaller-sized PSD cones
• Quantum mappings and characterization of entangled quantum states

This page was built for publication: Dvoretzky's theorem and the complexity of entanglement detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645006)