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 large language model 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 1.4x), 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 to 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.

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 , the number of qubits times the number of 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 for arcsin (combining classical and formal search), and by up to 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.

Figure 3. Summary of verified results. a) Quantum algorithm cost for baselines and solutions from this work across application domains. b) Logical-qubit and -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}†) {citep}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 , raising its cost by 0.85%. c) Cost for 25-bit fixed-point arcsin () against piecewise-polynomial evaluation.[10] d) Speedup in expected number of rounds for large of our verified parallel Grover circuits over the strongest published baseline[62, 63, 64, 65, 66] for powers of two , when finding any one or all of marked targets with parallel queries per round (dashed contours: 1.00× boundary; * markers: peak speedups of 1.22× and 1.41×).
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 -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.

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 . 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 on the system and ancilla qubits (extra qubits used to aid computation) must simulate time evolution for every physically allowed electron state, up to a specified error, and return the ancillas to . (3) The compiled program must act as on grid states whenever the ancillas start in . (4) The cost is a function of the logical spacetime volume multiplied by the repeated runs of the stopping power routine: 50 repeats 10 time steps (§ 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 § 7).
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.
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 § 6). 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 marked items in a list of 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 parallel queries per round on a shared quantum register (rather than independent, uncoupled devices), [9, 63] we require algorithms to succeed with certainty and score them by their expected oracle rounds for large , evaluated at powers of two up to 1,024 for both and (Figure 3d). We compare against the strongest published protocol in each regime, [62, 63, 64, 65, 66] including Zalka’s partition combined with weakly measured search at , evaluated under the same metric (Appendix § 9).
Our Lean-verified circuits match this baseline on the and boundaries and outperform it across all multi-target parallel settings (; 100/121 grid points) for finding a single element, reducing expected rounds by up to 1.22×, and in all 110/121 multi-target settings () for finding all elements, by up to 1.41×. Part of our gain stems from combining published ideas via classical control, such as pairing domain partitioning or parallel restarts with weak measurements (which result in only partial collapse of quantum coherence but also only gives partial success information). Beyond that, we also identify novel mechanisms inside search stages. For instance, in one find-all algorithm we discovered, each parallel query stream couples a pair of workspace registers to advance two finds at once, and combines weak measurements with zero-query un-marking, preserving unmeasured coherence across stages.
Table 3a. Summary of results using absolute cost.
Fixed-Point arcsin
Computing the function 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 is represented by 25-classical bits, and the output must be accurate to an error across the domain . For this setting, the best-known published baseline implementation is a piecewise-polynomial construction,[10] which requires a spacetime cost exceeding for an error of .
Unlike the other examples in this work, 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 ( 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,698 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 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 particle passing through it. No classical method for these dynamics is both efficient and systematically improvable.[48, 70, 71, 72, 73]
We consider an particle and 218 electrons moving among 216 fixed protons. A candidate circuit must simulate the time evolution of the system with error 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 per run, averaged over the 500 runs (Appendix § 11). This builds from a sequence of walk steps, each encoding , where is the sum of the absolute weights when is written as a linear combination of unitaries (LCU). The number of walk steps[25] scales as .
Running our discovery workflow, we find a solution with 4,374 logical qubits and lower spacetime cost (Figure 4a). To understand the main improvement, we note that over 90% of the baseline’s comes from electron–proton and electron–electron interactions, and that 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 in one LCU branch and 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 . In the final circuit, this cuts the walk steps by , at the gates per step.

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 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 , 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, is calculated cheaply and rescaled within each interval to . Through random sampling, one of four classically precomputed coefficients is chosen, with probabilities set by (dot area). In expectation, this gives as a Bernstein polynomial,[67] as shown for one value of (shaded). g) Each nucleus has integer charge . In the electron–nucleus attraction, rather than preparing these weights via alias sampling,[24] a uniform superposition is created and reversible logic assigns of them to each nucleus. Applying a unit-charge interaction on every branch then gives each nucleus its full charge .
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 gates per step by 10% (Figure 4c). More details are given in Appendix § 11.
Non-Born–Oppenheimer Dynamics of
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 , 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 for fs, to within error , for every initial state.
Improving the published estimate[58] by the authors’ subsequent work[59] gives a baseline cost of (Appendix § 12). In this work we find a solution that costs only , a reduction of (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 with a multiplication step,[58] we obtain in expectation from a piecewise Bernstein polynomial in ,[67] using only comparisons and a table lookup (Figure 4f). Finally, a nucleus of charge attracts an electron just as unit charges at the same point would. The solution exploits this by creating an equal superposition and assigning 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 § 12.
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 ) with the fixed double-factorized tensor-hypercontraction (DFTHC) Hamiltonian.[60] For every eigenstate within Ha of the ground state, the circuit must estimate the energy with root-mean-square error at most mHa, including all approximation errors.
For this problem, the best published spacetime cost is [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 of the ground state, giving a cumulative baseline of on 481 logical qubits (Appendix § 13).
For this problem, we find a solution that achieves a spacetime cost of , a reduction of . 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 -gate saving per step and most of the qubit saving. More details are given in Appendix § 13.
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, Figure 5a). Whereas the wiki transferred verified code, conferences exchanged unverified proposals and critique: the largest single drop () 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).

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 reduction of each step. Within-team discoveries enter from below; cross-team conference and wiki ideas enter from above. b) Share of the logarithmic 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).
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.
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 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 § 6): 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 reduction in expected oracle rounds for parallel Grover search, a spacetime reduction for fixed-point arcsin, and , and 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 § 8), 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 gates can run in parallel, may instead favor minimizing qubits times 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]

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+ 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 . These assert that for every initial (classical-quantum) state satisfying the precondition , all executions of the program terminate in a (classical-quantum) state satisfying the postcondition . 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 . We call this the expectation of satisfaction. A triple then asserts that, for every initial state , the expectation of satisfying an assertion is bounded above by the expectation of the resulting state (obtained after running the program on ) to satisfy .
Verification is performed via reasoning about weakest preconditions. Starting from a given postcondition , 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].
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 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 of quantum variables each associated with a Hilbert space of dimension respectively. We restrict our set-up to a single quantum variable with associated Hilbert space of dimension , where is a positive natural number. In practice, can be identified with . This loses no expressiveness if we limit ourselves to finitely many quantum variables: if these are of dimensions can be combined into one register of dimension . Although, this requires lifting operations to the full space explicitly. Supporting multiple named quantum variables is left for future work.
Classical-quantum states. Let be the set of Hermitian operators (matrices) on and the set of partial density operators, ordered by the Löwner order. A classical-quantum state is a function with countable support whose total trace is at most . In particular, any deficit represents nontermination. In other words, for a classical store , is the probability of being in the classical branch and , 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 , where and are the zero and identity matrix respectively. A classical-quantum assertion is a map . This approach is inspired by classical probabilistic program logics, mirroring the use of by real-valued expectations there.98 We formalize this as follows, where Observable d is our formalization of :
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 and uncompute them upon completion.

