Symmetry and AI-assisted discovery of magic-state factories

Fault-tolerant quantum computers can usually run Clifford gates cheaply, but universal computation also needs non-Clifford gates such as T, CS or CCZ. These gates are applied by consuming magic states, and magic-state distillation turns many noisy magic states into fewer, cleaner ones. Resource estimates attribute a large share of a machine’s qubits and time to these factories.

A factory’s cost depends strongly on how often it fails, which grows with the number of input states, and on its distance, which sets how fast the output error falls. Recent symmetry-based methods made searches at distance two tractable, and exhaustive classification covers small factories with up to 54 inputs (our companion paper). Large algorithms need distance three or more, and there the landscape between a few dozen and a few hundred inputs was largely uncharted.

With Adam Wills and Shraddha Singh at IBM Quantum, we wrote triorthogonal codes and distillation circuits in one binary-matrix language. In it, each input flips a set of checks, called its syndrome, and distance at least three is the same as every syndrome being nonzero and all of them being different. That splits the search in two: first choose the syndromes, then look for output gates compatible with them. The same formulation drives the exhaustive search in our companion paper; here we go beyond its range.

Choosing the syndromes is where the search space explodes. We restricted it with group symmetry, so that choosing syndromes becomes choosing orbits under a group, and we let language-model agents propose which groups and starting structures to try. Every proposal was then solved deterministically and checked by an independent verifier, so each factory we report is an explicit circuit.

The searches produced 699 factory classes, 564 of them new. They include factories for pure T states and factories with entangled outputs that combine T, CS and CCZ. The overhead exponent measures how fast the number of inputs per output grows as the target error falls, and lower is better. Our [[63, 11, 3]] and [[850, 128, 6]] pure-T factories have the lowest exponents we know of among protocols with at most 100 and 1000 inputs. Our [[1715, 287, 6]] factory is the smallest known pure-T factory with an exponent below one. The catalogue, the search engine, the verifiers and the briefs we used to steer the agents are all in an open database, so others can extend the search to their own needs.