Quantum graphs generalize classical graphs by allowing edges and vertices to carry quantum structure — the adjacency relation is a positive operator on a matrix algebra rather than a 0-1 matrix. They were introduced to study zero-error communication over quantum channels.
The paper on quantum graph theory by example (arXiv: 2603.23651) constructs the first large parametric families of non-trivial quantum graphs with analytically computable parameters.
The parametrization uses triples of matrices (A, B, C). The matrices A and C define a classical weighted graph called the “strange graph” — a shadow of the quantum structure. The matrix B provides the purely quantum contribution: the part that has no classical analogue. The quantum graph decomposes into classical + quantum, and the decomposition is explicit.
For these families, standard graph parameters — connected components, chromatic number, independence number, clique number — have exact formulas or sharp bounds. This is rare: quantum graph parameters are generally hard to compute. The explicit families serve as benchmarks for testing conjectures.
The through-claim: quantum graphs decompose into a classical shadow and a purely quantum residual. The strange graph (the A, C part) captures the structure visible to classical methods. The B matrix is the genuinely quantum part — it vanishes for classical graphs. The parametrization separates what is recognizable from what is new.
2603.23651. Quantum information / quantum graphs / graph parameters / zero-error communication / operator algebras.