Figure S2. A formal definition of the clean-ancilla property. Here, a program implements the unitary on register rTarget and returns the disjoint ancilla register rAnc to : for every predicate , from any input with clean ancillas, must end with clean ancillas and satisfy at least as often as applying would. Since is arbitrary, acts exactly as on all such inputs.
Similarly to CQState, CQAssertion has a partial order: we can lift the Löwner order on observables by declaring , if for all classical stores . 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 -CPO with respect to the Löwner order: it has a least element, and every increasing chain 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 102 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 :
The image set is countable;
For each , the preimage is definable by a classical assertion.
We do not need to impose condition (1) separately: when the set of classical variables Var is finite, is countable, so the image of is automatically countable. We prove this in CQAssertion.equivCountable. Condition (2) holds automatically since we represent classical assertions as predicates . 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 -CPO. We encounter the same roadblock to the -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 satisfying a cq-assertion :
This can be thought of as the expected satisfaction of in state , averaging over all possible classical branches . 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) : ℝ := ∑' σ, ⟪⟨(𝜃 σ).val, Δ σ⟩⟫_ℝ
notation "E[" Δ ", " 𝜃 "]" => expect Δ 𝜃
This definition and Equation (1) are equivalent: the inner product of the Hermitian matrices and 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 Δ Θ 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]:
Our formalization diverges from Ref. 42 in the following ways: we omit random assignment , we work with a single quantum system rather than several quantum variables, and we represent expressions and guards 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 and on a single -dimensional quantum system ( an arbitrary positive natural number, with for qubits). Classical expressions and decidable guards are shallowly embedded as functions of the classical store , 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 , apply U applies a unitary operator , and performs an -outcome quantum measurement with Kraus operators , , storing the outcome in . 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:
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 and a postcondition , computes the “weakest” cq-assertion whose expectation in any initial state equals the expectation of in the state reached after executing . Since cq-assertions form an -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 , 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 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 . This is built sequentially from nine primitive unitary gates PrimitiveGate (Clifford+, 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 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 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 and an initial cq-state with total trace , the branch-weighted expected cost (expectedCost) is defined by structural recursion on alongside the denotational semantics :
for primitive commands , taking values in 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 across sequences, branches, and loops, bounding a qwhile loop by its per-iteration cost times the expected number of iterations, which can where , .
| Program | Denotational semantics | Weakest precondition |
skip | ||
abort | ||
qset | ||
apply | ||
qif then else | ||
qwhile loop |
Table S3. Figure S3: Inductive definitions of the denotational semantics and weakest precondition . For a guard , retains where and sets all other branches to 0 (similarly for and ). Loop unrollings start from and .
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 § 9). 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 as the input size grows, ordered lexicographically on , 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.

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.

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.
Wiki record #1 · Team 2 · PR #N verified
. One 288-qubit shared ancilla register is reused by every step of the circuit.
read from the wiki
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”
verified and published to the wiki
Wiki record #2 · Team 3 verified — 14.5%
. “Builds on the 288-wire . . . baseline (PR #N) by composing 7 orthogonal verified seams”, including: • catalyst prepared with 0 ancillas (: 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.
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 , defined as total peak logical qubits (including clean workspace ancillas) multiplied by total -gate count , pricing clean-ancilla Toffoli gates at 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 while memory footprint tracks , making proportional to , the topological spacetime volume.[1, 2, 43, 89] [114, 115] Optimizing also regularizes space–time tradeoffs against degenerate extremes—neither permitting unbounded clean-ancilla QROAM replication to suppress -gate count[4, 24] [116] nor forcing deep ancilla-starved recomputation to save a handful of qubits[10] [117]—and aligns directly with the metrics reported across standard resource-estimation benchmarks.[3, 27, 48, 58, 60, 88] [118, 119]
Physical device cost departs from in two principal architectural regimes. First, provisioning parallel magic-state factories compresses execution depth from toward -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 and 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 , with dashed lines at reference midpoints and feathered boundaries reflecting spread across estimates.
| Capability regime | Midpoint | ceiling | ceiling | Benchmarks & references | |
| Medium-term FTQC (teraquop) | – | – | Cytochrome P450; compact catalysis & ECC7,60,61,88,89,113,114,118 | ||
| Application-scale FTQC (FASQ) | – | – | Stopping power, dynamics; catalysis, materials & RSA1–3,27,48,58,115,119,120,122 |
Table S1. Table S1: Fault-tolerant capability regimes and hardware horizons. Summary of the capability regimes referenced in Figure 3b, listing plotted dashed-line midpoints , nominal upper-bound ceilings (rendered in Figure 3b with 14-step normal-quantile feathering spanning –, – for teraquop planar and –, – for FASQ), nominal spacetime volume , and representative benchmarks and references.
Medium-term FTQC (teraquop planar). Gidney et al.114 (§ 2.1) define the teraquop scale at reliable logical operations ( logical qubits over steps at per-step error ), and Low et al.61 quantify how denser planar surface-code layouts and magic-state cultivation set the corresponding qubit and -gate ceilings across planar code distances. This regime sits at midpoint , , and , with feathered ceiling and .
Application-scale FTOC (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 -gate budgets required across materials, chemistry, dynamics, and factoring. This regime sits at midpoint , , and , with feathered ceiling and .
Parallel Grover Search
Problem specification and oracle model
Given a search space of size () and an unknown marked subset of known size , we study two exact (zero-error) search problems across (121 settings): Find-Any, which must terminate with probability 1 and output an index , and Find-All, which must terminate with probability 1 and output all elements of (so algorithms cannot trade error probability for fewer queries). We allow up to parallel queries per round[63] [123] (Figure S6). Access to is given by the -qubit reversible marking oracle

Figure S6. Parallel Grover query model. Workspace allocation (qset, +0 query cost) initializes query registers of qubits and ancilla qubits in together with a classical state . Unitary evolution (step, +0) applies any -independent unitary across all qubits. Parallel oracle querying (oracle, +1) applies (Eq. (5)) simultaneously across disjoint -qubit subregisters. Projective measurement (measure, +0) measures a subregister into classical variable in while leaving unmeasured wires coherent. Classical control (qif/qwhile; Appendix § 4) branches and loops on predicates of , weighting each oracle round by the active-branch probability until outputs the result.
where is a single-qubit target bit and is the -qubit index. Starting from on an unconstrained -qubit workspace, an algorithm interleaves zero-cost -independent unitaries, projective measurements, and classical branching or loops with parallel -query rounds
on any disjoint -qubit registers, weighted in expectation by the probability of being in an active loop branch. To query fewer than registers in a round, the remaining target qubits are prepared in , on which acts as the identity. Our cost metric is the expected number of parallel query rounds (query depth).
Depending on how the target qubit is prepared (and optionally measured), a single call to implements three operations. Preparing applies the phase flip for , while preparing and measuring tests whether (and once a subset has been found, unmarking via is independent of and costs zero queries). More generally, preparing for leaves unchanged for while mapping for , where . Measuring in therefore applies, with ,
a click () projects onto with no false positives, while a no-click () only slightly damps the marked amplitude and still flips its sign by for the next Grover diffusion step.
To compare algorithms independent of the domain size , let be a program’s expected query depth on marked set , and let be its average over all -element subsets (which equals the worst-case expected depth over , since indices can be randomly permuted at zero query cost). We normalize by the fixed reference scales
and certify in Lean a rational constant satisfying for all sufficiently large . Because 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 cancels out.
Published prior baselines
Every quantum search protocol obeys scaling in domain size, [62, 63] [124] with parallel round lower bounds for Find-Any (Zalka’s bound [63] for ; the general case follows from the parallel adversary bound 123) and for Find-All, [65] so protocols at fixed compete on their asymptotic leading constant . 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 regime, together with the direct combination of Zalka’s partition [63] and weakly measured search [66] on the boundary (Figure S7). Parallel quantum-walk and learning-graph algorithms 123 target multi-element certificates and do not tighten these baselines.

Figure S7. Published parallel Grover baselines and verified bounds across . 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 relative to (Eq. (7)). b, c Winning baseline envelopes for finding any one (b) or all (c) targets, with dashed contours marking regime boundaries.
Boundary regime ( or ; BBHT, ZK, WG). On a single register () with marked items, each Grover iteration rotates the state toward by , so iterations reach angle and find a marked item upon measurement with probability . Standard Grover runs to (), where flattens out and the final queries buy little success probability. Boyer, Brassard, Høyer and Tapp [62] (BBHT) instead stop early at and restart from scratch on failure: each run costs queries and succeeds after expected runs, minimizing expected queries at
Across the and boundaries of Find-Any and Find-All (which coincide when ), sets the projective-restart baseline. For and in both tasks, Zalka’s (ZK) partition [63] splits into disjoint blocks of size so the unique block containing the target runs at (). For and in Find-All, repeating early-stopped search times while unmarking each found item at zero query cost [62] [129] achieves at every stage.
On the single-register boundary (, for Find-Any, and 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 (50% marked weight, costing ), and then alternates calibrated weak checks (Eq. (6), ) with single zero-query diffusion
| Reference | Evaluation in metric | Find-Any Regime | Find-Any Rel. rounds | Find-All Regime | Find-All Rel. rounds |
| Boyer et al. [62] (BBHT, Eq. (8)) | Early-stop restart + strike-out | — | — | , ★ | 0.879 |
| Zalka[63] (ZK, Eq. (8)) | -block partition + early stop | , | 0.879 | , | 0.879 |
| Gingrich et al. [64] (GW, Eq. (10)) | Unpartitioned -slot early stop | ★ | 0.942–0.997 | — | — |
| Grover & Radhakrishnan[65] (GR0) | Two-pass -block staircase () | — | — | ★ | 0.060–0.955 |
| Fang & Heunen[66] (WG; +ZK, Eq. (9)) | Calibrated weak loop (+ZK at ) | or ★ | 0.818 | ★ | 0.818 |
| This work (Lean-verified circuits) | 0.818 | 0.051–0.818 | |||
| Speedup vs. baseline envelope (Figure 3d) | 100/121 cells () | up to 1.22× | 110/121 cells () | up to 1.41× |
Table S7a. Published parallel Grover baselines and verified bounds

Figure S7b. Finding any one target.

Figure S7c. Finding all targets.
steps. Whenever a check does not click, its slight damping and phase flip are offset by the diffusion step to return the state back to without losing superposition; waiting for a click adds expected queries, giving
For and in both tasks, running WG inside each of Zalka’s disjoint blocks of size (ZK+WG) is a direct substitution—the empty blocks never click while the unique target block evolves at scale —upgrading the boundary from to .
Interior Find-Any (; GW). When both and , naive domain splitting breaks down because each of the blocks receives a random, unknown number of targets (and most blocks are empty when ), causing multi-target blocks to rotate faster and overshoot under any fixed schedule. Gingrich, Williams and Cerf[64] (GW) avoid this unknown-load problem by running all registers independently over the full domain . Stopping all registers synchronously after rounds finds a target unless all independent measurements miss (probability ); minimizing expected rounds selects with
Because unentangled copies combine success probabilities classically rather than coherently, is independent of and degrades from at to at , setting the published baseline on all 100 interior cells (Figure S7).
Interior Find-All (; GR0). To let registers find distinct targets in parallel at block scale, Grover and Radhakrishnan[65] randomly partition into blocks of size . Each block receives an unknown target count , which they clear via a descending staircase of exact amplitude-amplification stages127 at assumed counts (total depth ), testing and unmarking hits after each stage. Counting down guarantees emptying every block with : even if stages miss, once reaches a block’s remaining count , the assumed and actual counts match, finding a target with certainty and stepping in lockstep with (while mismatched stages still hit with probability ). Because Theorem 3 of ref. [65] leaves tail cleanup at order, we evaluate a concrete two-pass schedule (GR0): Pass 1 runs a staircase from the optimal integer cap down to 1, and Pass 2 clears all remaining targets via a second staircase from down to 1 (Figure S7).
Algorithmic mechanisms in verified circuits
Beyond the boundary (ZK+WG), our interior baselines are single-paper protocols; Fig. S8a 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 three of the many mechanisms found per class. Since mechanisms interact, Figure S7 reports only joint speedups, while Fig. S8b,c details the verified relative round costs and winning circuit regimes across .
Unlike distributed baselines such as GW and GR0 that run uncoupled registers, our shared-workspace model allows inter-slot entanglement: coupling all slots via odd-parity fanout in Find-Any extends the boundary constant to every interior , while Find-All entangles slot and storage registers. Although non-oracle unitaries carry zero query cost in the black-box specification, our verified circuits use qubits and each unitary step decomposes into elementary gates. fig:S8: Verified parallel Grover mechanisms and relative round costs across . a Selected algorithmic mechanisms in our Lean-verified circuits (not exhaustive). b, c Verified asymptotic expected parallel rounds relative to (Eq. (7)) for finding any one (b) or all (c) targets, with dashed contours marking distinct winning circuit regimes.
| Mechanism | Builds on | Regime | Description |
| Automatic recombinations | |||
| Weak-loop pipelining | [62, 64, 66] [131] | Find-All, | Full-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, | 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, | Under-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-Any | Conjugating by marker-qubit gates gives a reflection about slot tuples holding an odd number of targets. |
| Tensor-power conveyor | [9] | Find-All, | A zero-query rotation repeatedly moves found amplitude from each query register into storage registers. |
| Collective all-hit weak probe | [63] [131] | Find-All, | Lockstep block searches are weakly probed for whether all remaining targets are found; a click returns all, a non-click continues coherently. |
Table S8a. Selected mechanisms in verified circuits.

Figure S8b.
Figure S8c.
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 reversibly on a fixed-point register, a subroutine that often dominates the non-Clifford gate count.[10] [136]
We consider reversible evaluation on signed two’s-complement registers, where is the input register, is the output register, and approximates . Because diverges as , 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 . Allowing for some small rounding error, we require a maximum absolute error across all inputs . Using clean ancillas, a candidate program in Clifford+ gates and mid-circuit measurements must apply this exact action across all basis states and return all ancillas to .
Baseline
We consider as baseline the algorithm by Häner et al. [10], which uses a piecewise-polynomial approach.[1] We compare against their fixed-point two’s-complement configuration, whose maximum error is driven by the error in the square root computation (Fig. 6 of ref. 10), and larger than our target bound of , thus providing a lower bound on the spacetime cost. As shown in Figure S9, this baseline splits the computation of arcsin on the interval between a degree-3 polynomial evaluation on and a Newton iteration for .4 As their Appendix D 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 gates). The latter can be implemented using 245 qubits and requires 73,442 Toffoli gates to implement it as the product of with , as described in their Appendix C.2, and an additional 2,094 Toffoli gates to also reverse the product operation, being already a reversible operation, for a total of 75,536 Toffolis (302,144 gates).

Figure S9. Baseline circuit to implement the arcsin function,[10] using , , . After restricting to the positive range, the approximation splits the calculation of arcsin between a degree-3 polynomial in the interval and a Newton iteration for the square root function in . Number of 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 by using the maximum number of required qubits in the two subcircuits, 245, and the sum of the gates required for them, 440,576 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 (, CNOT, Toffoli and CSWAP), Pauli- measurement-based uncomputation,[23] and diagonal , and phase corrections so that every basis input stays a single signed basis state 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() subroutine, but on a restricted input range rather than . 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 gates).
However, the kickmix gate set is limited, and we expect that the full Clifford+ 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 gates, Figure S10 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 S10,Figure S10). This drove the cost down by a further 11% to 369,800 (100 qubits, 3,698 gates), 290× below the baseline[10] (Figure 3a,Figure 3c).

