cqm — a compiled language for Categorical Quantum Mechanics

Warning

This is a highly experimental project. I am using large amounts of large language model usage, almost NO CODE is being written by hand. This is an experimental usage of the linxiv tool; to see if a Large Language Model with access to a curated, vast, knowledge base of open source research knowledge from an active research area can create something that only has a couple of close semantic matches overall.

cqm is a small programming language and ahead-of-time compiler for Categorical Quantum Mechanics. A .cqm program is a string diagram (a point-free term in a dagger-compact closed category); the compiler typechecks it, lowers it to a content-addressed hypergraph IR, rewrites it with a convex-DPO ZX engine, verifies diagram equality, simulates it to an exact symbolic state, and can lower it to a native binary.

Everything is exact and symbolic — there is no floating point anywhere. Amplitudes are elements of an exact ring (rationals, roots of unity zeta_n, and a free-angle Laurent variable t = e^{i·alpha}), never decimals.

Scope: v0 targets a classical native binary (no quantum hardware) and does its real work at and above the IR. It is not a numerical simulator, QIR/MLIR backend, or a PyZX-style optimizer. See CONTEXT.md and docs/adr/.

Build

Requires a recent Rust toolchain and LLVM 21 (the backend links inkwell/llvm-sys):

# point llvm-sys at your LLVM 21 prefix (Fedora shown; adjust for your distro)
export LLVM_SYS_211_PREFIX=/usr/lib64/llvm21
cargo build            # builds the `cqm` binary at target/debug/cqm
cargo test --workspace # 296 tests, all exact, no floats

Optional: the symengine feature wires a real CAS behind the scalar arm (needs libsymengine-dev); it is off by default (the build works without it):

cargo test -p cqm-scalar --features symengine

Quick start

cqm examples/snake.cqm

entry : ["q"] -> ["q"]   [2x2]   ir-hash be26b2e58d5cad1e
amplitudes:
[0,0] : 1
[1,1] : 1

The "snake" — (cup ⊗ id) ; (id ⊗ cap) — pulls straight to the identity wire (the yanking equation), so it simulates to the 2×2 identity.

The language

A program is a sequence of declarations. Comments are // or #.

colour q quantum ;                         // declare a wire colour (object generator)
def bell : I -> q (x) q = cup[q] ;          // a named diagram (def)

Objects (types) are words over colours: I is the unit (empty word), q, q (x) q, … A diagram has a type dom -> cod.

Building diagrams (point-free combinators):

syntax	meaning
f ; g	sequential composition (needs cod(f) = dom(g))
f (x) g	tensor / parallel ((x) is ⊗)
f^	dagger (adjoint): mirror + entry-wise conjugation
id(w)	identity wire(s) on word w
swap[a, b]	swap two wires
cup[c] / cap[c]	the cup I -> c⊗c / cap c⊗c -> I (Bell unit/counit)

ZX generators (spiders), with an optional phase and a [dom,cod] leg arity:

literal	meaning
Z(p)[d,c]	Z-spider, d legs in, c legs out, phase p
X(p)[d,c]	X-spider
H[1,1]	Hadamard (1→1 only)

Examples: Z(pi/2)[1,1] is the S gate; Z(0)[1,2] and X(0)[2,1] build a CNOT; Z(0)[0,3] is a 3-qubit GHZ state.

Phases are angles: integers, pi, rationals like pi/2 / pi/4, a free symbol alpha, and + - * /. Rational-π phases become exact roots of unity; a bare free angle alpha/-alpha becomes the Laurent variable t = e^{i·alpha}. Mixed/multi-angle phases (e.g. alpha + pi/2) are out of the exact ring — see Ceilings below.

Generators you declare with gen f : q -> q ; exist for typing, but only the built-in ZX vocabulary (Z/X/H, cup/cap/swap/id) has executable semantics in v0.

defs may reference other defs by name — they are inlined.

Qudits (d-level wires). A colour defaults to a qubit (2 levels); declare a wider one with dim <n> (n ≥ 2). The exact d-level oracle simulates and decides diagrams over qudits (d ≥ 3): the Z-spider with its d−1 per-level phases Z(p1, ..., p_{d-1})[d,c] (positional — Z(a,b) ≠ Z(b,a)), the X-spider X(...) (the Fourier-conjugate of the Z-spider), and the d-level Fourier gate (the Hadamard generalisation, which is H at dim=2):

colour q3 quantum dim 3 ;                         // a qutrit wire (3 levels)
def ghz3 : I -> q3 (x) q3 (x) q3 = Z(0)[0,3] ;    // a qutrit GHZ

This simulates to |000> + |111> + |222> — in base-3 flat indexing, a 27×1 vector with amplitude 1 at |0>, |13>, |26>:

entry : [] -> ["q3", "q3", "q3"]   [27x1]   ir-hash dce33d6087f11552
amplitudes:
|0> : 1
|13> : 1
|26> : 1

