betaFeedback

WorksPhysics and Astronomy

Discovering formally verified quantum programs with AI

Abstract

The timeline by which quantum computers can solve breakthrough problems in science depends on improved quantum algorithms as much as on better hardware. Such algorithmic advances are typically achieved through many years of expert human collaboration. In mathematics and computer science, large language models have accelerated progress through automated discovery loops. However, quantum algorithms can only be evaluated by classical computers on restricted or small instances. Here we demonstrate automated discovery of quantum programs beyond these regimes including order-of-magnitude improvements on scientific applications. To achieve this, we build a quantum program library in the Lean theorem prover in which Gemini 4 agents synthesize novel programs against formal problem specifications and verify their correctness and cost. Agent teams collaborate, sharing results and knowledge through wikis and discussing ideas at organized conferences. Our results improve on prior baselines for parallel search (up to 2.55x), quantum arithmetic (290x), and simulations relevant to fusion, photochemistry and drug-metabolism by 11x, 8x and 2.5x respectively. Combining human and artificial intelligence at scale, under the rigor of mathematical proof, lets researchers design algorithms that today's classical and quantum computers cannot test, shortening the path to practical quantum computation.

Quantum computers promise to tackle problems beyond classical reach across cryptanalysis,[11] optimization,[12] chemistry and drug discovery,[13, 14, 15] materials science,[16, 17] and high-energy and plasma physics.[18, 19, 20] Many of the most promising applications are estimated to require a device with thousands of error-corrected (logical) qubits executing 10910^{9} to 101510^{15} logical operations,[1, 21] well beyond the roughly one million operations projected for early fault-tolerant processors.[2] Beyond improvements in hardware and quantum error correction to build better logical qubits from noisy physical qubits,[22] closing this gap relies on cumulative algorithmic resource reductions that lower qubit and gate counts.[23, 24, 25, 26, 27] Historically, such reductions take sustained scientific effort over many years.[3, 4]

Artificial intelligence (AI) offers a promising route to accelerate these improvements. Traditional machine learning has already been successfully applied to e.g. quantum hardware control,[28, 29, 30] error-correction decoding,[31] and small-scale circuit synthesis.[32] While large language models (LLMs) are rapidly advancing mathematics and classical algorithms via execution-based search and automated reasoning[5, 33, 34, 35, 36, 37, 38, 39] as well as formal theorem proving for fixed conjectures,[6, 40] their application to quantum computing lags behind due to the challenge of verifying general correctness without fault-tolerant hardware to test on. High-throughput validation of LLM-generated quantum programs has thus been restricted to circuit regimes that can be classically simulated,[7, 8] limiting the design space and scale of discovery (Figure 1b), whereas concurrent LLM-assisted formalization has focused on verifying known algorithms (Appendix § 4). Bringing AI discovery to general quantum algorithms instead requires pairing formal models of quantum computation with mathematical proofs of correctness and cost, with access to tools such as numerical heuristics where they are effective. Formal reasoning is particularly critical when targeting asymptotic speedups and large-scale applications spanning thousands of qubits—just like scientists have reasoned about quantum algorithms over the past decades.

Formally verified multi-agent quantum program discovery workflow and research approaches

Figure 1. Formally verified multi-agent quantum program discovery. a) Researchers write a Lean quantum Hoare logic specification of correctness and cost, then launch their agent team, which iterates on error feedback from the Lean kernel. Teams publish independently re-verified solutions, partial results and dead ends to a shared wiki, and exchange ideas and critiques in scheduled conferences. b) Bars indicate which problem each approach can reach. AI search checked by numerical tests can only produce solutions that can be simulated classically (dashed line), which for arcsin means a restricted gate set.[7]

In this work, we introduce a Lean[41] verification library based on quantum Hoare logic (QHL),[42] engineer a multi-agent research workflow built around it, and prove new resource reductions across asymptotic algorithms and large-scale scientific simulations. Our library pairs a language for quantum programs and classical control flow with formal proofs of correctness and resource cost, chosen per specification. For fault-tolerant circuits we use the spacetime cost Q⋅TQ \cdot\mathcal{T}, the number QQ of qubits times the number T\mathcal{T} of TT gates, which are costly in error-corrected quantum computers.[43] Researchers launch heterogeneous teams of LLM agents that iterate on algorithms, and exchange concepts, partial results, and dead ends through a shared wiki and scheduled cross-team virtual conferences, while an independent verifier audits every proof against a frozen specification written in our library (Figure 1a). Across five problems (Figure 1b)—computing arcsin, parallel Grover search, cytochrome P450 energy levels, fusion alpha-particle stopping power and non-Born–Oppenheimer molecular dynamics—this workflow discovers new programs and circuits with machine-checked proofs of correctness and cost, reducing resource costs by 290× for arcsin (combining classical and formal search), and by up to 11× for our scientific applications compared to the strongest prior baselines (Figure 3). Together, these advances shift researchers’ effort from manual circuit design, optimization, and resource tracking to problem specification and scientific interpretation.

Summary of verified results panels b–d

Figure 3. Summary of verified results. a) Quantum algorithm cost for baselines and solutions from this work across application domains. b) Logical-qubit and TT-gate improvements on the three scientific applications, with feathered hardware horizons (dashed lines at geometric midpoints) for medium-term fault-tolerant quantum computing (FTQC{sup}†) (teraquop planar architectures[7, 61]) and application-scale FTQC{sup}‡ (fault-tolerant application-scale quantum computers, FASQ[1, 2, 61]). Grey points denote published baselines, red points denote refined baselines incorporating subsequent methodological improvements from the literature, and blue points denote this work. For cytochrome P450, the published ground-state estimate is extended to all eigenstates within 0.1 Ha of E0E_0, raising its cost by 0.85%. c) Cost for 25-bit fixed-point arcsin (ε≤1.25×10−7\varepsilon\le1.25 \times10^{-7}) against piecewise-polynomial evaluation.[10] d) Speedup in expected number of rounds for large NN of our verified parallel Grover circuits over the strongest published baseline[62, 63, 64, 65, 66] for powers of two mm, k≤210k \le2^{10} when finding any one or all of kk marked targets with mm parallel queries per round (dashed contours: 1.00× boundary; * markers: peak speedups of 1.22× and 2.55×).

Formally Verified Multi-Agent Discovery

Formal Verification of Quantum Algorithms

We implement our verification and resource-counting library[44] in the Lean theorem prover,[41] building on Mathlib[45] and Physlib’s Lean-QuantumInfo.[46, 47] These formalize core objects of quantum information, but reasoning about quantum programs also requires a programming language to express them and a program logic to prove them correct. Our library fills this gap by combining a classical-quantum programming language, a classical-quantum Hoare logic to reason about program correctness[42] and support for resource counting. Besides classical operations such as assignment, conditional branching and unbounded loops, the formalized language supports core quantum operations: unitary transformations, mid-program qubit measurement, and state reset. We include further details in Appendix § 4.

Correctness theorems are formulated as so-called Hoare triples of (precondition, program, postcondition), which state that all executions of a program starting in a state satisfying a specified precondition end in a state satisfying a chosen postcondition. Triples are proved backwards from the postcondition by computing the weakest preconditions for each step of the program.[42] Alongside correctness, our library proves bounds on both expected and worst-case resource costs across branches and loops, including TT-gate count and number of qubits required to execute the algorithm. To pose a program discovery task, we write a problem specification as a Lean file (Figure 2) that states the target correctness and cost theorems while leaving placeholders (sorry) to be filled in with a candidate program, its cost bound, and their proofs.

Lean specifications for discovery tasks

Figure 2. Lean specifications for discovery tasks. An abridged specification for electronic stopping power in warm-dense hydrogen,[48] where the goal is to construct a quantum program that simulates time evolution under the system Hamiltonian HH. The agents fill in each sorry statement, which is Lean’s placeholder for an unfilled definition or proof: the ancilla qubit count, the circuit and its claimed cost, and the proofs of the correctness and cost theorems. (1) The system qubits store the momentum of every quantum particle. (2) A unitary matrix WW on the system and ancilla qubits (extra qubits used to aid computation) must simulate time evolution e−iH(c)te^{-iH(c)t} for every physically allowed electron state, up to a specified error, and return the ancillas to ∣0⟩|0\rangle. (3) The compiled program must act as WW on grid states whenever the ancillas start in ∣0⟩|0\rangle. (4) The cost is a function of the logical spacetime volume Q⋅TQ \cdot T multiplied by the repeated runs of the stopping power routine: 50 repeats × 10 time steps × Q⋅TQ \cdot T (§ 2.3).

Multi-Agent Discovery Architecture

To begin the search on a problem, researchers write the specification and launch independent teams of LLM agents with high-level optimization prompts rather than problem-specific ideas (Figure 1a). The agent teams then explore candidate algorithms and prove their correctness and cost against the independent verifier. Each researcher chooses their own team setup, from a single agent iterating on a candidate to hierarchical teams targeting individual subroutines, using tools such as analytical derivations, simulation, and numerical optimization (Appendix § 6). Unlike multi-agent science systems with a fixed architecture[49, 50, 51, 52] or single search loop,[5, 36, 40, 53, 54] we prescribe no internal team design and fix only the shared specification, verifier, and workflow. All large-scale experimental runs of autonomous discovery were performed using Gemini 4 Carbon models.

Agent teams can share progress through two channels. A wiki stores each problem’s best verified solution, reusable Lean lemmas, and reviewed notes on promising ideas and dead ends.[55] Newly launched teams can start from the wiki’s best solution. Teams also meet in scheduled forum conferences to critique proposals and discuss unverified conjectures, which count as results only once verified.

Because agents can freely modify files in their workspace, they may exploit loopholes by weakening theorem statements, altering definitions, or adding axioms.[56] To prevent this, an external verifier checks every submission against the frozen specification using the Lean Comparator,[57] confirming that all target theorems, underlying definitions, and allowed axioms are unchanged (Appendix § 5). Researchers thus review only the specification before a run and can trust that any found and verified solution is a valid algorithm.

Results

We demonstrate automated quantum program discovery on five applications (Figure 3): parallel unstructured search (§ 2.1), fault-tolerant arithmetic (§ 2.2), and three physical and chemical simulations (§ 2.3–§ 2.5).

Parallel Grover Search

