The computational atlas and open directions
On this page · Permalink · Source line 4804
12.1 The exact computational atlas
On this page · Permalink · Source line 4805
12.1.1 Purpose and design
On this page · Permalink · Source line 4813
The accompanying code is an audit-oriented finite mathematics package rather than a production compiler. Its goals are:
exact state representations with no floating-point ambiguity;
complete finite search where the state space is tractable;
explicit witnesses and reconstructible paths;
small, dependency-free core algorithms;
frozen JSON results and regression tests;
separation between proved, computed, and proposed claims.
The package is named catalytic_gate_atlas. Binary matrices are tuples of integer row bitmasks, and reversible Boolean maps are exact permutations of basis-state indices.
12.1.2 State models
On this page · Permalink · Source line 4833
12.1.2.1 Binary matrices
On this page · Permalink · Source line 4834
An \(m\times m\) matrix over \({\mathbb F}_2\) is stored as
where bit \(j\) of \(r_i\) is the \((i,j)\) entry. Matrix multiplication is exact XOR accumulation.
12.1.2.2 Symplectic Clifford states
On this page · Permalink · Source line 4841
An \(n\)-qubit Clifford modulo global phase and Pauli translation is represented by its action on Pauli exponent vectors
The state space is \({\operatorname{Sp}}(2n,2)\). The restricted parabolic group is generated by \(S\), CZ, and CNOT; the ambient group additionally permits \(H\).
12.1.2.3 Classical reversible states
On this page · Permalink · Source line 4848
A reversible map on \(n\) bits is stored as a permutation of \(\{0,\ldots,2^n-1\}\). Composition is exact. The affine subgroup is generated by \(X\) and CNOT, and the ambient three-bit group adds Toffoli.
12.1.3 Shortest-path engines
On this page · Permalink · Source line 4851
The package implements:
breadth-first search for unit costs;
\(0\)–\(1\) breadth-first search when gates are free or unit cost;
Dijkstra search for general nonnegative integer weights;
parent maps for witness reconstruction;
defect distributions on a restricted target set.
Algorithm 12.1: Breadth-first defect census
Given restricted generators \(S_R\), ambient generators \(S_A\), and identity \(e\):
compute \(d_R\) on \(\langle S_R\rangle\);
compute \(d_A\) on \(\langle S_A\rangle\);
for every restricted state \(x\), compare \(d_R(x)\) and \(d_A(x)\);
record the pair \((d_R(x),d_A(x))\) and reconstruct witnesses for strict inequalities.
For a finite group this is complete because every vertex reachable from the identity is visited exactly once at its minimum distance.
12.1.4 Zero-cost gates
On this page · Permalink · Source line 4873
When local Clifford gates are free and entangling gates cost one, ordinary BFS is invalid. The package uses a deque-based \(0\)–\(1\) BFS. A zero-cost edge is pushed to the front and a unit-cost edge to the back. The resulting labels are exact shortest entangling costs.
A common error is to quotient by free gates without proving that the quotient preserves the target subset and all left/right actions. The atlas avoids this issue by running \(0\)–\(1\) BFS directly on the finite group for the reported small cases.
12.1.5 The optimized Clifford verifier
On this page · Permalink · Source line 4878
The three-qubit symplectic group has
states. A compact C++ implementation enumerates the full group and the parabolic subgroup exactly. It supports:
total primitive count;
total count with unit-cost SWAP;
entangling count with \(H\) and \(S\) free;
exact distance distributions and JSON output.
The C++ program and the independent Python implementation use the same gate matrices but different traversal code. Witness reconstruction is supplied by the Python implementation, not by the C++ census executable.
12.1.6 Computed Clifford census
On this page · Permalink · Source line 4892
| \(n\) | Metric | SWAP | \(|P_n|\) | \(|{\operatorname{Sp}}(2n,2)|\) | Defects | Max defect |
|---|---|---|---|---|---|---|
| 1 | total | no | 2 | 6 | 0 | 0 |
| 1 | entangling | no | 2 | 6 | 0 | 0 |
| 2 | total | no | 48 | 720 | 0 | 0 |
| 2 | entangling | no | 48 | 720 | 4 | 1 |
| 3 | total | no | 10,752 | 1,451,520 | 24 | 1 |
| 3 | total | yes | 10,752 | 1,451,520 | 0 | 0 |
| 3 | entangling | no | 10,752 | 1,451,520 | 1,624 | 2 |
The detailed defect distributions are:
Exact finite computation
Every entry in the table is a complete finite enumeration in the declared binary symplectic model. Phases and Pauli translations are not part of the state space. These are exact results for that quotient model, not full hardware Clifford optimizations.
12.1.7 Computed affine-versus-Toffoli census
On this page · Permalink · Source line 4922
For three bits:
The complete census finds no affine target with a strict defect under total primitive count or under entangling count with NOT free.
| Metric | Restricted size | Ambient size | Restricted diameter | Defects |
|---|---|---|---|---|
| Total | 1,344 | 40,320 | 7 | 0 |
| Entangling | 1,344 | 40,320 | 6 | 0 |
12.1.8 Linear symbolic checks
On this page · Permalink · Source line 4940
The Python module verifies that the displayed six-row ambient and restricted words produce the same canonical target modulo
The lower bounds and ring universality are proved in the core chapter; these modular checks are regression tests rather than the logical basis of the theorem.
12.1.9 Witness format
On this page · Permalink · Source line 4947
A witness record contains:
the target matrix or permutation;
restricted and ambient costs;
a named restricted gate path;
a named ambient gate path;
the metric and gate alphabet;
the state-model convention.
For example, the two-qubit entangling Clifford witness has restricted path
and ambient path
Only two gates in the ambient path are charged by the entangling metric.
12.1.10 Certificates beyond full enumeration
On this page · Permalink · Source line 4967
For larger systems, the following certificate styles are supported in principle.
Meet in the middle. Store forward and backward balls whose radii sum to the candidate length.
SAT/SMT. Encode gate choices and endpoint equations; use an UNSAT certificate below the claimed optimum.
Integer programming. Useful when a fixed gate skeleton leaves discrete routing choices.
Algebraic elimination. Eliminate continuous gate parameters from bounded-length word equations.
Dual potentials. Exhibit a one-Lipschitz potential attaining the claimed lower bound.
Quotient search. Search cosets only after proving that the quotient is compatible with the cost and target class.
12.1.11 Multiobjective search
On this page · Permalink · Source line 4978
Let each gate have a vector cost in \({\mathbb N}^r\). At each state, retain only nondominated labels. The algorithm terminates for finite state spaces with a bounded search region, but the frontier can grow exponentially.
A practical exact strategy is to scalarize with several positive weight vectors, use the resulting optima to identify candidate Pareto points, and then certify each candidate by constrained search.
12.1.12 Reproducibility commands
On this page · Permalink · Source line 4983
From the code directory:
Python atlas commands.
On this page · Permalink · Source line 4985
python -m pip install -e . --no-build-isolation
python scripts/run_atlas.py --output ../results/atlas_small.json
python -m pytest testsThe optimized three-qubit verifier can be compiled by
C++ Clifford verifier.
On this page · Permalink · Source line 4991
g++ -O3 -std=c++20 scripts/clifford_census.cpp -o scripts/clifford_census
./scripts/clifford_census --n 3 --metric total --output ../results/clifford_n3_total.json
./scripts/clifford_census --n 3 --metric entangling --output ../results/clifford_n3_entangling.json12.1.13 Validation policy
On this page · Permalink · Source line 4997
The release uses four layers of validation.
Unit tests for matrix, permutation, and path primitives.
Cross-checks of group sizes against known finite formulas.
Independent Python and C++ computations for selected Clifford cases.
Frozen JSON outputs and SHA-256 manifests in the release archive.
12.1.14 Scaling limits
On this page · Permalink · Source line 5006
Full group enumeration grows rapidly:
The four-qubit symplectic group is far beyond direct Python BFS. Future work should exploit:
double-coset normal forms,
Bruhat or parabolic decompositions,
admissible heuristics for A* search,
SAT encodings,
orbit reduction,
tensor-network representations,
distributed meet in the middle.
12.1.15 What the atlas does not prove
On this page · Permalink · Source line 5023
A finite census establishes only the declared finite model. It does not prove:
an asymptotic theorem without a separate proof,
a hardware advantage under a different cost,
robustness to approximation,
equivalence after adding ancillas,
a result for global phases or Pauli translations if they were quotiented out.
The status metadata in every result file is intended to make these boundaries machine readable.