Pith. sign in

REVIEW 3 major objections 5 minor 50 references

Existence and nonexistence of commutativity gadgets for entangled CSPs

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that non-classical quantum endomorphism monoids obstruct commutativity gadgets, ruling out gadgets for k-colouring when k≥4 while constructing one in the oracular setting.

desk verdict A useful framework and a likely-correct no-go theorem, but the proof of the main k-colouring application has a repairable gap that needs fixing before publication. read the letter →

arxiv 2509.07835 v1 pith:ARO4FRK7 submitted 2025-09-09 quant-ph cs.CCmath.OA

Eric Culf , Josse van Dobben de Bruyn , Matthijs Vernooij , Peter Zeman This is my paper · ORCID
classification quant-phcs.CCmath.OA MSC 05C1520G4268Q1781P68 PACS 03.67.-a
keywords commutativitygadgetsentangledconstraintsatisfactionproblemsquantumendomorphismmonoidspermutationgroupsk-colouringoracularnonlocalgamesRE-hardnessweakadjacencycongruence
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Commutativity gadgets are the standard tool that lifts NP-hardness proofs for classical constraint satisfaction problems to undecidability proofs for their entangled quantum versions: a gadget forces the measurement operators of two variables to commute without restricting the classical values those variables may take. This paper establishes a general obstruction: if a relational structure has a non-classical quantum endomorphism monoid, then it has no commutativity gadget. Applied to $k$-colouring, this rules out commutativity gadgets for every $k \geq 4$, because the complete graph $K_k$ carries a noncommuting quantum permutation group. The paper then shows that a different presentation of $k$-colouring, the oracular game, does admit a commutativity gadget built from the complement of an even cycle, and derives that oracular entangled $k$-colouring is undecidable for every $k \geq 3$. It also provides a checkable criterion, weak adjacency congruence, for detecting non-classical quantum endomorphisms, and shows that odd cycles and odd graphs have only classical endomorphisms, leaving their gadget status open.

What carries the argument

The central object is the quantum endomorphism monoid $\mathrm{end}^{+}(A)$, the quantum space of all structure-preserving maps from $A$ to itself, generated by projection-valued measures $p_{a,b}$ that play the role of 'element $a$ is assigned value $b$'; the oracular variant $\mathrm{end}^{o+}(A)$ additionally requires that generators sharing a variable commute. The load-bearing argument is a composition identity: composing a non-classical endomorphism with the assignment supplied by a gadget produces a representation of the gadget in which the two distinguished variables' PVMs both must commute and cannot commute. A secondary tool is the weak-adjacency-congruence (WAC) condition on two classical endomorphisms, a directly checkable property that guarantees the existence of a non-classical quantum endomorphism; a further theorem transfers oracular commutativity gadgets to categorical powers of graphs.

What would settle it

Check whether the paper's own even-cycle complement gadget satisfies the robust-defect bound: construct a sequence of finite-dimensional tracial states on the constraint-variable algebra whose defect tends to zero while the trace of the commutator $[p_{0a},p_{1b}]$ stays bounded away from zero; such a sequence would refute Lemma 4.6 and break the undecidability reduction. An explicit commutativity gadget for $K_4$ would refute Theorem 4.11 outright.

Watch

Extended reading notes

Core claim

The central discovery is a no-go theorem: for any relational structure $A$, if the quantum endomorphism monoid $\mathrm{end}_{qa}(A)$ is strictly larger than the classical endomorphism set $\mathrm{end}_{c}(A)$, then no commutativity gadget for $A$ exists, and the analogous statement holds for oracular gadgets and the oracular monoid. The proof is a composition argument: a non-classical endomorphism $\pi_0$ exhibits two outputs whose projection-valued measures fail to commute, while the defining property of a gadget would force exactly those PVMs to commute when the gadget's two distinguished variables are assigned those outputs. Since the quantum permutation group $\mathcal{S}^{+}_{k}$ is noncommutative for $k \geq 4$, the theorem rules out a commutativity gadget for $K_k$, that is, for $k$-colouring. Against this negative result, the complement of the cycle $C_{2k}$ is shown to be an oracular algebraic commutativity gadget for $K_k$: there are classical homomorphisms realizing every pair of colours, and all relevant generators commute in the oracular algebra. Together with a reduction theorem presented as implicit in prior work, this yields RE-hardness of oracular entangled $k$-colouring for every $k \geq 3$. Further results give a checkable sufficient condition for non-classical endomorphisms and show that, for graphs without 4-cycles, oracular and non-oracular commutativity gadgets coincide.

