Quantum Graph Theory by Example

Quantum 10, 2228 (2026). https://doi.org/10.22331/q-2026-10-06-2228 Quantum graphs have been introduced by Duan, Severini, and Winter to describe the zero-error behaviour of quantum channels. Since then, quantum graph theory has become a field of study in its own right. A substantial source of difficulty in working with quantum graphs compared to classical graphs stems from the fact that they are no longer discrete objects. This makes it generally difficult to construct insightful, non-trivial examples. We present a collection of non-trivial quantum graphs that can be thought of in discrete terms, and that can be expressed in the diagrammatic formalism introduced by Musto, Reutter, and Verdon. The examples arise as the quantum graphs acted on by increasingly smaller classical matrix groups, and are parametrised by triples of matrices $(A, B, C)$. The parametrisation reveals a clean decomposition of quantum graph structure into classical and genuinely quantum components: $A$ and $C$ are described by a classical weighted graph called the strange graph, while $B$ provides a purely quantum contribution with no classical analogue. Based on this model, we give exact formulas or establish bounds for quantum graph parameters, such as the number of connected components, the chromatic number, the independence number, and the clique number. Our results provide the first large, parametric families of quantum graphs for which standard graph parameters can be computed analytically.

Quantum graphs have been introduced by Duan, Severini, and Winter to describe the zero-error behaviour of quantum channels. Since then, quantum graph theory has become a field of study in its own right. A substantial source of difficulty in working with quantum graphs compared to classical graphs stems from the fact that they are no longer discrete objects. This makes it generally difficult to construct insightful, non-trivial examples. We present a collection of non-trivial quantum graphs that can be thought of in discrete terms, and that can be expressed in the diagrammatic formalism introduced by Musto, Reutter, and Verdon. The examples arise as the quantum graphs acted on by increasingly smaller classical matrix groups, and are parametrised by triples of matrices $(A, B, C)$. The parametrisation reveals a clean decomposition of quantum graph structure into classical and genuinely quantum components: $A$ and $C$ are described by a classical weighted graph called the strange graph, while $B$ provides a purely quantum contribution with no classical analogue. Based on this model, we give exact formulas or establish bounds for quantum graph parameters, such as the number of connected components, the chromatic number, the independence number, and the clique number. Our results provide the first large, parametric families of quantum graphs for which standard graph parameters can be computed analytically.

[1] Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis, ``Quantum and non-signalling graph isomorphisms'' Journal of Combinatorial Theory, Series B 136, 289-328 (2019). https://doi.org/10.1016/j.jctb.2018.11.002

[2] Teodor Banica ``Symmetries of a generic coaction'' Mathematische Annalen 314, 763–780 (1999). https://doi.org/10.1007/s002080050315

[3] Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, and Xiaoming Sun, ``From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: Another bridge between graphs and alternating matrix spaces'' SIAM Journal on Computing 50, 924–971 (2021). https://doi.org/10.1137/19M1299128

[4] Michael Brannan, Priyanga Ganesan, and Samuel J. Harris, ``The quantum-to-classical graph homomorphism game'' Journal of Mathematical Physics 63, 112204 (2022). https://doi.org/10.1063/5.0072288

[5] Arkadiusz Bochniakand Paweł Kasprzak ``Quantum Mycielski graphs'' Journal of Noncommutative Geometry 2025 (2025). https://doi.org/10.4171/jncg/629

[6] Michael Brannan, Alexandru Chirvasitu, Kari Eifler, Samuel Harris, Vern Paulsen, Xiaoyu Su, and Mateusz Wasilewski, ``Bigalois Extensions and the Graph Isomorphism Game'' Communications in Mathematical Physics 375, 1777–1809 (2020). https://doi.org/10.1007/s00220-019-03563-9

[7] Gareth Boreland, Ivan G Todorov, and Andreas Winter, ``Sandwich theorems and capacity bounds for non-commutative graphs'' Journal of Combinatorial Theory, Series A 177, 105302 (2021). https://doi.org/10.1016/j.jcta.2020.105302

[8] Ingemar Bengtssonand Karol Zyczkowski ``Geometry of quantum states: an introduction to quantum entanglement'' Cambridge University Press (2006). https://doi.org/10.1017/CBO9780511535048

[9] Toby S. Cubitt, Jianxin Chen, and Aram W. Harrow, ``Superactivation of the Asymptotic Zero-Error Classical Capacity of a Quantum Channel'' IEEE Transactions on Information Theory 57, 8114–8126 (2011). https://doi.org/10.1109/TIT.2011.2169109

[10] Kristin Courtney, Priyanga Ganesan, and Mateusz Wasilewski, ``Connectivity for quantum graphs via quantum adjacency operators'' (2025). https://doi.org/10.48550/arXiv.2505.22519 arXiv:2505.22519

[11] Man-Duen Choi ``Completely positive linear maps on complex matrices'' Linear algebra and its applications 10, 285–290 (1975). https://doi.org/10.1016/0024-3795(75)90075-0

[12] Bob Coecke, Dusko Pavlovic, and Jamie Vicary, ``A new description of orthogonal bases'' Mathematical Structures in Computer Science 23, 555–567 (2013). https://doi.org/10.1017/S0960129512000047

[13] Matthew Daws ``Quantum graphs: different perspectives, homomorphisms and quantum automorphisms'' Communications of the American Mathematical Society 4, 117–181 (2024). https://doi.org/10.1090/cams/30

[14] Reinhard Diestel ``Graph theory: Springer GTM'' Reinhard Diestel (2025). https://doi.org/10.1007/978-3-662-70107-2

[15] Runyao Duan, Simone Severini, and Andreas Winter, ``Zero-Error Communication via Quantum Channels, Noncommutative Graphs, and a Quantum Lovász Number'' IEEE Transactions on Information Theory 59, 1164–1174 (2013) Conference Name: IEEE Transactions on Information Theory. https://doi.org/10.1109/TIT.2012.2221677

[16] Runyao Duan ``Super-Activation of Zero-Error Capacity of Noisy Quantum Channels'' (2009). https://doi.org/10.48550/arXiv.0906.2527

[17] Tilo Eggelingand Reinhard F Werner ``Separability properties of tripartite states with U $\otimes$ U $\otimes$ U symmetry'' Physical Review A 63, 042111 (2001). https://doi.org/10.1103/PhysRevA.63.042111

[18] Priyanga Ganesan ``Spectral bounds for the quantum chromatic number of quantum graphs'' Linear Algebra and its Applications 674, 351–376 (2023). https://doi.org/10.1016/j.laa.2023.06.007

[19] Aabhas Gulati, Ion Nechita, and Satvik Singh, ``Entanglement in cyclic sign invariant quantum states'' Journal of Mathematical Physics 66 (2025). https://doi.org/10.1063/5.0285294

[20] Adina Goldberg ``Quantum games and synchronicity'' Quantum 10, 1964 (2026). https://doi.org/10.22331/q-2026-01-14-1964

[21] Daniel Gromada ``Some examples of quantum graphs'' Letters in Mathematical Physics 112, 122 (2022). https://doi.org/10.1007/s11005-022-01603-5

[22] Daniel Gromada ``Quantum symmetries of Hadamard matrices'' Transactions of the American Mathematical Society 377, 6341–6377 (2024). https://doi.org/10.1090/tran/9153

[23] Roe Goodmanand Nolan R Wallach ``Symmetry, representations, and invariants'' Springer (2009). https://doi.org/10.1007/978-0-387-79852-3

[24] Chris Heunenand Jamie Vicary ``Categories for Quantum Theory: An Introduction'' Oxford University PressOxford (2019). https://doi.org/10.1093/oso/9780198739623.001.0001

[25] Teiko Heinosaariand Mário Ziman ``The mathematical language of quantum theory: from uncertainty to entanglement'' Cambridge University Press (2011). https://doi.org/10.1017/CBO9781139031103

[26] Emanuel Knilland Raymond Laflamme ``Theory of quantum error-correcting codes'' Physical Review A 55, 900 (1997). https://doi.org/10.1103/PhysRevA.55.900

[27] Michael Keyland Reinhard F Werner ``Optimal cloning of pure states, testing single clones'' Journal of Mathematical Physics 40, 3283–3299 (1999). https://doi.org/10.1063/1.532887

[28] Junichiro Matsuda ``Classification of quantum graphs on M2 and their quantum automorphism groups'' Journal of Mathematical Physics 63 (2022). https://doi.org/10.1063/5.0081059

[29] Junichiro Matsuda ``Algebraic connectedness and bipartiteness of quantum graphs'' Communications in Mathematical Physics 405, 185 (2024). https://doi.org/10.1007/s00220-024-05046-y