Figure S10. Sketch of the algorithm to implement the fixed-point arcsin module. (a) Full kickmix circuit. It uses 50 data qubits ( and , 25 each) and 50 ancilla qubits reused across stages, and a total of 4,152 gates. The bin index has 9 bits but needs only 2 extra ancillas. After "shift ", 6 bits of are simply the top 6 bits of , which identify the bin within its group. A 7th bit replaces the bit of , which can be recomputed from and is erased. The remaining 2 bits use one ancilla each: one is stored directly, and the other replaces the top bit of , whose value is moved into an ancilla. is computed into the ancillas freed by clearing . At peak, the ancillas hold (19), and (24), 5 lookup work qubits, 1 bit of , and the moved bit of . (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 gates. Each coefficient bit is computed by one inner-product block taking a variable number of product pairs and using gates. We have 26 blocks totaling 364 gates before , and 15 blocks totaling 230 gates on the freed qubits after clearing . Each inner-product block leaves an extra sign phase that is then removed before returning the result. The whole circuit requires now 3,698 gates instead of 4,152 gates. (c) Example of the optimized inner-product block for two product pairs, using 6 gates, which could not be expressed in the kickmix framework.
Table S2: Summary for fixed-point on at . The baseline evaluates the configuration,[10] assuming 4 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 gates comprise 776 four- temporary-AND gates (3,104 ) plus 594 single-qubit gates across 41 inner-product gadgets.
| Method | Toffoli | Spacetime cost () | |||
| Baseline[10] (lower bound) | 110,144 | 440,576 | 245 | ||
| – on | 34,608 | 138,432 | — | — | |
| – | 75,536 | 302,144 | — | — | |
| Kickmix | 1,038 | 4,152 | 100 | 415,200 | |
| Non-kickmix (Lean 4) | 776 | 3,698 | 100 | 369,800 |
Table S2.
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 S10 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. , 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,
and approximate the remainder using a separate quadratic polynomial on 440 intervals of . 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 , where grows steeply. The closest input to 1 on the fixed-point grid is away, so finitely many intervals cover all inputs. The point is handled separately. Subsequently, the circuit looks for the interval that contains and stores its index in a 9-bit register . It does so by using a barrel shift, i.e. it counts the leading zeros of , and shifts the magnitude bits left using controlled swaps to form the local offset . A lookup block then computes the interval’s coefficients , , for , and squarer and adder circuits add to . As an optimization, the 19 high bits of are added to and erased so that the remaining coefficient bits can be computed on the same qubits. Similarly, and are erased midway so their qubits can be reused for the rest of . Measurements with and corrections erase the coefficients and all other scratch qubits at zero cost. Finally, the circuit is made reversible by undoing the shift and the sign conversion, restoring and returning all ancillas to .
As shown in Figure S10, a large amount of the total kickmix gates are spent on the coefficient lookup phase. Specifically, each coefficient bit is a fixed function of the interval number , given by a table with one entry per interval. Any such table can be written as an XOR of products of bits of , e.g. . 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 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 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 and gates, and then makes the branches interfere to get the appropriate bit. However, each inner-product circuit leaves a sign that depends on the specific , which is cancelled across each lookup pass with and gates at zero 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 and until after has been added to and cleared, leaving more spare qubits for that adder and reducing the lookup-and-add stage from 1,348 to 894 gates. Together, these changes lower the full circuit from 4,152 to 3,698 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 electrons (, mass 1) and one -particle projectile (, mass , matching 3.9726 proton masses in Table 2 of ref. [48]) in a periodic cubic cell of volume containing 216 fixed protons at arbitrary positions . In plane-wave first quantization, each electron momentum coordinate is stored in signed-magnitude qubits and each projectile coordinate in signed-magnitude qubits,[27, 48] giving system qubits. The valid grid subspace excludes the signed-magnitude negative zero from every coordinate, leaving integer momenta in for each electron ( plane waves, covering the classical time-dependent density-functional grid of Table 1 in ref. 48) and for the projectile, at wavevectors . The projectile’s momenta are taken relative to its initial mean momentum , with for compatibility with the cell’s periodicity and a.u. ( a.u.).
On valid grid states, the discretized Hamiltonian in atomic units is
and acts as zero outside the valid grid subspace. Here and range over the electrons (, ) and the projectile (, ), , and .
For every proton configuration , initial projectile momentum , evolution time a.u., and partition of the 218 electron registers into spin-up and spin-down subsets, a candidate circuit over Clifford+ and mid-circuit measurement using ancilla qubits must realize a single unitary that matches up to a global phase , satisfying
at for every normalized grid state antisymmetric under exchange of same-spin electrons. All ancillas begin in in each run, rather than carrying pre-prepared resource states (such as phase-gradient states) across runs. Every circuit is compiled into Clifford+ 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 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 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 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 Ha, a block-encoding cost of Toffolis per walk step, and logical qubits (3,948 system and 1,702 ancilla qubits). Each electron–proton or electron–electron pair contributes Ha to , giving Ha from electron–proton attraction and Ha from electron–electron repulsion (91.4% of ).
Generalized QSP139 implements as a polynomial in a qubitized walk operator[25] that block-encodes , with one walk step per query. Evaluating the query count140 in Eq. (12) of ref. [48],
at and summing over the 50 runs at each of a.u. gives walk steps, or Toffolis over all 500 runs. This is an average of walk steps and Toffolis per run, so gates per run and per run ( over 500 runs), the number presented in Figure 3a. The same study[48] also quotes an eighth-order product-formula estimate ( 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 (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 , 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 in one LCU branch and in the other. Averaging the two branches gives for electrons on the point, which equals for and has magnitude at most one for any . 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 interaction terms. Therefore, the circuit reproduces the interaction up to a constant, while each such term adds its potential to once rather than once for every electron that could occupy the point. At separations beyond , 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 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 . Earlier real-space solutions computed and uncomputed around each shift, summing all 218 electron momenta four times per walk step, which made up about a fifth of the gates per step. Only the protons and the projectile change , and both act in the real-space step, so the final circuit keeps 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 gates per step by 10% (Figure 4c).
Resource counts
Our solution uses 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 . The improvements above lower to Ha. Each run of length is split into segments of 0.5 a.u., each implemented by generalized QSP139,140 of degree 68,053, giving an average of walk steps per run.
Each walk step uses roughly 152,000 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 gates per run. Averaged over a.u., this gives gates and 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 gates per step, a 10.9× lower cost (Figure 4a).
Non-Born–Oppenheimer Dynamics of CHNO
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 particles of composition CHNO: 47 nuclei (23 , 20 , 3 , and 1 , with charges ) followed by 187 electrons (). Each Cartesian coordinate is stored as a signed -bit integer on system qubits, representing position in a cubic box of width Å (83.15 ) with grid spacing . Electron masses are , and nuclear masses (not stated in the baseline[58]) are set in electron-mass units from the , , , and isotopic atomic masses minus .
The discretized non-Born–Oppenheimer Hamiltonian is , with
where , is the quantum Fourier transform on the three coordinates of particle , and the squared Coulomb saturation distance is when both and are nuclei ( in Table IV of ref. [58]) and otherwise, capping electron interactions at and nuclear repulsion at .
A candidate circuit over Clifford+ and mid-circuit measurement must realize a single clean-ancilla unitary satisfying Eq. (12) at for 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 , so resource states such as phase-gradient states must be prepared within the circuit. Every Toffoli is compiled into Clifford+ gates and checked at that gate level by the correctness proof, and where later gates are conditioned on measurement outcomes we count the gates of the most expensive branch.
The baseline instead bounds only the block-encoding error (Appendix C of ref. [58]), where is the part of the circuit that starts and ends with the ancillas in . This leaves out the ancilla error, the part of the output in which the ancillas are not returned to . The two parts are orthogonal, so the error in Eq. (12) splits as
and any circuit meeting Eq. (12) at also meets the block-encoding criterion at . For the baseline QSP circuit, the polynomial approximation error bounds the ancilla error[25] [139, 140] by , so with the error split in Table IV of ref. [58] () it is only guaranteed to meet Eq. (12) at , four times our target.
Baseline
Table I of ref. [58] reports Toffolis per femtosecond on qubits at , a spacetime cost of . Each walk step uses about gates, of which 52% go to the swap network, 25% to preparing the LCU weights and 22% to evaluating (Figure 5a of ref. [58]). These give the baseline values of 46.8k, 22.5k and 19.8k gates per step in Sec. 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, (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 in front of (Theorem 1 of ref. [59], via Kapteyn’s inequality),
where , and . 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 fixes independently of the polynomial degree, so the -gate count per step and the qubit count are unchanged. At the reported Ha ( at a.u.) and , Theorem 2 lowers the number of walk steps from to ( with Theorem 1). Rescaling the published Toffoli count by this ratio gives our baseline,
the number presented in Figure 3a. At this large the subleading terms barely matter: using Theorem 1 instead, or simply dividing the published Toffoli count by , gives the same cost to three significant figures.
Main improvements
Section 2.4 summarizes three changes to the walk step that account for almost all of the reduction in gates per step relative to the baseline (Figure 4e–Figure 4g). Here we describe each one alongside the baseline construction it replaces, and Appendix H.4 gives the resulting 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-X measurements and classically controlled CZ corrections,[23] [116] as done for momentum bits copied in plane-wave kinetic terms[27] (Figure 4e).
Second, the potential in Eq. (14) requires computing for . Because the coordinates are stored as integers, can be obtained cheaply using integer subtraction and squaring. To get without a square root, the baseline prepares an ancilla register in uniform superposition over integers , assigning to branches with and an alternating sign to the rest. The alternating terms cancel, so the average over branches approximates , but the test requires multiplying by , which dominates its cost.[58] In this work, the range of is split into coarse intervals with rescaled position , and on each interval is approximated by a cubic Bernstein polynomial (512 precomputed coefficients in total). Rather than multiplying powers of , the circuit samples this polynomial directly.[67] [142] It compares against three ancilla registers in uniform superposition and counts how many are smaller, which gives with exactly the binomial weights above. Looking up then gives the polynomial in expectation (Figure 4f).
Finally, in the electron–nucleus terms of , each nucleus is weighted by its integer charge . 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 states to each nucleus , 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 logical qubits, consisting of 5,616 system qubits and 441 clean ancillas. Evaluating the 1-norm at Å together with potential shifting gives block-encoding scale Ha and generalized QSP degree .
Each uncontrolled walk step uses 30,504 gates (30,516 on the two boundary controlled steps): 1,256 for reversible nuclear-charge and pair-weight preparation, 24,526 to copy selected particle coordinates into ancillas and 908 for -basis measurement uncomputation (25,434 total routing, against 46.8k for the baseline swap network), 3,116 for the 512-entry Bernstein evaluation, 446 for the QFT kinetic term, and 252 for the LCU reflection, plus 76 per step for QSP rotations and 247 for one-time phase-gradient initialization. This totals gates and (8.08× below baseline).
Cytochrome P450 Compound I
Hamiltonian and specification
The system is active space X of Compound I, with electrons in spatial orbitals.[88] Under the Jordan–Wigner transformation each spin orbital is stored on qubit , giving 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 D F T H C 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 double-factorized tensor-hypercontraction (DFTHC) factorization of tbl:5 in ref. 60, with the released tensors144 rounded to bits:
where for unit orbital vectors () and , as follows from expanding in the DFTHC construction.[60] As in the released dataset,144 Eq. (18) omits the scalar , and adding the classical Hartree–Fock shift 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 of with energy . Assuming an eigenstate as input loses no generality for resource estimation: phase estimation on any state gives, with probability , the same outcomes145 as on the eigenstate . In practice only approximates the ground state , so finding takes on average 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+ gates and mid-circuit measurements on the system and ancillas that start in . 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 -qubit phase register among the ancillas is measured, and its outcome is converted into the energy estimate
where , and are fixed numbers chosen with the circuit. This form covers both standard qubitization and sum-of-squares spectral amplification. For a walk eigenphase , the energy is in the first[4, 24, 25, 89] and in the second.[60] [147] Since at the energies measured here, both read , with and respectively. When phase estimation applies the walk forward or backward depending on the phase register, estimates , so Eq. (19) estimates .
If the specification only covered the ground state, a circuit with no gates and would pass by setting within of the ground-state energy . The specification therefore requires the same circuit and decoder to work for every eigenstate up to , with Ha and Ha. For each 63-electron eigenstate with energy , the outcome distribution must satisfy
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 , with estimates above counted as . For an eigenstate above the window, it only requires that estimates do not fall more than below . A circuit that ignores gives the same estimates for every eigenstate, and in root mean square these would have to lie within of and at most below at once. This is possible only if mHa, far below 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 mHa matches prior resource estimates on this active space, although separating the doublet and quartet states would require tighter tolerances.
All ancillas begin in , so resource states such as phase-gradient states must be prepared within the circuit. Every Toffoli is compiled into Clifford+ gates and checked at that gate level by the correctness proof, and where later gates are conditioned on measurement outcomes we count the 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 ), where is block-encoded with norm and energy-window gap using the phase-estimation step count[24, 60]
Adding to in that estimate[60] raises its step count from 51,510 to 51,948 and its cost to (+0.85%). The published construction[60] forms the one-body term from the exact two-electron tensor , while the squares in Eq. (18) use the factorized tensor . The Hamiltonian it block-encodes therefore differs from the Hamiltonian by a one-body term that lowers the low-lying energies by about 0.6 Ha. Its subtracts the sum-of-squares bound of the block-encoded Hamiltonian from the sextet Hartree–Fock energy of the Hamiltonian,144 so it is about 0.6 Ha larger than when both energies come from one Hamiltonian, which overestimates the cost. We form from , so that Eq. (18) is the Hamiltonian up to a constant, whose CCSD(T) correlation energy is within 0.28 mHa of that of . This lowers from 97.4395 to 97.3864 Ha ( Ha), and with both energies evaluated on this Hamiltonian Ha including (49,269 steps). Bounding Ha with the quartet () ROHF determinant instead lowers to 5.143 Ha, giving Ha and .
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 before space–time tradeoffs. Thirteen bits suffice because the angles enter the orbital vectors[4] as and , and the overall sign of each vector does not affect , so fixing that sign puts every angle index of in . 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 index registers from an 8-bit outer index 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-QROAM116 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 rather than in , 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 remains exact. Minimizing over QROAM block sizes and angle batch sizes gives logical qubits and Toffolis/step (5.65 × Toffolis, gates), for a baseline cost of
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 § 13.4 gives the resulting 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 or a one-body term, and the inner stage picks , which fixes the orbital vector . 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 § 13.§ 2). Our solution instead builds a 145-qubit one-hot register in each SELECT call, for 296 . Each of its qubits stands for two orbital vectors, so the register covers 290 of them: the 261 vectors and 29 of the 58 eigenvectors of . The other 29 eigenvectors are handled by the second call of the step. A further qubit records which vector of the pair was chosen. Each angle bit then enters the phase-gradient adder of its rotation as
where is the control qubit of the rotation and , and 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 , and Eq. (23) is 0 for and the bit of the chosen vector for . 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 . With the one-hot register, the rotations and their angles cost 11,818 per call rather than 18,844 , and the angle register is no longer needed.
The inner stage uses the same idea. It keeps a 126-qubit one-hot register for and a 5-bit binary register for , so each alias-sampling lookup[24] costs 390 , against 1,968 for the QROAM of the baseline. Together with the one-hot SELECT, this accounts for 96% of the 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 , 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 , as many as one block of swaps, and erases it with -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 logical qubits and gates, so , 2.49× below the baseline (Figure 3a,Figure 3b). This comes from 1.67× fewer gates per walk step (Appendix § 13.§ 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.
The circuit runs walk steps. We bound Ha with a 3,000-determinant quartet wavefunction, whose energy is checked in Table S1 below. This is 0.31 Ha below the target ROHF bound of the baseline and gives Ha and 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 by at most 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 .
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 per step of Table S3, 1 block of 1,024 steps borrows 10 qubits (28,298 per step), and 7 blocks of 128 steps borrow 7 qubits (31,010 per step). On top of Table S3, the baseline spends 268 per step on reflections and phase-estimation control, for 46,068 in total. Each of our blocks uses 84 for each reflection between its steps and 232 for an ordinary first swap block. The 127 single steps cost 37,642 each (including 418 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 , with 31 reflections controlled by the phase-estimation register. Preparing the initial state of the phase-estimation register takes 142,248 , the inverse QFT 12,603 and the phase-gradient state 1,036 . Adding these up gives the = 1,310,839,337 quoted above.
| Part of a walk step | Baseline | This work |
| Rotations and their angles | 37,688 | 23,636 |
| Index decoding | 264 | 440 |
| Spin swaps | 928 | 464 |
| Outer state preparation | 1,032 | 598 |
| Inner state preparation | 5,888 | 2,264 |
| Total | 45,800 | 27,402 |
Table S3 (PDF p. 41). 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.
Code Availability and Reproducibility
Appendix References
Beverland, M. E. et al. Assessing requirements to scale to practical quantum advantage 2022. arXiv: 2211.07629 [quant-ph].
Preskill, J. Beyond NISQ: The Megaquop Machine. ACM Transactions on Quantum Computing 6, 1–7. arXiv: 2502.17368 [quant-ph] (2025).
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).
Lee, J. et al. Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction. PRX Quantum 2, 030305 (2021).
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).
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.
Häner, T., Roetteler, M. & Svore, K. M. Optimizing Quantum Circuits for Arithmetic 2018. arXiv: 1805.12445 [quant-ph].
Gidney, C. Halving the cost of quantum addition. Quantum 2, 74 (2018).
Babbush, R. et al. Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity. Physical Review X 8, 041015 (2018).
Low, G. H. & Chuang, I. L. Hamiltonian Simulation by Qubitization. Quantum 3, 163 (2019).
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).
De Moura, L. & Ullrich, S. The Lean 4 Theorem Prover and Programming Language in Automated Deduction – CADE 28 12699 (Springer, 2021), 625–635.
Feng, Y. & Ying, M. Quantum Hoare Logic with Classical Variables. ACM Transactions on Quantum Computing 2, 1–43 (2021).
Litinski, D. A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery. Quantum 3, 128 (2019).
We will shortly open source our Lean 4 library, problem specifications and verified solutions.
References
- [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]Preskill, J. Beyond NISQ: The Megaquop Machine. ACM Transactions on Quantum Computing 6, 1–7. arXiv: 2502.17368 [quant-ph] (2025).DOI
- [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]Lee, J. et al. Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction. PRX Quantum 2, 030305 (2021).DOI
- [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]Hubert, T. et al. Olympiad-level formal mathematical reasoning with reinforcement learning. Nature 651, 607–613 (2026).DOI
- [7]Babbush, R. et al. Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigation. PRX Quantum 7, 031001. arXiv: 2603.28846 [quant-ph] (2026).arxiv.org/abs/2603.28846
- [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]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]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]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]Jordan, S. P. et al. Optimization by decoded quantum interferometry. Nature 646, 831–836 (2025).
- [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]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]Santagati, R. et al. Drug design on quantum computers. Nature Physics 20, 549–557 (2024).DOI
- [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]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]Jordan, S. P., Lee, K. S. M. & Preskill, J. Quantum Algorithms for Quantum Field Theories. Science 336, 1130–1133 (2012).DOI
- [19]Bauer, C. W. et al. Quantum Simulation for High-Energy Physics. PRX Quantum 4, 027001 (2023).DOI
- [20]Joseph, I. et al. Quantum computing for fusion energy science applications. Physics of Plasmas 30, 010501 (2023).DOI
- [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]Acharya, R. et al. Quantum error correction below the surface code threshold. Nature 638, 920–926 (2025).DOI
- [23]Gidney, C. Halving the cost of quantum addition. Quantum 2, 74 (2018).DOI
- [24]Babbush, R. et al. Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity. Physical Review X 8, 041015 (2018).DOI
- [25]Low, G. H. & Chuang, I. L. Hamiltonian Simulation by Qubitization. Quantum 3, 163 (2019).
- [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]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]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]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]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]Bausch, J. et al. Learning high-accuracy error decoding for quantum processors. Nature 635, 834–840 (2024).DOI
- [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]Fawzi, A. et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature 610, 47–53 (2022).DOI
- [34]Mankowitz, D. J. et al. Faster sorting algorithms discovered using deep reinforcement learning. Nature 618, 257–263 (2023).DOI
- [35]Romera-Paredes, B. et al. Mathematical discoveries from program search with large language models. Nature 625, 468–475 (2024).
- [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]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]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]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]Achim, T. et al. Aristotle: IMO-level Automated Theorem Proving 2025. arXiv: 2510.01346 [cs.AI].arxiv.org/abs/2510.01346
- [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]Feng, Y. & Ying, M. Quantum Hoare Logic with Classical Variables. ACM Transactions on Quantum Computing 2, 1–43 (2021).DOI
- [43]Litinski, D. A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery. Quantum 3, 128 (2019).
- [44]We will shortly open source our Lean 4 library, problem specifications and verified solutions.
- [45]The mathlib Community. The Lean mathematical library in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (POPL 2020), 367–381.DOI
- [46]The Physlib Community. Physlib: The Lean Physics Library https://github.com/leanprover-community/physlib. 2024.
- [47]Meiburg, A. Quantum Information in Lean https://github.com/Timeroot/Lean-QuantumInfo. 2024.
- [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]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]Gottweis, J., Weng, W.-H., Daryin, A., et al. Accelerating scientific discovery with Co-Scientist. Nature 655, 487–496 (2026).DOI
- [51]Lu, C. et al. Towards end-to-end automation of AI research. Nature 651, 914–919 (2026).arxiv.org/abs/2606.15497
- [52]Ghareeb, A. E. et al. A multi-agent system for automating scientific discovery. Nature 655, 497–505 (2026).
- [53]Yuksekegonul, 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]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]Qu, A. et al. CORAL: Towards Autonomous Multi-Agent Evolution for Open-Ended Discovery in Proceedings of the Conference on Language Modeling (COLM) (2026). arXiv: 2604.01658 [cs.AI].arxiv.org/abs/2604.01658
- [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]Lean FRO. comparator: A trustworthy judge for Lean proofs from untrusted sources https://github.com/leanprover/comparator. Accessed Nov. 2026. 2025.
- [58]Pocrnic, 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].arxiv.org/abs/2602.11272
- [59]Pocrnic, M. & Motlagh, D. Improved constant factors for qubitized Hamiltonian simulation 2026. arXiv: 2608.02734 [quant-ph].arxiv.org/abs/2608.02734
- [60]Low, G. H. et al. Fast Quantum Simulation of Electronic Structure by Spectral Amplification. Physical Review X 15, 041016 (2025).DOI
- [61]Low, G. H. et al. A denser planar surface code 2026. arXiv: 2605.30455 [quant-ph].arxiv.org/abs/2605.30455
- [62]Boyer, M., Brassard, G., Høyer, P. & Tapp, A. Tight Bounds on Quantum Searching. Fortschritte der Physik 46, 493–505 (1998).
- [63]Zalka, C. Grover’s quantum searching algorithm is optimal. Physical Review A 60, 2746–2751 (1999).DOI
- [64]Gingrich, R. M., Williams, C. P. & Cerf, N. J. Generalized quantum search with parallelism. Physical Review A 61, 052313 (2000).DOI
- [65]Grover, L. K. & Radhakrishnan, J. Quantum search for multiple items using parallel queries 2004. arXiv: quant-ph/0407217.DOI
- [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]Goyal, V. & Sigman, K. On simulating a class of Bernstein polynomials. ACM Transactions on Modeling and Computer Simulation 22, 1–5 (2012).DOI
- [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]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]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]Correa, A. A. Calculating electronic stopping power in materials from first principles. Computational Materials Science 150, 291–303 (2018).DOI
- [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]Grabowski, P. E. et al. Review of the first charged-particle transport coefficient comparison workshop. High Energy Density Physics 37, 100905 (2020).DOI
- [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]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]Gentry, E. C. & Knowles, R. R. Synthetic Applications of Proton-Coupled Electron Transfer. Accounts of Chemical Research 49, 1546–1556 (2016).DOI
- [77]Polli, D. et al. Clinical intersection dynamics of the primary photoisomerization event in vision. Nature 467, 440–443 (2010).DOI
- [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]Mai, S. & González, L. Molecular Photochemistry: Recent Developments in Theory. Angewandte Chemie International Edition 59, 16832–16846 (2020).DOI
- [80]Hammes-Schiffer, S. & Stuchebrukhov, A. A. Theory of Coupled Electron and Proton Transfer Reactions. Chemical Reviews 110, 6939–6960 (2010).
- [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]Crespo-Otero, R. & Barbatti, M. Recent Advances and Perspectives on Nonadiabatic Mixed Quantum–Classical Dynamics. Chemical Reviews 118, 7026–7068 (2018).
- [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]Denisov, I. G., Makris, T. M., Sligar, S. G. & Schlichting, I. Structure and Chemistry of Cytochrome P450. Chemical Reviews 105, 2253–2278 (2005).
- [85]Guengerich, F. P. Cytochrome P450 and Chemical Toxicology. Chemical Research in Toxicology 21, 70–83 (2008).pubmed.ncbi.nlm.nih.gov/18052394
- [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]Shaik, S. et al. P450 Enzymes: Their Structure, Reactivity, and Selectivity—Modeled by QM/MM Calculations. Chemical Reviews 110, 949–1017 (2010).
- [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]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]Gidney, C. How to factor 2048 bit RSA integers with less than a million noisy qubits 2025. arXiv: 2505.15917 [quant-ph].