Quantum polymorphism characterisation of commutativity gadgets in all quantum models

arXiv:2604.01408 · quant-ph, cs.CC, math.OA · Submitted 2026-04-01 · Read on arXiv

quant-ph, cs.CC, math.OA

Submitted: 2026-04-01

Updated: 2026-09-22

Comments: 44 pages, 3 figures. v2: lemma 8.10 added to correct a technical error; small edits throughout

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Core — 14× in this paper · explained in 2 episodes
• Trace — 5× in this paper · explained in 2 episodes
• Entanglement — 4× in this paper · explained in 3 episodes
• Hilbert Space — 4× in this paper · explained in 2 episodes
• Robustness — 2× in this paper · explained in 5 episodes
• Symposium on Foundations of Computer Science — 2× in this paper
• Consistency — 1× in this paper · explained in 3 episodes
• Fingerprinting — 1× in this paper · explained in 2 episodes
• Generalization — 1× in this paper · explained in 13 episodes
• Verification — 1× in this paper · explained in 2 episodes

Sources

• Extending and Characterizing Quantum Magic Games
• Existence and nonexistence of commutativity gadgets for entangled CSPs
• Quantum Polymorphisms and the Complexity of Quantum Constraint Satisfaction
• RE-completeness of entangled constraint satisfaction problems
• Possible consequences for physics of the negative resolution of Tsirelson's problem
• Binary Constraint System Games and Locally Commutative Reductions
• MIPco=coRE
• Almost synchronous correlations and Tomita-Takesaki theory

Related papers

• Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
• Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
• Polynomial-time classical and quantum simulation of quantum impurity models
• A quasiparticle-protected superconducting qubit
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians