No quantum solutions to linear constraint systems in odd dimension from Pauli group and diagonal Cliffords

Markus Frembs; Cihan Okay; Ho Yiu Chung

doi:10.22331/q-2025-01-08-1583

No quantum solutions to linear constraint systems in odd dimension from Pauli group and diagonal Cliffords

Markus Frembs¹, Cihan Okay², and Ho Yiu Chung²

¹Centre for Quantum Dynamics, Griffith University, Yugambeh Country, Gold Coast, QLD 4222, Australia
²Department of Mathematics, Bilkent University, Ankara, Turkey

Published:	2025-01-08, volume 9, page 1583
Editor:	Dan Browne
Eprint:	arXiv:2209.14018v2
Doi:	https://doi.org/10.22331/q-2025-01-08-1583
Citation:	Quantum 9, 1583 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Linear constraint systems (LCS) have proven to be a surprisingly prolific tool in the study of non-classical correlations and various related issues in quantum foundations. Many results are known for the Boolean case, yet the generalisation to systems of odd dimension is largely open. In particular, it is not known whether there exist LCS in odd dimension, which admit finite-dimensional quantum, but no classical solutions. In recent work, [27] have shown that unlike in the Boolean case, where the $n$-qubit Pauli group gives rise to quantum solutions of LCS such as the Mermin-Peres square, the n-qudit Pauli group never gives rise to quantum solutions of a LCS in odd dimension. Here, we generalise this result towards the Clifford hierarchy. More precisely, we consider tensor products of groups generated by (single-qudit) Pauli and diagonal Clifford operators.

► BibTeX data

@article{Frembs2025noquantumsolutions,
  doi = {10.22331/q-2025-01-08-1583},
  url = {https://doi.org/10.22331/q-2025-01-08-1583},
  title = {No quantum solutions to linear constraint systems in odd dimension from {P}auli group and diagonal {C}liffords},
  author = {Frembs, Markus and Okay, Cihan and Chung, Ho Yiu},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1583},
  month = jan,
  year = {2025}
}

► References

[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys. Rev. A, 70:052328, (Nov 2004).
https://doi.org/10.1103/PhysRevA.70.052328

[2] Alex Arkhipov. Extending and characterizing quantum magic games. arXiv.1209.3819 (2012).
https://doi.org/10.48550/arXiv.1209.3819

[3] Ingemar Bengtsson, Kate Blanchfield, Earl Campbell, and Mark Howard. Order 3 symmetry in the clifford hierarchy. J. Phys. A, 47(45):455302, (2014).
https://doi.org/10.1088/1751-8113/47/45/455302

[4] Richard Cleve, Li Liu, and William Slofstra. Perfect commuting-operator strategies for linear system games. J. Math. Phys. 58(1):012202, (2017).
https://doi.org/10.1063/1.4973422

[5] Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming, pages 320–331, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-662-43948-7_27

[6] S. X. Cui, D. Gottesman, and A. Krishna. Diagonal gates in the Clifford hierarchy. Phys. Rev. Lett., 95(1):012329, (2017).
https://doi.org/10.1103/PhysRevA.95.012329

[7] Niel de Beaudrap. A linearized stabilizer formalism for systems of finite dimension. Quantum Info. Comput., 13(1-2):73–115, (Jan 2013).
https://doi.org/10.26421/QIC13.1-2-6

[8] Nadish de Silva. Efficient quantum gate teleportation in higher dimensions. Proc. Math. Phys. Eng. Sci., 477(2251):20200865, (2021).
https://doi.org/10.1098/rspa.2020.0865

[9] Markus Frembs, Sam Roberts, and Stephen D. Bartlett. Contextuality as a resource for measurement-based quantum computation beyond qubits. New J. Phys., 20(10):103011, (Oct 2018).
https://doi.org/10.1088/1367-2630/aae3ad

[10] Markus Frembs, Sam Roberts, Earl T Campbell, and Stephen D Bartlett. Hierarchies of resources for measurement-based quantum computation. New J. Phys., 25(1):013002, (Jan 2023).
https://doi.org/10.1088/1367-2630/acaee2

[11] Tobias Fritz. Tsirelson’s problem and Kirchberg’s conjecture. Rev. Math. Phys., 24(05):1250012, (2012).
https://doi.org/10.1142/S0129055X12500122

[12] Tobias Fritz. Quantum logic is undecidable. Arch. Math. Logic 60, 329-341, (2021).
https://doi.org/10.1007/s00153-020-00749-0

[13] Keisuke Fujii. Stabilizer Formalism and Its Applications, pages 24–55. Springer Singapore, Singapore, (Dec 2015).
https://link.springer.com/chapter/10.1007/978-981-287-996-7_2

[14] Daniel Gottesman. Stabilizer codes and quantum error correction. arXiv:quant-ph/9705052 (1997).
https://doi.org/10.48550/arXiv.quant-ph/9705052
arXiv:quant-ph/9705052

[15] Daniel Gottesman. Theory of fault-tolerant quantum computation. Phys. Rev. A, 57:127–137, (Jan 1998).
https://doi.org/10.1103/PhysRevA.57.127

[16] Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402(6760):390–393, (Nov 1999).
https://doi.org/10.1038/46503

[17] David Gross and Maarten Nest. The LU-LC conjecture, diagonal local operations and quadratic forms over $GF(2)$. Quantum Information & Computation, 8:263–281, (Mar 2008).
https://dl.acm.org/doi/10.5555/2011763.2011766

[18] Brian C. Hall. Lie Groups, Lie Algebras, and Representations: An Elementary Introduction. Springer.
https://doi.org/10.1007/978-3-319-13467-3

[19] Mark Howard. Maximum nonlocality and minimum uncertainty using magic states. Phys. Rev. A, 91:042103, (Apr 2015).
https://doi.org/10.1103/PhysRevA.91.042103

[20] Mark Howard and Jiri Vala. Qudit versions of the qubit ${\pi}/8$ gate. Phys. Rev. A, 86:022316, (Aug 2012).
https://doi.org/10.1103/PhysRevA.86.022316

[21] Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. $\mathrm{MIP}^*=\mathrm{RE}$. Communications of the ACM, Volume 64, Issue 11 (2021), p131-138.
https://doi.org/10.1145/3485628

[22] M. Junge, M. Navascues, C. Palazuelos, D. Perez-Garcia, V. B. Scholz, and R. F. Werner. Connes' embedding problem and Tsirelson's problem. J. Math. Phys., 52(1), (Jan 2011).
https://doi.org/10.1063/1.3514538

[23] Eberhard Kirchberg. On non-semisplit extensions, tensor products and exactness of group $C^*$-algebras. Inventiones mathematicae, 112:449–489, (1993).
https://doi.org/10.1007/BF01232444

[24] N. David Mermin. Simple unified form for the major no-hidden-variables theorems. Phys. Rev. Lett., 65:3373–3376, (Dec 1990).
https://doi.org/10.1103/PhysRevLett.65.3373

[25] N. David Mermin. Hidden variables and the two theorems of John Bell. Rev. Mod. Phys., 65:803–815, (Jul 1993).
https://doi.org/10.1103/RevModPhys.65.803

[26] Cihan Okay and Robert Raussendorf. Homotopical approach to quantum contextuality. Quantum, 4:217, (Jan 2020).
https://doi.org/10.22331/q-2020-01-05-217

[27] Hammam Qassim and Joel J Wallman. Classical vs quantum satisfiability in linear constraint systems modulo an integer. J. Phys. A, 53(38):385304, (Aug 2020).
https://doi.org/10.1088/1751-8121/aba306

[28] Robert Raussendorf. Contextuality in measurement-based quantum computation. Phys. Rev. A, 88(2):022322, (Aug 2013).
https://doi.org/10.1103/PhysRevA.88.022322

[29] William Slofstra. The set of quantum correlations is not closed. Forum of Mathematics, Pi, 7:41, (Jan 2019).
https://doi.org/10.1017/fmp.2018.3

[30] William Slofstra. Tsirelson’s problem and an embedding theorem for groups arising from non-local games. J. Am. Math. Soc., 33(1):1–56, (Sep 2019).
https://doi.org/10.1090/jams/929

[31] William Slofstra and Luming Zhang. private communication.

[32] Boris S. Tsirelson. Bell inequalities and operator algebras. This was posted by Boris Tsirelson as problem, 33., (2006).
http://web.archive.org/web/20090414083019/http://www.imaph.tu-bs.de/qi/problems/33.html

[33] Bei Zeng, Xie Chen, and Isaac L Chuang. Semi-Clifford operations, structure of $C(k)$ hierarchy, and gate complexity for fault-tolerant quantum computation. Phys. Rev. A, 77(4):042313, (Apr 2008).
https://doi.org/10.1103/PhysRevA.77.042313

Cited by

[1] Axel Muller and Alain Giorgetti, "An abstract structure determines the contextuality degree of observable-based Kochen-Specker proofs", Journal of Mathematical Physics 66 8, 082203 (2025).

[2] Nadish de Silva and Oscar Lautsch, "The Clifford hierarchy for one qubit or qudit", Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 481 2324, 20250035 (2025).

[3] Ho Yiu Chung, Cihan Okay, and Igor Sikora, "Simplicial techniques for operator solutions of linear constraint systems", arXiv:2305.07974, (2023).

[4] Andrei A. Bulatov and Stanislav Živný, "Satisfiability of commutative vs. non-commutative CSPs", arXiv:2404.11709, (2024).

[5] William Slofstra and Lu-Ming Zhang, "Operator solutions of linear systems and small cancellation", arXiv:2412.10305, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 18:50:28) and SAO/NASA ADS (last updated successfully 2026-08-09 18:50:29). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.