Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

The membership problem for constant-sized quantum correlations is undecidable



Carl A. Miller, Honghao Fu, William Slofstra


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. Intuitively, our result means that the undecidability that arises in understanding Bell experiments is innate, and 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.


Bell experiment, computational complexity, undecidability, quantum nonlocality, entanglement


Miller, C. , Fu, H. and Slofstra, W. (2021), The membership problem for constant-sized quantum correlations is undecidable, arXiv, [online],, (Accessed July 25, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created January 26, 2021, Updated November 29, 2022