The membership problem for constant-sized quantum correlations is undecidable
arXiv:2101.11087 · doi:10.1007/s00220-024-05229-7
Abstract
When two spatially separated parties make measurements on an unknown entangled quantum state, what correlations can they achieve? How difficult is it to determine whether a given correlation is a quantum correlation? These questions are central to problems in quantum communication and computation. Previous work has shown that the general membership problem for quantum correlations is computationally undecidable. In the current work we show something stronger: there is a family of constant-sized correlations -- that is, correlations for which the number of measurements and number of measurement outcomes are fixed -- such that solving the quantum membership problem for this family is computationally impossible. Thus, the undecidability that arises in understanding Bell experiments is not dependent on varying the number of measurements in the experiment. This places strong constraints on the types of descriptions that can be given for quantum correlation sets. Our proof is based on a combination of techniques from quantum self-testing and from undecidability results of the third author for linear system nonlocal games.
v4: final version. v3: more polishes. v2: 55 pages, simplified main proof and minor fixes. v1: 68 pages and 1 figure. All comments are welcome
References in corpus (23)
- Information Causality as a Physical Principle
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- All multipartite Bell correlation inequalities for two dichotomic observables per site
- A limit on nonlocality in any world in which communication complexity is not trivial
- Testing the Hilbert space dimension
- A glance beyond the quantum model
- Local orthogonality as a multipartite principle for quantum correlations
- Connes' embedding problem and Tsirelson's problem
- Geometry of the set of quantum correlations
- Tsirelson's problem and Kirchberg's conjecture
- Estimating quantum chromatic numbers
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Perfect Commuting-Operator Strategies for Linear System Games
- A synchronous game for binary constraint systems
- Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
- Lower bounds on the entanglement needed to play XOR non-local games
- Undecidability of the Spectral Gap in One Dimension
- Almost quantum correlations violate the no-restriction hypothesis
- A two-player dimension witness based on embezzlement, and an elementary proof of the non-closure of the set of quantum correlations
- Structure of the set of quantum correlators via semidefinite programming
- Nonlocal Games, Compression Theorems, and the Arithmetical Hierarchy
- Constant-sized correlations are sufficient to robustly self-test maximally entangled states with unbounded dimension
- Geometry of the set of synchronous quantum correlations