Load-bearing premise

The undecidability result for oracular $k$-colouring rests on an unproved implication: the paper states without proof that every oracular algebraic commutativity gadget is automatically a robust commutativity gadget (Lemma 4.6), and the theorem that turns robust gadgets into RE-hardness is only sketched and credited to earlier work; if either of those steps fails, the hardness chain does not go through.

Editorial extensions

If this is right

  • The standard reduction route to undecidability of entangled $k$-colouring is closed for $k \geq 4$ in the non-oracular setting; any undecidability proof must use a different presentation or a new mechanism.
  • Oracular entangled $k$-colouring is RE-hard for every $k \geq 3$, making the oracular variant at least as hard as the halting problem in the gapped, succinct setting.
  • Every graph with a non-classical quantum automorphism group is a template with no commutativity gadget; the WAC criterion turns this into a search problem on classical endomorphisms.
  • For graphs with no 4-cycle, oracular and non-oracular commutativity gadgets are the same, so for odd cycles and odd graphs the undecidability question reduces to finding one gadget in either model.
  • Concrete four-element graph templates such as the diamond graph and the six-cycle with a chord have neither an oracular nor a non-oracular commutativity gadget.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural completeness question the authors leave open: the WAC criterion is sufficient for non-classical endomorphisms, and a converse would turn the obstruction into a full characterization of when commutativity gadgets cannot exist.
  • The unproved algebraic-to-robust step is the hinge of the oracular undecidability result; a counterexample there would preserve the no-go theorem but remove RE-hardness, so testing that step on the paper's even-cycle gadget is the first place to look.
  • Because oracular gadgets survive categorical powers, composing the $K_k$ gadget with other NP-complete templates could spread undecidability to a wider family of oracular entangled CSPs.
  • For odd cycles, a positive gadget construction would immediately yield a non-oracular gadget thanks to oracularisability, and hence undecidability of entangled colouring by odd cycles; the paper's appendix shows the most obvious prism-like candidate fails.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces quantum (and oracular quantum) endomorphism monoids of relational structures, viewed as the quantum spaces of self-homomorphisms, and connects their classicality to the existence of commutativity gadgets. The central no-go result, Theorem 4.11, states that if a relational structure A has a non-classical quantum endomorphism monoid then A admits no commutativity gadget, and likewise in the oracular setting. The authors apply this to k-colouring: Proposition 5.1 claims that for k >= 4 the complete graph K_k has no commutativity gadget, while Proposition 5.2 constructs an oracular algebraic commutativity gadget for K_k from the complement of C_{2k}. Combining these with Theorem 4.10 and Lemma 4.6 yields Corollary 5.5, RE-hardness of oracular entangled k-colouring for k >= 3. The paper also proves a Schmidt-type sufficient condition (WAC) for non-classical endomorphisms, shows preservation of oracular gadgets under categorical powers, proves that graphs without a four-cycle are oracularisable, and shows that odd cycles and odd graphs have only classical endomorphisms. An appendix rules out a natural prism-gadget extension for larger odd cycles.

