Quantum Graph Theory by Example
- 1LaBRI, Université de Bordeaux, CNRS, Bordeaux INP, UMR-5800, France
- 2Laboratoire de Physique Théorique, Université de Toulouse, CNRS, UPS, France
Abstract
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.
Related
- A Quantum/Classical Example Oracle Separation for Making Things Up
- An example of universal braiding in Links--Gould topological quantum computation
- A general theorem in spectral extremal graph theory
- Single-graph rational exponents in mixed multicolour Ramsey theory
- Chaotic CLT using Poisson Fourth Moment Theorem and Graph Theory
BibTeX
@article{spitzer2026quantum,
title = {{Quantum Graph Theory by Example}},
author = {Gian Luca Spitzer and Ion Nechita},
journal = {Quantum},
year = {2026},
month = oct,
doi = {10.22331/q-2026-10-06-2228},
eprint = {2603.23651},
archivePrefix = {arXiv},
url = {https://quantum-journal.org/papers/q-2026-10-06-2228/},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Quantum Graph Theory by Example
AU - Gian Luca Spitzer
AU - Ion Nechita
PY - 2026
DA - 2026/10/06
JO - Quantum
DO - 10.22331/q-2026-10-06-2228
UR - https://quantum-journal.org/papers/q-2026-10-06-2228/
AB - 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.
SN - 2521-327X
ER -