Symmetry and AI-assisted discovery of magic-state factories

AI summary

Overview

Research area: Quantum information science — fault-tolerant quantum computing, magic-state distillation, and AI-assisted protocol discovery (quant-ph).

Technical level: Advanced. The paper assumes familiarity with stabilizer/CSS codes, the Clifford hierarchy, and the T/CS/CCZ gate set, though its central insight (the distance-three syndrome criterion) is stated and proved in elementary terms.

Scope (one sentence): The paper develops a unified binary-matrix framework plus symmetry-restricted and LLM-agent-driven search methods to discover magic-state distillation factories at distance three and above, reporting 699 factory classes, 564 of them new.

What This Paper Is About

Magic-state distillation converts many noisy magic states into fewer, cleaner ones, and it dominates the resource budget of fault-tolerant quantum computers. The cost of a factory is governed by its distance, but searching for distance-three and higher factories at moderate numbers of inputs has been computationally out of reach. The authors build a formulation in which distance three becomes a simple condition on syndromes, then use group symmetry and large-language-model agents to search that space, producing a catalog of new factories including several with record-low overhead exponents.

Key Contributions

1. A unified binary-matrix formulation. A single matrix G is shown to describe a factory both as a triorthogonal (or generalized triorthogonal) code and as a list of parity rotations in a circuit, with the borrowed-identity and direct-circuit search perspectives appearing as different coordinate choices on one coset (Theorem 2).

2. A distance-three syndrome criterion (Theorem 1). For a reduced circuit, distance at least three holds if and only if all syndromes are nonzero and pairwise distinct. This separates the choice of syndromes (the "parent") from the search for compatible output gates, eliminating the need to enumerate fault sets at d = 3.

3. The symmetry slot ansatz. Syndromes are grouped into orbits under a chosen group G ≤ GL(r,2), and the parent must be a union of orbits with a common output label per orbit, replacing decisions about individual syndromes with decisions about whole orbits.

4. An LLM-agent search workflow with deterministic verification. Language-model agents propose candidate structures (groups, parents), while deterministic solving and independent verification check the resulting circuits; the paper also releases a context directory of search briefs and campaign notes so readers can train their own agents.

Main Findings

• Catalog size: The searches yield 699 factory classes, of which 564 are new, spanning distances three through nine. By distance: 493 classes (382 new) at d=3, 88 (72) at d=4, 69 (65) at d=5, 42 (39) at d=6, 5 (4) at d=7, 1 (1) at d=8, and 1 (1) at d=9.

• Range of new results: New classes span n = 55 to 1715, with 320 of them at n ≤ 127. In Figure 1, of the 294 classes drawn up to n = 127, 65 lie in the exhaustively classified band n ≤ 54, 225 are new in this work, and the remaining four were already known.

• Record overhead exponents: The pure-T factories [[63,11,3]] with γ = 1.589 and [[850,128,6]] with γ = 1.057 achieve the lowest overhead exponents the authors know of among protocols with at most 100 and 1000 inputs respectively. The [[1715,287,6]] factory, with γ = 0.998, is the smallest known pure-T factory with γ < 1.

• Comparison with punctured Reed–Muller codes: Against the tabulated codes of Haah and Hastings, the authors reach a lower exponent at every distance in Table 3: d=3 [[750,210,3]] γ = 1.159 versus [[863,161,3]] γ = 1.528; d=4 [[429,83,4]] γ = 1.185 versus [[872,152,4]] γ = 1.260; d=5 [[879,145,5]] γ = 1.120 versus [[887,137,5]] γ = 1.161; d=6 [[850,128,6]] γ = 1.057 versus [[912,112,6]] γ = 1.170.

• Improvements at small sizes too: At distance three, [[127,23,3]] uses approximately 5.52 inputs per output versus 5.74 for [[109,19,3]], and [[63,11,3]] has a similar ratio of 5.73 inputs per output while consuming 63 inputs rather than 109.

• Entangled outputs: New factories deliver combinations of T, CS and CCZ states, for example [[63,6,3]] for CS^⊗3, [[63,6,3]] for CCZ^⊗2, [[100,12,4]] for CCZ^⊗4, [[63,7,3]] for T ⊗ CCZ^⊗2, [[63,12,3]] for T^⊗9 ⊗ CCZ, [[99,13,3]] for T ⊗ CCZ^⊗4, and [[112,16,3]] for T^⊗4 ⊗ CCZ^⊗4. Together the targets span every magic state needed to teleport a diagonal gate in the third level of the Clifford hierarchy.

• Scale of the search space: With r checks there are 2^(2^r − 1) candidate parents, already 2^127 at r = 7. An incomplete enumeration of the parent consisting of all nonzero length-6 columns alone found 418,281 distance-three factories at n = 63, inequivalent up to GL(k,2).

• Scope of comparison: Every reported protocol is a postselected diagonal CSS protocol, and all comparisons are within that class; catalytic and Hadamard-assisted protocols lie outside it and could reach parameters the catalog does not.

Methodology in Plain English

