A large language model rewrites quantum arithmetic circuits, cutting both Toffoli count and qubits on seven of eight compilation tasks
Synopsis
Running quantum algorithms requires compiling classical functions into reversible, coherently executable circuits, and that compilation has long relied on predefined equivalence-preserving rewrites that keep search close to a fixed design. An evolutionary framework in which a large language model proposes candidates and an independent evaluator verifies and scores them produced circuits across eight compilation tasks spanning numerical computation, chemistry, optimization, quantum simulation and number theory. On seven of the eight, the discovered circuits reduce both Toffoli and qubit counts relative to the state of the art; on the eighth, the search found a new reversible architecture for prime-field modular inversion that makes divsteps viable for reversible integer arithmetic.
Interpretation
The design space of quantum circuits can now be explored by having a large language model propose candidates while an independent evaluator judges correctness and cost, instead of searching only within hand-supplied equivalence-preserving rewrites. Automated circuit optimizers have typically preserved correctness by restricting the search to predefined rewrites, which limits them to variations of a fixed design. Across eight compilation tasks, seven discovered circuits use both fewer Toffolis and fewer qubits than the corresponding baseline, and the eighth, prime-field modular inversion, yields a new reversible architecture.
Each search starts from a hand-written task specification and a blank program, and the model writes reusable functions and registers through a high-level Python interface, so one conceptual change can reorganize operations throughout the circuit. Representing candidates as gate sequences or predefined circuit blocks obscures the algorithmic structure, whereas program structure makes arithmetic subroutines and their composition explicit. In each iteration the evaluator simulates a candidate on computational-basis inputs, checking outputs, preserved inputs, cleared ancillas and phase, then scores it by the product of Toffoli count and peak qubit count, the TQ-cost.
The discovered circuits repeatedly apply three shared practices: replacing conditional arithmetic with conditional routing so one expensive operation is shared, decoding branch decisions from the computation's state instead of retaining a full history, and localizing resources needed only for rare inputs so they can be omitted under a bounded failure budget. A naive reversible implementation places a separately controlled arithmetic block for every branch and stores each overwritten value in a history stack that grows with the number of rounds. On the Reed–Solomon decoding task, replacing the synchronized Euclidean solve with the Berlekamp–Massey recurrence cut the forward solve from about 1.9 million Toffolis to about 140,000, and the full decoder circuit uses 440,000 Toffolis and 1,837 qubits against a baseline of 5.1 million Toffolis and 1,938 qubits.
Perspective
The demonstrated scope is eight compilation tasks, each with a hand-written task specification, a fixed computational-basis interface, an input distribution and an accuracy target; circuits are ranked by the product of Toffoli count and peak qubit count, and for large input domains the evaluator samples trajectories rather than checking all of them. The authors note that the scoring function can be replaced with a hardware-appropriate combination of resources, but determining that objective remains a matter of application and hardware judgment.
Correctness rests on sampled tests: the Reed–Solomon decoder produced a wrong sign in seven of 100,000 tests of the complete circuit. Circuits that permit failure exclude rare inputs, with the modular-inversion stopping-time window failing at a probability of about 10^-5 and the history-stack limit overflowing at a rate of 2.4×10^-6. The framework also excludes optimizations whose advantage comes from changing the encoding itself, such as coset representations. The authors describe cross-layer co-design as an opportunity rather than a demonstrated result.