Unstructured search, the problem of finding one or all of kk marked items in a list of NN candidates, provided one of the earliest provable quantum advantages, with Grover’s algorithm achieving a quadratic speedup over classical search.[9] Marked items are identified by an oracle subroutine assumed to dominate runtime, so cost is measured solely in oracle queries. Allowing up to mm parallel queries per round on a shared quantum register (rather than mm independent, uncoupled devices),[9, 63] we require algorithms to succeed with certainty and score them by their expected oracle rounds for large NN, evaluated at powers of two up to 1,024 for both mm and $k ({xref}Fig. 3d). We compare against the strongest published protocol in each regime,{citep}62–66 including Zalka’s partition combined with weakly measured search at $k = 1$, evaluated under the same metric ({xref}Appendix E`).

Our Lean-verified circuits match this baseline on the m=1m = 1 and k=1k = 1 boundaries for finding a single element and outperform it at all multi-target parallel settings (m,k≥2m, k \ge2), reducing expected rounds by up to 1.22×; for finding all elements, they outperform it at all multi-target settings (k≥2k \ge2), by up to 2.55×. Part of this gain comes from combining published ideas via classical control, such as pairing domain partitioning or parallel restarts with weak measurements, which collapse coherence only partially at the price of only partial success information. The largest find-all gains come from a new coherence mechanism: instead of splitting the list into mm blocks with unknown target counts, the circuit holds a superposition over all sets of mm candidates, and each parallel query imprints a sign set by the parity of how many remaining targets a set contains. Between queries, a fixed, target-independent walk on the Johnson graph of these sets steers amplitude toward sets containing every remaining target, which a final query records at once (Appendix § 8.§ 3).

ProblemApplicationBaseline Q⋅TQ \cdot TThis work Q⋅TQ \cdot TReduction
Fixed-point arcsin[10]State preparation>1.08×108> 1.08 \times10^{8}3.70×1053.70 \times10^{5}>290×> 290\times
α\alpha + hydrogen stopping power[48]Fusion5.42×10155.42 \times10^{15}4.98×10144.98 \times10^{14}10.9×10.9\times
C23H20N3O\mathrm{C}_{23}\mathrm{H}_{20}\mathrm{N}_{3}\mathrm{O} non-BO dynamics[58, 59]Photochemistry4.98×10154.98 \times10^{15}6.16×10146.16 \times10^{14}8.08×8.08\times
Cytochrome P450 ground and low-lying state energies[60, 61]Drug metabolism1.09×10121.09 \times10^{12}4.37×10114.37 \times10^{11}2.49×2.49\times

Table 3a. a) Summary of results using absolute cost.

Fixed-Point arcsin

Computing the function arcsin⁡(y)\arcsin(y) on a quantum superposition of inputs is an important subroutine for loading numbers into a wavefunction, used in many algorithms including for solving linear systems of equations. We specifically consider the case where the input yy is represented by 25-classical bits, and the output must be accurate to an error ≤1.25×10−7\le1.25 \times10^{-7} across the domain y∈[−1,1]y \in[-1,1]. For this setting, the best-known published baseline implementation is a piecewise-polynomial construction,[10] which requires a spacetime cost exceeding 1.08×1081.08 \times10^{8} for an error of ∼10−6\sim10^{-6}.

Unlike the other examples in this work, arcsin⁡\arcsin is known to have quantum implementations that can be efficiently simulated classically using a restricted gate set called kickmix.[7] Therefore, we run automated discovery in two steps. First, the agents only consider kickmix circuits, exploiting that solutions can be verified in a matter of seconds. This leads to fast improvements, overall reducing the spacetime cost to 4.15×1054.15 \times10^{5} (4,152 T4{,}152\ T gates on 100 qubits). Subsequently, we use our formal verification library to lift the kickmix restriction and further optimize the algorithm, using a new quantum gate set that makes the solution hard to verify outside Lean. From this, the agents discover a solution in which a certain component, the coefficient lookup, can be implemented using 33% fewer gates, leading to a further overall 11% lower cost of 3.70×1053.70 \times10^{5} (3,698 TT gates on 100 qubits), 290× below the baseline.[10]

Stopping Power in Inertial-Confinement Fusion

In inertial-confinement fusion, hydrogen fuel ignites only if the energetic α\alpha particles it produces deposit enough of their energy back into the fuel to sustain the reaction.[68, 69] Modeling this requires knowing the fuel’s stopping power, the rate at which it absorbs the kinetic energy of an α\alpha particle passing through it. No classical method for these dynamics is both efficient and systematically improvable.[48, 70, 71, 72, 73]

We consider an α\alpha particle and 218 electrons moving among 216 fixed protons. A candidate circuit must simulate the time evolution of the system e−iHte^{-iHt} with error ε=10−2\varepsilon= 10^{-2} on every state antisymmetric under exchange of same-spin electrons. The full stopping-power calculation repeats this evolution 500 times.

Our baseline is constructed from Ref. [48]: we take the 5,650 logical qubits and parameters in its Table 2 and evaluate its equation (12), giving a spacetime cost of 5.42×10155.42 \times10^{15} per run, averaged over the 500 runs (Appendix § 10). This builds e−iHte^{-iHt} from a sequence of walk steps, each encoding H/λH/\lambda, where λ\lambda is the sum of the absolute weights when HH is written as a linear combination of unitaries (LCU). The number of walk steps[25] scales as λt\lambda t.

Running our discovery workflow, we find a solution with 4,374 logical qubits and 10.9×10.9\times lower spacetime cost (Figure 4a). To understand the main improvement, we note that over 90% of the baseline’s λ\lambda comes from electron–proton and electron–electron interactions, and that λ\lambda must account for every state the qubits can be in, including unphysical ones. Our main innovation is to quantum Fourier transform all electrons to a real-space grid to apply these interactions (Figure 4b). Importantly, in real space the solution can exploit Pauli exclusion, which allows at most two opposite spin electrons on any grid point. For the short-range part of the potential, a subroutine kicks back a phase of ii in one LCU branch and −i-i in the other for each electron on a nearby grid point. The branches interfere to apply the correct interaction, up to a constant, for two or fewer electrons, while keeping it no larger for three or more, so these grid points no longer set λ\lambda. In the final circuit, this cuts the walk steps by 12.8×12.8\times, at 1.52×1.52\times the TT gates per step.

Where program improvements come from

Figure 4. Where program improvements come from. a, d) Cost of verified solutions. Arrows mark where the mechanisms in the other panels were introduced. Interestingly, the drop at iteration 49 in a) is not present in the final solution. b) A quantum Fourier transform (QFT) moves the electrons onto a real-space grid and back. On the grid, the pair potential v(r)v(r) is split into long-range (blue) and short-range (hatched) parts. The long-range part costs about 30 times less per pair than in the momentum basis (red dashed). For the short-range part, a subroutine bounds the interaction strength of configurations that violate the Pauli exclusion principle, further reducing its cost. c) Protons sit off the grid, so to apply an electron–proton interaction the circuit shifts all electrons to put the proton on a grid point, a phase set by the sum of all 218 electron momenta. Keeping this sum in a 42-qubit register between walk steps halves the summations per step. e) To apply the electrostatic interaction ZiZj/rijZ_iZ_j/r_{ij}, rather than swapping the coordinates of the interacting pair into fixed slots and back, a copy is loaded into ancilla qubits. This can be cleared cheaply by measurement without destroying the originals. f) From the loaded coordinates, rij2r_{ij}^{2} is calculated cheaply and rescaled within each interval to r~ij2∈[0,1)\tilde{r}_{ij}^{2} \in[0, 1). Through random sampling, one of four classically precomputed coefficients is chosen, with probabilities set by r~ij2\tilde{r}_{ij}^{2} (dot area). In expectation, this gives 1/rij1/r_{ij} as a Bernstein polynomial,[67] as shown for one value of rij2r_{ij}^{2} (shaded). g) Each nucleus has integer charge Zn∈{1,6,7,8}Z_n \in\{1, 6, 7, 8\}. In the electron–nucleus attraction, rather than preparing these weights via alias sampling,[24] a uniform superposition is created and reversible logic assigns ZnZ_n of them to each nucleus. Applying a unit-charge interaction on every branch then gives each nucleus its full charge ZnZ_n.

The largest other improvement comes from keeping the total electron momentum, needed to apply the electron–proton interaction, in a 42-qubit register between walk steps. This halves how often it is recomputed and cuts the TT gates per step by 10% (Figure 4c). More details are given in Appendix § 10.

Non-Born–Oppenheimer Dynamics of C23_{23}H20_{20}N3_3O

Light-driven chemical processes such as solar energy conversion,[74, 75] photocatalysis[76] and biological photoreception[77] proceed through excited-state pathways where electronic and nuclear motion occur on comparable timescales. This invalidates the Born–Oppenheimer approximation,[78, 79, 80] meaning the nuclei must also be included in the quantum wavefunction. Methods that treat the nuclei classically struggle to simulate quantum tunneling and superpositions of electronic states,[81, 82] while exact classical simulation scales exponentially with system size.[14, 78]

Following Reaction 5 of Ref. [58], we simulate time evolution of C23_{23}H20_{20}N3_3O, modeled on molecules proposed for photo-activated, proton-coupled electron transfer.[75, 83] Unlike the fixed protons of § 2.3, all 47 nuclei are treated quantum mechanically alongside the 187 electrons (5,616 system qubits). Here a candidate circuit must implement time evolution e−iHte^{-iHt} for t=1 fst = 1\,\mathrm{fs}, to within error ε=10−2\varepsilon= 10^{-2}, for every initial state.

Improving the published estimate[58] by the authors’ subsequent work[59] gives a baseline cost of 4.98×1015 Q⋅T4.98 \times10^{15}\ Q \cdot\mathcal{T} (Appendix § 11). In this work we find a solution that costs only 6.16×1014 Q⋅T6.16 \times10^{14}\ Q \cdot\mathcal{T}, a reduction of 8.08×8.08\times (Figure 4d).

Within each walk step, three changes lead to the most significant improvements. First, rather than swapping interacting particles into fixed sets of qubits and back,[58] our solution loads their coordinates into ancilla qubits, which can be cleared by cheap measurement[23, 27] (Figure 4e). Second, instead of evaluating 1/r1/r with a multiplication step,[58] we obtain 1/r1/r in expectation from a piecewise Bernstein polynomial in r2r^2,[67] using only comparisons and a table lookup (Figure 4f). Finally, a nucleus of charge ZnZ_n attracts an electron just as ZnZ_n unit charges at the same point would. The solution exploits this by creating an equal superposition and assigning ZnZ_n of the branches to each nucleus via classical Boolean logic,[27] rather than preparing unequal weights by alias sampling[24, 58] (Figure 4g). More details are given in Appendix § 11.

Cytochrome P450 Compound I

Cytochrome P450 enzymes break down most human medicines, so understanding how they react with a drug candidate helps predict how quickly the drug is cleared from the body and whether it produces toxic byproducts.[84, 85, 86] These reactions are driven by a short-lived intermediate of the enzyme, Compound I, whose reactivity depends on several closely-spaced spin states. Approximate classical methods such as density functional theory disagree on the energy ordering of these states,[87] making it a central target for quantum phase estimation, a quantum algorithm to obtain eigenstate energies.[3, 88]

We consider a model of Compound I with 63 electrons in 58 orbitals (active space XX)[88] with the fixed double-factorized tensor-hypercontraction (DFTHC) Hamiltonian.[60] For every eigenstate within Δ=0.1\Delta= 0.1 Ha of the ground state, the circuit must estimate the energy with root-mean-square error at most ε=1\varepsilon= 1 mHa, including all approximation errors.

For this problem, the best published spacetime cost is 2.26×10122.26 \times10^{12}[60] To be conservative, we further integrate recent compilation improvements,[61, 89] which roughly halve the cost. Finally, since the published estimate is for the ground-state energy only, we adjust it for our task of predicting all energies within Δ\Delta of the ground state, giving a cumulative baseline of 1.09×10121.09 \times10^{12} on 481 logical qubits (Appendix § 12).

For this problem, we find a solution that achieves a spacetime cost of 4.37×10114.37 \times10^{11}, a reduction of 2.49×2.49 \times. To understand the main improvement, consider the baseline. To apply a Hamiltonian term, each walk step performs 57 rotations in orbital space, to define new coordinates in which the term acts on one orbital.[4] The chosen term is stored as a binary number, which is used to read the rotation angles needed into a 247-qubit register from a quantum read-only memory.[24] Our circuit instead gives each term its own qubit, and sets only the qubit of the chosen term to 1 (a one-hot register). Each angle can then be read from these qubits with only cheap (Clifford) gates once the register is built, with no table lookup. Prior work[89] found this narrowly worse than the baseline because it needs more qubits, and suggested mixing one-hot and binary encodings. Our solution uses this both to look up the term weights and to supply the rotation angles, accounting for over 95% of the TT-gate saving per step and most of the qubit saving. More details are given in Appendix § 12.

Collaboration Across Agent Teams

We now discuss the dynamics of the agentic runs to better understand the role of multiple agent teams in search. Our best solutions emerged from collaboration across teams rather than any single team working alone. In non-Born–Oppenheimer dynamics, for example, the leading record changed teams seven times after Team 1’s initial run, and the final circuit combines techniques from three agent teams, superseding intermediate improvements from other teams (Figure 4e–Figure 4g, 5a). Whereas the wiki transferred verified code, conferences exchanged unverified proposals and critique: the largest single drop (−34%) began as a Team 1 conference proposal that Team 2 refined and proved (Figure 4e), and a second key improvement grew from a similar exchange (Figure 4f).

Such cross-team contributions were sustained across all three scientific applications. To estimate each channel’s share once both were active, we classify every verified gain by where its new idea originated (Figure 5b). Averaged across the three scientific applications, 61% of the total cost reduction came from within-team ideas, 15% from cross-team wiki entries or Lean files, and 24% from conferences. The cross-team share ranges from 13% in stopping power to 63% in cytochrome P450. Credit is often hard to separate cleanly, as one proof often combines ideas from a team’s own search, the wiki, and conferences.

Cross-team collaboration and idea lineage: panels a, b, and c showing idea lineage in non-Born–Oppenheimer dynamics, origin of gains, and spread of one idea in stopping power

Figure 5. Cross-team collaboration and idea lineage. a) Lineage of verified circuits for non-Born–Oppenheimer dynamics across Teams 1–3 (of seven participating teams) from the baseline (seed) to the final circuit (star), with the Q⋅TQ \cdot\mathcal{T} reduction of each step. Within-team discoveries enter from below; cross-team conference and wiki ideas enter from above. b) Share of the logarithmic Q⋅TQ \cdot\mathcal{T} reduction from within-team ideas, cross-team wiki entries, and conference exchanges once both channels were active on each scientific application, with reduction factors over this window shown at right and the unweighted average at bottom. c) Cross-team evolution of one stopping-power idea across wiki records #1–#5 and conference critiques, narrowing the shared ancilla register from 288 to 231 qubits before the final space–time trade-off (246 qubits).

Figure 5c traces one such cross-team exchange in stopping power, where Teams 2 and 3 refined a shared ancilla register across five successive wiki records with conference input from Team 1, narrowing it from 288 to 231 qubits before a final update used 246 qubits to cut TT gates. Beyond complete proofs, dead-end notes and partial proofs also transferred across teams: a note proving why a proposed shortcut fails stopped two proposals from other teams, while helper Lean modules proved by one team were imported by a second and reused in a third team’s stopping-power circuit.

Machine-checked verification is also what makes open collaboration safe at this scale, letting teams build on one another’s Lean proofs without manual code review. Flawed candidates and claims fell into two categories (Appendix § 5): broken proofs or inaccurate script-based estimates (such as candidates that bypassed local Lean checks), which our external verifier and conference critique filtered out, and loopholes in the specifications themselves (such as exploiting how Toffoli gates were counted without improving the circuit), which researchers and teams closed by revising the specification.

Discussion and Outlook

In this work, we show that combining formal verification with LLM agents can push the frontier of quantum algorithm development. We demonstrate this across fundamental algorithms, fault-tolerant subroutines and full-scale scientific applications, achieving up to a 2.55×2.55 \times reduction in expected oracle rounds for parallel Grover search, a 290×290 \times spacetime reduction for fixed-point arcsin, and 10.9×10.9 \times, 8.08×8.08 \times and 2.49×2.49 \times reductions on simulations relevant to fusion, photochemistry and drug metabolism. Where classical simulation can check candidate circuits, as with arcsin, numerical testing with formal proving on top is effective. For asymptotic bounds and general algorithms on hundreds or thousands of qubits, formal proof is essential.

Beyond these results, our experiments point to a new research workflow. Rather than replacing human researchers, formal AI discovery shifts where human effort is applied. Researchers and domain experts choose problems, carefully prepare faithful formal specifications. External verification lets independent agent teams build on one another’s work without manual review, and carry out the search and formal proofs that drive down costs. Finally, researchers interpret the verified solutions to guide future research directions.

Our end-to-end simulations still demand far more resources than projected for the first fault-tolerant quantum computers[2] (Figure 3b; Appendix § 7), and reaching early hardware will require further orders-of-magnitude improvements. Part of the challenge is for us to choose specifications well, as agents cannot optimize beyond them. For example, to match the baseline, our non-Born–Oppenheimer dynamics specification requires correctness on all input states, even unphysical ones that break exchange symmetry. Similarly, fixing the factorization in cytochrome P450 excludes the representation advances behind recent gains.[4, 60, 88]

Bringing algorithms onto real hardware also means extending formal specifications to error-correcting codes, qubit routing and physical layout,[43, 61] so human–agent teams can optimize algorithms for a given code or co-design both. Furthermore, qubits are expected to be a more limited resource than gates for early machines, suggesting optimizing each factor unequally.[90] Other hardware designs, where TT gates can run in parallel, may instead favor minimizing qubits times TT depth.[43] Formalizing these architectural constraints allows us to optimize algorithms and fault-tolerant layouts together before large-scale quantum processors exist. Over time, collaborative proof search can thus turn what were once isolated, multi-year derivations into cumulative resource reductions, closing the gap to useful quantum computation from above while physical hardware scales from below.

Code availability

Our Lean library will be open sourced shortly, together with the problem specifications and verified solutions discussed in this manuscript.[44]

Verification library and specification stack

Figure S1. Verification library and specification stack. Built on Mathlib,[45] Physlib’s Lean-QuantumInfo[46, 47] in Lean, our quantum Hoare logic[42] [97] formalizes classical–quantum states, weakest preconditions and resource costs, supporting problem specifications (correctness theorem and cost bound) across dynamic Clifford+TT circuits and black-box query algorithms.

Formal Quantum Computation Library

We formalize our verification and resource-counting framework for quantum algorithms in Lean,[41] an interactive theorem proving language based on dependent type theory. We chose Lean for its already established rich library ecosystem for broad mathematics, physics, and quantum information theory.[45, 46, 47] Moreover, Lean has seen significant traction in recent months for verification of AI-generated proofs. In particular, formalizing quantum algorithms in Lean allows us to model a broader semantics of quantum programming, complementing fast fuzz-testing evaluators like kickmix.[7] Prior formal frameworks for quantum program verification have been developed across several interactive theorem provers. In Rocq (formerly Coq), SQIR91 verifies unitary quantum circuits, while CoqQ92 formalizes quantum Hoare logic93 for pure quantum while programs. In Isabelle/HOL, QHLProver94 provides an earlier mechanization of quantum Hoare logic for imperative quantum algorithms. Concurrent work has also explored quantum verification in Lean,95 most notably QEDIA,96 which formalizes classical-quantum Hoare logic97 for partial and total correctness. Beyond correctness verification, our framework includes formal support for measuring the worst-case and expected resource costs of algorithms, which is critical for quantum algorithm discovery.

The core of our Lean library is formed by a formalization of a classical-quantum imperative while language with an associated classical-quantum Hoare logic.[42] Supporting classical variables and classical control flow is crucial in practice: realistic quantum algorithms routinely interleave quantum operations with classical arithmetic, loops, and measurement-dependent branching. Handling classical states natively avoids the state-space overhead of encoding classical data into quantum registers.

Correctness in this work is expressed through total Hoare triples {{Θ}} P {{Ψ}}\{\{\Theta\}\}\ P\ \{\{\Psi\}\}. These assert that for every initial (classical-quantum) state Δ\Delta satisfying the precondition Θ\Theta, all executions of the program PP terminate in a (classical-quantum) state satisfying the postcondition Ψ\Psi. In the classical case, pre– and postconditions are predicates on the state. In the quantum case, a state no longer simply satisfies or violates an assertion, the condition is quantitative and takes value in [0,1][0,1]. We call this the expectation of satisfaction. A triple then asserts that, for every initial state Δ\Delta, the expectation of Δ\Delta satisfying an assertion Θ\Theta is bounded above by the expectation of the resulting state Δ′\Delta' (obtained after running the program PP on Δ\Delta) to satisfy Ψ\Psi.

Verification is performed via reasoning about weakest preconditions. Starting from a given postcondition Ψ\Psi, we compute the weakest precondition for this to hold by inductively reasoning about the program backwards. The full semantics of weakest preconditions is given in Figure S3. We follow the source closely but not fully faithfully: we have made certain modifications both to fit our verification purposes and to address ambiguities in the paper. We next outline the main ingredients of the logic and where our formalization differs from Ref. [42].

Inductive definitions of the denotational semantics and weakest precondition

Figure S3. Inductive definitions of the denotational semantics ⟦P⟧(Δ)\llbracket P \rrbracket(\Delta) and weakest precondition wp⁡(P,Ψ)\operatorname{wp}(P,\Psi). For a guard bb, Δ∣b\Delta|_b retains Δ(σ)\Delta(\sigma) where b(σ)≠0b(\sigma) \ne0 and sets all other branches to 0 (similarly for Ψ∣b\Psi|_b and ¬b\neg b). Loop unrollings start from W0(Δ)=0W_0(\Delta)=0 and Ψ0=0\Psi_0=0.

Variable types. Programs operate on two kinds of variables: classical and quantum. In Ref. [42] classical variables can have two types, boolean and integer. We focus on integer-valued classical variables. This is without loss of generality, since boolean values can be encoded as integers. More precisely, given a type Var of classical variables, the type of classical states (stores) is:

abbrev Store (Var : Type) : Type := Var → ℤ

For quantum variables, Feng and Ying[42] consider a countably infinite set qVar of quantum variables q1,q2,…q_1, q_2, \ldots each associated with a Hilbert space of dimension dq1,dq2,…d_{q_1}, d_{q_2}, \ldots respectively. We restrict our set-up to a single quantum variable qq with associated Hilbert space H(d)\mathcal{H}(d) of dimension dd, where dd is a positive natural number. In practice, H(d)\mathcal{H}(d) can be identified with Cd\mathbb{C}^{d}. This loses no expressiveness if we limit ourselves to finitely many quantum variables: if these are of dimensions d1,…,dnd_1, \ldots, d_n can be combined into one register of dimension d=∏i=1ndid = \prod_{i=1}^{n} d_i. Although, this requires lifting operations to the full space explicitly. Supporting multiple named quantum variables is left for future work.

Classical-quantum states. Let L(d)\mathcal{L}(d) be the set of Hermitian operators (matrices) on H(d)\mathcal{H}(d) and D(d)={ρ∈L(d)∣0⪯ρ,Tr⁡(ρ)≤1}\mathcal{D}(d) = \{\rho\in\mathcal{L}(d) \mid0 \preceq\rho, \operatorname{Tr}(\rho) \le1\} the set of partial density operators, ordered by the Löwner order. A classical-quantum state Δ\Delta is a function Δ:Store⁡ Var→D(d)\Delta: \operatorname{Store}\ Var \to\mathcal{D}(d) with countable support whose total trace ∑σtr⁡(Δ(σ))\sum_{\sigma} \operatorname{tr}(\Delta(\sigma)) is at most 11. In particular, any deficit 1−∥Δ∥1 - \lVert\Delta\rVert represents nontermination. In other words, for a classical store σ\sigma, tr⁡(Δ(σ))\operatorname{tr}(\Delta(\sigma)) is the probability of being in the classical branch σ\sigma and Δ(σ)\Delta(\sigma), suitably normalized, is the quantum state in that branch. We represent this as:

def CQState (Var : Type) (d : ℕ) : Type :=
{Δ : Store Var → 𝒟 d // ∃ c, HasSum (fun σ ↦ (Δ σ).1.trace) c ∧ c ≤ 1}

which our formalization shows is equivalent to Definition 3.1 of Ref. [42]; countable support need not be separately imposed, since a suitable family of non-negative reals has countable support (covered by HasSum). The formalization and proofs of this can be found in CQState.lean.[44]

Classical-quantum assertions. We define the set of unit-interval observables[42] (quantum predicates) as O(d)={M∈L(d)∣0⪯M⪯I}\mathcal{O}(d) = \{M \in\mathcal{L}(d) \mid0 \preceq M \preceq I\}, where 00 and II are the zero and identity matrix respectively. A classical-quantum assertion is a map Θ:Store⁡ Var→O(d)\Theta: \operatorname{Store}\ Var \to\mathcal{O}(d). This approach is inspired by classical probabilistic program logics, mirroring the use of real-valued expectations there.98 We formalize this as follows, where Observable dd is our formalization of O(d)\mathcal{O}(d):

abbrev CQAssertion (Var : Type) (d : ℕ) : Type :=
  Store Var → Observable d

As an example, Figure S2 shows how CQAssertion is used to express the clean-ancilla property for subroutines that initialize workspace qubits in ∣0⟩\lvert0\rangle and uncompute them upon completion.

Formal definition of the clean-ancilla property

Figure S2. A formal definition of the clean-ancilla property. Here, a program PP implements the unitary UU on register rTarget and returns the disjoint ancilla register rAnc to ∣0⋯0⟩|0 \cdots0\rangle: for every predicate MM, from any input with clean ancillas, PP must end with clean ancillas and satisfy MM at least as often as applying UU would. Since MM is arbitrary, PP acts exactly as UU on all such inputs.

Similarly to CQState, CQAssertion has a partial order: we can lift the Löwner order on observables by declaring Θ1⪯Θ2\Theta_1 \preceq\Theta_2, if Θ1(σ)⪯Θ2(σ)\Theta_1(\sigma) \preceq\Theta_2(\sigma) for all classical stores σ\sigma. Note that since we work with a single quantum variable, in contrast to Ref. [42], we need not impose further conditions on the quantum variables used when defining the order. CQAssertion is a pointed ω\omega-CPO with respect to the Löwner order: it has a least element, and every increasing chain Θ0⪯Θ1⪯⋯\Theta_0 \preceq\Theta_1 \preceq\cdots has a supremum. This structure is crucial as it allows us to define the weakest precondition on a while loop as the supremum of the weakest preconditions of its finite unrollings and to prove the soundness of the while loop rule. In most logics, assertions form a complete lattice, a stronger structure in which every set of assertions has a supremum and an infimum. This matters in practice: existing verification generator frameworks such as Lean’s vcgen tactic99 and Loom100,101 require this. The observables on a Hilbert space of dimension at least 22102 do not even form a lattice under the Löwner order, so these frameworks are not presently applicable. Therefore, we implemented the quantum Hoare logic and weakest precondition calculus from scratch.

At first glance, the formalization of CQAssertion above differs from Definition 3.5 of Ref. 42, which includes the two conditions on Θ:Store Var→O(d)\Theta: \mathrm{Store}\ \mathrm{Var} \to O(d):

  1. The image set Θ(Store Var)\Theta(\mathrm{Store}\ \mathrm{Var}) is countable;

  1. For each M∈Θ(Store Var)M \in\Theta(\mathrm{Store}\ \mathrm{Var}), the preimage Θ−1(M)\Theta^{-1}(M) is definable by a classical assertion.

We do not need to impose condition (1) separately: when the set of classical variables Var is finite, Store Var = Var →Z\to\mathbb{Z} is countable, so the image of Θ:Store Var→O(d)\Theta: \mathrm{Store}\ \mathrm{Var} \to O(d) is automatically countable. We prove this in CQAssertion.equivCountable. Condition (2) holds automatically since we represent classical assertions as predicates Store Var →\to Prop. However, if the classical assertions are first-order logic formulas over Var as is stated in the beginning of Section 3.2 of Ref. 42, cq-assertions are no longer closed under suprema of increasing chains in the Löwner order and therefore, not an ω\omega-CPO. We encounter the same roadblock to the ω\omega-CPO structure if we explicitly impose condition (1) on the cq-assertions while allowing countably infinitely many classical variables, as opposed to obtaining it naturally by restricting to finitely many classical variables. The full formalization can be found in CQAssertion.lean.[44]

Expectation. To reason about program correctness, we need a quantifiable notion of how much a cq-state satisfies a cq-assertion. In the quantum case, this is no longer a boolean predicate; instead, we consider the expectation of a cq-state Δ\Delta satisfying a cq-assertion Θ\Theta:

E[Δ,Θ]≔∑σtr⁡(Θ(σ)Δ(σ))∈[0,1].(1)\mathbb{E}[\Delta,\Theta] \coloneqq\sum_{\sigma} \operatorname{tr}(\Theta(\sigma)\Delta(\sigma)) \in[0,1]. \tag*{(1)}

This can be thought of as the expected satisfaction of Θ\Theta in state Δ\Delta, averaging over all possible classical branches σ\sigma. Note that since we have one quantum variable, our formula is a simplified version of Definition 3.7 in Ref. 42. We formalize Equation (1) as follows:

def expect (Δ : CQState Var d) (𝜃 : CQAssertion Var d) : R := ∑' σ, ⟪⟪(𝜃 σ).val, Δ σ⟫⟫_R
notation "E[" Δ ", " 𝜃 "]" => expect Δ 𝜃

This definition and Equation 1 are equivalent: the inner product of the Hermitian matrices Θ(σ)\Theta(\sigma) and Δ(σ)\Delta(\sigma) is the real value of the trace of their product as defined in Equation 1. The prime around the sum stands for Mathlib’s tsum, or topological sum, the limit of finite partial sums of possibly infinite index type. Finally, expect Δ\Delta Θ\Theta takes values in the unit-interval, even though its return type is the real numbers. This follows from the trace of positive semi-definite matrices being non-negative combined with lemmas we prove in our library establishing the term inside the sum is bounded above by 1 (see theorems expect_mono, expect_top, CQState.trace_le_one in Expectation.lean[44]).

Syntax. Programs are expressed in the following variant of the classical-quantum imperative while-language of Feng and Ying[42]:

P::=skip∣abort∣x:=e∣qset∣apply U∣x:=measure M∣P1;P2∣qif b then P1 else P2∣qwhile b loop P(2)\begin{aligned} P &::= \mathop{\mathrm{skip}} \mid\mathop{\mathrm{abort}} \mid x := e \mid\mathop{\mathrm{qset}} \mid\mathop{\mathrm{apply}}\ U \\ &\mid x := \mathop{\mathrm{measure}}\ \mathcal{M} \mid P_1 ; P_2 \\ &\mid\mathop{\mathrm{qif}}\ b\ \mathop{\mathrm{then}}\ P_1\ \mathop{\mathrm{else}}\ P_2 \mid\mathop{\mathrm{qwhile}}\ b\ \mathop{\mathrm{loop}}\ P \tag*{(2)} \end{aligned}

Our formalization diverges from Ref. [42] in the following ways: we omit random assignment x:=$gx :=\$ g, we work with a single quantum system rather than several quantum variables, and we represent expressions ee and guards bb directly as Lean functions on the classical store. We embed this language in Lean as an inductive datatype QProg, with the commands as constructors.

A QProg program is parameterized by a finite type Var of integer-valued classical variables xx and on a single dd-dimensional quantum system (dd an arbitrary positive natural number, with d=2nd = 2^n for nn qubits). Classical expressions e:Store Var→Ze : \mathop{\mathrm{Store}}\ \mathop{\mathrm{Var}} \to\mathbb{Z} and decidable guards b:Store Var→Propb : \mathop{\mathrm{Store}}\ \mathop{\mathrm{Var}} \to\mathop{\mathrm{Prop}} are shallowly embedded as functions of the classical store σ\sigma, avoiding the need to encode boolean guards as nonzero integers and aligning branch conditions directly with Lean’s propositional tactics. The command qset resets the quantum system to ∣0⟩\lvert0\rangle, apply UU applies a unitary operator UU, and x:=measure Mx := \mathop{\mathrm{measure}}\ \mathcal{M} performs an ii-outcome quantum measurement with Kraus operators M={Mo}o<i\mathcal{M} = \{M_o\}_{o<i}, ∑oMo†Mo⪯I\sum_o M_o^\dagger M_o \preceq I, storing the outcome oo in xx. The commands qif and qwhile respectively branch and loop on classical guards. As an example, simple applications of qwhile provide support for repeat-until-success loops. Denotational semantics for QProg are given in Figure S3.

Weakest Preconditions

Program verification is performed backwards using the weakest precondition (wp) transformer (Figure S3), which takes a program and a target postcondition and computes the weakest assertion that must hold before execution:

wp:QProg Var d→CQAssertion Var d→CQAssertion Var d\mathop{\mathrm{wp}} : \mathop{\mathrm{QProg}}\ \mathop{\mathrm{Var}}\ d \to\mathop{\mathrm{CQAssertion}}\ \mathop{\mathrm{Var}}\ d \to\mathop{\mathrm{CQAssertion}}\ \mathop{\mathrm{Var}}\ d

This formalizes the predicate transformer of Table 3 in Ref. [42]. Since we are interested in terminating classical-quantum programs, we focus our attention on total correctness. Therefore, we formalize the weakest precondition calculus from Ref. [42] and omit the weakest liberal preconditions, which are only needed for partial correctness.

Particularly, given a classical-quantum program PP and a postcondition Ψ\Psi, wp PP Ψ\Psi computes the “weakest” cq-assertion whose expectation in any initial state Δ\Delta equals the expectation of Ψ\Psi in the state reached after executing PP. Since cq-assertions form an ω\omega-CPO under the Löwner order, the weakest precondition is the largest element with respect to the Löwner order for which the desired postcondition still holds.

The wp rules on basic commands are described in Figure S3. They are all faithfully formalized to the source, apart from the syntax and variable-type choices in QProg, and can be found in WP.lean[44].

We use the weakest precondition calculus to prove total-correctness Hoare triples {Θ} P {Ψ}\{\Theta\}\ P\ \{\Psi\}, formalized as propositions:

def Triple (Θ : CQAssertion Var d) (c : QProg Var d) (Ψ : CQAssertion Var d) : Prop :=
∀ Δ : CQState Var d, E[Δ, Θ] ≤ E[(interp c).toStateFun Δ, Ψ]

Here (interp c).toStateFun Δ formalizes the output state ⟦c⟧(Δ)\llbracket c\rrbracket(\Delta) of Figure S3. The central property connecting the forward denotational semantics and the backward wp transformer is exact expectation duality (Lemma 4.14 in Ref. 42):

theorem expect_wp (c : QProg Var d) (Δ : CQState Var d) (Ψ : CQAssertion Var d) :
E[Δ, wp c Ψ] = E[(interp c).toStateFun Δ, Ψ]

Exact expectation duality (expect_wp) immediately implies soundness: that wp c Ψ is itself a valid precondition, and that it is indeed the weakest such precondition. These are formalized in wp_soundness and wp_weakest in WP.lean.

Resource Counting and Cost Models

Alongside correctness, our library supports two ways of calculating the resource cost of a program: syntactic gate counting over structured circuits, and semantic expected-cost accounting over program executions with branching and unbounded loops. At the circuit level, straight-line circuits are represented as the inductive type Circuit parametrized by the number of wires nn. This is built sequentially from nine primitive unitary gates PrimitiveGate (Clifford+TT, SWAP and TOFF gates). The count of each gate type is obtained simply by summing its occurrences along the sequence. Because each gate type is tracked separately, the cost assigned to each gate is tunable in a specification (for instance, counting only TT gates while treating Cliffords as free). Circuits can also include mid-circuit single-qubit measurements and classical branching, packaged in the type DynamicCircuit which appears in the problems described in this work. For these, we set the resource counting to have measurements add 0 to gate counts, while the cost of a classical branch is the maximum of its two branch counts, giving a worst-case bound. Through the typing of the output circuit, we also keep track of the number of qubits used to include in resource counts. All of this can be found in the folder Circuits, with basic definitions in Basic.lean, and the resource counting framework in ResourceCounting.lean.

To calculate exact expected resource usage directly on QProg, a user-supplied cost model (CostModel) assigns nonnegative integer weights ww to each primitive command (assignmentCost, resetCost, measurementCost, and unitaryCost). Unitary and measurement weights may depend on the operator applied. For instance, one can charge 1 for a designated oracle unitary and 0 for all other operations.

Given ww and an initial cq-state Δ\Delta with total trace ∥Δ∥=∑σtr⁡(Δ(σ))\lVert\Delta\rVert= \sum_{\sigma}\operatorname{tr}(\Delta(\sigma)), the branch-weighted expected cost cost⁡w(P,Δ)\operatorname{cost}_{w}(P,\Delta) (expectedCost) is defined by structural recursion on PP alongside the denotational semantics ⟦P⟧(Δ)\llbracket P\rrbracket(\Delta):

cost⁡w(skip⁡,Δ)=cost⁡w(abort⁡,Δ)=0,cost⁡w(c,Δ)=∥Δ∥⋅w(c),cost⁡w(P1;P2,Δ)=cost⁡w(P1,Δ)+cost⁡w(P2,⟦P1⟧(Δ)),cost⁡w(qif⁡ b then⁡ P1 else⁡ P2,Δ)=cost⁡w(P1,Δ∣b)+cost⁡w(P2,Δ∣¬b),cost⁡w(qwhile⁡ b loop⁡ P,Δ)=∑n≥0Cn(Δ),C0(Δ)=0,Cn+1(Δ)=cost⁡w(P,Δ∣b)+Cn(⟦P⟧(Δ∣b)),(3)\begin{aligned} \operatorname{cost}_{w}(\operatorname{skip},\Delta) &= \operatorname{cost}_{w}(\operatorname{abort},\Delta) = 0,\qquad\operatorname{cost}_{w}(c,\Delta) = \lVert\Delta\rVert\cdot w(c),\\ \operatorname{cost}_{w}(P_{1};P_{2},\Delta) &= \operatorname{cost}_{w}(P_{1},\Delta) + \operatorname{cost}_{w}(P_{2},\llbracket P_{1}\rrbracket(\Delta)),\\ \operatorname{cost}_{w}(\operatorname{qif}\ b\ \operatorname{then}\ P_{1}\ \operatorname{else}\ P_{2},\Delta) &= \operatorname{cost}_{w}(P_{1},\Delta|_{b}) + \operatorname{cost}_{w}(P_{2},\Delta|_{\neg b}),\\ \operatorname{cost}_{w}(\operatorname{qwhile}\ b\ \operatorname{loop}\ P,\Delta) &= \sum_{n\geq0} C_{n}(\Delta),\qquad C_{0}(\Delta)=0,\quad C_{n+1}(\Delta)=\operatorname{cost}_{w}(P,\Delta|_{b}) + C_{n}(\llbracket P\rrbracket(\Delta|_{b})), \tag*{(3)} \end{aligned}

for primitive commands cc, taking values in [0,∞][0,\infty] so that loop suprema always exist. The total trace, which could also be seen as the probability mass of entering the current branch of the program, is formalized as stateMass. Our library provides compositional rules to upper-bound cost⁡w(P,Δ)\operatorname{cost}_{w}(P,\Delta) across sequences, branches, and loops, bounding a qwhile loop by its per-iteration cost times the expected number of iterations, which can itself be bounded via wp. These definitions and compositional rules on the costs (formalized as CostBound) are mechanized in QuantumHoareLogic/ResourceCounting.

Each problem specification specializes this framework along two axes. First, the counted resource is chosen to match the computational model, such as gate counts & spacetime, or black-box oracle calls (charging weight 1 per oracle application and 0 for all other operations, as in parallel Grover search; Appendix § 8). Second, costs can be measured either as concrete numerical bounds at a fixed problem size (like the arcsin problem) or as asymptotic bounds. In many cases, these asymptotic bounds are enforced to be of the form c⋅Nac \cdot N^a as the input size NN grows, ordered lexicographically on (a,c)(a,c), which gives a straightforward ordering on discovered solutions.

Verification Pipeline

Each problem is defined by a specification file pinned to a frozen repository commit, declaring the target correctness theorem and resource-cost function with typed sorry placeholders for the candidate construction, workspace parameters, and proofs (§ 1.1). Because agents may game local checks without discovering or improving the algorithm, for instance by weakening theorem statements, modifying helper definitions, adding axioms, disabling local kernel checks, or misreporting costs,[56] [103] candidate grading is isolated from the agent environment.

Every submission is replayed in a clean sandbox by an external verifier using the Lean Comparator[57] against the frozen specification. A submission passes only if: (i) all target theorem statements and every transitive definition they depend on match the specification; (ii) the compiled proof terms depend solely on standard Lean axioms (propext, Quot.sound, and Classical.choice), with no sorry or custom axioms; and (iii) the proved resource theorem reduces to the claimed closed-form cost. The same check runs automatically before any solution is merged into the shared wiki. Numerical estimates and agent-reported figures are used only internally by teams to prioritize search directions, whereas researchers need only audit the physical model and cost conventions of the specification itself, revising the pinned specification if an unintended modeling loophole is found.

Multi-Agent Orchestration

Agent teams. Each researcher configures and operates an independent team of LLM agents, choosing the agent framework, models, prompts, and division of labor. Setups ranged from a single agent iterating on a candidate construction to multi-agent hierarchical organizations that split subroutine design, error analysis, and Lean proof engineering across specialized workers. In this study, researchers put their domain knowledge, discussion, and design into the problem specification itself rather than seeding domain knowledge or steering the research while underway, though the workflow naturally supports active human seeding and steering as well. During exploration, agents may invoke any external tools, including natural-language derivations, classical simulation, numerical optimization, and remote compute clusters.

Shared wiki. Teams exchange persistent artifacts through a version-controlled repository with one directory per problem.[55] [104] Each entry contains: (i) the current best verified solution, which any new run can adopt as its starting point; (ii) reusable partial Lean files verified to compile against the shared library; and (iii) reviewed notes classifying explored idea families as verified, promising, or dead ends, alongside short technical lessons. Whereas solutions and partial Lean files are machine-checked, idea notes are reviewed summaries rather than formal proofs (see Figure S4). A candidate solution is merged only if it passes automatic re-verification against the frozen specification and clears a minimum relative cost-improvement threshold (5% by default) so that teams do not spend effort adapting to frequent minor updates. Because verified Lean solutions grow large across successive iterations, problems with established solutions also accept updates that substantially shorten the Lean code (by at least 20%) while strictly reducing cost, keeping files within agent context limits and reducing Lean compilation time. Recording negative results with concrete obstructions (such as numerical counterexamples or Lean lemmas) prevents later runs across all teams from repeating known dead ends.

Layout of one problem directory in the shared wiki

Figure S4. Layout of one problem directory in the shared wiki (stopping power). The best solution and the reusable partial Lean modules are checked by the external verifier against the frozen specification before merging, while idea notes are reviewed summaries labeled verified, promising, or dead-end. Each verified record in history.md lists the teams credited for it.

Conferences. Because many useful exchanges discuss unverified conjectures, teams convene periodically every four hours on a shared forum open across participating researchers and agent frameworks. During each session, agents pose questions, critique claims, and propose candidate constructions for other teams to test (see Figure S5). Discussion rules encourage direct replies between teams as opposed to standalone status reports, preventing the one-way broadcasting typical of unstructured agent boards.105,106 To uphold the correctness of intermediate work, statements and cost projections posted in a conference carry no weight until independently verified and published to the wiki.

!Wiki record #1 · Team 2 · PR #N verified. Q⋅T=6.34×1017Q \cdot T = 6.34 \times10^{17}. One 288-qubit shared ancilla register is reused by every step of the circuit. Team 3 · re-verifies and proposes. Re-checks Team 2’s record, then proposes two changes on top of it: a smaller subroutine and a catalyst prepared without scratch qubits. “Independently verified merged PR #N . . . on our checker.” “compresses [the subroutine] from 1,098 .TOFF down to 109 .TOFF . . . (+0 ancillas, . . . UNVERIFIED, Lean proof in progress)” “est. −25..−28 Q, UNVERIFIED”. Team 1 · endorses and asks (reply to 1). Agrees the catalyst change is sound and asks how Team 3 will prove the 109-Toffoli subroutine correct. “is a clean way to eliminate [the 28 scratch qubits] because the catalyst is prepared only once per shot” “are you proving the equivalence . . . by factoring the 67-wire circuit . . . or by symbolic . . . normalization?” Team 3 · answers (reply to 2). Gives the proof plan: split the circuit into three blocks, each checked by a small case analysis. “the circuit is structured as [three blocks] (47 + 15 + 47 = 109 .TOFFs) . . . each stage closes by tiny finite case analysis”. next conference session. Team 1 · critiques (reply to 3). Warns where the plan breaks once the subroutine sits inside Team 2’s record, gives the fix, and asks Team 3 to combine both changes. “pitfall: When lifting [the 109-Toffoli circuit] into . . . PR #N . . . proving the conjugation identity at the unitary . . . level before [substituting clean ancillas] avoids repeating the . . . proof across all 47 inverted Toffolis.” “are you pairing [the subroutine] with your [catalyst] ancilla reduction (−25..−28 Q)?” Team 3 · confirms (reply to 4). Adopts Team 1’s proof strategy. “Confirmed on the proof-architecture point”. Wiki record #2 · Team 3 verified −14.5%. Q⋅T=5.42×1017Q \cdot T = 5.42 \times10^{17}. “Builds on the 288-wire . . . baseline (PR #N) by composing 7 orthogonal verified seams”, including: catalyst prepared with 0 ancillas (QQ: 4,431 → 4,406) ← proposed in 1, endorsed in 2; 109-Toffoli subroutine ← proposed in 1, proof plan in 3–5. Credited authors: Team 3 agents and Team 2. read from the wiki. verified and published to the wiki bbox=0.14,0.22,0.86,0.69

Figure S5. A cross-team conference exchange between two verified records in the stopping power problem (records #1 and #2 of Figure 5c). Each numbered post replies directly to the one above it, across two conference sessions. Colored bars mark the team, the italic line is an analysis summary, and quoted text is verbatim from the conference; “. . .” marks omitted text, and words in square brackets, such as [the subroutine], replace Lean code snippets used in the original posts.

Fault-Tolerant Cost Metric and Hardware Horizons

Logical spacetime volume and architectural assumptions

Throughout the fault-tolerant benchmarks in this work, candidate circuits and literature baselines are compared at matched system encodings and error budgets by their logical spacetime volume Q⋅TQ \cdot\mathcal{T}, defined as total peak

logical qubits QQ (including clean workspace ancillas) multiplied by total T\mathcal{T}-gate count T\mathcal{T}, pricing clean-ancilla Toffoli gates at 4T4\mathcal{T} via measurement-based temporary-AND uncomputation.[23] [107, 108] This metric models compilation onto two-dimensional planar surface-code architectures using lattice surgery.[43] [109, 110] Because Clifford gates can be tracked in the classical Pauli frame or absorbed into multi-qubit Pauli product measurements, fault-tolerant overhead is dominated by preparing non-Clifford magic states through distillation or cultivation.[43] [111, 112, 113]

Under Pauli-based or serial-factory execution—where magic states are consumed at a fixed logical cycle rate—execution time tracks T\mathcal{T} while memory footprint tracks QQ, making Q⋅TQ \cdot\mathcal{T} proportional to Qlogical⋅DcyclesQ_{\mathrm{logical}} \cdot D_{\mathrm{cycles}}, the topological spacetime volume.[1, 2, 43, 89] [114, 115] Optimizing Q⋅TQ \cdot\mathcal{T} also regularizes space–time tradeoffs against degenerate extremes—neither permitting unbounded clean-ancilla QROAM replication to suppress T\mathcal{T}-gate count[4, 24] [116] nor forcing deep ancilla-starved recomputation to save a handful of qubits[10] [117]—and aligns directly with the (QQ, Toffoli/T\mathcal{T}) metrics reported across standard resource-estimation benchmarks.[3, 27, 48, 58, 60, 88] [118, 119]

Physical device cost departs from Q⋅TQ \cdot\mathcal{T} in two principal architectural regimes. First, provisioning parallel magic-state factories compresses execution depth from T\mathcal{T} toward T\mathcal{T}-depth at the expense of dedicated factory footprint and routing overhead.[1, 43] [115] Second, architectures incorporating non-local connectivity, high-rate quantum low-density parity-check (qLDPC) memory, or Active Volume compilation decouple idle memory storage from active reaction layers, lowering the spatial cost of inactive data qubits relative to active workspace.[61, 89, 90] [120, 121] Because every verified scientific simulation in Figure 3b reduces both QQ and T\mathcal{T} relative to its baseline, our improvements hold under any monotone weighting of logical space and non-Clifford-gate count.

Fault-tolerant capability regimes and hardware horizons

To place end-to-end logical resource counts in hardware context, Figure 3b overlays two fault-tolerant capability regimes (Table S1) as upper-bound resource envelopes (Q≤Qmax⁡Q \le Q_{\max}, T≤Tmax⁡\mathcal{T} \le\mathcal{T}_{\max}), with dashed lines at reference midpoints and feathered boundaries reflecting spread across estimates.

Capability regimeMidpoint (QQ, T\mathcal{T})QQ ceilingT\mathcal{T} ceilingQ⋅TQ \cdot\mathcal{T}Benchmarks & references
Medium-term FTQC (teraquop)(10310^{3}, 10910^{9})5×1025 \times10^{2}–2×1032 \times10^{3}3×1083 \times10^{8}–3×1093 \times10^{9}101210^{12}Cytochrome P450; compact catalysis & ECC[60, 61, 88, 89] [113, 114, 118]
Application-scale FTQC (FASQ)(10410^{4}, 101110^{11})5×1035 \times10^{3}–2×1042 \times10^{4}3×10103 \times10^{10}–3×10113 \times10^{11}101510^{15}Stopping power, C23_{23}H20_{20}N3_{3}O dynamics; catalysis, materials & RSA[1, 2, 3, 27, 48, 58] [115, 119, 120, 122]

Table S1. Fault-tolerant capability regimes and hardware horizons. Summary of the capability regimes referenced in Figure 3b, listing plotted dashed-line midpoints (QQ, T\mathcal{T}), nominal upper-bound ceilings (Qmax⁡Q_{\max}, Tmax⁡\mathcal{T}_{\max}) (rendered in Figure 3b with 14-step normal-quantile feathering spanning Q≈5.9×102Q \approx5.9 \times10^{2}–1.7×1031.7 \times10^{3}, T≈3.5×108\mathcal{T} \approx3.5 \times10^{8}–2.9×1092.9 \times10^{9} for teraquop planar and Q≈5.0×103Q \approx5.0 \times10^{3}–2.0×1042.0 \times10^{4}, T≈3.5×1010\mathcal{T} \approx3.5 \times10^{10}–2.9×10112.9 \times10^{11} for FASQ), nominal spacetime volume Q⋅TQ \cdot\mathcal{T}, and representative benchmarks and references.

Medium-term FTQC (teraquop planar). Gidney et al. 114 (§ 2.1) define the teraquop scale at 101210^{12} reliable logical operations (∼103\sim10^{3} logical qubits over ∼109\sim10^{9} steps at per-step error ∼10−12\sim10^{-12}), and Low et al. 61 quantify how denser planar surface-code layouts and magic-state cultivation set the corresponding qubit and T\mathcal{T}-gate ceilings across planar code distances. This regime sits at midpoint Q=103Q = 10^{3}, T=109\mathcal{T} = 10^{9}, and Q⋅T=1012Q \cdot\mathcal{T} = 10^{12}, with feathered ceiling Q∈[5×102,2×103]Q \in[5 \times10^{2}, 2 \times10^{3}] and T∈[3×108,3×109]\mathcal{T} \in[3 \times10^{8}, 3 \times10^{9}].

Application-scale FTQC (FASQ / petaquop). Preskill 2 defines the fault-tolerant application-scale quantum (FASQ) regime for full-scale scientific and cryptographic workloads, and Beverland et al. 1 (Table I) establish the logical-qubit and T\mathcal{T}-gate budgets required across materials, chemistry, dynamics, and factoring. This regime sits at midpoint Q=104Q = 10^{4}, T=1011\mathcal{T} = 10^{11}, and Q⋅T=1015Q \cdot\mathcal{T} = 10^{15}, with feathered ceiling Q∈[5×103,2×104]Q \in[5 \times10^{3}, 2 \times10^{4}] and T∈[3×1010,3×1011]\mathcal{T} \in[3 \times10^{10}, 3 \times10^{11}].

Parallel Grover Search

Problem specification and oracle model

Given a search space {0,…,N−1}\{0,\ldots,N-1\} of size N=2nN=2^n (n≥1n\ge1) and an unknown marked subset S⊂{0,…,N−1}S\subset\{0,\ldots,N-1\} of known size ∣S∣=k≤N\lvert S\rvert=k\le N, we study two exact (zero-error) search problems across (m,k)∈{1,2,4,…,1024}2(m,k)\in\{1,2,4,\ldots,1024\}^2 (121 settings): Find-Any, which must terminate with probability 1 and output an index x∈Sx\in S, and Find-All, which must terminate with probability 1 and output all kk elements of SS (so algorithms cannot trade error probability for fewer queries). We allow up to mm parallel queries per round[63] [123] (Figure S6). Access to SS is given by the (n+1)(n+1)-qubit reversible marking oracle

Parallel Grover query model

Figure S6. Parallel Grover query model. Workspace allocation (qset, +0 query cost) initializes mm query registers of n+1n+1 qubits and ww ancilla qubits in ∣0⟩⊗Q\lvert0\rangle^{\otimes Q} together with a classical state σ∈Σ\sigma\in\Sigma. Unitary evolution (step, +0) applies any SS-independent unitary U∈U(2Q)U \in U(2^Q) across all QQ qubits. Parallel oracle querying (oracle, +1) applies OS⊗mO_S^{\otimes m} (Eq. (5)) simultaneously across mm disjoint (n+1)(n+1)-qubit subregisters. Projective measurement (measure, +0) measures a subregister into classical variable yy in σ\sigma while leaving unmeasured wires coherent. Classical control (qif/qwhile; Appendix § 4) branches and loops on predicates of σ\sigma, weighting each oracle round by the active-branch probability ∑σ:b(σ)Tr⁡(Δt(σ))\sum_{\sigma:b(\sigma)}\operatorname{Tr}(\Delta_t(\sigma)) until ¬b(σ)\neg b(\sigma) outputs the result.

OS∣b⟩∣x⟩=∣b⊕[x∈S]⟩∣x⟩,b∈{0,1}, x∈{0,…,N−1},(4)O_S\lvert b\rangle\lvert x\rangle=\lvert b\mathbin{\oplus}[x\in S]\rangle\lvert x\rangle,\qquad b\in\{0,1\},\ x\in\{0,\ldots,N-1\}, \tag*{(4)}

where bb is a single-qubit target bit and xx is the nn-qubit index. Starting from ∣0⟩⊗Q\lvert0\rangle^{\otimes Q} on an unconstrained QQ-qubit workspace, an algorithm interleaves zero-cost SS-independent unitaries, projective measurements, and classical branching or loops with parallel mm-query rounds

OS⊗m=⨂j=1mOS(j)(5)O_S^{\otimes m}=\bigotimes_{j=1}^{m}O_S^{(j)} \tag*{(5)}

on any mm disjoint (n+1)(n+1)-qubit registers, weighted in expectation by the probability of being in an active loop branch. To query fewer than mm registers in a round, the remaining target qubits are prepared in ∣+⟩\lvert+\rangle, on which OSO_S acts as the identity. Our cost metric is the expected number of parallel query rounds (query depth).

Depending on how the target qubit bb is prepared (and optionally measured), a single call to OSO_S implements three operations. Preparing ∣b⟩=∣−⟩\lvert b\rangle=\lvert-\rangle applies the phase flip (I−2ΠS)(I-2\Pi_S) for ΠS=∑x∈S∣x⟩⟨x∣\Pi_S=\sum_{x\in S}\lvert x\rangle\langle x\rvert, while preparing ∣b⟩=∣0⟩\lvert b\rangle=\lvert0\rangle and measuring bb tests whether x∈Sx\in S (and once a subset F⊆SF\subseteq S has been found, unmarking FF via ∣b⟩∣x⟩↦∣b⊕[x∈F]⟩∣x⟩\lvert b\rangle\lvert x\rangle\mapsto\lvert b\mathbin{\oplus}[x\in F]\rangle\lvert x\rangle is independent of SS and costs zero queries). More generally, preparing ∣χγ⟩=cos⁡γ∣0⟩−sin⁡γ∣1⟩\lvert\chi_\gamma\rangle=\cos\gamma\lvert0\rangle-\sin\gamma\lvert1\rangle for γ∈(0,π/4]\gamma\in(0,\pi/4] leaves ∣χγ⟩\lvert\chi_\gamma\rangle unchanged for x∉Sx\notin S, while mapping ∣χγ⟩↦−sin⁡(2γ)∣χγ⟩+cos⁡(2γ)∣χγ⊥⟩\lvert\chi_\gamma\rangle\mapsto-\sin(2\gamma)\lvert\chi_\gamma\rangle+\cos(2\gamma)\lvert\chi_\gamma^\perp\rangle for x∈Sx\in S, where ∣χγ⊥⟩=sin⁡γ∣0⟩+cos⁡γ∣1⟩\lvert\chi_\gamma^\perp\rangle=\sin\gamma\lvert0\rangle+\cos\gamma\lvert1\rangle. Measuring bb in {∣χγ⟩,∣χγ⊥⟩}\{\lvert\chi_\gamma\rangle,\lvert\chi_\gamma^\perp\rangle\} therefore applies, with κ=cos⁡2(2γ)∈(0,1)\kappa=\cos^2(2\gamma)\in(0,1),

M1=κΠS (outcome ∣χγ⊥⟩),M0=(I−ΠS)−1−κΠS (outcome ∣χγ⟩):(6)M_1=\sqrt{\kappa}\Pi_S\ \text{(outcome }\lvert\chi_\gamma^\perp\rangle),\qquad M_0=(I-\Pi_S)-\sqrt{1-\kappa}\Pi_S\ \text{(outcome }\lvert\chi_\gamma\rangle): \tag*{(6)}

a click (∣χγ⊥⟩\lvert\chi_\gamma^\perp\rangle) projects onto SS with no false positives, while a no-click (∣χγ⟩\lvert\chi_\gamma\rangle) only slightly damps the marked amplitude and still flips its sign by −1-1 for the next Grover diffusion step.

To compare algorithms independent of the domain size N=2nN=2^n, let E[Dn(S)]\mathbb{E}[D_n(S)] be a program’s expected query depth on marked set SS, and let D‾n,m,k=(Nk)−1∑∣S∣=kE[Dn(S)]\overline{D}_{n,m,k}=\binom{N}{k}^{-1}\sum_{\lvert S\rvert=k}\mathbb{E}[D_n(S)] be its average over all kk-element subsets (which equals the worst-case expected depth over ∣S∣=k|S|=k, since indices can be randomly permuted at zero query cost). We normalize D‾n,m,k\overline{D}_{n,m,k} by the fixed reference scales

Dstdany(N,m,k)=π4Nmk,Dstdall(N,m,k)=∑r=1kπ4Nmr=π4Hk(1/2)Nm,Hk(1/2)=∑r=1k1r.(7)D_{\mathrm{std}}^{\mathrm{any}}(N,m,k)=\frac{\pi}{4}\sqrt{\frac{N}{mk}},\qquad D_{\mathrm{std}}^{\mathrm{all}}(N,m,k)=\sum_{r=1}^{k}\frac{\pi}{4}\sqrt{\frac{N}{mr}}=\frac{\pi}{4}H_k^{(1/2)}\sqrt{\frac{N}{m}},\qquad H_k^{(1/2)}=\sum_{r=1}^{k}\frac{1}{\sqrt{r}}. \tag*{(7)}

and certify in Lean a rational constant R(m,k)R(m,k) satisfying D‾n,m,k≤R(m,k)Dstd(2n,m,k)\overline{D}_{n,m,k}\le R(m,k)D_{\mathrm{std}}(2^n,m,k) for all sufficiently large nn. Because DstdD_{\mathrm{std}} is only a fixed reference scale rather than a lower bound, all speedups are computed as ratios against published baselines in the same metric, so DstdD_{\mathrm{std}} cancels out.

Published prior baselines

Every quantum search protocol obeys Θ(N)\Theta(\sqrt{N}) scaling in domain size, [62, 63] [124] with parallel round lower bounds Ω(N/(mk))\Omega(\sqrt{N/(mk)}) for Find-Any (Zalka’s bound[63] for k=1k=1; the general case follows from the parallel adversary bound123) and Ω(Nk/(mmin⁡(m,k)))\Omega(\sqrt{Nk/(m\min(m,k))}) for Find-All,[65] so protocols at fixed (m,k)(m,k) compete on their asymptotic leading constant r(m,k)=lim⁡N→∞D‾n,m,k/Dstd(N,m,k)r(m,k)=\lim_{N\to\infty}\overline{D}_{n,m,k}/D_{\mathrm{std}}(N,m,k). Prior work spans exact and fixed-point amplitude amplification[9] [125, 126, 127, 128]; early-stopped projective restarts with domain partitioning, independent parallel runs, or sequential strike-out[62, 63, 64] [129]; and damped or weakly measured loops.[66] [130, 131] We compare against the strongest published protocol in each (m,k)(m,k) regime, together with the direct combination of Zalka’s partition[63] and weakly measured search[66] on the k=1k=1 boundary (Figure S7). Parallel quantum-walk and learning-graph algorithms123 target multi-element certificates and do not tighten these baselines.

Published parallel Grover baselines and verified bounds across parallel queries per round and marked targets

Figure S7. Published parallel Grover baselines and verified bounds across mm, k∈{1,2,4,…,1024}k \in\{1, 2, 4, \ldots, 1024\}. a Each row evaluates a prior baseline protocol in our zero-error asymptotic metric (★ marks the winning baseline in each regime); the bottom rows summarize our Lean-verified circuits and speedups over the baseline envelope. Values report asymptotic expected parallel rounds as N=2n→∞N=2^n\to\infty relative to DstdD_{\mathrm{std}} (Eq. (7)). b, c Winning baseline envelopes for finding any one (b) or all kk (c) targets, on a logarithmic colour scale, with dashed contours marking regime boundaries.

Boundary regime (m=1m=1 or k=1k=1; BBHT, ZK, WG). On a single register (m=1m=1) with kk marked items, each Grover iteration rotates the state toward SS by 2θ=2arcsin⁡k/N≈2k/N2\theta=2\arcsin\sqrt{k/N}\approx2\sqrt{k/N}, so jj iterations reach angle ϕ=(2j+1)θ≈2jk/N\phi=(2j+1)\theta\approx2j\sqrt{k/N} and find a marked item upon measurement with probability sin⁡2ϕ\sin^2\phi. Standard Grover runs to ϕ=π/2\phi=\pi/2 (r=1r=1), where sin⁡2ϕ\sin^2\phi flattens out and the final queries buy little success probability. Boyer, Brassard, Høyer and Tapp[62] (BBHT) instead stop early at ϕ<π/2\phi<\pi/2 and restart from scratch on failure: each run costs j≈ϕ2N/kj\approx\frac{\phi}{2}\sqrt{N/k} queries and succeeds after 1/sin⁡2ϕ1/\sin^2\phi expected runs, minimizing expected queries ϕ2sin⁡2ϕN/k\frac{\phi}{2\sin^2\phi}\sqrt{N/k} at

rBBHT=2ϕ∗πsin⁡2ϕ∗≈0.878567,tan⁡ϕ∗=2ϕ∗(ϕ∗≈1.1656, sin⁡2ϕ∗≈0.845).(8)r_{\mathrm{BBHT}}=\frac{2\phi^*}{\pi\sin^2\phi^*}\approx0.878567,\qquad\tan\phi^*=2\phi^*\quad(\phi^*\approx1.1656,\ \sin^2\phi^*\approx0.845). \tag*{(8)}

Across the m=1m=1 and k=1k=1 boundaries of Find-Any and Find-All (which coincide when k=1k=1), rBBHTr_{\mathrm{BBHT}} sets the projective-restart baseline. For k=1k=1 and m≥2m\ge2 in both tasks, Zalka[63] (ZK) splits {0,…,N−1}\{0,\ldots,N-1\} into mm disjoint blocks of size N/mN/m so the unique block containing the target runs at ϕ∗\phi^* (rZK=rBBHTr_{\mathrm{ZK}}=r_{\mathrm{BBHT}}). For m=1m=1 and k≥2k\ge2 in Find-All, repeating early-stopped search kk times while unmarking each found item at zero query cost[62] [129] achieves rBBHTr_{\mathrm{BBHT}} at every stage.

On the single-register boundary (m=1,k≥1m=1,k\ge1 for Find-Any, and (1,1)(1,1) for Find-All), early-stopped projective search is superseded by Fang and Heunen’s weakly measured loop[66] (WG), which avoids discarding the amplified state when a check misses. Instead, WG first runs standard Grover halfway to α∗=π/4\alpha^*=\pi/4 (50% marked weight, costing 12Dstdany\frac{1}{2}D_{\mathrm{std}}^{\mathrm{any}}), and then alternates calibrated weak checks (Eq. (6)), k≈8k/Nk\approx8\sqrt{k/N} with single zero-query diffusion steps. Whenever a check does not click, its slight damping and −1-1 phase flip are offset by the diffusion step to return the state back to π/4\pi/4 without losing superposition; waiting for a click adds 1πDstdany\frac{1}{\pi}D_{\mathrm{std}}^{\mathrm{any}} expected queries, giving

rWG=12+1π≈0.818310.(9)r_{\mathrm{WG}}=\frac{1}{2}+\frac{1}{\pi}\approx0.818310. \tag*{(9)}

For k=1k=1 and m≥2m\ge2 in both tasks, running WG inside each of Zalka’s mm disjoint blocks of size N/mN/m (ZK+WG) is a direct substitution—the m−1m-1 empty blocks never click while the unique target block evolves at scale N/m\sqrt{N/m}—upgrading the k=1k=1 boundary from rZK≈0.879r_{\mathrm{ZK}}\approx0.879 to rWG≈0.818r_{\mathrm{WG}}\approx0.818.

ReferenceEvaluation in metricFind-Any RegimeFind-Any Rel. roundsFind-All RegimeFind-All Rel. rounds
Boyer et al.[62] (BBHT, Eq. (8))Early-stop restart + strike-out——m=1m=1, k≥2k\ge2★0.879
Zalka[63] (ZK, Eq. (8))mm-block partition + early stopm≥2m\ge2, k=1k=10.879m≥2m\ge2, k=1k=10.879
Gingrich et al.[64] (GW, Eq. (10))Unpartitioned mm-slot early stopmm, k≥2k\ge2★0.942–0.997——
Grover & Radhakrishnan[65] (GR0)Two-pass mm-block staircase (t1t_1)——mm, k≥2k\ge2★0.060–0.955
Fang & Heunen[66] (WG; +ZK, Eq. (9))Calibrated weak loop (+ZK at k=1k=1)m=1m=1 or k=1k=1★0.818k=1k=1★0.818
This work (Lean-verified circuits)all0.818all0.027–0.818
Speedup vs. baseline envelope (Figure 3d)mm, k≥2k\ge2up to 1.22×k≥2k\ge2up to 2.55×

Table a. Published baselines and verified bounds

Interior Find-Any (mm, k≥2k \ge2; GW). When both m≥2m \ge2 and k≥2k \ge2, naive domain splitting breaks down because each of the mm blocks receives a random, unknown number of targets (and most blocks are empty when k<mk < m), causing multi-target blocks to rotate faster and overshoot π/2\pi/2 under any fixed schedule. Gingrich, Williams and Cerf[64] (GW) avoid this unknown-load problem by running all mm registers independently over the full domain {0,…,N−1}\{0,\ldots,N-1\}. Stopping all mm registers synchronously after j≈ϕ2N/kj \approx\frac{\phi}{2}\sqrt{N/k} rounds finds a target unless all mm independent measurements miss (probability cos⁡2mϕ\cos^{2m}\phi); minimizing expected rounds ϕ2(1−cos⁡2mϕ)N/k\frac{\phi}{2(1-\cos^{2m}\phi)}\sqrt{N/k} selects ϕ∗(m)<ϕ∗\phi^*(m)<\phi^* with

rGW(m)=2mϕ∗(m)π(1−cos⁡2mϕ∗(m)),1−cos⁡2mϕ∗(m)(1+2mϕ∗(m)tan⁡ϕ∗(m))=0.(10)r_{\mathrm{GW}}(m)=\frac{2\sqrt{m}\phi^*(m)}{\pi(1-\cos^{2m}\phi^*(m))},\qquad1-\cos^{2m}\phi^*(m)(1+2m\phi^*(m)\tan\phi^*(m))=0. \tag*{(10)}

Because mm unentangled copies combine success probabilities classically rather than coherently, rGW(m)r_{\mathrm{GW}}(m) is independent of kk and degrades from 0.942 at m=2m=2 to 0.997 at m=1024m=1024, setting the published baseline on all 100 interior cells (Figure S7).

Interior Find-All (mm, k≥2k \ge2; GR0). To let mm registers find distinct targets in parallel at N/m\sqrt{N/m} block scale, Grover and Radhakrishnan[65] randomly partition {0,…,N−1}\{0,\ldots,N-1\} into mm blocks of size N/mN/m. Each block receives an unknown target count cc, which they clear via a descending staircase of exact amplitude-amplification stages127 at assumed counts s=t,t−1,…,1s=t,t-1,\ldots,1 (total depth Ht(1/2)π4N/mH_t^{(1/2)}\frac{\pi}{4}\sqrt{N/m}), testing and unmarking hits after each stage. Counting down guarantees emptying every block with c≤tc \le t: even if stages s>cs>c miss, once ss reaches a block’s remaining count cc, the assumed and actual counts match, finding a target with certainty and stepping c→c−1c \to c-1 in lockstep with ss (while mismatched stages s≠cs \ne c still hit with probability sin⁡2(π2c/s)\sin^2(\frac{\pi}{2}\sqrt{c/s})). Because Theorem 3 of ref.[65] leaves tail cleanup at Θ(⋅)\Theta(\cdot) order, we evaluate a concrete two-pass schedule (GR0): Pass 1 runs a staircase from the optimal integer cap 1≤t∗(m,k)<k1 \le t^*(m,k)<k down to 1, and Pass 2 clears all R1=k−∣found∣R_1=k-\lvert\mathrm{found}\rvert remaining targets via a second staircase from R1R_1 down to 1 (Figure S7).

Algorithmic mechanisms in verified circuits

Beyond the k=1k=1 boundary (ZK+WG), our interior baselines are single-paper protocols; Figure S8 separates automatic recombinations, which join unchanged published subroutines by new classical control, from new coherent mechanisms, which alter the quantum dynamics or measurements within a search stage, listing a few of the many mechanisms found per class. Since mechanisms interact, Figure S7 reports only joint speedups, while Figure S8,Figure S8 details the verified relative round costs and winning circuit regimes across (m,k)(m,k).

Verified parallel Grover mechanisms and relative round costs

Figure S8. Verified parallel Grover mechanisms and relative round costs across m,k∈{1,2,4,…,1024}m,k \in\{1,2,4,\ldots,1024\}. a Selected algorithmic mechanisms in our Lean-verified circuits (not exhaustive). b, c Verified asymptotic expected parallel rounds relative to DstdD_{\mathrm{std}} (Eq. (7)) for finding any one (b) or all kk (c) targets, on a logarithmic colour scale, with dashed contours and labels marking the winning mechanism in each region (cf. panel a; WG and ZK+WG denote ties with the baseline).

Unlike distributed baselines such as GW and GR0 that run mm uncoupled registers, our shared-workspace model allows inter-slot entanglement: coupling all mm slots via odd-parity fanout in Find-Any extends the boundary constant rWGr_{\mathrm{WG}} to every interior (m,k≥2)(m,k \ge2), while Find-All entangles slot and storage registers. In our strongest Find-All mechanism (k≲mk \lesssim m; Figure S9), three ideas avoid the bin-load variance of partitioned search: (i) preparing a uniform superposition over mm-element subsets ∣E⟩\lvert E\rangle so one ∣−⟩\lvert-\rangle-marked call to OS⊗mO_S^{\otimes m} (unmarking archived hits FF) supplies all target information via the hit-parity phase (−1)∣E∩(S∖F)∣(-1)^{|E\cap(S\setminus F)|}; (ii) alternating that query with a fixed, SS-independent reflection on the Johnson-scheme eigenspaces of mm-subsets123—analogous to Grover’s uniform diffusion step and compiled via quantum singular value transformation (QSVT),[26] plus a terminal phase kick, driving the hit count w=∣E∩(S∖F)∣w=|E\cap(S\setminus F)| coherently from 0 to r=∣S∖F∣r=|S\setminus F| in under N/m\sqrt{N/m} rounds; and (iii) batch readout, where one final query writes all w∈[wlo,r]w\in[w_{\mathrm{lo}},r] hits into ∣F⟩\lvert F\rangle at once, retrying or clearing any remainder via exact loops. Although SS-independent unitaries carry zero query cost in the black-box specification, our verified circuits use O((m+k)n)O((m+k)n) qubits and each unitary step compiles into poly⁡(n,m,k)\operatorname{poly}(n,m,k) elementary gates (within error 2−Ω(n)2^{-\Omega(n)} for the QSVT-compiled diffusion steps).

High-level circuit for the collective Johnson-graph walk

Figure S9. High-level circuit for the collective Johnson-graph walk. Registers hold mm address slots (∣0⟩⊗mn)(|0\rangle^{\otimes mn}), mm flag qubits (∣0⟩⊗m)(|0\rangle^{\otimes m}), and a knkn-qubit archive ∣F⟩|F\rangle of found targets. (1) prep prepares the uniform superposition (Nm)−1/2∑∣E∣=m∣E⟩\binom{N}{m}^{-1/2}\sum_{|E|=m}|E\rangle over mm-subsets E⊆{0,…,N−1}E\subseteq\{0,\ldots,N-1\}. (2) For L<N/mL<\sqrt{N/m} rounds (L×L\times), (XH)⊗m(XH)^{\otimes m} (XX then HH) and (HX)⊗m(HX)^{\otimes m} switch the flags between ∣0⟩⊗m|0\rangle^{\otimes m} and ∣−⟩⊗m|-\rangle^{\otimes m}; OS⊗mO_S^{\otimes m} is the parallel marking oracle; UFU_F unmarks slots already in FF, so the dotted block applies (−1)∣E∩(S\F)∣(-1)^{|E\cap(S\backslash F)|}; and RJR_J is an SS-independent Johnson-graph reflection compiled via QSVT. (3) After one call to OS⊗mO_S^{\otimes m} and UFU_F, UstoreU_{\mathrm{store}} records new hits into ∣F′⟩|F'\rangle and measuring the flags outputs the hit count w=∣E∩(S\F)∣w=|E\cap(S\backslash F)|.

MechanismBuilds onRegimeDescription
Automatic recombinations
Weak-loop pipelining[62, 64, 66] [131]Find-All, k≳mk \gtrsim mFull-domain slots run weakly measured loops; a click strikes out its target and restarts only that slot, while the others keep their progress.
Sibling sub-block re-search[62, 63, 65]Find-All, k≈mk \approx\sqrt{m}A target missed by a partitioned sweep most likely shares a block with a found one; only those blocks are re-searched, split across all slots.
Re-partitioned sweeps[62, 65, 66]Find-All, k<mk < mUnder-rotated sweeps over fresh (bit-swapped) partitions stop once all targets are found; a weakly measured loop finds the last one.
New coherent mechanisms
Odd-parity joint reflection[63, 66]Find-AnyConjugating OS⊗mO_{S}^{\otimes m} by marker-qubit gates gives a reflection about slot tuples holding an odd number of targets.
Tensor-power conveyor[9]Find-All, k≫mk \gg mA zero-query rotation repeatedly moves found amplitude from each query register into d−1d-1 storage registers.
Collective Johnson walk[26, 63] [123]Find-All, m≥4m \ge4Alternating odd-parity mm-subset queries with SS-independent Johnson-graph reflections (compiled via QSVT) drives the hit count from 00 to kk in one pass.
Slice zoom[63, 65]Find-All, k≤8k \le8Restricting the search to target-independent rotated slices of the domain zooms in on the few marked items, so later rounds search a much smaller effective list.

Table a. Selected mechanisms in verified circuits.

Fixed-Point arcsin

Problem and specification

Many fault-tolerant quantum algorithms require converting amplitudes held in a quantum register into single-qubit rotation angles, including probability-distribution loading and state preparation,132 eigenvalue inversion in quantum linear-system solvers,133 and quantum rejection and Metropolis sampling.134,135 Implementing these rotations via phase kickback or controlled Pauli gates first evaluates arcsin⁡(y)\arcsin(y) reversibly on a fixed-point register, a subroutine that often dominates the non-Clifford gate count.[10] [136]

We consider reversible evaluation ∣y⟩∣b⟩∣0⟩⊗m↦∣y⟩∣(b+z(y)) mod 2k⟩∣0⟩⊗m|y\rangle|b\rangle|0\rangle^{\otimes m}\mapsto|y\rangle|(b+z(y))\bmod2^k\rangle|0\rangle^{\otimes m} on k=25k=25 signed two’s-complement registers, where yy is the input register, bb is the output register, and z(y)z(y) approximates arcsin⁡(y)\arcsin(y). Because ddyarcsin⁡(y)=(1−y2)−1/2\frac{d}{dy}\arcsin(y)=(1-y^2)^{-1/2} diverges as ∣y∣→1|y|\to1, uniform polynomial approximations require high degree near the endpoints, while iterative shift-and-add methods accumulate deep chains of reversible multiplications.[10] [137] Our signed two’s complement representation (1 sign, 1 integer and 23 fractional bits) matches the float32 mantissa size. With 23 fractional bits, the smallest representable value is 2−23≃1.19×10−72^{-23}\simeq1.19\times10^{-7}. Allowing for some small rounding error, we require a maximum absolute error ∣z(y)−arcsin⁡(y)∣≤1.25×10−7|z(y)-\arcsin(y)|\le1.25\times10^{-7} across all 224+1=16,777,2172^{24}+1=16,777,217 inputs y∈[−1,1]y\in[-1,1]. Using mm clean ancillas, a candidate program in Clifford+TT gates and mid-circuit measurements must apply this exact action across all 2502^{50} basis states (y,b)(y,b) and return all ancillas to ∣0⟩⊗m|0\rangle^{\otimes m}.

Baseline

We consider as baseline the algorithm by Häner et al. [10], which uses a piecewise-polynomial approach.[1] We compare against their (n,m,d)=(35,3,3)(n,m,d)=(35,3,3) fixed-point two’s-complement configuration, whose maximum error ∼10−6\sim10^{-6} is driven by the error in the square root computation (Fig. 6 of ref. 10), and larger than our target bound of 1.25×10−71.25\times10^{-7}, thus providing a lower bound on the spacetime cost. As shown in Figure S10, this baseline splits the computation of arcsin⁡\arcsin on the interval [−1,1][-1,1] between a degree-3 polynomial evaluation on [−0.5,0.5][-0.5,0.5] and a Newton iteration for z=z⋅1/z\sqrt{z}=z\cdot1/\sqrt{z}.[2] As their Appendix § 7 describes, the former can be implemented using 140 qubits and requires 17,304 Toffoli gates and the same amount for reversing the computation, for a total of 34,608 Toffoli gates (138,432 TT gates). The latter can be implemented using 245 qubits and requires 73,442 Toffoli gates to implement it as the product of zz with 1/z1/\sqrt{z}, as described in their Appendix C.2, and an additional 2,094 Toffoli gates to also reverse the product operation, being 1/z1/\sqrt{z} already a reversible operation, for a total of 75,536 Toffolis (302,144 TT gates).

Baseline circuit to implement the arcsin function, with input $|y\rangle$, branch selection, square-root and polynomial subcircuits, sign flip, and uncomputation

Figure S10. Baseline circuit to implement the arcsin function,[10] using n=35n = 35, m=3m = 3, d=3d = 3. After restricting to the positive range, the approximation splits the calculation of arcsin between a degree-3 polynomial in the interval [0,0.5][0, 0.5] and a Newton iteration for the square root function in [0.5,1][0.5, 1]. Number of TT gates and number of qubits calculated as in their Appendix, for reversible computation.

We calculate a lower bound of the full circuit spacetime cost of 1.08×1081.08 \times10^{8} by using the maximum number of required qubits in the two subcircuits, 245, and the sum of the TT gates required for them, 440,576 TT gates. We thus ignore persistent registers and the smaller branch-selection and combination blocks, which would further increase the cost.

Program Discovery

While our library lets us represent arbitrary gates and formally verify the cost of algorithms, the kickmix model[7] restricts circuits to classical reversible gates (X, CNOT, Toffoli and CSWAP), Pauli-X measurement-based uncomputation,[23] and diagonal Z, CZ and CCZ phase corrections so that every basis input stays a single signed basis state (−1)ϕ∣x⟩(-1)^{\phi}|x\rangle along each measurement branch, enabling fast classical fuzz-testing without statevector simulation. The fact that agentic systems can produce compact arithmetic quantum circuits by using the feedback from kickmix testing is already known,117,138 and has also been applied to a related arcsin(c/Xc/X) subroutine, but on a restricted input range rather than [−1,1][-1, 1]. We exploited this speed by first running our multi-agent system to search for circuits using kickmix. The result was a circuit of spacetime cost 498,168 (102 qubits, 4,884 TT gates).

However, the kickmix gate set is limited, and we expect that the full Clifford+TT gate set could allow for a more efficient implementation. To obtain more general algorithms that are not limited by the kickmix restrictions, we need a different way to verify the circuit, and this is where our formal library helps. Starting from the algorithm obtained with kickmix, we instructed agents to start using our quantum algorithm specification and verification framework to further optimize the algorithm. For a while, agents were able to continue optimizing the circuit up to a cost of 415,200 (100 qubits, 4,152 TT gates, Figure S11 and Table S2), which continued using a restricted set of gates, and could still be translated to kickmix. Subsequently, the agents truly took advantage of our library and produced circuits that could not be expressed and efficiently simulated with kickmix (Figure S11,Figure S11). This drove the cost down by a further 11% to 369,800 (100 qubits, 3,698 TT gates), 290× below the baseline[10] (Figure 3a,Figure 3c).

Methodε\varepsilonToffoliTTQQSpacetime cost (Q⋅TQ \cdot T)
Baseline[10] (lower bound)∼10−6\sim10^{-6}110,144440,5762451.08×1081.08 \times10^8
– arcsin on [−0.5,0.5][-0.5, 0.5]34,608138,432——
– 1/z1/\sqrt{z}75,536302,144——
Kickmix1.25×10−71.25 \times10^{-7}1,0384,152100415,200
Non-kickmix (Lean 4)1.25×10−71.25 \times10^{-7}7763,698100369,800

Table S2. Summary for fixed-point arcsin(yy) on [−1,1][-1, 1] at k=25k = 25. The baseline evaluates the (n,m,d)=(35,3,3)(n,m,d) = (35, 3, 3) configuration,[10] assuming 4 TT per Toffoli.[23] [107] We derive a lower bound on its spacetime cost by summing the two dominant reversible submodules on the 245-qubit square-root workspace while neglecting persistent registers and the steps that combine the two parts. In the non-kickmix Lean 4 circuit, the 3,698 TT gates comprise 776 four-TT temporary-AND gates (3,104 TT) plus 594 single-qubit TT/T†T^\dagger gates across 41 inner-product gadgets.

Sketch of the algorithm to implement the fixed-point arcsin module

Figure S11. Sketch of the algorithm to implement the fixed-point arcsin module. (a) Full kickmix circuit. It uses 50 data qubits (∣y⟩|y\rangle and ∣b⟩|b\rangle, 25 each) and 50 ancilla qubits reused across stages, and a total of 4,152 TT gates. The bin index ss has 9 bits but needs only 2 extra ancillas. After "shift ∣y∣→t|y| \rightarrow t", 6 bits of ss are simply the top 6 bits of tt, which identify the bin within its group. A 7th bit replaces the 12\frac{1}{2} bit of ∣y∣|y|, which can be recomputed from ss and is erased. The remaining 2 bits use one ancilla each: one is stored directly, and the other replaces the top bit of ∣y⟩|y\rangle, whose value is moved into an ancilla. t2t^2 is computed into the ancillas freed by clearing AA. At peak, the ancillas hold AA (19), BB and CC (24), 5 lookup work qubits, 1 bit of ss, and the moved bit of ∣y⟩|y\rangle. (b) Improved block in the non-kickmix circuit. Algorithm verification with our formal quantum computation library allows further optimization of the circuit. Specifically, the coefficient lookup block can be replaced with a more efficient block, saving overall 454 TT gates. Each coefficient bit is computed by one inner-product block taking a variable number r∈{2,…,7}r \in\{2, \ldots, 7\} of product pairs and using 2r+22r + 2 TT gates. We have 26 blocks totaling 364 TT gates before +A+A, and 15 blocks totaling 230 TT gates on the freed qubits after clearing AA. Each inner-product block leaves an extra sign phase that is then removed before returning the result. The whole circuit requires now 3,698 TT gates instead of 4,152 TT gates. (c) Example of the optimized inner-product block for two product pairs, using 6 TT gates, which could not be expressed in the kickmix framework.

In other words, for this problem, our agents using kickmix can do an efficient search in the restricted subspace without the overhead of a formal proof. Afterwards, our agents using formal verification lift the gate-set restriction and allow further optimization that would not be easily testable classically. Every circuit that can be simulated with kickmix can also be proven in Lean, and seeding a Lean discovery agent from a kickmix solution further improves the solution.

Interpretation

Figure S11 provides an interpretation of the algorithms that we obtained, and shows where the optimization using the Lean verifier obtained an improvement.

Since arcsin is an odd function, i.e. z(−y)=−z(y)z(-y) = -z(y), we can perform the calculation only for positive inputs, and flip the output register according to the sign. Subsequently, we also split off the linear part, z(∣y∣)=∣y∣+r(∣y∣)z(\lvert y\rvert) = \lvert y\rvert+ r(\lvert y\rvert) and approximate the remainder r(∣y∣)≈arcsin⁡(∣y∣)−∣y∣r(\lvert y\rvert) \approx\arcsin(\lvert y\rvert) - \lvert y\rvert using a separate quadratic polynomial on 440 intervals of [0,1][0, 1]. Each interval is chosen to have a width roughly proportional to its distance to 1, so on each interval the square root is smooth, a second order polynomial fits well, and the fit error shrinks when getting closer to 1. The intervals get narrower toward ∣y∣=1\lvert y\rvert= 1, where arcsin⁡(∣y∣)≈π2−2(1−∣y∣)\arcsin(\lvert y\rvert) \approx\frac{\pi}{2} - \sqrt{2(1-\lvert y\rvert)} grows steeply. The closest input to 1 on the fixed-point grid is 2−232^{-23} away, so finitely many intervals cover all inputs. The point ∣y∣=1\lvert y\rvert= 1 is handled separately. Subsequently, the circuit looks for the interval that contains ∣y∣\lvert y\rvert and stores its index in a 9-bit register ss. It does so by using a barrel shift, i.e. it counts the leading zeros of 1−∣y∣1-\lvert y\rvert, and shifts the magnitude bits left using controlled swaps to form the local offset tt. A lookup block then computes the interval’s coefficients AA, BB, CC for ss, and squarer and adder circuits add A+Bt+Ct2A + Bt + Ct^2 to bb. As an optimization, the 19 high bits of AA are added to bb and erased so that the remaining coefficient bits can be computed on the same qubits. Similarly, CC and t2t^2 are erased midway so their qubits can be reused for the rest of +Bt+Bt. Measurements with ZZ and CZCZ corrections erase the coefficients and all other scratch qubits at zero TT cost. Finally, the circuit is made reversible by undoing the shift and the sign conversion, restoring yy and returning all ancillas to ∣0⟩\lvert0\rangle.

As shown in Figure S11, a large amount of the total kickmix TT gates are spent on the coefficient lookup phase. Specifically, each coefficient bit is a fixed function of the interval number ss, given by a table with one entry per interval. Any such table can be written as an XOR of products of bits of ss, e.g. s1s4⊕s2s3s7⊕s5s_1s_4 \oplus s_2s_3s_7 \oplus s_5. The kickmix circuit first builds a few products that many coefficient bits share, and then builds each coefficient bit by XOR-ing in the products it needs using a 4 TT AND circuit for each product.

The non-kickmix circuit replaces most of these bitwise product blocks with 41 inner-product circuits that need roughly half as many TT gates. Indeed, each block puts its coefficient qubit in an equal superposition of 0 and 1 states, writes the products as a relative phase between the two branches using TT and T†T^\dagger gates, and then makes the branches interfere to get the appropriate bit. However, each inner-product circuit leaves a sign ±1\pm1 that depends on the specific ss, which is cancelled across each lookup pass with ZZ and CZCZ gates at zero TT cost. Because each inner

product writes directly into its target coefficient qubit and needs no extra scratch qubits, the circuit can postpone more coefficient bits of BB and CC until after AA has been added to bb and cleared, leaving more spare qubits for that adder and reducing the lookup-and-add stage from 1,348 to 894 TT gates. Together, these changes lower the full circuit from 4,152 to 3,698 TT gates on the same 100 qubits.

Stopping Power in Inertial-confinement Fusion

Hamiltonian and specification

Following Eqs. (1)–(7) and Tables 1–2 of ref. 48, the system consists of η=218\eta= 218 electrons (ζe=−1\zeta_e = -1, mass 1) and one α\alpha-particle projectile (ζproj=+2\zeta_{\mathrm{proj}} = +2, mass Mproj=7,294.29954171 meM_{\mathrm{proj}} = 7{,}294.29954171\,m_e, matching 3.9726 proton masses in Table 2 of ref. 48) in a periodic cubic cell of volume Ω=2,419.68282 a03\Omega= 2{,}419.68282\,a_0^3 containing 216 fixed protons at arbitrary positions Rℓ∈R3R_\ell\in\mathbb{R}^3. In plane-wave first quantization, each electron momentum coordinate is stored in np=6n_p = 6 signed-magnitude qubits and each projectile coordinate in nn=8n_n = 8 signed-magnitude qubits,27,48{}^{27,48} giving Qsys=3(ηnp+nn)=3,948Q_{\mathrm{sys}} = 3(\eta n_p+n_n)=3{,}948 system qubits. The valid grid subspace excludes the signed-magnitude negative zero ∣1,0⋯0⟩\lvert1,0\cdots0\rangle from every coordinate, leaving integer momenta in G=[−31,31]3G=[-31,31]^3 for each electron (63363^3 plane waves, covering the 53353^3 classical time-dependent density-functional grid of Table 1 in ref. 48) and G~=[−127,127]3\widetilde{G}=[-127,127]^3 for the projectile, at wavevectors kν=2πν/Ω1/3k_\nu=2\pi\nu/\Omega^{1/3}. The projectile’s momenta are taken relative to its initial mean momentum kprojk_{\mathrm{proj}}, with kprojΩ1/3/(2π)∈Z3k_{\mathrm{proj}}\Omega^{1/3}/(2\pi)\in\mathbb{Z}^3 for compatibility with the cell’s periodicity and ∥kproj∥2≤29,376\lVert k_{\mathrm{proj}}\rVert_2\leq29{,}376 a.u. (vα≈4v_\alpha\approx4 a.u.).

On valid grid states, the discretized Hamiltonian in atomic units is

H=∑i=1η∑p∈G~∥kp∥222∣p⟩⟨p∣i+∑p∈G~∥kp−kproj∥222Mproj∣p⟩⟨p∣proj+∑a∑p,q∈Gap≠qζaS(p−q)K(p−q)∣p⟩⟨q∣a+12∑a≠bν≠0∑p∈Ga,q∈Gbp+ν∈Ga,q−ν∈GbζaζbK(ν)∣p+ν⟩⟨p∣a∣q−ν⟩⟨q∣b,(11)\begin{aligned} H={}&\sum_{i=1}^{\eta}\sum_{p\in\widetilde{G}}\frac{\lVert k_p\rVert_2^2}{2}\lvert p\rangle\langle p\rvert_i+\sum_{p\in\widetilde{G}}\frac{\lVert k_p-k_{\mathrm{proj}}\rVert_2^2}{2M_{\mathrm{proj}}}\lvert p\rangle\langle p\rvert_{\mathrm{proj}}\\ &+\sum_a\sum_{\substack{p,q\in G_a\\p\ne q}}\zeta_aS(p-q)K(p-q)\lvert p\rangle\langle q\rvert_a\\ &+\frac{1}{2}\sum_{\substack{a\ne b\\\nu\ne0}}\sum_{\substack{p\in G_a,q\in G_b\\p+\nu\in G_a,q-\nu\in G_b}}\zeta_a\zeta_bK(\nu)\lvert p+\nu\rangle\langle p\rvert_a\lvert q-\nu\rangle\langle q\rvert_b, \tag*{(11)} \end{aligned}

and acts as zero outside the valid grid subspace. Here aa and bb range over the η\eta electrons (Ga=GG_a=G, ζa=−1\zeta_a=-1) and the projectile (Gproj=G~G_{\mathrm{proj}}=\widetilde{G}, ζproj=+2\zeta_{\mathrm{proj}}=+2), K(ν)=4π/(Ω∥kν∥22)K(\nu)=4\pi/(\Omega\lVert k_\nu\rVert_2^2), and S(ν)=∑ℓ=1216e−ikν⋅RℓS(\nu)=\sum_{\ell=1}^{216}e^{-i k_\nu\cdot R_\ell}.

For every proton configuration {Rℓ}\{R_\ell\}, initial projectile momentum kprojk_{\mathrm{proj}}, evolution time t∈{1,…,10}t\in\{1,\ldots,10\} a.u., and partition of the 218 electron registers into spin-up and spin-down subsets, a candidate circuit over Clifford+TT and mid-circuit measurement using mm ancilla qubits must realize a single unitary WW that matches e−iHte^{-iHt} up to a global phase φ\varphi, satisfying

∥W(∣ψ⟩⊗∣0⟩⊗m)−eiφ(e−iHt∣ψ⟩)⊗∣0⟩⊗m∥2≤ε(12)\left\lVert W\left(\lvert\psi\rangle\otimes\lvert0\rangle^{\otimes m}\right)-e^{i\varphi}\left(e^{-iHt}\lvert\psi\rangle\right)\otimes\lvert0\rangle^{\otimes m}\right\rVert_2\leq\varepsilon \tag*{(12)}

at ε=10−2\varepsilon=10^{-2} for every normalized grid state ∣ψ⟩\lvert\psi\rangle antisymmetric under exchange of same-spin electrons. All ancillas begin in ∣0⟩⊗m\lvert0\rangle^{\otimes m} in each run, rather than carrying pre-prepared resource states (such as phase-gradient states) across runs. Every circuit is compiled into Clifford+TT gates, mid-circuit measurements and classical feed-forward, and checked at that gate level by the correctness proof. Where later gates are conditioned on measurement outcomes, we count the TT gates of the most expensive outcome branch.

To extract the stopping power from the projectile’s rate of energy loss, the protocol repeats time evolution 50 times at each of t=1,…,10t=1,\ldots,10 a.u. (500 runs) to estimate the mean projectile kinetic energy, omitting state preparation and readout as their cost is negligible. In this work, our Lean specification asks for the algorithm to prove correctness and cost for all 500 circuits. However, in § 2.3 and Figure 4 we report the average TT count over the circuits, since this more accurately reflects the size of circuit a fault-tolerant quantum computer would need to coherently execute. We apply this to both the baseline and our solution, so the factor of improvement reported is equal regardless. However, the baseline costing convention[48] (total over all circuits) can be obtained by simply multiplying our arithmetic mean by 500.

Baseline

Table 2 of ref. [48] gives a momentum-space LCU 1-norm of λ=1,744,784.42 Ha\lambda= 1{,}744{,}784.42\ \mathrm{Ha}, a block-encoding cost of CBE=2.498×104C_{\mathrm{BE}} = 2.498 \times10^{4} Toffolis per walk step, and Qbase=5,650Q_{\mathrm{base}} = 5{,}650 logical qubits (3,948 system and 1,702 ancilla qubits). Each electron–proton or electron–electron pair contributes ∑ν∈[−62,62]∖{0}(πΩ1/3∥ν∥2−1)=22.53 Ha\sum_{\nu\in[-62,62]\setminus\{0\}}(\pi\Omega^{1/3}\lVert\nu\rVert_{2}^{-1}) = 22.53\ \mathrm{Ha} to λ\lambda, giving 1.06×106 Ha1.06 \times10^{6}\ \mathrm{Ha} from electron–proton attraction and 5.33×105 Ha5.33 \times10^{5}\ \mathrm{Ha} from electron–electron repulsion (91.4% of λ\lambda).

Generalized QSP139 implements e−iHte^{-iHt} as a polynomial in a qubitized walk operator[25] that block-encodes H/λH/\lambda, with one walk step per query. Evaluating the query count140 in Eq. (12) of ref. [48],

Nsteps(t)=λt+32/32(λt)1/3log⁡22/3(1/ε),(13)N_{\mathrm{steps}}(t) = \lambda t + \frac{3^{2/3}}{2}(\lambda t)^{1/3}\log_{2}^{2/3}(1/\varepsilon), \tag*{(13)}

at ε=10−2\varepsilon= 10^{-2} and summing over the 50 runs at each of t=1,…,10t = 1,\ldots,10 a.u. gives 4.80×1094.80 \times10^{9} walk steps, or 1.20×10141.20 \times10^{14} Toffolis over all 500 runs. This is an average of 9.60×1069.60 \times10^{6} walk steps and NToffbase=2.40×1011N_{\mathrm{Toff}}^{\mathrm{base}} = 2.40 \times10^{11} Toffolis per run, so Tbase=4NToffbase=9.59×1011 TT_{\mathrm{base}} = 4N_{\mathrm{Toff}}^{\mathrm{base}} = 9.59 \times10^{11}\ T gates per run and Qbase⋅Tbase=5.42×1015Q_{\mathrm{base}}\cdot T_{\mathrm{base}} = 5.42 \times10^{15} per run ( 2.71×10182.71 \times10^{18} over 500 runs), the number presented in Figure 3a. The same study[48] also quotes an eighth-order product-formula estimate (1.40×10151.40 \times10^{15} Toffolis on 6,170 qubits over 500 runs), which we do not use as a baseline since it needs 11.7× more Toffolis than the QSP estimate above.

Main improvements

Section 2.3 summarizes the two changes that account for most of the reduction (Figure 4b,Figure 4c). Here we describe each one alongside the baseline construction it replaces, and Appendix G.4 gives the resulting resource counts.

The baseline applies the electron–proton and electron–electron terms in momentum space, where each pair contributes 22.53 Ha to λ\lambda (Appendix G.2). Our solution instead Fourier transforms all electrons to a real-space grid each step to apply the electron–proton, electron–projectile and electron–electron interactions, while the kinetic and projectile–proton terms stay in momentum space. This basis change alone halves the contribution of each pair to λ\lambda, to 11.3 Ha, but that reduction is canceled out by the extra cost of applying the walk step in real space. However, a further reduction follows by being in the position basis, where the solution can exploit Pauli exclusion. A subroutine checks every electron against each grid point near a given electron or proton, and each electron found there kicks back a phase of ii in one LCU branch and −i-i in the other. Averaging the two branches gives cos⁡(nπ/2)\cos(n\pi/2) for nn electrons on the point, which equals 1−n1-n for n≤2n \le2 and has magnitude at most one for any nn. The Lean solution also proves that states antisymmetric under exchange of same-spin electrons have at most two electrons on any grid point, allowing it to satisfy the specification while not faithfully applying the n>2n > 2 interaction terms. Therefore, the circuit reproduces the interaction up to a constant, while each such term adds its potential to λ\lambda once rather than once for every electron that could occupy the point. At separations beyond ≈0.6 a0\approx0.6\ a_{0}, where the potential is below 1.4 Ha, the interaction is too weak for the savings to outweigh the cost of the subroutine. The pair potential is therefore range-separated at 1.4 Ha, with the subroutine applied only to the short-range part and the long-range part summed over all pairs, each contributing 0.74 Ha (Figure 4b).

The second most significant improvement found, in terms of cost reduction, relates to the electron–proton interaction. Protons do not sit on grid points, so to apply this term the circuit shifts all electrons by −Rℓ-R_{\ell} to put each proton on a grid point, and then shifts them back. In the plane-wave basis this shift is a phase set by the total electron momentum PP. Earlier real-space solutions computed and uncomputed PP around each shift, summing all 218 electron momenta four times per walk step, which made up about a fifth of the TT gates per step. Only the protons and the projectile change PP, and both act in the real-space step, so the final circuit keeps PP in a 42-qubit register between walk steps, clearing it before the real-space step and rebuilding it after. This halves the sums and cuts the TT gates per step by 10% (Figure 4c).

Resource counts

Our solution uses Q=4,374Q = 4{,}374 logical qubits: 3,948 system qubits and 426 clean ancillas, against the baseline’s 1,702. The ancillas are a 42-qubit register that keeps the total electron momentum between walk steps, a 48-qubit phase-gradient register prepared in each run, 87 control and data qubits for the block encoding, and 249 workspace qubits that every subroutine borrows and returns to ∣0⟩\lvert0\rangle. The improvements above lower λ\lambda to 1.356×1051.356 \times10^{5} Ha. Each run of length tt is split into 2t2t segments of 0.5 a.u., each implemented by generalized QSP139,140 of degree 68,053, giving an average of 7.49×1057.49 \times10^{5} walk steps per run.

Each walk step uses roughly 152,000 TT gates: 3,400 for LCU state preparation, 129,000 for the QFTs and the real- and momentum-space Hamiltonian terms, 19,900 for walk reflections and valid-grid guards, and 110 amortized for QSP rotations. One-time initialization adds 59,600 TT gates per run. Averaged over t=1,…,10t = 1, \ldots, 10 a.u., this gives 1.14×10111.14 \times10^{11} TT gates and Q⋅T=4.98×1014Q \cdot\mathcal{T} = 4.98 \times10^{14} per run, or 248,770,927,504,980,000 over all 500 runs. Compared with the baseline, this is 12.8× fewer walk steps and 1.29× fewer qubits at 1.52× the TT gates per step, a 10.9× lower cost (Figure 4a).

Non-Born–Oppenheimer Dynamics of C23_{23}H20_{20}N3_3O

Hamiltonian and specification

Following Reaction 5 in Eqs. (2)–(10) and (23)–(25) and Tables I and IV of ref. 58, the system consists of η=234\eta= 234 particles of composition C23_{23}H20_{20}N3_3O: 47 nuclei (23 12C^{12}\mathrm{C}, 20 1H^{1}\mathrm{H}, 3 14N^{14}\mathrm{N}, and 1 16O^{16}\mathrm{O}, with charges ζi=Zi∈{6,1,7,8}\zeta_i = Z_i \in\{6, 1, 7, 8\}) followed by 187 electrons (ζi=−1\zeta_i = -1). Each Cartesian coordinate is stored as a signed ng=8n_g = 8-bit integer qi,w∈[−128,127]q_{i,w} \in[-128, 127] on Qsys=3ηng=5,616Q_{\mathrm{sys}} = 3\eta n_g = 5{,}616 system qubits, representing position ri,w=qi,wΔr_{i,w} = q_{i,w}\Delta in a cubic box of width L=44L = 44 Å (83.15 a083.15\,a_0) with grid spacing Δ=L/(2ng−1)≈0.326 a0\Delta= L/(2^{n_g} - 1) \approx0.326\,a_0. Electron masses are mi=1m_i = 1, and nuclear masses mim_i (not stated in the baseline[58]) are set in electron-mass units from the 1H^{1}\mathrm{H}, 12C^{12}\mathrm{C}, 14N^{14}\mathrm{N}, and 16O^{16}\mathrm{O} isotopic atomic masses minus ZimeZ_i m_e.

The discretized non-Born–Oppenheimer Hamiltonian is H=T+VH = T + V, with

T=2π2L2∑i=1η1miQFT⁡i†(∑k∈G∥k∥22∣k⟩⟨k∣)QFT⁡i,V=12∑i≠jζiζjΔmax⁡(∥qi−qj∥2,Γ~ij).(14)T = \frac{2\pi^2}{L^2}\sum_{i=1}^{\eta}\frac{1}{m_i}\operatorname{QFT}_i^\dagger\left(\sum_{k\in G}\lVert k\rVert_2^2\lvert k\rangle\langle k\rvert\right)\operatorname{QFT}_i,\qquad V = \frac{1}{2}\sum_{i\ne j}\frac{\zeta_i\zeta_j}{\Delta\max(\lVert q_i-q_j\rVert_2,\widetilde{\Gamma}_{ij})}. \tag*{(14)}

where G=[−128,127]3G = [-128,127]^3, QFT⁡i\operatorname{QFT}_i is the quantum Fourier transform on the three coordinates of particle ii, and the squared Coulomb saturation distance is Γ~ij2=8\widetilde{\Gamma}_{ij}^{2} = 8 when both ii and jj are nuclei (nΓ=3n_{\Gamma} = 3 in tbl:IV of ref. 58) and Γ~ij2=1\widetilde{\Gamma}_{ij}^{2} = 1 otherwise, capping electron interactions at 1/Δ1/\Delta and nuclear repulsion at 1/(8Δ)1/(\sqrt{8}\Delta).

A candidate circuit over Clifford+TT and mid-circuit measurement must realize a single clean-ancilla unitary WW satisfying Eq. (12) at ε=10−2\varepsilon= 10^{-2} for t=1t = 1 fs on every state of the system register. Matching the baseline,[58] initial-state preparation and observable readout are not costed, since in end-to-end fault-tolerant simulations of photochemical dynamics, real-time Hamiltonian evolution dominates initial-state preparation by orders of magnitude.141 All ancillas begin in ∣0⟩⊗m\lvert0\rangle^{\otimes m}, so resource states such as phase-gradient states must be prepared within the circuit. Every Toffoli is compiled into Clifford+TT gates and checked at that gate level by the correctness proof, and where later gates are conditioned on measurement outcomes we count the TT gates of the most expensive branch.

The baseline instead bounds only the block-encoding error ∥A−eiφe−iHt∥op≤ϵBE\lVert A-e^{i\varphi}e^{-iHt}\rVert_{\mathrm{op}}\leq\epsilon_{\mathrm{BE}} (Appendix C of ref. 58), where A=(I⊗⟨0m∣)W(I⊗∣0m⟩)A=(I\otimes\langle0^{m}|)W(I\otimes|0^{m}\rangle) is the part of the circuit that starts and ends with the ancillas in ∣0m⟩|0^{m}\rangle. This leaves out the ancilla error, the part ∣ψ⊥⟩|\psi_{\perp}\rangle of the output in which the ancillas are not returned to ∣0m⟩|0^{m}\rangle. The two parts are orthogonal, so the error in Eq. (12) splits as

∥W(∣ψ⟩⊗∣0m⟩)−eiφ(e−iHt∣ψ⟩)⊗∣0m⟩∥22=∥(A−eiφe−iHt)∣ψ⟩∥22+∥∣ψ⊥⟩∥22,(15)\left\lVert W\left(|\psi\rangle\otimes|0^{m}\rangle\right)-e^{i\varphi}\left(e^{-iHt}|\psi\rangle\right)\otimes|0^{m}\rangle\right\rVert_{2}^{2}=\left\lVert\left(A-e^{i\varphi}e^{-iHt}\right)|\psi\rangle\right\rVert_{2}^{2}+\lVert|\psi_{\perp}\rangle\rVert_{2}^{2}, \tag*{(15)}

and any circuit meeting Eq. (12) at ϵ\epsilon also meets the block-encoding criterion at ϵBE=ϵ\epsilon_{\mathrm{BE}}=\epsilon. For the baseline QSP circuit, the polynomial approximation error bounds the ancilla error[25] [139, 140] by ∥∣ψ⊥⟩∥22≤2ϵexp\lVert|\psi_{\perp}\rangle\rVert_{2}^{2}\leq2\epsilon_{\mathrm{exp}}, so with the error split in Table IV of ref. 58 (ϵexp=ϵBE/12.95\epsilon_{\mathrm{exp}}=\epsilon_{\mathrm{BE}}/12.95) it is only guaranteed to meet Eq. (12) at ϵBE2+2ϵexp≈0.041\sqrt{\epsilon_{\mathrm{BE}}^{2}+2\epsilon_{\mathrm{exp}}}\approx0.041, four times our target.

Baseline

Table I of ref. 58 reports NToffpub=2.73×1011N_{\mathrm{Toff}}^{\mathrm{pub}}=2.73\times10^{11} Toffolis per femtosecond on Qpub=6,198Q_{\mathrm{pub}}=6{,}198 qubits at ϵBE=10−2\epsilon_{\mathrm{BE}}=10^{-2}, a spacetime cost of 6.77×10156.77\times10^{15}. Each walk step uses about 9.0×1049.0\times10^{4} TT gates, of which 52% go to the swap network, 25% to preparing the LCU weights and 22% to evaluating 1/r1/r (Figure 5a of ref. 58). These give the baseline values of 46.8k, 22.5k and 19.8k TT gates per step in § 2.4 and Figure 4e–Figure 4g.

The baseline costs the time evolution as the number of walk steps times the cost of one step, NToff=Dold(τ,ϵexp)⋅THN_{\mathrm{Toff}}=D_{\mathrm{old}}(\tau,\epsilon_{\mathrm{exp}})\cdot\mathcal{T}_{H} (Eqs. (C1) and (C4)–(C5) of ref. 58), where the number of steps is the degree of the generalized QSP polynomial.139,140 Two of the same authors tighten this degree bound, removing the factor e/2≈1.36e/2\approx1.36 in front of τ\tau (Theorem 1 of ref. 59, via Kapteyn’s inequality),

Dold(τ,ϵexp)=⌈e2τ+ln⁡2cϵexp⌉,D_{\mathrm{old}}(\tau,\epsilon_{\mathrm{exp}})=\left\lceil\frac{e}{2}\tau+\ln\frac{2c}{\epsilon_{\mathrm{exp}}}\right\rceil,
dThm 1(τ,ϵexp)=⌈τcosh⁡([3τln⁡2ϵexp(1−e−θ0)]1/3)⌉,(16)d_{\mathrm{Thm\,1}}(\tau,\epsilon_{\mathrm{exp}})=\left\lceil\tau\cosh\left(\left[\frac{3}{\tau}\ln\frac{2}{\epsilon_{\mathrm{exp}}(1-e^{-\theta_{0}})}\right]^{1/3}\right)\right\rceil, \tag*{(16)}

where τ:=αHt\tau:=\alpha_{H}t, c=4(2π e1/13)−1≈1.4776c=4(\sqrt{2\pi}\,e^{1/13})^{-1}\approx1.4776 and θ0=[3τln⁡(2/ϵexp)]1/3\theta_{0}=\left[\frac{3}{\tau}\ln(2/\epsilon_{\mathrm{exp}})\right]^{1/3}. Theorem 2 there further tightens the subleading term via Watson’s inequality. That work[59] does not apply this bound to the system studied here, but it improves the same QSP construction, so we include it so that our solutions are compared against the strongest available baseline.

The tighter bound only reduces the number of walk steps. The error split tϵH+ϵexp≤ϵBEt\epsilon_{H}+\epsilon_{\mathrm{exp}}\leq\epsilon_{\mathrm{BE}} fixes ϵH\epsilon_{H} independently of the polynomial degree, so the TT-gate count TH\mathcal{T}_{H} per step and the qubit count Qpub=6,198Q_{\mathrm{pub}}=6{,}198 are unchanged. At the reported αH=2.16×105\alpha_{H}=2.16\times10^{5} Ha (τ≈8.93×106\tau\approx8.93\times10^{6} at t=41.34t=41.34 a.u.) and ϵexp=ϵBE/12.95\epsilon_{\mathrm{exp}}=\epsilon_{\mathrm{BE}}/12.95, Theorem 2 lowers the number of walk steps from Dold=12,136,779D_{\mathrm{old}}=12{,}136{,}779 to dThm 2=8,930,416d_{\mathrm{Thm\,2}}=8{,}930{,}416 (8,930,8778{,}930{,}877 with Theorem 1). Rescaling the published Toffoli count by this ratio gives our baseline,

NToffbase=NToffpubdThm 2Dold≈2.01×1011,Tbase=4NToffbase≈8.04×1011,Qpub⋅Tbase≈4.98×1015,(17)\begin{aligned} N_{\mathrm{Toff}}^{\mathrm{base}}&=N_{\mathrm{Toff}}^{\mathrm{pub}}\frac{d_{\mathrm{Thm\,2}}}{D_{\mathrm{old}}}\approx2.01\times10^{11},\\ \mathcal{T}_{\mathrm{base}}&=4N_{\mathrm{Toff}}^{\mathrm{base}}\approx8.04\times10^{11},\\ Q_{\mathrm{pub}}\cdot\mathcal{T}_{\mathrm{base}}&\approx4.98\times10^{15}, \tag*{(17)} \end{aligned}

the number presented in Figure 3a. At this large τ\tau the subleading terms barely matter: using Theorem 1 instead, or simply dividing the published Toffoli count by e/2e/2, gives the same cost to three significant figures.

Main improvements

§ 2.4 summarizes three changes to the walk step that account for almost all of the reduction in TT gates per step relative to the baseline (Figure 4e–Figure 4g). Here we describe each one alongside the baseline construction it replaces, and Appendix § 11.4 gives the resulting TT counts.

First, to apply a two-body interaction, the baseline swaps the coordinates of the selected pair into the two particle registers on which its interaction circuit acts, applies the interaction there, and swaps them back afterward.[58] Instead, our solution copies the selected coordinates into an ancilla register, leaving the particle register untouched. Because the ancilla holds only a copy, it can be cleared using mid-circuit Pauli-XX measurements and classically controlled CZCZ corrections,[23] [116] as done for momentum bits copied in plane-wave kinetic terms[27] (Figure 4e).

Second, the potential VV in Eq. (14) requires computing 1/r=(r2)−1/21/r=(r^2)^{-1/2} for r=∥qi−qj∥2r=\lVert q_i-q_j\rVert_2. Because the coordinates are stored as integers, r2=∑w(qi,w−qj,w)2r^2=\sum_w(q_{i,w}-q_{j,w})^2 can be obtained cheaply using integer subtraction and squaring. To get to 1/r1/r without a square root, the baseline prepares an ancilla register in uniform superposition over integers m<Mm<M, assigning +1+1 to branches with m2r2<M2m^2r^2<M^2 and an alternating sign (−1)m(-1)^m to the rest. The alternating terms cancel, so the average over branches approximates 1/r1/r, but the test requires multiplying m2m^2 by r2r^2, which dominates its cost.[58] In this work, the range of r2r^2 is split into coarse intervals with rescaled position r~2∈[0,1)\tilde r^2\in[0,1), and 1/r1/r on each interval is approximated by a cubic Bernstein polynomial ∑k=03(3k)(r~2)k(1−r~2)3−kwk\sum_{k=0}^{3}\binom{3}{k}(\tilde r^2)^k(1-\tilde r^2)^{3-k}w_k (512 precomputed coefficients wkw_k in total). Rather than multiplying powers of r~2\tilde r^2, the circuit samples this polynomial directly.[67] [142] It compares r~2\tilde r^2 against three ancilla registers in uniform superposition and counts how many are smaller, which gives k∈{0,1,2,3}k\in\{0,1,2,3\} with exactly the binomial weights above. Looking up wkw_k then gives the polynomial in expectation (Figure 4f).

Finally, in the electron–nucleus terms of VV, each nucleus ii is weighted by its integer charge ZiZ_i. Rather than preparing these weights via coherent alias sampling[24] with amplitude amplification,[58] a uniform superposition of basis states is prepared and a reversible classical circuit assigns ZiZ_i states to each nucleus ii, as proposed for fixed nuclei[27] and for quantum nuclei.141 Our solution applies this to every weight of the linear combination (Figure 4g).

Resource counts

The verified circuit found in this work uses Q=6,057Q=6{,}057 logical qubits, consisting of 5,616 system qubits and 441 clean ancillas. Evaluating the 1-norm at L=44L=44 Å together with potential shifting gives block-encoding scale α=8.045×104\alpha=8.045\times10^4 Ha and generalized QSP degree d=3,326,871d=3{,}326{,}871.

Each uncontrolled walk step uses 30,504 TT gates (30,516 TT on the two boundary controlled steps): 1,256 TT for reversible nuclear-charge and pair-weight preparation, 24,526 TT to copy selected particle coordinates into ancillas and 908 TT for XX-basis measurement uncomputation (25,434 TT total routing, against 46.8k TT for the baseline swap network), 3,116 TT for the 512-entry Bernstein 1/r1/r evaluation, 446 TT for the QFT kinetic term, and 252 TT for the LCU reflection, plus 76 TT per step for QSP rotations and 247 TT for one-time phase-gradient initialization. This totals T=3,326,871×(30,504+76)+2×30,516+247=101,735,776,459≈1.02×1011T=3{,}326{,}871\times(30{,}504+76)+2\times30{,}516+247=101{,}735{,}776{,}459\approx1.02\times10^{11} TT gates and Q⋅T=616,213,598,012,163≈6.16×1014Q\cdot T=616{,}213{,}598{,}012{,}163\approx6.16\times10^{14} (8.08× below baseline).

Cytochrome P450 Compound I

Hamiltonian and specification

The system is active space X of Compound I, with η=63\eta=63 electrons in N=58N=58 spatial orbitals.[88] Under the Jordan–Wigner transformation each spin orbital (p,σ)(p,\sigma) is stored on qubit 2p+σ2p+\sigma, giving Qsys=2N=116Q_{\mathrm{sys}}=2N=116 system qubits.

GPU-accelerated density matrix renormalization group (DMRG) calculations now converge this 58-orbital active space classically,143 yet leave the physical spin-state ordering unresolved because dynamic correlation from omitted orbitals exceeds the sub-millihartree doublet–quartet gap.[88] [143] Active space X nonetheless serves as the standard benchmark across fault-tolerant resource estimates,[60, 88, 89] and circuit improvements to its DFTHC walk structure[60] carry over to the larger active spaces needed to capture dynamic correlation and resolve the spin ordering.143

The Hamiltonian is the (R,B,C)=(9,29,14)(R, B, C) = (9, 29, 14) double-factorized tensor-hypercontraction (DFTHC) factorization of Table V in ref. [60], with the released tensors144 rounded to (bcoeff,brot)=(10,15)(b_{\mathrm{coeff}}, b_{\mathrm{rot}}) = (10, 15) bits:

HDFTHC=∑σ,p,qhpq′apσ†aqσ+12∑r=0R−1∑c=0C−1(W(rc)I+∑b=0B−1Wb(rc)nbu(r))2(18)H_{\mathrm{DFTHC}} = \sum_{\sigma,p,q} h'_{pq} a^\dagger_{p\sigma}a_{q\sigma} + \frac{1}{2}\sum_{r=0}^{R-1}\sum_{c=0}^{C-1}\left(W^{(rc)}I+\sum_{b=0}^{B-1}W_b^{(rc)}n_b^{u^{(r)}}\right)^2 \tag*{(18)}

where nu=∑σ(∑pupapσ)†(∑quqaqσ)n_u = \sum_{\sigma}\left(\sum_p u_p a_{p\sigma}\right)^\dagger\left(\sum_q u_q a_{q\sigma}\right) for unit orbital vectors ub(r)∈R58u_b^{(r)} \in\mathbb{R}^{58} (M=RB=261M = RB = 261) and W(rc)=wB(rc)−∑b<Bwb(rc)W^{(rc)} = w_B^{(rc)}-\sum_{b<B}w_b^{(rc)}, as follows from expanding OSF,rcO_{\mathrm{SF},rc} in the DFTHC construction.[60] As in the released dataset,144 Eq. (18) omits the scalar −12∑r,c(W(rc))2-\frac{1}{2}\sum_{r,c}(W^{(rc)})^2, and adding the classical Hartree–Fock shift EHF−EHFDFTHCE_{\mathrm{HF}}-E_{\mathrm{HF}}^{\mathrm{DFTHC}} recovers the active-space total energy (Eqs. 42–43 of ref. [60]). We define the problem to not allow for improvement in the DFTHC factors,144 which reproduce the active-space coupled-cluster correlation energy to 0.28 mHa, to separate quantum circuit optimization from classical tensor fitting.

We cost one run of phase estimation on the 116 system qubits, started in a 63-electron eigenstate ∣ψ⟩|\psi\rangle of HDFTHCH_{\mathrm{DFTHC}} with energy EE. Assuming an eigenstate as input loses no generality for resource estimation: phase estimation on any state ∣ϕ⟩|\phi\rangle gives, with probability ∣⟨ψj∣ϕ⟩∣2|\langle\psi_j|\phi\rangle|^2, the same outcomes145 as on the eigenstate ∣ψj⟩|\psi_j\rangle. In practice ∣ϕ⟩|\phi\rangle only approximates the ground state ∣ψ0⟩|\psi_0\rangle, so finding E0E_0 takes on average 1/∣⟨ψ0∣ϕ⟩∣21/|\langle\psi_0|\phi\rangle|^2 runs, each also paying for trial-state preparation.146 Like prior resource estimates,[60, 88, 89] we do not count this overhead. The circuit uses Clifford+TT gates and mid-circuit measurements on the system and mm ancillas that start in ∣0⟩|0\rangle. The specification applies to this gate-level circuit, so its error bound includes rotation synthesis and approximate state preparation as well as phase estimation. At the end, a bb-qubit phase register among the ancillas is measured, and its outcome y∈{0,…,2b−1}y \in\{0,\ldots,2^b-1\} is converted into the energy estimate

E^(y)=Eoff+s∣cos⁡(πy2b)∣,(19)\widehat{E}(y) = E_{\mathrm{off}} + s\left|\cos\left(\frac{\pi y}{2^b}\right)\right|, \tag*{(19)}

where bb, EoffE_{\mathrm{off}} and ss are fixed numbers chosen with the circuit. This form covers both standard qubitization and sum-of-squares spectral amplification. For a walk eigenphase φ\varphi, the energy is E=λcos⁡φE=\lambda\cos\varphi in the first,[24, 25, 89] and E=ESOS+Λ(1+cos⁡φ)E=E_{\mathrm{SOS}}+\Lambda(1+\cos\varphi) in the second.[60] [147] Since cos⁡φ≤0\cos\varphi\le0 at the energies measured here, both read E=Eoff+s∣cos⁡φ∣E=E_{\mathrm{off}}+s|\cos\varphi|, with (Eoff,s)=(0,−λ)(E_{\mathrm{off}},s)=(0,-\lambda) and (ESOS+Λ,−Λ)(E_{\mathrm{SOS}}+\Lambda,-\Lambda) respectively. When phase estimation applies the walk forward or backward depending on the phase register, 2πy/2b2\pi y/2^b estimates ±2φ\pm2\varphi, so Eq. (19) estimates EE.

If the specification only covered the ground state, a circuit with no gates and s=0s=0 would pass by setting EoffE_{\mathrm{off}} within ε\varepsilon of the ground-state energy E0E_0. The specification therefore requires the same circuit and decoder to work for every eigenstate up to Etop=E0+ΔE_{\mathrm{top}}=E_0+\Delta, with Δ=0.1\Delta=0.1 Ha and ε=10−3\varepsilon=10^{-3} Ha. For each 63-electron eigenstate ∣ψ⟩|\psi\rangle with energy EE, the outcome distribution p(y∣ψ)p(y\mid\psi) must satisfy

∑yp(y∣ψ)(min⁡(E^(y),Etop)−min⁡(E,Etop))2≤ε2.(20)\sum_y p(y\mid\psi)\left(\min(\widehat{E}(y),E_{\mathrm{top}})-\min(E,E_{\mathrm{top}})\right)^2 \le\varepsilon^2. \tag*{(20)}

This is the root-mean-square error behind the phase-estimation step counts of Eqs. (21)–(23) in ref. [24]. For an eigenstate inside the window, it bounds the root-mean-square error of the estimate by ε\varepsilon, with estimates above EtopE_{\mathrm{top}} counted as EtopE_{\mathrm{top}}. For an eigenstate above the window, it only requires that estimates do not fall more than ε\varepsilon below EtopE_{\mathrm{top}}. A circuit that ignores ∣ψ⟩|\psi\rangle gives the same estimates for every eigenstate, and in root mean square these would have to lie within ε\varepsilon of E0E_0 and at most ε\varepsilon below E0+ΔE_0+\Delta at once. This is possible only if Δ≤2ε=2\Delta\le2\varepsilon= 2 mHa, far below Δ=0.1\Delta= 0.1 Ha. The window also spans the gap of about 75 mHa between the quartet and sextet states found by DMRG (Figure 4 of ref. 143). The tolerance ε=1\varepsilon= 1 mHa matches prior resource estimates on this active space, although separating the doublet and quartet states would require tighter tolerances.

All ancillas begin in ∣0⟩⊗m\lvert0\rangle^{\otimes m}, so resource states such as phase-gradient states must be prepared within the circuit.

Every Toffoli is compiled into Clifford+TT gates and checked at that gate level by the correctness proof, and where later gates are conditioned on measurement outcomes we count the TT gates of the most expensive branch.

Baseline

Our baseline starts from the sum-of-squares spectral amplification estimate in Table V of ref. [60] (51,510 walk steps at 9,535 Toffolis/step on 1,150 qubits, or a spacetime cost of 2.26×10122.26 \times10^{12}), where HDFTHC−ESOS=Hsqrt†HsqrtH_{\mathrm{DFTHC}} - E_{\mathrm{SOS}} = H_{\mathrm{sqrt}}^{\dagger} H_{\mathrm{sqrt}} is block-encoded with norm Λ\Lambda and energy-window gap Egap=Eub+Δ−ESOSE_{\mathrm{gap}} = E_{\mathrm{ub}} + \Delta- E_{\mathrm{SOS}} using the phase-estimation step count[24, 60]

λeff=Egap(2Λ−Egap),Nsteps=⌈πλeff2ε⌉.(21)\lambda_{\mathrm{eff}} = \sqrt{E_{\mathrm{gap}}(2\Lambda-E_{\mathrm{gap}})}, \qquad N_{\mathrm{steps}} = \left\lceil\frac{\pi\lambda_{\mathrm{eff}}}{2\varepsilon}\right\rceil. \tag*{(21)}

Adding Δ\Delta to EgapE_{\mathrm{gap}} in that estimate[60] raises its step count from 51,510 to 51,948 and its cost to 2.28×10122.28 \times10^{12} (+0.85%). The published construction[60] forms the one-body term h′h' from the exact two-electron tensor gg, while the squares in Eq. (18) use the factorized tensor g~\tilde{g}. The Hamiltonian it block-encodes therefore differs from the (h,g~)(h,\tilde{g}) Hamiltonian by a one-body term that lowers the low-lying energies by about 0.6 Ha. Its EgapE_{\mathrm{gap}} subtracts the sum-of-squares bound of the block-encoded Hamiltonian from the sextet Hartree–Fock energy of the (h,g~)(h,\tilde{g}) Hamiltonian,144 so it is about 0.6 Ha larger than when both energies come from one Hamiltonian, which overestimates the cost. We form h′h' from g~\tilde{g}, so that Eq. (18) is the (h,g~)(h,\tilde{g}) Hamiltonian up to a constant, whose CCSD(T) correlation energy is within 0.28 mHa of that of (h,g)(h,g). This lowers Λ\Lambda from 97.4395 to 97.3864 Ha (ESOS=−134.8874E_{\mathrm{SOS}} = -134.8874 Ha), and with both energies evaluated on this Hamiltonian Egap=5.189E_{\mathrm{gap}} = 5.189 Ha including Δ\Delta (49,269 steps). Bounding E0≤Eub=−129.8443E_0 \leq E_{\mathrm{ub}} = -129.8443 Ha with the quartet (S=3/2S = 3/2) ROHF determinant instead lowers EgapE_{\mathrm{gap}} to 5.143 Ha, giving λeff=31.23\lambda_{\mathrm{eff}} = 31.23 Ha and Nsteps=49,056N_{\mathrm{steps}} = 49,056.

Adding a coherent 16-qubit phase-estimation register and storing each of the 57 Givens angles in 13 rather than 15 bits gives 1,052 qubits and a cost of 1.97×10121.97 \times10^{12} before space–time tradeoffs. Thirteen bits suffice because the angles θp=2πkp/215\theta_p = 2\pi k_p/2^{15} enter the orbital vectors[4] as cos⁡2θp\cos2\theta_p and sin⁡2θp\sin2\theta_p, and the overall sign of each vector does not affect nun_u, so fixing that sign puts every angle index of HDFTHCH_{\mathrm{DFTHC}} in 0≤kp<2130 \leq k_p < 2^{13}. As suggested in prior work,[89] we use both these observations and integrate them into our baseline. We then apply recent compilation options,[61] recomputing the (G,r,c,σ,b=B)(G,r,c,\sigma,b=B) index registers from an 8-bit outer index xox_o with minimum-Toffoli comparators108 and loading the 57 Givens angles in three batches of 19 (5 QROM lookups per SELECT) while reusing idle angle wires as clean-QROM116 workspace. These options come from later work than the spectral-amplification study,[60] but we include them so that our solutions are compared against the strongest available baseline. On our 13-bit instance we also pad CC rather than RR in xox_o, skip the two always-zero addend bits in the 15-bit phase-gradient adders,[23] and include 32 Toffolis/step to control the walk reflections from the phase-estimation register, omitting approximate state preparation and rotation synthesis so HDFTHCH_{\mathrm{DFTHC}} remains exact. Minimizing Q⋅TQ \cdot\mathcal{T} over QROM block sizes and angle batch sizes gives Qbase=481Q_{\mathrm{base}} = 481 logical qubits and CBE=11,517C_{\mathrm{BE}} = 11,517 Toffolis/step (5.65 × 10810^8 Toffolis, Tbase=4CBENsteps=2.26×109\mathcal{T}_{\mathrm{base}} = 4C_{\mathrm{BE}}N_{\mathrm{steps}} = 2.26 \times10^9 TT gates), for a baseline cost of

Qbase⋅Tbase=1.087×1012≈1.09×1012,(22)Q_{\mathrm{base}} \cdot\mathcal{T}_{\mathrm{base}} = 1.087 \times10^{12} \approx1.09 \times10^{12}, \tag*{(22)}

the number presented in Figure 3a. At a fixed number of walk steps, the 13-bit angles and these compilation options[61] together roughly halve the published cost,[60] from 1,150 qubits and 9,535 Toffolis per step to 481 qubits and 11,517, including the phase-estimation register. Figure 3b shows the published estimate,[60] extended to the energy window, in gray and this baseline in red.

Main improvements

Section 2.5 summarizes the main change in our solution, which replaces the angle lookups of the baseline with a one-hot register for the chosen orbital vector, and uses the same trick in the inner state preparation. Here we describe both alongside the baseline construction they replace, together with a smaller change to the spin swaps that the main text leaves out. Appendix I.4 gives the resulting TT counts.

Each walk step block-encodes Eq. (18) with a state preparation and two SELECT calls.[60] The outer stage of the state preparation picks a square (r,c)(r,c) or a one-body term, and the inner stage picks bb, which fixes the orbital vector ub(r)u_{b}^{(r)}. SELECT rotates this vector into a single orbital with 57 Givens rotations, acts on that orbital and rotates back.[4]

In the baseline, each SELECT call loads the 13-bit Givens angles of the chosen vector into a 247-qubit register, 19 at a time with 5 QROM lookups per call, and each rotation adds its angle into the phase-gradient register (Appendix I.2). Our solution instead builds a 145-qubit one-hot register in each SELECT call, for 296 TT. Each of its qubits stands for two orbital vectors, so the register covers 290 of them: the 261 vectors ub(r)u_{b}^{(r)} and 29 of the 58 eigenvectors of h′h'. The other 29 eigenvectors are handled by the second call of the step. A further qubit ss records which vector of the pair was chosen. Each angle bit then enters the phase-gradient adder of its rotation as

(α⊕M1)(β⊕M0)⊕M01,β=qcs,α=qc⊕β,(23)(\alpha\oplus M_{1})(\beta\oplus M_{0}) \oplus M_{01}, \qquad\beta= q_{c}s,\quad\alpha= q_{c} \oplus\beta, \tag*{(23)}

where qcq_{c} is the control qubit of the rotation and M0M_{0}, M1M_{1} and M01M_{01} are CNOT parities of the one-hot qubits whose first vector, second vector or both vectors have that bit set. At most one one-hot qubit is set, so M0M1=M01M_{0}M_{1}=M_{01}, and Eq. (23) is 0 for qc=0q_{c}=0 and the bit of the chosen vector for qc=1q_{c}=1. The baseline already uses one AND gate per angle bit to control the rotation. Eq. (23) also needs one AND gate per bit, plus one per rotation for β\beta. With the one-hot register, the rotations and their angles cost 11,818 TT per call rather than 18,844 TT, and the angle register is no longer needed.

The inner stage uses the same idea. It keeps a 126-qubit one-hot register for (r,c)(r,c) and a 5-bit binary register for bb, so each alias-sampling lookup[24] costs 390 TT, against 1,968 TT for the QROAM of the baseline. Together with the one-hot SELECT, this accounts for 96% of the TT gates saved per walk step (Table S3).

Our solution also includes a second, smaller improvement, which halves the cost of the spin swaps. Rather than performing the basis rotations once for each spin, the baseline applies them to the spin-up qubits only and, controlled by a qubit in superposition, swaps the spin-down qubits into their place before and back after, with four blocks of 58 controlled swaps per step.[60] Since swapping two qubits only flips the sign of their antisymmetric state (∣01⟩−∣10⟩)/2(\lvert01\rangle-\lvert10\rangle)/\sqrt{2}, each block can instead be implemented as a single controlled sign flip, applied when an odd number of the 58 orbitals are in that state. After a Clifford change of basis to Bell pairs, the circuit computes this parity with 58 Toffolis, or 232 TT, as many as one block of swaps, and erases it with XX-basis measurements for free. Since the system register is untouched between consecutive SELECT calls, one parity serves two swap blocks.

Resource counts

The best verified circuit uses Q=333Q=333 logical qubits and T=1,310,839,337≈1.31×109\mathcal{T}=1{,}310{,}839{,}337 \approx1.31 \times10^{9} TT gates, so Q⋅T=436,509,499,221≈4.37×1011Q\cdot\mathcal{T}=436{,}509{,}499{,}221 \approx4.37 \times10^{11}, 2.49× below the baseline (Figure 3a,Figure 3b). This comes from 1.67× fewer TT gates per walk step (Appendix I.3), 1.44× fewer qubits and 3% fewer walk steps. The qubits are the 116 system qubits, a 16-qubit phase-estimation register, an 11-qubit phase-gradient register, 17 and 24 qubits for the outer and inner state-preparation registers, and 149 qubits of workspace shared by the subroutines. Most of the saving against the 481 qubits of the baseline comes from dropping its 247-qubit angle register.

Part of a walk stepBaselineThis work
Rotations and their angles37,68823,636
Index decoding264440
Spin swaps928464
Outer state preparation1,032598
Inner state preparation5,8882,264
Total45,80027,402

caption: tbl:S3: TT gates per walk step for the baseline and for a step inside the first eight blocks (45,440 steps) of the best verified circuit. Reflections and phase-estimation control are counted separately in the text.

:::

The circuit runs M=47,487M = 47,487 walk steps. We bound E0≤Eub=−130.1526E_0 \le E_{\mathrm{ub}} = -130.1526 Ha with a 3,000-determinant quartet wavefunction, whose energy is checked in Lean. This is 0.31 Ha below the quartet ROHF bound of the baseline and gives Egap=4.835E_{\mathrm{gap}} = 4.835 Ha and λeff=30.30\lambda_{\mathrm{eff}} = 30.30 Ha, 3% below the 31.23 Ha of the baseline. A slightly tighter error bound for phase estimation than Eq. (21) saves another 0.2%. The state preparation is approximate, so the block-encoded Hamiltonian differs from HDFTHCH_{\mathrm{DFTHC}} by at most 4.0×10−74.0 \times10^{-7} Ha on the 63-electron sector. This comes from the synthesized rotations in the state preparation, and the correctness proof adds it to the phase-estimation error to show that the total stays within ε\varepsilon.

The walk steps run in 16 blocks totaling 47,360 steps, followed by 127 single steps. As qubits of the phase-estimation register are prepared stage by stage, fewer remain free as extra workspace for SELECT: 8 blocks (45,440 steps in total) borrow 11 unprepared qubits for 160 workspace qubits at the 27,402 TT per step of Table S3, 1 block of 1,024 steps borrows 10 qubits (28,298 TT per step), and 7 blocks of 128 steps borrow 7 qubits (31,010 TT per step). On top of Table S3, the baseline spends 268 TT per step on reflections and phase-estimation control, for 46,068 TT in total. Each of our blocks uses 84 TT for each reflection between its steps and 232 TT for an ordinary first swap block. The 127 single steps cost 37,642 TT each (including 418 TT per inner lookup), because all phase-estimation qubits are then in use and SELECT has to fit in 149 qubits of workspace. The reflections between blocks and between single steps, together with phase-estimation control, take 13,316 TT, with 31 reflections controlled by the phase-estimation register. Preparing the initial state of the phase-estimation register takes 142,248 TT, the inverse QFT 12,603 TT and the phase-gradient state 1,036 TT. Adding these up gives the T=1,310,839,337\mathcal{T} = 1,310,839,337 quoted above.

Appendix References

  1. Beverland, M. E. et al. Assessing requirements to scale to practical quantum advantage 2022. arXiv: 2211.07629 [quant-ph].

  1. Preskill, J. Beyond NISQ: The Megaquop Machine. ACM Transactions on Quantum Computing 6, 1–7. arXiv: 2502.17368 [quant-ph] (2025).

  1. Reiher, M., Wiebe, N., Svore, K. M., Wecker, D. & Troyer, M. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences 114, 7555–7560 (2017).

  1. Lee, J. et al. Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction. PRX Quantum 2, 030305 (2021).

  1. Babbush, R. et al. Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations. PRX Quantum 7, 030101. arXiv: 2603.28846 [quant-ph] (2026).

  1. Grover, L. K. A fast quantum mechanical algorithm for database search in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (1996), 212–219.

  1. Häner, T., Roetteler, M. & Svore, K. M. Optimizing Quantum Circuits for Arithmetic 2018. arXiv: 1805.12445 [quant-ph].

References

  1. [1]Beverland, M. E. et al. Assessing requirements to scale to practical quantum advantage 2022. arXiv: 2211.07629 [quant-ph].arxiv.org/abs/2211.07629
  2. [2]Preskill, J. Beyond NISQ: The Megaquop Machine. ACM Transactions on Quantum Computing 6, 1–7. arXiv: 2502.17368 [quant-ph] (2025).DOI
  3. [3]Reiher, M., Wiebe, N., Svore, K. M., Wecker, D. & Troyer, M. Elucidating reaction mechanisms on quantum computers. Proceedings of the National Academy of Sciences 114, 7555–7560 (2017).
  4. [4]Lee, J. et al. Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction. PRX Quantum 2, 030305 (2021).DOI
  5. [5]Novikov, A. et al. AlphaEvolve: A coding agent for scientific and algorithmic discovery 2025. arXiv: 2506.13131 [cs.AI].arxiv.org/abs/2506.13131
  6. [6]Hubert, T. et al. Olympiad-level formal mathematical reasoning with reinforcement learning. Nature 651, 607–613 (2026).DOI
  7. [7]Babbush, R. et al. Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations. PRX Quantum 7, 031001. arXiv: 2603.28846 [quant-ph] (2026).arxiv.org/abs/2603.28846
  8. [8]Crichigno, M. & Flammia, S. Automating quantum circuit optimization with AI agents Oct. 2026. arXiv: 2610.31352 [quant-ph].arxiv.org/abs/2610.31352
  9. [9]Grover, L. K. A fast quantum mechanical algorithm for database search in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (1996), 212–219.arxiv.org/abs/quant-ph/9605043
  10. [10]Häner, T., Roetteler, M. & Svore, K. M. Optimizing Quantum Circuits for Arithmetic 2018. arXiv: 1805.12445 [quant-ph].arxiv.org/abs/1805.12445
  11. [11]Shor, P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing 26, 1484–1509 (1997).
  12. [12]Jordan, S. P. et al. Optimization by decoded quantum interferometry. Nature 646, 831–836 (2025).
  13. [13]Aspuru-Guzik, A., Dutoi, A. D., Love, P. J. & Head-Gordon, M. Simulated Quantum Computation of Molecular Energies. Science 309, 1704–1707 (2005).
  14. [14]Kassal, I., Jordan, S. P., Love, P. J., Mohseni, M. & Aspuru-Guzik, A. Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proceedings of the National Academy of Sciences 105, 18681–18686 (2008).DOI
  15. [15]Santagati, R. et al. Drug design on quantum computers. Nature Physics 20, 549–557 (2024).DOI
  16. [16]Bauer, B., Bravyi, S., Motta, M. & Chan, G. K.-L. Quantum Algorithms for Quantum Chemistry and Quantum Materials Science. Chemical Reviews 120, 12685–12717 (2020).DOI
  17. [17]Delgado, A. et al. Simulating key properties of lithium-ion batteries with a fault-tolerant quantum computer. Physical Review A 106, 032428 (2022).DOI
  18. [18]Jordan, S. P., Lee, K. S. M. & Preskill, J. Quantum Algorithms for Quantum Field Theories. Science 336, 1130–1133 (2012).DOI
  19. [19]Bauer, C. W. et al. Quantum Simulation for High-Energy Physics. PRX Quantum 4, 027001 (2023).DOI
  20. [20]Joseph, I. et al. Quantum computing for fusion energy science applications. Physics of Plasmas 30, 010501 (2023).DOI
  21. [21]Dalzell, A. M. et al. Quantum Algorithms: A Survey of Applications and End-to-end Complexities arXiv: 2310.03011 [quant-ph] (Cambridge University Press, 2025).DOI
  22. [22]Acharya, R. et al. Quantum error correction below the surface code threshold. Nature 638, 920–926 (2025).DOI
  23. [23]Gidney, C. Halving the cost of quantum addition. Quantum 2, 74 (2018).DOI
  24. [24]Babbush, R. et al. Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity. Physical Review X 8, 041015 (2018).DOI
  25. [25]Low, G. H. & Chuang, I. L. Hamiltonian Simulation by Qubitization. Quantum 3, 163 (2019).
  26. [26]Gilyén, A., Su, Y., Low, G. H. & Wiebe, N. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019), 193–204.DOI
  27. [27]Su, Y., Berry, D. W., Wiebe, N., Rubin, N. & Babbush, R. Fault-Tolerant Quantum Simulations of Chemistry in First Quantization. PRX Quantum 2, 040332 (2021).DOI
  28. [28]Fösel, T., Tighineanu, P., Weiss, T. & Marquardt, F. Reinforcement Learning with Neural Networks for Quantum Feedback. Physical Review X 8, 031084. arXiv: 1802.05267 [quant-ph] (2018).DOI
  29. [29]Sivak, V. V. et al. Real-time quantum error correction beyond break-even. Nature 616, 50–55. arXiv: 2211.09116 [quant-ph] (2023).DOI
  30. [30]Krenn, M., Landgraf, J., Foesel, T. & Marquardt, F. Artificial intelligence and machine learning for quantum technologies. Physical Review A 107, 010101. arXiv: 2208.03836 [quant-ph] (2023).DOI
  31. [31]Bausch, J. et al. Learning high-accuracy error decoding for quantum processors. Nature 635, 834–840 (2024).DOI
  32. [32]Ruiz, F. J. R. et al. Quantum circuit optimization with AlphaTensor. Nature Machine Intelligence 7, 374–385. arXiv: 2402.14396 [quant-ph] (2025).arxiv.org/abs/2402.14396
  33. [33]Fawzi, A. et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature 610, 47–53 (2022).DOI
  34. [34]Mankowitz, D. J. et al. Faster sorting algorithms discovered using deep reinforcement learning. Nature 618, 257–263 (2023).DOI
  35. [35]Romera-Paredes, B. et al. Mathematical discoveries from program search with large language models. Nature 625, 468–475 (2024).
  36. [36]Lange, R. T., Imaizuku, Y. & Cetin, E. ShinkaEvolve: Towards Open-Ended And Sample-Efficient Program Evolution in International Conference on Learning Representations (ICLR) (2026). arXiv: 2509.19349 [cs.CL].arxiv.org/abs/2509.19349
  37. [37]Alman, J. & Vassilevska Williams, V. Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs 2026. arXiv: 2610.06783 [cs.DS].arxiv.org/abs/2610.06783
  38. [38]OpenAI. The Exponential Time Hypothesis is False https://github.com/openai/math/tree/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026. Preprint, dated October 25, 2026; AI-generated, not peer-reviewed. Oct. 2026.
  39. [39]Anthropic & Claude. A 2ᵒ⁽ⁿ⁾ Time Algorithm for 3-SAT https://github.com/anthropics/formal-math/tree/main/exp. Paper and Lean 4 formalization (Lean v4.33.1, Mathlib v4.33.1); AI-generated, not peer-reviewed. Oct. 2026.
  40. [40]Achim, T. et al. Aristotle: IMO-level Automated Theorem Proving 2025. arXiv: 2510.01346 [cs.AI].arxiv.org/abs/2510.01346
  41. [41]De Moura, L. & Ullrich, S. The Lean 4 Theorem Prover and Programming Language in Automated Deduction – CADE 28 12699 (Springer, 2021), 625–635.DOI
  42. [42]Feng, Y. & Ying, M. Quantum Hoare Logic with Classical Variables. ACM Transactions on Quantum Computing 2, 1–43 (2021).DOI
  43. [43]Litinski, D. A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery. Quantum 3, 128 (2019).
  44. [44]We will shortly open source our Lean 4 library, problem specifications and verified solutions.
  45. [45]The mathlib Community. The Lean mathematical library in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (2020), 367–381.DOI
  46. [46]The Physlib Community. Physlib: The Lean Physics Library https://github.com/leanprover-community/physlib. 2024.
  47. [47]Meiburg, A. Quantum Information in Lean https://github.com/Timeroot/Lean-QuantumInfo. 2024.
  48. [48]Rubin, N. C. et al. Quantum computation of stopping power for inertial fusion target design. Proceedings of the National Academy of Sciences 121, e2317772121 (2024).
  49. [49]Swanson, K., Wu, W., Bulaong, N. L., Pak, J. E. & Zou, J. The Virtual Lab of AI agents designs new SARS-CoV-2 nanobodies. Nature 646, 716–723 (2025).DOI
  50. [50]Gottweis, J., Weng, W.-H., Daryin, A., et al. Accelerating scientific discovery with Co-Scientist. Nature 655, 487–496 (2026).DOI
  51. [51]Lu, C. et al. Towards end-to-end automation of AI research. Nature 651, 914–919 (2026).arxiv.org/abs/2606.15497
  52. [52]Ghareeb, A. E. et al. A multi-agent system for automating scientific discovery. Nature 655, 497–505 (2026).
  53. [53]Yuksekgonul, M. et al. Learning to Discover at Test Time in Proceedings of the 43rd International Conference on Machine Learning (ICML) (2026). arXiv: 2601.16175 [cs.LG].
  54. [54]Tsoukalas, G. et al. Advancing mathematics research with AI-driven formal proof of search. Science 394, 234–239. arXiv: 2605.22763 (2026).arxiv.org/abs/2605.22763
  55. [55]Qu, A. et al. CORAL: Towards Autonomous Multi-Agent Evolution for Open-Ended Discoveries in Proceedings of the Conference on Language Modeling (COLM) (2026). arXiv: 2604.01658 [cs.AI].arxiv.org/abs/2604.01658
  56. [56]Zhong, Z., Raghunathan, A. & Carlini, N. ImpossibleBench: Measuring LLMs’ Propensity of Exploiting Test Cases 2025. arXiv: 2510.20270.arxiv.org/abs/2510.20270
  57. [57]Lean FRO. comparator: A trustworthy judge for Lean proofs from untrusted sources https://github.com/leanprover/comparator. Accessed Nov. 2026. 2025.
  58. [58]Porcnic, M., Loaiza, I., Arrazola, J. M., Wiebe, N. & Motlagh, D. Efficient Simulation of Pre-Born-Oppenheimer Dynamics on a Quantum Computer 2026. arXiv: 2602.11272 [quant-ph].
  59. [59]Porcnic, M. & Motlagh, D. Improved constant factors for qubitized Hamiltonian simulation 2026. arXiv: 2608.02734 [quant-ph].
  60. [60]Low, G. H. et al. Fast Quantum Simulation of Electronic Structure by Spectral Amplification. Physical Review X 15, 041016 (2025).DOI
  61. [61]Low, G. H. et al. A denser planar surface code 2026. arXiv: 2605.30455 [quant-ph].arxiv.org/abs/2605.30455
  62. [62]Boyer, M., Brassard, G., Høyer, P. & Tapp, A. Tight Bounds on Quantum Searching. Fortschritte der Physik 46, 493–505 (1998).
  63. [63]Zalka, C. Grover’s quantum searching algorithm is optimal. Physical Review A 60, 2746–2751 (1999).DOI
  64. [64]Gingrich, R. M., Williams, C. P. & Cerf, N. J. Generalized quantum search with parallelism. Physical Review A 61, 052313 (2000).DOI
  65. [65]Grover, L. K. & Radhakrishnan, J. Quantum search for multiple items using parallel queries 2004. arXiv: quant-ph/0407217.DOI
  66. [66]Fang, W. & Heunen, C. Weakly Measured Loops for Quantum Amplitude Amplification: Oracle Savings and Adaptive Search with Unknown Target Probability 2026. arXiv: 2609.39621 [quant-ph].arxiv.org/abs/2609.39621
  67. [67]Goyal, V. & Sigman, K. On simulating a class of Bernstein polynomials. ACM Transactions on Modeling and Computer Simulation 22, 1–5 (2012).DOI
  68. [68]Hentschel, T. W. et al. Improving dynamic collision frequencies: Impacts on dynamic structure factors and stopping powers in warm dense matter. Physics of Plasmas 30, 062703 (2023).DOI
  69. [69]Hurricane, O. A. et al. Physics principles of inertial confinement fusion and U.S. program overview. Reviews of Modern Physics 95, 025005 (2023).DOI
  70. [70]Grabowski, P. E., Surh, M. P., Richards, D. F., Graziani, F. R. & Murillo, M. S. Molecular Dynamics Simulations of Classical Stopping Power. Physical Review Letters 111, 215002 (2013).pubmed.ncbi.nlm.nih.gov/24313494
  71. [71]Correa, A. A. Calculating electronic stopping power in materials from first principles. Computational Materials Science 150, 291–303 (2018).DOI
  72. [72]Ding, Y. H., White, A. J., Hu, S. X., Certik, O. & Collins, L. A. Ab Initio Studies on the Stopping Power of Warm Dense Matter with Time-Dependent Orbital-Free Density Functional Theory. Physical Review Letters 121, 145001 (2018).DOI
  73. [73]Grabowski, P. E. et al. Review of the first charged-particle transport coefficient comparison workshop. High Energy Density Physics 37, 100905 (2020).DOI
  74. [74]Scholes, G. D., Fleming, G. R., Olaya-Castro, A. & van Grondelle, R. Lessons from nature about solar light harvesting. Nature Chemistry 3, 763–774 (2011).DOI
  75. [75]Lennox, J. C., Kurtz, D. A., Huang, T. & Dempsey, J. L. Excited-State Proton-Coupled Electron Transfer: Different Avenues for Promoting Proton/Electron Movement with Solar Photons. ACS Energy Letters 2, 1246–1256 (2017).DOI
  76. [76]Gentry, E. C. & Knowles, R. R. Synthetic Applications of Proton-Coupled Electron Transfer. Accounts of Chemical Research 49, 1546–1556 (2016).DOI
  77. [77]Polli, D. et al. Clinical intersection dynamics of the primary photoisomerization event in vision. Nature 467, 440–443 (2010).DOI
  78. [78]Worth, G. A. & Cederbaum, L. S. Beyond Born–Oppenheimer: Molecular Dynamics Through a Conical Intersection. Annual Review of Physical Chemistry 55, 127–158 (2004).pubmed.ncbi.nlm.nih.gov/15117250
  79. [79]Mai, S. & González, L. Molecular Photochemistry: Recent Developments in Theory. Angewandte Chemie International Edition 59, 16832–16846 (2020).DOI
  80. [80]Hammes-Schiffer, S. & Stuchebrukhov, A. A. Theory of Coupled Electron and Proton Transfer Reactions. Chemical Reviews 110, 6939–6960 (2010).
  81. [81]Subotnik, J. E. et al. Understanding the Surface Hopping View of Electronic Transitions and Decoherence. Annual Review of Physical Chemistry 67, 387–417 (2016).DOI
  82. [82]Crespo-Otero, R. & Barbatti, M. Recent Advances and Perspectives on Nonadiabatic Mixed Quantum–Classical Dynamics. Chemical Reviews 118, 7026–7068 (2018).
  83. [83]Ren, G., Meng, Q., Zhao, J. & Chu, T. Molecular Design for Electron-Driven Double-Proton Transfer: A New Scenario for Excited-State Proton-Coupled Electron Transfer. The Journal of Physical Chemistry A 122, 9191–9198 (2018).DOI
  84. [84]Denisov, I. G., Makris, T. M., Sligar, S. G. & Schlichting, I. Structure and Chemistry of Cytochrome P450. Chemical Reviews 105, 2253–2278 (2005).
  85. [85]Guengerich, F. P. Cytochrome P450 and Chemical Toxicology. Chemical Research in Toxicology 21, 70–83 (2008).pubmed.ncbi.nlm.nih.gov/18052394
  86. [86]Rittle, J. & Green, M. T. Cytochrome P450 Compound I: Capture, Characterization, and C–H Bond Activation Kinetics. Science 330, 933–937 (2010).DOI
  87. [87]Shaik, S. et al. P450 Enzymes: Their Structure, Reactivity, and Selectivity—Modeled by QM/MM Calculations. Chemical Reviews 110, 949–1017 (2010).
  88. [88]Goings, J. J. et al. Reliably assessing the electronic structure of cytochrome P450 on today’s classical computers and tomorrow’s quantum computers. Proceedings of the National Academy of Sciences 119, e2203533119 (2022).DOI
  89. [89]Caesura, A. et al. Faster Quantum Chemistry Simulations on a Quantum Computer with Improved Tensor Factorization and Active Volume Compilation. PRX Quantum 6, 030337 (2025).DOI
  90. [90]Gidney, C. How to factor 2048 bit RSA integers with less than a million noisy qubits 2025. arXiv: 2505.15917 [quant-ph].arxiv.org/abs/2505.15917

Paper details

vlnc:W_6pa2eb83
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 17

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents