Symmetry and AI-assisted discovery of magic-state factories
Authors: Shubham P. Jain, Adam Wills, Shraddha Singh
Organizations: Joint Center for Quantum Information and Computer Science, NIST/University of Maryland, College Park, Maryland 20742, USA · IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, New York 10598, USA · Center for Theoretical Physics, a Leinweber Institute, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA
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 γ<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.
Figures & tables
Figure 1: The distance-three catalog up to n=127 . A circle is a factory with a pure- T⊗k output, and a diamond one with any other output. Color is the T -count of the output gate, labeled “minimal T -count” on the color bar. Hatched markers are entangled outputs too wide for that exact minimization. A pure- T factory is omitted when a wider one at the same n and d already delivers it. The green band is n≤54 , the range the companion paper [ 62 ] classifies exhaustively at this distance. The markers inside the band are classes that the methods of this paper found independently of the exhaustive classification. The right panel counts the drawn classes in bins of five consecutive n across the same range and splits each bin by T -count. The bins are placed so that n=54 falls on a boundary, and no bar mixes the two sides of the band. Of the 294 classes drawn, 65 lie in the band, 225 are new in this work and the remaining four were already known.
d
3
4
5
6
7
8
9
all
classes
493
88
69
42
5
1
1
699
new
382
72
65
39
4
1
1
564
Table 1: The classes this paper reports, by distance, and how many of them are new. A class is a quadruple (n,k,d,output gate) as defined in the text. A class counts as new when no published protocol states it and it lies outside the range of exhaustive classifications.
output gate
factory
N
T⊗7
[[55,7,3]]
14
T⊗11
[[63,11,3]]
17
T⊗16
[[100,16,3]]
23
T⊗23
[[127,23,3]]
30
T⊗128
[[850,128,6]]
166
CS⊗3
[[63,6,3]]
12
Table 2: Some highlighted factories resulting from our methods. The [[850,128,6]] factory has overhead exponent γ=1.057 (Table 3 ), the lowest we know at n≤1000 . Each factory listed has the smallest input count we know of for its output at its distance.
Ref. [ 25 ]
this work
d
factory
γ
factory
γ
3
[[863,161,3]]
1.528
[[750,210,3]]
1.159
4
[[872,152,4]]
1.260
[[429,83,4]]
1.185
5
[[887,137,5]]
1.161
[[879,145,5]]
1.120
6
[[912,112,6]]
1.170
[[850,128,6]]
1.057
Table 3: The punctured Reed–Muller factories tabulated by Haah and Hastings [ 25 ] , beside the lowest overhead exponent we find at n≤1000 for the same distance. Every factory in the table is a pure T⊗k factory, and γ=log(n/k)/logd is the overhead exponent, where lower is better. At each distance, our work achieves the lowest exponents known and the distance-six one is the lowest known at any distance at n≤1000 .
Figure 2: The catalog at distances four and five, on logarithmic axes from n=48 to 1683 . Conventions are as in Fig. 1 , with pure- T factories at any n represented by their highest k member. Of the 97 classes drawn, 78 are new in this work.
Figure 3: The [[8,3,2]]CCZ factory as a circuit [ 54 ] and as a matrix [ 36 , 10 ] . Four wires prepared in ∣+⟩ receive eight parity rotations Zα , drawn as a vertical connector with a dot on each wire in the support of α and the T box on the check wire. Beneath each rotation is its corresponding column in the matrix G with support on every wire the rotation touches, the top three rows being the outputs and the bottom row the check. At the end the check wire is measured in the X basis and the run is kept only if the outcome is +1 (no check flipped). Three output wires carry the delivered ∣CCZ⟩=CCZ∣+++⟩ state. By Eq. ( 3 ), every column count is even except that of the triple {1,2,3} , which lies only in (111∣1) , so the circuit applies CCZ123 . A single fault flips the check and is detectable. Two faults cancel on the check but, being distinct columns, differ on the outputs, so d=2 [ 54 ] .
reading
perspective
search object
code
triorthogonal code
rows of Gy
circuit
borrowed identity
displacement h∈KN
direct circuit search
selection y
Table 4: The binary matrix formulation underlies both readings of a magic-state factory. Read as a code, the matrix is a triorthogonal code. Read as a circuit, it is searched through a borrowed identity or directly.
Figure 4: The slot ansatz, drawn for one example group. (a) G is the order-three permutation of the r=7 check wires that rotates {1,2,3} and {4,5,6} and fixes wire 7 . (b) Syndromes fall into orbits under G . The seven syndromes constant on each triple are fixed points, and the other 120 form 40 orbits of size three, 47 orbits in all. (c) A slot pairs an orbit ω with an output label P∈F2k and stands for the columns (P∣s) of G , one for each s∈ω .
Figure 5: The agent loop. An opening prompt, written by the user, sets the aim of the campaign. On the proposal side the reviewer reads the results of earlier rounds and sets a direction, which the proposers use to generate proposals. A proposal names a symmetry group and its action, a syndrome or puncture set, or an explicit column list, and carries a one-line rationale. The heavy line separates the two sides, and only files cross it. Proposals go right as specification files and column lists, and verdicts, logs and rejection reasons come back left. No model runs on the solver side. Ingest parses each proposal, rejects one it cannot read and drops one already run. The engine runs the tool the proposal names. Many proposals return no circuit, and those negatives are passed back to the proposal side along with the successes. A circuit that does come back goes to the verifier, which re-derives its gate, width and distance from the matrix alone, with no knowledge of the agents’ proposal. Merge keeps one row per class, a class being (n,k,d,output gate) with the gate taken up to GL(k,2) and diagonal Clifford corrections, as in Sec. II . Where several circuits reach the same class, the one on fewest wires is kept. The merged catalog is reverified once more at the end of the round. One round is one pass around the loop, and a campaign is a sequence of rounds.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 6: One logged round of the agent loop, quoted from the campaign’s brief, its direction files, its proposal set and its run log. The brief is fixed for the whole campaign. Everything below it belongs to this round. The proposal shown is one of 84 , and it returned a factory at n=64 where the catalog held 66 . Most of the round’s runs failed cheaply, forty-five UNSAT in seconds. That is what let the review close the next round to distance four and above. The same round produced the [[60,2,4]] and [[48,2,4]] records.