Ceiling: v0 ships the exact d-level oracle but no d-level rewrite rules, so on d ≥ 3 the engine abstains and the exact Oracle tier decides. The qudit-Clifford / dit-stabiliser rewrite fragment is the next lever.

The qudit generators follow Wang's qufinite ZX-calculus — the X-spider is the (unnormalized) Fourier-conjugate of the Z-spider, X = F·Z·F† (see Citations).

Running

The entry point is a def named main, or the last def, or one chosen with --gen.

cqm <file.cqm>                      # simulate the entry, print its exact symbolic state
cqm <file.cqm> --gen <def>          # pick which def to run
cqm <file.cqm> --no-sim             # lower + canonical-hash only (skip the matrix)
cqm <file.cqm> --emit-binary <out>  # compile a native binary that prints the state
cqm verify <file.cqm> <defA> <defB> # decide equality of two defs, print the verdict
cqm simplify <file.cqm> <def>       # reduce a circuit, print edges before->after + verdict
cqm phase <angle>                   # lower an angle to its exact ring scalar

cqm simplify runs the rewrite engine as a reducer: it lowers the def, rewrites it to a fixpoint under the v0 ZX data rules (H;H cancellation, Z(a);Z(b) fusion, Z(0) identity-removal) plus phase-aware Clifford-simp — graph-state local-complementation / pivot eliminations that shrink Clifford circuits up to a scalar — and reports the edge count before → after plus the equivalence verdict (the reduced diagram decided against the input, so the shrink is verified to preserve the map). Clifford-simp rides the best-effort engine tier only; the forced equality decider stays data-rule-only, so no procedure can reach a forced verdict:

cqm simplify examples/simplify_demo.cqm main
# main: 16 edges -> 2 edges   ir-hash 12dd241fe4352b39   EQUAL_UP_TO_PHASE

--no-sim does only the graph work (lowering + the automorphism-pruned canonical hash), which is polynomial in diagram size and independent of qubit count — so it scales to many qubits where the exponential state vector would not fit in memory:

cqm examples/entangle32.cqm --no-sim
# entry : [q×32] -> [q×32]   [2^32 x 2^32]   ir-hash dd27a69c4ffb705b   (no-sim)   (~10 ms)

Verdicts

cqm verify returns a three-valued, sound-but-incomplete verdict:

• EQUAL — the diagrams denote the same map.
• EQUAL_UP_TO_PHASE — equal up to a nonzero global scalar (e.g. the unnormalized-H convention drops a factor of √2 per Hadamard).
• NOT_EQUAL — proven distinct.
• UNKNOWN — not decided. UNKNOWN is never widened to NOT_EQUAL — the verifier abstains rather than guess, so a definite verdict is always trustworthy.

cqm verify examples/ghz_circuit.cqm ghz_circuit ghz_spider   # EQUAL_UP_TO_PHASE

Examples

file	shows
snake.cqm	yanking: (cup⊗id);(id⊗cap) = id
bell.cqm	a Bell state `
cnot.cqm	CNOT from a control Z[1,2] + target X[2,1] spider
ghz.cqm	a 3-qubit GHZ state as one spider Z(0)[0,3]
ghz_circuit.cqm	GHZ as a CNOT circuit vs. as a spider, verified equal; CNOT self-inverse
circuit.cqm	single-qubit multi-layer: def-inlining, dagger phases, free-angle × cyclotomic mixing
symmetry.cqm	iso-invariant canonical form: two terms for one diagram → one hash
entangle32.cqm	a 32-qubit connected entangler (H layer + CNOT ladder), run matrix-free
simplify_demo.cqm	cqm simplify: a 5-qubit, 16-gate redundant circuit the engine reduces to 2 spiders, verified equal

What's exact, and the ceilings

Exact symbolic throughout; no floats (a locked invariant, enforced by review + the backend's no-float gate). Known v0 limits (with upgrade paths) live in TODO.md — notably: the FdHilb oracle is exponential in qubit count (toy-to-small instances; use --no-sim above that line), the unnormalized Hadamard makes some equalities hold only up to scalar, and out-of-ring phases (mixed/multi free angle) are decided only by the optional SymEngine arm, not the simulator.

Going deeper

• CONTEXT.md — architecture, glossary, crate map.
• PROGRESS.md — what's built, with commit hashes.
• docs/adr/ — the load-bearing design decisions.
• docs/design/build-execution-plan.md — the full phased plan.

Citations

• Aleks Kissinger and John van de Wetering, Picturing Quantum Software: An Introduction to the ZX-Calculus and Quantum Compilation, zxcalc.github.io/book (2025) — qubit ZX-calculus conventions throughout.
• Quanlong Wang, Qufinite ZX-calculus: a unified framework of qudit ZX-calculi, arXiv:2104.06429 (2021) — qudit X-spider construction.