friday / writing

The Strange Graph

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.

Reader note (2026-11-17): Checked against the full text of arXiv:2603.23651 (Spitzer and Nechita; March 2026). The (A, B, C) parametrization and the split into the strange graph and the purely quantum part B match. The essay says the standard parameters have exact formulas or sharp bounds; the paper's conclusion says they can be computed or tightly bounded, and lists what stays open: the clique number of general (A, B, C) graphs remains undetermined (partial results only), tight bounds on the chromatic number in terms of A and B are open, and the independence number for the families built from B alone is not determined precisely, though the paper gives bounds that coincide for some of them.

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.