Significance. If all claims are established, the paper would provide the first known obstruction to the existence of commutativity gadgets and would give a new structural reason, via quantum endomorphism monoids, for why certain CSPs resist the standard gadget-based undecidability reductions. The distinction between oracular and non-oracular commutativity gadgets is a genuine conceptual contribution, and the WAC criterion supplies a practical tool for detecting non-classical endomorphisms. The proof of Theorem 4.11 itself is short and appears sound. However, two load-bearing points currently prevent the advertised conclusions from being considered proved: the representation in Proposition 5.1 is not a homomorphism for k > 4, and Lemma 4.6, which is needed to turn the algebraic oracular gadget into the robust gadget required for the complexity corollary, is stated without proof. A third point, Theorem 4.10, is only credited as implicit in prior work and is sketched rather than proved. These gaps are repairable, but they are not merely cosmetic.

major comments (3)
  1. [Section 5.1, Proposition 5.1] The explicit representation of End^+(K_k) given in the proof is not a *-homomorphism for k > 4. The proposed map sets pi(p_ij) = 0 for all i >= 4 and all j, so the row-sum relation sum_j p_ij = 1, which holds in End^+(K_k), is violated: sum_j pi(p_ij) = 0 for i >= 4. Consequently end_qa(K_k) != end_c(K_k) is not established by the displayed construction, and the application of Theorem 4.11 to K_k for k > 4 is unsupported as written. The gap appears repairable by quotienting through End^+(K_4) and setting pi(p_ii) = 1 for i >= 4, but the paper does not supply this argument. Since this is the only evidence connecting the no-go theorem to the headline claim that k-colouring has no commutativity gadget for k >= 4, the proof must be corrected.
  2. [Section 4.3, Lemma 4.6] Lemma 4.6 asserts that every oracular algebraic commutativity gadget is automatically a c-v-robust commutativity gadget, with the proof omitted and replaced by 'We omit the proof as it follows along exactly the same lines as the previous lemma.' This lemma is logically indispensable for Corollary 5.5: Proposition 5.2 constructs an oracular algebraic gadget, and Lemma 4.6 is what upgrades it to the robust gadget needed by Theorem 4.10 to produce the halting-problem reduction. The proof of Lemma 4.5 that is invoked is itself nontrivial, involving infinitesimal ideals and finite decompositions, and the oracular variant may require new estimates in Mor^{c-v}. The authors should either provide a complete proof or state precisely why the previous proof transfers verbatim.
  3. [Section 4.3, Theorem 4.10] Theorem 4.10 is presented as 'implicit in [CM24]' and its proof is only a sketch. The theorem is a central bridge: it turns robustness of a commutativity gadget into RE-hardness of succinct entangled CSPs. Corollary 5.5 depends on it directly. A reader of the present paper cannot verify the reduction without consulting [CM24] in detail. Please either give a complete proof (which may be long but should be included or placed in an appendix) or specify the exact statement and location in [CM24] from which each of the three cases follows, and explain how the c-v case sketch in the present text is justified. As written, the complexity-theoretic conclusions rest on an unverified citation.
minor comments (5)
  1. [Cross-references throughout] Several internal references point to the wrong environment: for example, 'Proof of Definition 5.2' should reference Proposition 5.2, 'Definition 4.11' should be Theorem 4.11, 'Definition 5.11' should be Proposition 5.11, 'Definition 5.19' should be Theorem 5.19, and 'Definition 5.3' and 'Definition 5.4' in Section 5.1 should be Lemma 5.3 and Lemma 5.4. These mislabels make the text substantially harder to follow.
  2. [Definition 4.2] In the displayed definition of a c-c-robust commutativity gadget, the second summation over S in sigma and y in S^G uses the index range j in [ar(R)] instead of j in [ar(S)]. The same typo appears in the definition of the c-v-robust quantity at the end of the paragraph. The intended range is ar(S) for the S-summand.
  3. [Example 5.12] In Example 5.12(a), the text says the diamond graph D has 'no commutativity gagdets'; the typo 'gagdets' should be 'gadgets'.
  4. [Section 3.2, Lemma 3.8] In the sentence preceding Lemma 3.8, the text says the specific support condition is 'see Definition 3.8', but Definition 3.8 does not exist; the intended reference is to the conditions stated in Lemma 3.8 itself. Please rephrase to avoid the dangling reference.
  5. [Section 4.1, Lemma 4.7] The proof of Lemma 4.7 is headed 'Proof of Definition 4.7'; the heading should identify the environment being proved rather than the definition.

