| Title: |
The NPA hierarchy does not always attain the commuting operator value |
| Authors: |
Fanizza, Marco; Kroell, Larissa; Mehta, Arthur; Paddock, Connor; Rochette, Denis; Slofstra, William; Zhao, Yuming |
| Contributors: |
Communications et Traitement Quantiques de l’Information (QURIOSITY); Laboratoire Traitement et Communication de l'Information (LTCI); Institut Mines-Télécom Paris (IMT)-Télécom Paris; Institut Mines-Télécom Paris (IMT)-Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Institut Mines-Télécom Paris (IMT)-Télécom Paris; Institut Mines-Télécom Paris (IMT)-Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre Inria de l'Institut Polytechnique de Paris; Centre Inria de Saclay; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre Inria de Saclay; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria); Département Informatique et Réseaux (INFRES); Télécom ParisTech; Department of Pure Mathematics Waterloo; University of Waterloo Waterloo; Department of Mathematics and Statistics Ottawa; University of Ottawa Ottawa; Departement of Mathematics and Statistics Ottawa, University of Ottawa; Institute for Quantum Computing Waterloo (IQC); University of Copenhagen = Københavns Universitet (UCPH); European Project: 818761,ERC-2018-COG,ERC-2018-COG,RESOURCE Q(2019) |
| Source: |
https://hal.science/hal-05482320 ; 2026. |
| Publisher Information: |
CCSD |
| Publication Year: |
2026 |
| Subject Terms: |
Quantum Physics (quant-ph); Computational Complexity (cs.CC); FOS: Physical sciences; FOS: Computer and information sciences; [PHYS.QPHY]Physics [physics]/Quantum Physics [quant-ph]; [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] |
| Description: |
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. |
| Document Type: |
report |
| Language: |
English |
| Relation: |
info:eu-repo/semantics/altIdentifier/arxiv/2510.04943; info:eu-repo/grantAgreement//818761/EU/Efficient Conversion of Quantum Information Resources/RESOURCE Q; ARXIV: 2510.04943 |
| DOI: |
10.48550/arXiv.2510.04943 |
| Availability: |
https://hal.science/hal-05482320; https://hal.science/hal-05482320v1/document; https://hal.science/hal-05482320v1/file/2510.04943v4.pdf; https://doi.org/10.48550/arXiv.2510.04943 |
| Rights: |
https://about.hal.science/hal-authorisation-v1/ ; info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.C521C414 |
| Database: |
BASE |