The membership problem for constant-sized quantum correlations is undecidable

One of the most fundamental and counterintuitive features of quantum mechanics is entanglement, which is central to many demonstrations of the quantum advantage. Studying quantum correlations generated by local measurements on an entangled physical system is one of the direct ways to gain insights into entanglement. The focus of this dissertation is to get better understanding of the hardness of determining if a given correlation is quantum, which is also known
as the membership problem of quantum correlations.

Previous work has shown that the general membership problem is computationally undecidable. Where does the hardness come from? Is it just because the size of a quantum correlation (i.e., the number of real values in the description of the correlation) can be arbitrarily large? We would like to understand the role played by the varying sizes of correlations in the hardness of the membership problem.

It has been shown that certain quantum correlations require the measured quantum system to be maximally entangled with a certain dimension. This is a unique phenomenon of quantum correlations and it is known as self-testing. The first step towards answering the hardness of the membership problem of quantum correlations is to get deeper understandings about self-testing, and more specifically, about the size of a correlation that can self-test a maximally entangled state of arbitrarily large dimension. If correlations of a fixed size can self-test entangled states of unbounded dimension, this phenomenon is a strong evidence suggesting that deciding membership of fixed-sized correlations can be very hard.

We first show that there exists an infinite subset of the set of all the prime numbers such that, for each prime p in this set, a maximally entangled state of local dimension (p-1) can be self-tested by a correlation of a fixed size. Since this set is infinite, this result implies that constant-sized correlations are sufficient to self-test maximally entangled states of unbounded dimension.

Building on the self-testing result, we show that the varying sizes of correlations are not the only root of the hardness. Specifically, we show that the membership problem of fixed finite-sized correlations is still computationally undecidable when the fixed size is sufficiently large. That is, the hardness of the membership problem of quantum correlations is independent of the varying sizes of correlations. In fact, the hardness arises from the fact that the structure of some set of correlations of a particular size is so complicated that no finite description of this set can allow a Turing machine to decide if a correlation is quantum or not.