Circularity Check

0 steps flagged · score 1.0 of 10

No definitional circularity: the no-go theorem is self-contained, and the [CM24] self-citation and omitted Lemma 4.6 proof are dependency/quality gaps, not circular reductions.

full rationale

The central obstruction (Theorem 4.11) is derived by composing a non-classical quantum endomorphism π0 ∈ end_qa(A) with the gadget's assignment morphism π_{a1,a2}: the noncommutation of π0(p_{a1b1}) and π0(p_{a2b2}) is transported directly to π(p_{xb1}) and π(p_{yb2}) (Section 4.4, proof of Theorem 4.11). This is a direct argument from the definitions of the Q-morphism category and of a commutativity gadget (Definition 4.1), with no fitted parameter, no quantity defined in terms of the conclusion, and no renaming of a known result. The oracular gadget construction for K_k (Proposition 5.2) is also self-contained: property (i) is verified by the explicit classical homomorphisms f(2a)=f(2a+1)=a and g(2a)=g(2a-1)=a, and property (ii) is verified by commutation relations in Mor_o^+(C_{2k},K_k) (Lemmas 5.3 and 5.4), not by assuming the conclusion. The main self-citation is Theorem 4.10, which begins 'The following result is implicit in [CM24]' and is used for the complexity bridge from oracular gadgets to RE-hardness; since [CM24] is prior external work and the present gadget/no-go results do not reduce to it, this is a dependency risk rather than a circular step. Two non-circular gaps should be weighed separately. Lemma 4.6 says 'We omit the proof as it follows along exactly the same lines as the previous lemma,' leaving the c−v-robustness of oracular algebraic gadgets unproved; this is an omitted proof, not a circularity. In Proposition 5.1 the displayed representation sets 'π(p_ij)=0 otherwise', so for k>4 the row-sum relation Σ_j π(p_ij)=1 fails for rows i≥4, making the explicit proof of end_qa(K_k)≠end_c(K_k) invalid as written; the underlying noncommutativity of S+_k is still an external theorem [Wan98]. These are correctness/completeness issues, not definitional circularity, so the circularity score remains low.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces new mathematical definitions (quantum endomorphism monoid, WAC condition) but no new physical entities; these are tracked as axioms and definitions rather than invented entities. No fitted parameters appear because this is a pure mathematics paper.

assumptions (6)
  • standard math CSP dichotomy theorem (Bulatov/Zhuk) is used to state that every finite-alphabet CSP is in P or NP-complete.
    Invoked in Section 2.10 to frame the complexity setting.
  • standard math MIP* = RE (Ji, Natarajan, Vidick, Wright, Yuen) is used as the background result that succinctly presented nonlocal games have undecidable quantum value.
    Cited in Section 2.9 and used to motivate undecidability of entangled CSPs.
  • standard math Wang's theorem that the quantum permutation group S_k^+ is non-classical for k>=4.
    Used in Proposition 5.1, though the paper also gives an explicit finite-dimensional representation.
  • standard math Schmidt's criterion for quantum automorphism groups of graphs [Sch20] is the template for the new endomorphism criterion.
    Section 5.2 generalizes it to endomorphisms via the WAC condition.
  • domain assumption The reduction theorem of Culf and Mastel [CM24] is assumed as the content of Theorem 4.10.
    Theorem 4.10 is stated as implicit in [CM24]; the paper does not reprove the reduction from the halting problem to entangled CSPs.
  • domain assumption Connes-embeddable traces are identified with quantum approximate strategies throughout the paper.
    The definitions of qa morphisms and entangled CSPs use Connes-embeddable traces; this is the standard framework in the area.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Existence and nonexistence of commutativity gadgets for entangled CSPs." pith.science (2026). https://pith.science/paper/ARO4FRK7

