  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.