[30] Benjamin Musto, David Reutter, and Dominic Verdon, ``A compositional approach to quantum functions'' Journal of Mathematical Physics 59, 081706 (2018). https://doi.org/10.1063/1.5020566

[31] Ion Nechitaand Sang-Jun Park ``Random covariant quantum channels'' Annales Henri Poincaré 1–61 (2025). https://doi.org/10.1007/s00023-025-01558-y

[32] Ion Nechitaand Satvik Singh ``A graphical calculus for integration over random diagonal unitary matrices'' Linear Algebra and its Applications 613, 46–86 (2021). https://doi.org/10.1016/j.laa.2020.12.014

[33] Sang-Jun Park, Yeong-Gwang Jung, Jeongeun Park, and Sang-Gyun Youn, ``A universal framework for entanglement detection under group symmetry'' Journal of Physics A: Mathematical and Theoretical 57, 325304 (2024). https://doi.org/10.1088/1751-8121/ad6413

[34] Vern Paulsen ``Completely bounded maps and operator algebras'' Cambridge University Press (2002). https://doi.org/10.1017/CBO9780511546631

[35] Oliver Rudolph ``A separability criterion for density operators'' Journal of Physics A: Mathematical and General 33, 3951 (2000). https://doi.org/10.1088/0305-4470/33/21/308

[36] Oliver Rudolph ``On the cross norm criterion for separability'' Journal of Physics A: Mathematical and General 36, 5825 (2003). https://doi.org/10.1088/0305-4470/36/21/311

[37] P. Selinger ``A Survey of Graphical Languages for Monoidal Categories'' Springer Berlin Heidelberg (2011). https://doi.org/10.1007/978-3-642-12821-9_4

[38] C. Shannon ``The zero error capacity of a noisy channel'' IRE Transactions on Information Theory 2, 8–19 (1956). https://doi.org/10.1109/TIT.1956.1056798

[39] Satvik Singhand Ion Nechita ``Diagonal unitary and orthogonal symmetries in quantum theory'' Quantum 5, 519 (2021). https://doi.org/10.22331/q-2021-08-09-519

[40] Gian Luca Spitzer ``Unification of Quantum Graph Properties'' (2026) arXiv:2607.28024 [math.OA]. https://doi.org/10.48550/arXiv.2607.28024

[41] Dan Stahlke ``Quantum zero-error source-channel coding and non-commutative graph theory'' IEEE Transactions on Information Theory 62, 554–577 (2015). https://doi.org/10.1109/TIT.2015.2496377

[42] Helge Tverberg ``A generalization of Radon's theorem'' J. London Math. Soc 41, 123–128 (1966). https://doi.org/10.1112/jlms/s1-41.1.123

[43] Jamie Vicary ``Categorical Formulation of Finite-Dimensional Quantum Algebras'' Communications in Mathematical Physics 304, 765–796 (2011). https://doi.org/10.1007/s00220-010-1138-0

[44] Mateusz Wasilewski ``On quantum Cayley graphs'' Documenta Mathematica 29, 1281–1317 (2024). https://doi.org/10.4171/DM/987

[45] Nik Weaver ``Quantum relations'' (2010). https://doi.org/10.48550/arXiv.1005.0354 arXiv:1005.0354

[46] Nik Weaver ``A “quantum” Ramsey theorem for operator systems'' Proceedings of the American Mathematical Society 145, 4595–4605 (2017). https://doi.org/10.1090/proc/13606

[47] Nik Weaver ``The "quantum" turan problem for operator systems'' Pacific Journal of Mathematics 301, 335–349 (2019). https://doi.org/10.2140/pjm.2019.301.335

[48] Nik Weaver ``Quantum graphs as quantum relations'' The Journal of Geometric Analysis 31, 9090–9112 (2021). https://doi.org/10.1007/s12220-020-00578-w

[49] Reinhard F Werner ``Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model'' Physical Review A 40, 4277 (1989). https://doi.org/10.1103/PhysRevA.40.4277

Could not fetch Crossref cited-by data during last attempt 2026-10-06 13:06:39: Could not fetch cited-by data for 10.22331/q-2026-10-06-2228 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2026-10-06 13:06:39).

analiza aiqbench

Quantum Graph Theory by Example

Subiecte conexe