@misc{pith2026250907835,
  author       = {Pith},
  title        = {Pith review of: Existence and nonexistence of commutativity gadgets for entangled CSPs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ARO4FRK7}},
  note         = {Machine review of arXiv:2509.07835}
}
abstract

Commutativity gadgets allow NP-hardness proofs for classical constraint satisfaction problems (CSPs) to be carried over to undecidability proofs for the corresponding entangled CSPs. This has been done, for instance, for NP-complete boolean CSPs and 3-colouring in the work of Culf and Mastel. For many CSPs over larger alphabets, including $k$-colouring when $k \geq 4$, it is not known whether or not commutativity gadgets exist, or if the entangled CSP is decidable. In this paper, we study commutativity gadgets and prove the first known obstruction to their existence. We do this by extending the definition of the quantum automorphism group of a graph to the quantum endomorphism monoid of a CSP, and showing that a CSP with non-classical quantum endomorphism monoid does not admit a commutativity gadget. In particular, this shows that no commutativity gadget exists for $k$-colouring when $k \geq 4$. However, we construct a commutativity gadget for an alternate way of presenting $k$-colouring as a nonlocal game, the oracular setting. Furthermore, we prove an easy to check sufficient condition for the quantum endomorphism monoid to be non-classical, extending a result of Schmidt for the quantum automorphism group of a graph, and use this to give examples of CSPs that do not admit a commutativity gadget. We also show that existence of oracular commutativity gadgets is preserved under categorical powers of graphs; existence of commutativity gadgets and oracular commutativity gadgets is equivalent for graphs with no four-cycle; and that the odd cycles and the odd graphs have a commutative quantum endomorphism monoid, leaving open the possibility that they might admit a commutativity gadget.

Figures

Figures reproduced from arXiv: 2509.07835 by the authors.

Figure 1
Figure 1. The graphs C6 and C8 presented as prisms non-classical endomorphisms, and use this to find examples of graphs with no commutativity gadget. In Section 5.3, we show that commutativity gadgets extend to categorical powers. In Section 5.4, we study the quantum endomorphism monoids of some families of graphs, and show that odd cycles and odd graphs admit only classical endomorphisms. In Section 5.5, we show that graph C… view at source ↗
Figure 2
Figure 2. The diamond graph D (left) and the graph D′ = C6 + {0, 3} (right). It is easy to check that these are endomorphisms of D with disconnected supports. Hence by Definition 5.11 and Definition 4.11, D has no oracular or non-oracular commutativity gadget. This gives an example of a relational structure with alphabet size 4 with no commutativity gagdets. (b) Let D′ = C6 + {0, 3} be the graph obtained from C6 by adding the… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 23 canonical work pages

  1. [1]

    Abramsky, R

    [ABdSZ17] S. Abramsky, R. S. Barbosa, N. de Silva, and O. Zapata. The Quantum Monad on Relational Structures. In K. G. Larsen, H. L. Bodlaender, and J.-F. Raskin, editors,42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), volume 83 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:19, Dagstuh...

    work page 2017

  2. [11]

    Preprint

    Online:https://arxiv.org/abs/2503.11149. Preprint. [Bic03] J. Bichon. Quantum automorphism groups of finite graphs.Proceedings of the American Mathematical Society, 131(3): 665–673,

    work page arXiv

  3. [15]

    [BŽ25] A

    DOI: 10.1109/FOCS.2017.37. [BŽ25] A. A. Bulatov and S. Živný. Satisfiability of commutative vs. non-commutative csps. In52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), pages 37–1. Schloss Dagstuhl–Leibniz-Zentrum für Informatik,

    doi:10.1109/focs.2017.37 2017

  4. [16]

    [Cia24] L

    DOI: 10.4230/LIPIcs.ICALP.2025.37. [Cia24] L. Ciardo. Quantum advantage and CSP complexity. InProceedings of the 2024 39th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2024), pages 1–15. ACM,

    work page doi:10.4230/lipics.icalp.2025.37 2025

  5. [18]

    [CM24] E

    DOI: 10.1007/978-3-662-43948-7_27. [CM24] E. Culf and K. Mastel. RE-completeness of entangled constraint satisfaction problems,

    doi:10.1007/978-3-662-43948-7_27

  6. [19]

    RE-completeness of entangled constraint satisfaction problems

    Online:https://arxiv.org/abs/2410.21223. [DFK+25] J. van Dobben de Bruyn, A. Freslon, P. N. Kar, D. E. Roberson, and P. Zeman. Free inhomoge- neous wreath product of compact quantum groups,

    work page Pith review arXiv

  7. [20]

    Preprint

    Online:https://arxiv.org/abs/2504.13826. Preprint. [Din07] I. Dinur. The PCP theorem by gap amplification.Journal of the ACM, 54(3): #12,

    work page arXiv

  8. [21]

    [DKR+25] J

    DOI: 10.1145/1236457.1236459. [DKR+25] J. van Dobben de Bruyn, P. N. Kar, D. E. Roberson, S. Schmidt, and P. Zeman. Quantum automorphism groups of trees.Journal of Noncommutative Geometry,

    arXiv