The authors describe a factory as a binary matrix: each column is one input magic state, the top rows are output wires and the bottom rows are check wires. A faulty input flips exactly the checks listed in its column — that pattern is its syndrome — and corrupts the outputs listed as its label.

The key move is to choose syndromes first, not circuits. The paper proves that if all syndromes are nonzero and no two inputs share the same syndrome, the factory has distance at least three. So the design problem splits in two: pick a set of syndromes (the "parent"), then find compatible output rows for it. For a fixed parent, the legal output directions form a quotient space whose dimension is the parent's "capacity," and the compatible output frames can be enumerated or, when that is too expensive, tested one target at a time with linear algebra over the binary field.

When the parent space is far too large to enumerate — 2^127 candidates at seven checks — the authors restrict it using group symmetry. A chosen group acting on the syndromes partitions them into orbits, and the search then selects whole orbits and assigns each a label, shrinking the decision space dramatically.

Choosing which group or parent to start from is acknowledged as heuristic, so that choice is delegated to large-language-model agents coordinated by an orchestrator: agents read solver outcomes and write proposals for later runs. Crucially, the language model only proposes structures; a deterministic solver and independent verification check every resulting circuit. All reported protocols are explicit circuits available in a public database.

Why This Matters

Lower overhead exponents translate directly into fewer physical qubits and less time spent on distillation, which resource estimates identify as a large share of a fault-tolerant machine's cost. By charting distance-three-and-above factories beyond the exhaustively classified range (previously n + k ≤ 38 by Nezami and Haah, extended to n ≤ 54 in the authors' companion paper), the work opens a regime that matters for practical, large-algorithm error rates.

Real-world applications (as framed by the paper's context):

• Resource estimation and architecture planning for surface-code and other fault-tolerant layouts, where distillation cost is a dominant term.
• Compilation of large quantum algorithms that require error rates only distance-three-or-higher distillation can supply.
• Synthillation-style workflows, where a factory natively delivers the gate a circuit needs (CS, CCZ, or combinations) rather than the T states it would otherwise be built from.
• Supplying magic states for gate teleportation of any diagonal gate in the third level of the Clifford hierarchy, including entangled multi-qubit outputs.

Industry relevance: The work comes from IBM Quantum researchers (with a NIST/University of Maryland and an MIT affiliation) and is aimed squarely at the practical fault-tolerant regime; the authors describe their results as the beginning of an active, open-source repository of distillation protocols, methods and data for the quantum community.

Future Directions

• Extending distance and scale. The distance-three criterion is exact but higher distances remain conditions over fault subsets; the paper notes d ≥ 4 holds if and only if the labeling is additive on every triple of syndromes summing to zero, leaving room for efficient higher-distance searches.

• Removing the heuristic in group choice. The authors state that the choice of group or parent to start from remains heuristic and is delegated to AI agents; better principled criteria for choosing symmetry slots are an open problem.

• Broadening beyond the protocol class. Catalytic and Hadamard-assisted protocols lie outside the postselected diagonal CSS class studied here and could reach parameters the catalog does not.

• Community-driven agent searches. The released context directory of search briefs and campaign notes is intended to let readers train their own agents and tailor searches to their own requirements, extending the open-source repository.

Target Audience

Quantum information researchers working on fault-tolerant architectures, magic-state distillation, or quantum error-correcting codes; compiler and resource-estimation engineers who need concrete factory parameters; and AI-for-science practitioners interested in neuro-symbolic workflows where a language model proposes and an exact solver verifies. Readers without a stabilizer-code background will find the high-level framing accessible but the technical sections demanding.

Authors’ abstract

Magic-state distillation is a major resource cost in fault-tolerant quantum computing. The cost of a magic-state factory depends strongly on its failure rate, which grows with the number of input magic states. Although symmetry-restricted methods have recently made distance two searches tractable, distance three and above have remained elusive at moderate input counts. We develop symmetry- and AI-assisted methods to search this regime. We present a unified binary-matrix formulation encompassing both triorthogonal-code and direct circuit searches. We show that distance at least three is equivalent to nonzero, pairwise distinct syndromes, separating the choice of syndromes from the search for compatible output gates. We restrict the syndrome search using group symmetry and language-model agents, followed by deterministic solving and independent verification. Our searches yield 699 factory classes, including 564 new ones. These include factories for pure-T states and factories with entangled outputs comprising combinations of T, CS, and CCZ magic states. The pure-T factories [[63, 11, 3]] and [[850, 128, 6]] achieve the lowest overhead exponents we know among protocols with at most 100 and 1000 inputs, respectively, with $γ= 1.589$ and $γ= 1.057$. Our [[1715, 287, 6]] factory, with $γ= 0.998$, is the smallest known pure-T factory with $γ&lt; 1$. We also provide a context directory of search briefs and campaign notes with which readers can train their own agents and tailor the search to their requirements. With these results, we begin constructing an active, open-source repository of magic-state distillation protocols for the quantum community, supplemented by our methods and data, for the practical fault-tolerant quantum computing regime.