We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. Specifically, there is a computable mapping from Turing machines to /boolean constraint system (BCS) nonlocal games in which the halting property of the machine is encoded as a decision problem for the commuting operator value of the game. As a corollary, there is a BCS game for which the value of the Navascués-Pironio-Acín (NPA) hierarchy does not attain the commuting operator value at any finite level.
We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. Specifically, there is a computable mapping from Turing machines to /boolean constraint system (BCS) nonlocal games in which the halting property of the machine is encoded as a decision problem for the commuting operator value of the game. As a corollary, there is a BCS game for which the value of the Navascués-Pironio-Acín (NPA) hierarchy does not attain the commuting operator value at any finite level.
Compiling Bell games under cryptographic assumptions replaces the need for physical separation, allowing nonlocality to be probed with a single untrusted device. While Kalai et al. (STOC'23) showed that this compilation preserves quantum advantages, its quantitative quantum soundness has remained an open problem. We address this gap with two primary contributions. First, we establish the first quantitative quantum soundness bounds for all bipartite compiled Bell games via a newly formalized convergent sequential Navascués-Pironio-Acín (NPA) hierarchy: any polynomial-time prover's score is controlled by a finite-level hierarchy value, and finite-level convergence gives a negligible gap to the commuting quantum value, or to the tensor-product quantum value under flat optimality. Second, we develop the sequential NPA hierarchy as a computational tool of independent interest, establishing its convergence and a stopping criterion based on flatness, and identifying its conic dual as a sparse SOS hierarchy.
Characterising the correlations that arise from locally measuring a single part of a joint quantum system is one of the main problems of quantum information theory. The seminal work [M. Navascués et al., New J. Phys. 10, 073013 (2008)], known as the Navascués–Pironio–Acín (NPA) hierarchy, reformulated this question as a polynomial optimisation problem over noncommutative variables and proposed a convergent hierarchy of necessary conditions, each testable using semidefinite programming. More recently, the problem of characterising the quantum network correlations, which arise when locally measuring several independent quantum systems distributed in a network, has received considerable interest. Several generalisations of the NPA hierarchy, such as the scalar extension [A. Pozas-Kerstjens et al., Phys. Rev. Lett. 123, 140503 (2019)], were introduced while their converging sets remain unknown. In this work, we introduce a new bilocal factorisation NPA hierarchy, prove its equivalence to a modified bilocal scalar extension NPA hierarchy, and characterise its convergence in the case of the simplest network, the bilocal scenario. We further explore its relations with the other known generalisations.
Can uncomputability occur in the resource law of one fixed finite nonlocal game, rather than in a problem whose input is a game? We construct a finite two-player Boolean constraint-system game with rational question probabilities, quantum value one, and no finite-dimensional perfect strategy. If D(ε) is the least local dimension needed to win with probability at least 1−ε, then limn→∞log2D(2−n)/n=(3+θK)/4, where θK=∑e∈K4−(e+1) and K is the halting set. This exponent has the Turing degree of K. The construction combines finite operator relations for three Cantor clocks, a counter program with forced initialization, and a conditional clock that charges dimension for halting inputs. A Boolean compiler preserves weighted precision linearly and converts flat models to strategies with quadratic loss. The lower bound holds in every density matrix. Explicit finite models attain the same rate. The flag-density lower bound uses compactness without an effective modulus; convergence to the dimension exponent has no computable certified rate.
The Navascués--Pironio--Acín (NPA) hierarchy gives the standard semidefinite outer approximations to quantum behaviors. Whether \emph{any} finite level can already equal the quantum set has remained open even in the bipartite scenario with two binary measurements per party. We demonstrate that \emph{no finite level} is exact. For the symmetric doubly tilted CHSH functional hα=A0B0+A0B1+A1B0−A1B1+α(A0+B0), set T=1−α. Its quantum maximum satisfies [ωQ(1−T)−(4−2T)]/T3→4/3, whereas every fixed NPA level satisfies [ωL(1−T)−ωQ(1−T)]/T3→+∞. Under the corresponding boundary rescaling, an explicit expectation of the positive operator ωQ(1−t2)I−Ht converges to the Motzkin polynomial. A bounded fixed-level error would therefore make the Motzkin polynomial plus a nonnegative constant a sum of squares, which is impossible. Consequently, every standard NPA relaxation based on a fixed finite list of words in the measurement projectors strictly contains the complete quantum set, and its nonquantum behaviors accumulate at a local deterministic behavior. Thus, the finite-level exactness of CHSH and all one-sided tilted CHSH maxima does not extend to an exact finite-level description of the complete quantum set in the minimal scenario.
It is difficult to establish an analytical criterion to identify the boundaries of quantum correlations, even for the simplest Bell scenario. Here, we briefly reviewed the plausible analytical criterion, and we found a way to confirm the extremal conditions from another direction. For that purpose, we analyzed the Navascués-Pironio-Acín (NPA) hierarchy to study the algebraic structure and found that the problem could not be simplified using the 1+AB level. However, considering the plausible criterion, the 1+AB and second levels for correlations were equal, and the extremal condition in the simplest Bell scenario was replaced by that in the 1+AB level. Thus, the correctness of the plausible criterion was verified, and the results demonstrated that the plausible criterion held, thereby explaining its simplicity. It seemed plausible, but now it becomes more certain.
The conditional probabilities achievable by local measurements on a shared quantum state in a Bell scenario form the set of quantum behaviors, whose structure was studied by Tsirelson. In 1993, Tsirelson asked whether this set is semialgebraic, that is, describable by finite Boolean combinations of polynomial equations and inequalities. This question has remained open. We answer it in the negative: with four binary measurements per party, the set of finite-dimensional quantum behaviors, its closure, and the commuting-operator set are all nonsemialgebraic. More strongly, none admits a finite real-analytic description even locally near a particular classical behavior. These results rule out exact finite semidefinite representations and show that no finite level of the Navascués-Pironio-Acín hierarchy characterizes these sets exactly.