Dvoretzky's Theorem and the Complexity of Entanglement Detection
arXiv:1510.00578 · doi:10.19086/da.1242
Abstract
The well-known Horodecki criterion asserts that a state on is entangled if and only if there exists a positive map such that the operator is not positive semi-definite. We show that the number of such maps needed to detect all the robustly entangled states (i.e., states which remain entangled even in the presence of substantial randomizing noise) exceeds . 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.
arXiv commentAccepted talk in QIP'16. V2: added a variant of the main theorem showing that very highly entangled states are already hard to detect. V3: published version; improved presentation, results unchanged
References in corpus (16)
- Separability Criterion for Density Matrices
- Separability of Mixed States: Necessary and Sufficient Conditions
- Separability criterion and inseparable mixed states with positive partial transposition
- Robustness of entanglement
- Superadditivity of communication capacity using entangled inputs
- A complete family of separability criteria
- Largest separable balls around the maximally mixed bipartite quantum state
- Tensor products of convex sets and the volume of separable states on N qudits
- 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
- A quasipolynomial-time algorithm for the quantum separability problem
- Phase transitions for random states and a semi-circle law for the partial transpose
- 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
- -extendibility of high-dimensional bipartite quantum states