Dvoretzky's theorem and the complexity of entanglement detection

DOI10.19086/DA.1242MaRDI QIDQ4645006zbMATH OpenOpenAlexFDO

Authors G. Aubrun, Stanislaw J. Szarek

Publication date 9 January 2019

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(8)

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

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)