Show all 50 references
  1. [22]

    [Eif20] K

    DOI: 10.4171/JNCG/607. [Eif20] K. Eifler. Non-local games and quantum symmetries of quantum metric spaces,

    doi

  2. [23]

    Preprint

    Online:https://arxiv.org/abs/2011.03867. Preprint. [Far24] N. Faroß. Quantum automorphism groups of hypergraphs,

    2011 arXiv

  3. [24]

    Preprint

    Online:https://arxiv.org/abs/2405.09894. Preprint. [HMPS19] J. W. Helton, K. P. Meyer, V . I. Paulsen, and M. Satriano. Algebras, synchronous games, and chromatic numbers of graphs.The New York Journal of Mathematics, 25: 328–361,

    arXiv

  4. [25]

    [HN90] P

    Online:https://nyjm.albany.edu/j/2019/25-16.html. [HN90] P. Hell and J. Nešetˇril. On the complexity of H-coloring.Journal of Combinatorial Theory, Series B, 48(1): 92–110,

    2019

  5. [29]

    [LMR20] M

    DOI: 10.1007/s00013-020-01476-x. [LMR20] M. Lupini, L. Man ˇcinska, and D. E. Roberson. Nonlocal games and quantum permutation groups.Journal of Functional Analysis, 279(5): 108592,

    doi

  6. [30]

    [MdlS23] A

    DOI: 10.1016/j.jfa.2020.108592. [MdlS23] A. Marrakchi and M. de la Salle. Almost synchronous correlations and Tomita-Takesaki theory,

    2020

  7. [32]

    [MR16] L

    DOI: 10.1103/PhysRevLett.65.3373. [MR16] L. Manˇcinska and D. E. Roberson. Quantum homomorphisms.Journal of Combinatorial Theory. Series B, 118: 228–267,

    doi

  8. [34]

    [MSSV25] L

    DOI: 10.1145/3618260.3649702. [MSSV25] L. Man ˇcinska, P. Spaas, T. Spirig, and M. Vernooij. Gap-preserving reductions and RE- completeness of independent set games,

  9. [35]

    Preprint

    Online:https://arxiv.org/abs/2505.05253. Preprint. [OP16] C. M. Ortiz and V . I. Paulsen. Quantum graph homomorphisms via operator systems.Linear Algebra and its Applications, 497: 23–43,

    arXiv

  10. [36]

    [Oza13] N

    DOI: 10.1016/j.laa.2016.02.019. [Oza13] N. Ozawa. About the Connes embedding conjecture.Japanese Journal of Mathematics. 3rd Series, 8(1): 147–183,

    2016 doi

  11. [37]

    [Per90] A

    DOI: 10.1007/s11537-013-1280-5. [Per90] A. Peres. Incompatible results of quantum measurements.Physics Letters A, 151(3): 107–108,

    doi

  12. [38]

    [PSS+16] V

    DOI: 10.1016/0375-9601(90)90172-K. [PSS+16] V . I. Paulsen, S. Severini, D. Stahlke, I. G. Todorov, and A. Winter. Estimating quantum chromatic numbers.Journal of Functional Analysis, 270(6): 2188–2222,

    doi

  13. [39]

    49 [RS22] D

    DOI: 10.1016/j.jfa.2016.01.010. 49 [RS22] D. E. Roberson and S. Schmidt. Solution group representations as quantum symmetries of graphs.Journal of the London Mathematical Society, 106(4): 3379–3410,

    2016 doi

  14. [43]

    [Slo19] W

    DOI: 10.22028/D291-31806. [Slo19] W. Slofstra. The set of quantum correlations is not closed.Forum of Mathematics, Pi, 7: e1:1–e1:41,

    doi

  15. [44]

    [SW19] R

    DOI: 10.1017/fmp.2018.3. [SW19] R. Speicher and M. Weber. Quantum groups with partial commutation relations.Indiana University Mathematics Journal, 68(6): 1849–1883,

    2018 doi

  16. [45]

    [Tur36] A

    DOI: 10.1512/iumj.2019.68.7791. [Tur36] A. M. Turing. On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society. Second Series, 42: 230–265,

    2019 doi

  17. [47]

    Preprint

    Online:https://arxiv.org/abs/2507.22444. Preprint. [Vid22] T. Vidick. Almost synchronous quantum correlations.Journal of Mathematical Physics, 63(2),

  18. [48]

    [Wan98] S

    DOI: 10.1063/5.0056512. [Wan98] S. Wang. Quantum symmetry groups of finite spaces.Communications in Mathematical Physics, 195(1): 195–211,

    doi

  19. [49]

    [Zhu17] D

    DOI: 10.1007/s002200050385. [Zhu17] D. Zhuk. A proof of CSP dichotomy conjecture. InProceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), pages 331–342. IEEE,

    2017 doi

  20. [50]

    A Disproving an extension of Ji’s triangular prism gadget One way to express Ji’s triangular prism commutativity gadget is as C3□P

    DOI: 10.1145/3402029. A Disproving an extension of Ji’s triangular prism gadget One way to express Ji’s triangular prism commutativity gadget is as C3□P

    doi

  21. [1936]

    [TV25] A

    DOI: 10.1112/plms/s2-42.1.230. [TV25] A. Taller and T. Vidick. Approximating the quantum value of an LCS game is RE-hard,

    doi

  22. [1978]

    [Sch18] S

    DOI: 10.1145/800133.804350. [Sch18] S. Schmidt. The Petersen graph has no quantum symmetry.Bulletin of the London Mathematical Society, 50(3): 395–400,

  23. [1990]

    48 [Ji13] Z

    DOI: 10.1016/0095-8956(90)90132-J. 48 [Ji13] Z. Ji. Binary constraint system games and locally commutative reductions,

    doi

  24. [1991]

    [BGM+25] M

    DOI: 10.1007/BF01200056. [BGM+25] M. Brannan, D. Gromada, J. Matsuda, A. Skalski, and M. Wasilewski. A quantum Frucht’s theorem and quantum automorphisms of quantum Cayley graphs,

    doi

  25. [1998]

    [Ara04] P

    DOI: 10.1145/278298.278306. [Ara04] P. K. Aravind. Quantum mysteries revisited again.American Journal of Physics, 72(10): 1303– 1307,

  26. [2003]

    47 [Bic14] J

    DOI: 10.1090/S0002-9939-02-06798-9. 47 [Bic14] J. Bichon. Hopf-Galois objects and cogroupoids.Rev. Un. Mat. Argentina, 55(2): 11–69,

    doi

  27. [2004]

    [Ban05] T

    DOI: 10.1119/1.1773173. [Ban05] T. Banica. Quantum automorphism groups of homogeneous graphs.Journal of Functional Analysis, 224(2): 243–280,

    doi

  28. [2005]

    [BB07] T

    DOI: 10.1016/j.jfa.2004.11.002. [BB07] T. Banica and J. Bichon. Quantum automorphism groups of vertex-transitive graphs of order≤ 11.Journal of Algebraic Combinatorics, 26(1): 83–105,

    2004 doi

  29. [2007]

    [BCE+20] M

    DOI: 10.1007/s10801-006-0049-9. [BCE+20] M. Brannan, A. Chirvasitu, K. Eifler, S. Harris, V . Paulsen, X. Su, and M. Wasilewski. Bigalois extensions and the graph isomorphism game.Communications in Mathematical Physics, 375(3): 1777–1809,

    doi

  30. [2009]

    [Bul17] A

    DOI: 10.1109/FOCS.2009.32. [Bul17] A. A. Bulatov. A dichotomy theorem for nonuniform CSPs. In2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319–330. IEEE,

    2009 doi

  31. [2013]

    Preprint

    Online:https://arxiv.org/abs/1310.3794. Preprint. [JNV+21] Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen. MIP* = RE.Communications of the ACM, 64(11): 131–138,

    arXiv

  32. [2014]

    [BK09] L

    DOI: 10.33044/revuma. [BK09] L. Barto and M. Kozik. Constraint satisfaction problems of bounded width. In2009 50th Annual IEEE symposium on foundations of computer science, pages 595–603. IEEE,

    doi

  33. [2016]

    [MS24] K

    DOI: 10.1016/j.jctb.2015.12.009. [MS24] K. Mastel and W. Slofstra. Two prover perfect zero knowledge for MIP*. InProceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), pages 991–1002,

    2015 doi

  34. [2017]

    DOI: 10.4230/LIPIcs.MFCS.2017.35

    Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.MFCS.2017.35. [ÁDK+25] A. S. Árnadóttir, J. van Dobben de Bruyn, P. N. Kar, D. E. Roberson, and P. Zeman. Quantum automorphism groups of lexicographic products of graphs.Journal of the London Mathematical S...

    2017 doi

  35. [2018]

    [Sch20] S

    DOI: 10.1112/blms.12154. [Sch20] S. Schmidt.Quantum automorphism groups of finite graphs. PhD thesis, Universität des Saarlandes,

    doi

  36. [2019]

    [ALM+98] S

    DOI: 10.1016/j.jcss.2019.05.003. [ALM+98] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems.Journal of the ACM (JACM), 45(3): 501–555,

    2019 doi

  37. [2020]

    [BFL91] L

    DOI: 10.1007/s00220-019-03563-9. [BFL91] L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has two-prover interac- tive protocols.Computational Complexity, 1: 3–40,

    doi

  38. [2021]

    [JSW20] L

    DOI: 10.1145/3485628. [JSW20] L. Junk, S. Schmidt, and M. Weber. Almost all trees have quantum symmetry.Archiv der Mathematik, 115(4): 367–378,

    doi

  39. [2022]

    [Sch78] T

    DOI: 10.1112/jlms.12664. [Sch78] T. J. Schaefer. The complexity of satisfiability problems. InProceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC’78), pages 216–226,

    doi

  40. [2023]

    Preprint

    Online:https://arxiv.org/abs/2307.08129. Preprint. [Mer90] N. D. Mermin. Simple unified form for the major no-hidden-variables theorems.Physical Review Letters, 65(27): 3373–3376,

    arXiv

  41. [2024]

    [CM14] R

    DOI: 10.1145/3661814.3662118. [CM14] R. Cleve and R. Mittal. Characterization of binary constraint system games. InAutomata, Languages, and Programming (ICALP 2014), pages 320–331. Springer,

    2014

  42. [2025]

    [AKS19] A

    DOI: 10.1112/jlms.70141. [AKS19] A. Atserias, P. G. Kolaitis, and S. Severini. Generalized satisfiability problems via operator assignments.Journal of Computer and System Sciences, 105: 171–198,

    doi

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.