WorksPhysics and Astronomy
Formally verified harness for Shor's order finding algorithm with gate cost
Abstract
It is commonly understood that factoring a general -bit biprime via Shor's order finding algorithm requires gates by leveraging schoolbook integer arithmetics for addition and multiplication. Recent developments in quantum arithmetic circuits leveraging recursive Toom-Cook schemes have improved the cost scaling to . Here depends on algorithm implementation details of the recursive multiplication steps, which allow for a vast number of design choices. The challenge in navigating such design space also presents an opportunity for demonstrating innovative practices in quantum software engineering in the era of open agentic science. We present a formally verified harness that ingests a design specification (namely a "policy" that describes a recursive circuit design scheme) from an external source, which may be an AI agent, and produces a set of formalized proofs covering mathematical correctness of the algorithm implementation, asymptotic scaling of the end-to-end gate cost, as well as the correctness of translating the verified algorithm to a detailed circuit implementation with an intermediate representation. The harness is published as an open challenge where human researchers and AI agents can search for more efficient factoring circuits while retaining machine-checked guarantees of correctness and end-to-end asymptotic complexity.
Introduction
Integer factoring is a central use case for quantum computing, with consequences for both the study of quantum algorithms and the security of widely used public-key cryptography. Shor’s algorithm gives a polynomial-time method [1], but the resources needed at practical input sizes depend strongly on how its arithmetic is implemented. Mapping this resource frontier helps assess the capabilities of future quantum computers and the risks to cryptographic systems. A practical reference point is the Gidney-Ekera construction [2], whose reported Toffoli count for an -bit RSA integer scales as with schoolbook arithmetic, where suppresses polylogarithmic factors. In 2024, Kahanamoku-Meyer and Yao ([3]), hereafter KMY, developed a phase-based multiplication scheme built on recursive Toom-Cook multiplication [4 Sec. 1.3.3] that yields an logical gate count for Shor’s algorithm, for every fixed with suitable construction parameters. This gap in asymptotic scaling raises a practical question of whether the KMY construction offers a gate count advantage at relevant input sizes, and if so, where the crossover may be. Answering this requires explicit circuits and resource estimates under a common cost model [5]. We focus on gate count, since the construction studied here does not improve on the logical qubit count already achieved for RSA factoring using short discrete log methods [6, 7, 8, 9]. Implementing and optimizing the recursive structure of the KMY construction raises two challenges:
Searching the circuit design space. Breaking a multiplication into smaller ones and recombining their results can lower the total cost, but more pieces or costlier recombination can erase the gain. Choosing how to divide and recombine so that the circuit uses the fewest gates is the first challenge and an opportunity for AI-assisted research. Open projects [10, 11] show how public evaluation harnesses can autonomously process contributions from humans and agents. However, such open-ended agentic framework also raises a question about human understanding. A result may be technically correct yet hard for a human expert to parse, leading to the risk that autoresearch-generated and autoformalized results may accumulate faster than researchers can explain and absorb them [12 Secs. 6-7]. Inspecting and simplifying generated programs can reveal mathematical structure that guides further improvements [13]. In quantum circuit search, structured programs can likewise help researchers identify reusable ideas, such as recovering branch decisions from the arithmetic state to reduce stored history [14]. These successes raise the question of how useful insights can be reliably drawn from many unfamiliar submissions, and how much researcher effort reusing them will take. The challenge is to give humans and agents enough freedom to discover useful designs while structuring submissions so that researchers can readily inspect, compare, explain, and build upon them.
Certifying the resulting circuits. Each design needs correctness and gate-count guarantees that extend beyond tested instances. Tools such as Qualtran [15] and Qiskit [16] support circuit construction and analysis, but hardware limits and the exponential cost of general state-vector simulation restrict testing. Formal proofs must account for register sizes, ancilla uncomputation, relative phases, and approximation errors, with gate counts tied to the implemented operations under an explicit cost model. Existing methods support compo
sitional reasoning about quantum programs [17, 18, 19, 20] and semantics-preserving compilation and optimization [21, 22]. Peng et al. [23] have established correctness, success guarantees, certified gate counts, and executable circuit generation for Shor’s algorithm. Recursive fast arithmetic adds a further requirement, namely that the surrounding proofs must remain reusable as arithmetic designs change, supporting a continuing search for improvements. Recent work likewise calls for machine-checked correctness and cost proofs for parameterized circuit families in AI-assisted quantum optimization [24, 25].
Together, these two challenges call for a close connection between the freedom to explore arithmetic designs and the ability to understand and certify them. Recent works in AI assisted mathematics [26, 27] and quantum circuit optimization [14, 24, 28, 29] gives this need added urgency. As these efforts produce more results and implementations, researchers need ways to inspect their structure, check their assumptions, and incorporate them into larger constructions. For fast quantum order finding, this means we need an interface between arithmetic design and verification that specifies which choices can vary and which constraints each proposed design must satisfy. Formally proving that a new design satisfies those constraints should allow one to reuse the surrounding correctness proofs for the end-to-end implementation of the order finding circuit. The implementation can then be instantiated as concrete circuits for resource estimation.
We present ForShor, a formally verified harness for Shor’s order finding algorithm for factoring using recursive quantum multiplication. The harness is published as an open challenge akin to the previously mentioned examples5. However, the setting considered here is far more restrictive. Participants can only submit a policy (Definition 2.2, also see Figure 1) that conforms to a set of requirements which guarantee that it legitimately specifies the design of KMY’s recursive multiplication subroutine called PhaseProduct. Any policy proved legitimate in Lean (§ 2) yields a correct order finding circuit, regardless of how the policy was produced. Our proofs follow the hierarchy from factoring through order finding and modular exponentiation to arithmetic gates, establishing success guarantees, approximation bounds, circuit identities, and asymptotic gate counts. They also certify the lowered circuit from which Qualtran bloqs are extracted for resource estimation.
Figure 1. Schematic overview of the formally verified harness setup. A contributor supplies a design specification of the arithmetic circuit (namely a “policy”, see § 2), while the harness checks it in Lean, builds and lowers the order-finding circuit, and emits it to Qualtran.
As § 2 and Appendix § 9 show, an exact algorithm exists for the optimum over independent recursion trees, a class that contains every policy, but its table-construction step is out of reach at cryptographic sizes, which opens the problem to heuristic search. Optimizing PhaseProduct involves two linked choices at each recursion level: how many parts to split the register into (namely the arity, denoted as ), and which operations to perform on those parts (the program, denoted as ). The exact algorithm constructs the cheapest table for every arity and width by exhaustive search and combines the results by a dynamic program over register width and leaf-rotation count. Though it guarantees an optimal T-gate count, its table-construction step becomes intractable well before cryptographically relevant sizes: at arity and the third layer of its search graph alone holds states ( GiB), and at the measured 540 ns per candidate with candidates per state, we estimate core-hours to certify the best known tree (Appendix § 9.5.3). With a large solution space, a clear objective and machine-checked acceptance criteria, the problem is a natural testbed for agentic optimization (§ 2).
In the remainder of this paper, § 2 states the policy search problem, which is the problem exposed to external participants. § 3 describes the implementation details of the harness, including its submission interface and its guarantees, and § 4 describes the emission to Qualtran for resource estimation.
The PhaseProduct Policy Search Problem
Most of the computational cost in Shor’s order-finding algorithm is in the modular exponentiation subroutine, being controlled modular multiplications on an -bit register (Appendix § 8). Each multiplier and QFT is built from the PhaseProduct (PP) primitive [3], acting as on -bit registers. Splitting each register into chunks of width (the top chunk absorbs the remainder ), and , gives and for the chunk polynomials and . Their product has degree , so its coefficients are fixed by its values at any distinct points (with standing for the leading coefficient ). The coefficient vector for the Vandermonde interpolation matrix of the points with , . Substituting ,
so factors into PhaseProducts with classically precomputed angles . Each acts on evaluations only a few bits wider than , formed in place from the chunks by reversible additions, negations and shifts and undone afterwards, at cost, so the recursion gives (see Appendix § 8.2.2).
Definition 2.1 (Interpolation table). An interpolation table consists of an arity , an ordered list of evaluation points in , where evaluation at selects the leading coefficient, and a program of arithmetic operations (including shifts, negations, and scaled additions, as explained below), and checkpoints on registers. The -th checkpoint applies the child PhaseProduct with angle .
Definition 2.2 (Policy). A policy is an ordered list of pairs , where each is an interpolation table and the register-width thresholds satisfy . For a PhaseProduct on -bit registers, the policy selects the first table with . If no such table exists, it selects the schoolbook construction.
To define the basic arithmetic operations that constitute a program in a table, write for the current register values, each an integer linear combination of the initial chunks or . The arithmetic instructions act as
where , for scaled addition, , and is a nonnegative integer. Registers not targeted by an instruction remain unchanged. A right shift is permitted only when every coefficient of the symbolic expression for is divisible by , ensuring exact division for every input without discarding nonzero bits. The program starts with and is applied identically to the chunks of the other operand . At each checkpoint, the child PhaseProduct acts on the corresponding pair of registers, changing only their phase and leaving their arithmetic values unchanged. The register widths needed to implement these operations without overflow are determined separately by the width scan.
For example, consider the policy , where and are interpolation tables of arity 3 and 2, respectively. It selects for , for , and the schoolbook construction for . After selecting a table, the implementation checks whether its decomposition reduces the register width and falls back to schoolbook if it does not. For a given input width , all PhaseProduct operations at recursion depth share width . A legitimate policy must ensure that each table satisfies
C1 there are exactly points, one per coefficient of
C2 the points are distinct, so the interpolation matrix is invertible and (1) holds
C3 running the program from the initial state, each instruction ensures no right shift discards a nonzero bit, the -th checkpoint finds its register holding exactly the evaluation row of , and every point is consumed, in order
C4 the program returns every register to its initial value
and that its thresholds satisfy . Thus, the recursive steps induce an arity sequence , with and , terminating in the schoolbook construction at recursion depth . Figure 2 shows a table and the recursion it generates. In the harness implementation we require that these basic properties that make a policy legitimate be formally proven in Lean (§ 3.1).

Figure 2. Schematic recursive PhaseProduct policy. (1) An policy (Definition 2.2) pairs register width thresholds with interpolation tables (Definition 2.1), specifying one recursion level number of chunks (arity) , ordered interpolation points and a program of scaled additions, negations, and shifts. The first table decomposes a PhaseProduct on -bit registers with , so widths from induce an arity sequence down to a base level . For as shown here, thresholds with tables of arity 3 and 2 (the latter from Appendix § 8.2.2) give an arity sequence and . (2) A Lean-verified table is decomposed with interpolation points . The table uses 11 scaled additions within program blocks . (3) At each (numbered) checkpoint, a child PhaseProduct of width is instantiated and decomposed by the width-selected table, recursing until the base case leaves. Total T-count sums arithmetic and leaf operations (Eq. (2)). The Lean gate-count bound (Theorem 3.2) holds for every valid policy.
We restrict attention to policies that use at most one table for each arity for some maximum arity given a priori. For a table within a policy, for a given we fix the set of interpolation points to that of KMY [3], so a table chooses only their traversal order within and its program . We further take each child width to be the same given a parent width . We recognize this as a restricted family of policies, as opposed to the set of all valid policies. Even optimizing within this family, by numerical experiments we discover practical intractability for exact methods. As such, the full policy optimization problem is at least as hard as the restricted policy search problem considered in this paper. Each table associated with arity determines a child width function denoted as , whose value is approximately plus ancillary bits accounting for register growth during its program. Starting from , a policy selects arity at level and sets . We require at every recursive level. At depth , the remaining products are computed by the schoolbook method, with operations per product. As we detail below, we consider a restricted family of PhaseProduct schedules, retaining a constant at a given recursion level, with interpolation points defined from KMY [3 Appendix F. 2].
For each selected table , define its arithmetic charge as , where , , and count scaled additions, scaled subtractions, and explicit negations, respectively, in the full program, including restoration. The weights reflect the benchmark’s negate-add-negate implementation of subtraction. Shifts incur no direct arithmetic charge, and recursive calls at interpolation points are costed separately. The charge weights and width scan are detailed in Appendix § 9.2.2. Under the T-count model of § 4, the policy has cost
where and is the number of PhaseProduct instances at level . Here, is the total base-case T-count for schoolbook products of width , including the synthesis cost of rotations and their associated logical ANDs (Eq. (5)).
The policy search problem is the following constrained optimization problem. Given an input register width , a maximum arity , and the fixed interpolation point set for each arity, find an admissible policy that minimizes the total T-gate count in Eq. (2) for a PhaseProduct on -bit registers. The optimization jointly chooses (i) which arities to use; (ii) for each chosen arity, an ordering of its fixed point set and an admissible program , defining a table ; and (iii) the width thresholds and table assignments defining the policy’s bands, with schoolbook multiplication used when no band applies. At most one table per arity may be selected here. Meanwhile, the exact algorithm of Appendix § 9 relaxes this and lets every recursive call choose its own table, letting its optimum lower-bound the optimum of the problem stated in this section. The challenge as constructed does not require one table per arity. The objective includes both the arithmetic charges at all recursive levels and the total schoolbook leaf cost, rather than merely the cost of an individual table. Thus, the policy search problem optimizes over a restricted class of the policies in Definition 2.2. We optimize over the larger class of independent recursion trees in Appendix § 9.
Why is this problem difficult? First, the space of programs is unbounded within a table, so a program can visit the points in any order, write to any of the registers, keep partial sums between points, and scale by arbitrary shifts. The cost of computing the evaluation at the next interpolation point depends on the values currently stored in the registers, including intermediate results retained from earlier computations. Second, a table is evaluated by the total cost of the recursive circuit it induces, not merely by the length of its program. A program with fewer additions may produce wider inputs at its checkpoints, increasing the cost of the recursive child calls and their descendants. Thus, the cheapest policy need not use the shortest instruction lists. Finally, changing a table affects the cost at every recursion level that uses it. Also, adding an input bit may increase the largest block width for one arity but leave it unchanged for another. These effects can make the cheapest arity switch back and forth as increases. For example, with the exact optimum over independent trees uses arity 2 at , arity 3 at , and , arity 2 at , arity 3 at and arity 2 again at .
We summarize each table by three integers: one measures the cost of its additions and negations, and the other two specify how many extra bits are needed to store intermediate results (Theorem B.3). We optimize in two stages, first finding the cheapest table for every arity and profile, followed by a dynamic program which chooses whether to stop the recursion, or to use a particular table at every call (Appendix § 9.§ 4). The inner layer finds the cheapest table at each arity and width profile. This is performed by exhaustively enumerating skeletons of charged instructions and resolving the free shift amounts exactly by integer feasibility. The outer layer chooses whether to stop or which table to use for each call. Since the cost of leaf rotation synthesis is non-linear in their total number, it carries the total number of rotations as a state. A dynamic program will combine children for each call and apply the price over register widths and number of rotations. We find this program to scale as arithmetic operations, polynomial in , where . Integer feasibility inside the inner layer is solved by the Lenstra–Kannan algorithm [30]. We recover an exact, deterministic algorithm running in time (Theorem B.1), fixed-parameter in the arity bound and not practical for RSA-2048. The exponential cost is in the inner layer, measured in Appendix § 9.§ 5: the search graph for one table is memory-bound, and the time per candidate, 540 ns at arity 8, converts its size into core-hours. We leave further optimization to future work.
We implemented the planner of Appendix § 9 in Fortran 95 (Appendix § 9.§ 4), with the exact closed form and, for , tables built by exhaustive search over the KMY points. Each returned tree and table is re-verified by an independent replay. At it returns the exact optimum in 5.6 s and the optimum over its tables in about four minutes. The cost lies in table construction, where for one arity-8 table at the third layer of the search graph holds states ( GiB, about a 16 GiB machine), and certifying the best known policy is estimated at core-hours (sensitivity span to ) at a measured 540 ns per candidate, against core-hours for the arity-4 decision. At the exact optimal trees reach depth 4 at and , and at depth 6 at . Checking candidate policies in Lean is cheap by contrast, and their T-count follows in closed form from (2). Since the exact method is out of reach at , but we have an explicit objective function and easy machine-checked acceptance criteria, PhaseProduct policy optimization makes a natural target for heuristic search, with ForShor serving as the referee in full algorithmic integration.
The ForShor Harness
Submissions
ForShor separates the development into a fixed harness containing the circuit languages, the correctness criterion, the construction of the order finding circuit and all related theorems, and the emission pipeline. The policy (Definition 2.2) for recursion is the only part a participant provides (Figure 3).6 The harness decides whether submitted policies are valid, and if so the correctness and cost theorems, proved once for all valid policies, apply to the resulting circuit with no further proof.
Figure 3. The verified part of Figure 1 in detail. The order-finding circuit is written in Gate. Its PhaseProduct and QFT subroutines are constructed recursively once every table in the submitted policy passes C1–C4. A verified compiler produces the LowGate circuit from which the intermediate representation is extracted. Figure 2 is an expanded view of the PhaseProduct part of this schematic.
Each policy consists of a list of tables and their thresholds. In Lean, a valid table is formalized as a record ShorLoweringSetup holding , the points, the program, and a proof of each of C1–C4. A submission is a list of such records with their thresholds, together with a proof that the thresholds strictly decrease:
structure ShorPolicySubmission where
bands : List (N × ShorLoweringSetup)
sorted : (bands.map Prod.fst).IsChain (· > ·)
A policy is valid when it can be packaged appropriately, where every band’s table satisfies C1–C4 and the thresholds strictly decrease.
Guarantees for Every Submission
From a valid policy and an order-finding instance , the harness builds an order-finding circuit . The following theorems are proved once for every valid policy.
Theorem 3.1 (Correctness, generic in the policy). Let be any valid policy and any order-finding instance . Let be run at any precision , where is the threshold fixed by the harness, which costs extra work qubits. Then
The bound is half that of the ideal circuit with exact modular exponentiation. The fast QFT is exact and the lowering preserves the state, so the whole loss comes from the approximate multiplications (Appendix § 8.§ 4). The prescribed precision is chosen so that their accumulated error costs at most half the ideal bound, requiring extra work qubits (leaving the total work qubits count unchanged).
The second theorem bounds the size of the same circuit. The lowered gate count of is the cost of the LowGate circuit under the harness’s cost model, which charges each elementary gate as one and each arithmetic gate linearly in its register width.
Theorem 3.2 (Gate count, generic in the policy). Let be any valid policy with , and let be the number of chunks of . At every precision at which the work register has qubits, the lowered gate count of is , where is the bit length of . In particular this holds at the precision of Theorem 3.1.
Corollary 3.3. For every there is a such that every valid policy whose first table has chunks yields an order-finding circuit with gates.
The count is of the lowered circuit, so register extension, workspace management and the base case are all charged, and the prescribed precision adds only qubits, leaving the exponent unaffected. The lower bands of a policy act only on instances of bounded width, so they change the constant and not the exponent. The bound is on the same lowered circuit as Theorem 3.1, under the same hypotheses. § 4 evaluates more concrete resource estimations of the emitted circuit in Qualtran for one-band and varying- policies.
Proof Architecture
We now describe how the harness establishes these guarantees, and why the proofs apply to every valid submission. The development has three layers, as shown in Figure 3: i) The algorithmic layer is written in Gate, a high-level language in which the QFT and PhaseProduct are single primitives, the latter with the semantics . Two circuits live here. The ideal order-finding circuit uses an exact modular-exponentiation oracle, and the success argument of Shor’s algorithm, including the continued-fraction postprocessing, is proved for it once. The implemented circuit replaces the oracle by the fast modular multiplier of Appendix § 8.§ 4, built from these primitives, and is proved to approximate the ideal one. Neither argument depends on how PhaseProduct is implemented. ii) The compiler layer lowers Gate to LowGate. This is where the recursive constructions live and where the submitted tables enter, and the compiler is itself proved correct, so every guarantee established at the Gate level transfers to the lowered circuit. iii) The lowered gate layer is the LowGate circuit of elementary gates and width-indexed arithmetic. The gate-count theorem is proved against its cost model, and the intermediate representation of § 4 is extracted from it.
Recursive constructions live in the compiler. It replaces each Gate-level QFT by its Cooley–Tukey decomposition into two half-size QFTs joined by a PhaseProduct (Appendix § 8.§ 3), and each PhaseProduct by its Toom–Cook decomposition into smaller instances surrounded by interpolation arithmetic, recursing until the direct implementation is used. Its correctness therefore rests on the correctness of these two recursive decompositions, each proved to have the semantics of the primitive it replaces. Previous work by Nanniyur and Jayanti [31] worked to formalize classical Toom–Cook multiplication. We focus on formalizing quantum Toom–Cook from first-principles in Lean, as well as its integration in PhaseProduct and in Shor’s order-finding.
Theorem 3.4 (Compiler correctness). Let be any valid policy and a Gate circuit of the order-finding construction. For every state whose ancilla qubits are clean,
Here, eval and evalL are the evaluators for the Gate language and the LowGate language respectively. When a submitted policy, which enters the compiler(Figure 3), reaches a PhaseProduct, it selects the band for the current register width and decomposes by that band’s table, or uses the direct implementation if no band applies or the table does not reduce the width. Everything else is identical across submissions, so Theorem 3.4, and with it the theorems of § 3.2, holds for an arbitrary valid policy.
Translation to Qualtran
The verified circuit lives in Lean, while resource estimation is performed in Qualtran [15]. Qualtran has previously been used for resource estimation, allowing for scalability through symbolic gate calculation, including for the Toom-Cook multiplication we consider here [5]. We bridge the gap between Lean and Qualtran by exporting a lowered order-finding circuit from Lean as an intermediate representation. Since Lean is designed for constructing and checking proofs, not for large-scale computation, evaluating a circuit for order-finding of a 2048-bit number inside Lean would be extremely slow and memory-intensive. By exporting a compact symbolic description of the circuit, with recursive components such as the PhaseProduct and the QFT described by their recursive rule and auxiliary values like subproblem widths and phase coefficients exported as lookup tables, Qualtran can evaluate the description and perform logical resource estimation. The IR is extracted from the same Lean definitions as the correctness theorems, translated into a small language of primitive operations, register expressions, and recursive calls. Because the IR is derived from the verified definitions rather than from a separate implementation of the algorithm, the circuit that Qualtran prices is the circuit that was proved correct.
The formal verification ends where Qualtran begins. Once emitted, the IR is read by dictionaries that map tags, vocabulary, and operator names to a hard-coded analog in Qualtran. Leancentric primitives of Gates and LowGates are mapped to to Qualtran ‘Bloqs,’ being sequences of operations executed on a quantum register, with a parameterized easing scalable resource estimation by eliminating the need to walk a true circuit. Composing these Bloqs according to the Lean-emitted pattern allows for a numerical resource estimate for the number of phase rotations, Clifford gates, and Toffoli gates.
Upon conversion to Qualtran, we construct the full order-finding algorithm with numerical verification for each subroutine by operator distance for small instances , tracking accumulated phase, and gate count alignment upon decomposition to Toffoli gates, Clifford gates, and controlled rotations. For a numerical T-gate count estimate, we set a global error of for the order-finding algorithm, partitioning half () to rotation angle synthesis. Logical T-gate count uses Ross-Selinger synthesis [32]. With a per-rotation error allocation for the rotations of the whole order-finding circuit, each rotation is charged T-gates, the mean Ross-Selinger cost (confirmed with pygridsynth [33] on sampled angles). Logical T-gate count therefore has an additional scaling due to rotation synthesis.
For a given and , the recursion depth is optimized for a minimum T-count, and is compared to a custom policy with varying at each level in the recursion, reoptimized at each . At the main product is decomposed as over three recursive layers. This policy is not proven optimal and is the focus of future research (§ 2). For constant , we vary integer size , performing a least-squares fit on a range of integer sizes to represent an ‘asymptotic region,’ fitting with some constant , compounding constant factors from additions, multiplications, and synthesis. Results are presented in Figure 4.

Figure 4. Logical T-gate count of Shor’s order-finding algorithm using a PhaseProduct construction of Toom-Cook multiplication and QFT. Following a single -arity brings a best-found T-gate count at with T-gates, with asymptotic improvements for larger favoring higher . Upon using a varying- policy for PhaseProduct (different at different levels in the recursion), a lower T-gate count is identified with T-gates. Least-squares fits assert the derived exponent and fit a constant prefactor to each curve in an asymptotic region . Results are compared to previous instantiations of order-finding, such as Beauregard [36] [36] (brown dash), Häner-Roetteler-Svore (2016) [37] using a ripple-carry addition circuit [38, 39] (red dash), the same Häner-Roettler-Svore implementation swapping a Fourier addition subroutine [40] with an approximate QFT set at the published error (purple dots), the short discrete logarithm algorithm method of integer factorization of Gidney and Ekerå [2], and our calculated error (orange dot-dash). Without additional optimizations, we find that using PhaseProduct multiplication crosses the short DLP work of Gidney and Ekerå for a modulus size around 3.8 million bits.
The current resource estimation lies well above discrete logarithm methods for integer factorization [2]. The structure here is fairly straightforward in the substitution of QFT and multiplication routines by incorporating PhaseProduct.
Significant optimizations are available through compounding optimizations similar to current efforts, such as incorporating other synthesis techniques (fallback [34], catalysis [35]), zero-ancilla multiplication [3], approximate QFTs, and physical hardware considerations. More advanced structural optimizations like windowed multiplication [2] may also be applicable with broader implementations, highlighting the improvability of the current resource estimates as formally verified routines evolve. When compared with another reduction of integer factorization, namely the work of Gidney and Ekerå [2] for short discrete logarithms (Figure 4), we note the T-gate advantage requires an excessively large modulus size of bits. As such, additional optimizations are necessary if the current implementation of Shor’s order-finding algorithm is applicable at cryptographically relevant modulus sizes like . When implementing improved instantiations of Shor’s algorithm, a researcher engaging with the challenge can input and compare their work at ForShor.ai.7 This online interface allows for dynamic, rapid growth using the ForShor harness with a Qualtran resource estimation backend for quantitative comparison.
Limitations and Future Work
Although we prove algorithmic correctness and an asymptotic complexity of in Lean, we do not explicitly prove Lean-to-Qualtran faithfulness, relying on independent numerical validation of each subroutine’s action to double precision. Phase rotations are converted to T-gate estimates by allocating a per-rotation error and charging the mean Ross-Selinger cost per rotation (§ 4). This provides an upper-bounded T-gate count estimate, with optimization available with alternative synthesis techniques such as fallback [34] and catalytic embedding [35]. Numerical resource estimates across modulus sizes agree with the Lean-proved asymptotic scaling, but are themselves downstream of formal verification. Further, we leave physical resource estimation to future work, including magic state distillation/cultivation [41, 42], routing [43, 44], and error-correction [45, 46]. The exact optimizer of Appendix § 9 uses a theorem that is functional for free interpolation points, but we limit our implementation to the closed form and, for , tables built from the KMY points. The compute-time projection rests on measured layer sizes (floors) and a growth law validated at small slack, and is proportional to a time per candidate that we measured once (about 540 ns at arity 8, on a shared machine). We recognize, however, that if the time-per-candidate was even one picosecond (the timescale for a transistor to flip a zero to a one), it would still take an estimated core hours to exactly enumerate all candidates for .
While the work here focuses on Shor’s order-finding algorithm, the optimization we focus on is the multiplication subroutine. Multiplication has applications across integer factorization algorithms and beyond, including short discrete logarithms [2] and Regev’s algorithm [47]. The latter carries an base gate complexity, requiring iterations with efficient post-processing, giving a baseline total quantum complexity. This is attractive when compared to the base complexity of other integer factorization algorithms and questions the applicability of order-finding. Future work aims toward quantitative resource estimation for Regev’s algorithm along with the adaptation of PhaseProduct as a modular multiplication subroutine to comprehensively search algorithmic implementations.
For a consistent implementation by which T-count can be estimated, we utilize exact QFTs and ripple-carry adders [38]. Future work targets alternative subroutines to reduce T-count further, such as approximate QFTs [48] and alternative adders such as Fourier adders [40] or carry-lookahead adders [49]. In practice, approximate operations like approximate QFTs trade significant resource overhead for a small, partitioned error. Quantitative resource estimation incorporating these primitives will allow for direct comparison of quantum algorithms collectively aimed toward cryptography, guiding understanding as their utility comes into scope. Along with a highly-specified subset of valid policies for PhaseProduct requiring all children have the same working width, the use of a restricted set of interpolation points, picking a table from register width alone, and using the same policy for every modular multiplication instance are various extensions that can further expand the search space and improve T-gate count. The constructive nature of the ForShor harness allows future research to treat the order-finding architecture as modular. In this way, future efforts can swap out adders and QFTs, relax the policy constraints imposed currently, and later incorporate synthesis and larger algorithmic improvements while retaining clear validation criteria. We pose this as one of the greatest strengths of the present framework, currently scoped to exhibit a singular optimization, being fast multiplication.
Conclusion
ForShor is a Lean 4 harness that formally validates and construct Shor’s order-finding algorithm using recursive Toom-Cook PhaseProduct and a Cooley-Tukey QFT, resulting in an algorithm with asymptotic gate complexity of . The harness checks validity, preserves circuit semantics, and writes an intermediate representation that can be read into Qualtran for logical resource estimation. By explicitly defining the algorithmic construction, we allow for contributors to more easily make improvements and optimizations, with formalized details such as finite-width signed arithmetic and padded registers within an operator’s recursion lifting difficulties typical of manuscript-level algorithm descriptions.
Formally verifying the quantum circuit, we use an intermediate representation to map its construction in Qualtran. At , Ross-Selinger synthesis results in T-gates with a custom program with varying in the recursive definition. Toom-Cook -arity varies with modulus size , with direct impact on logical resources following Kahanamoku-Meyer and Yao’s asymptotic complexity analysis [3]. ForShor focuses on accessibility and optimization of the design space, supporting agentic search for improvement while ensuring fast, formally verified algorithmic correctness. The challenge is open at ForShor.ai.5
Acknowledgement
We thank Gregory Kahanamoku-Meyer and Peter Shor for helpful discussions. YC recognizes Unitary Foundation for early support in the project (grant awarded with title “Quantum factoring resource estimation”), which led to an initial publication [5] describing a Qualtran implementation of PhaseProduct with and provided a basis for the subsequent collaboration between Zapata Quantum and University of Maryland [50] that created ForShor.
Background and Algorithmic Overview
ForShor follows standard textbook constructions for the reduction from factoring to order finding, the quantum order-finding circuit with continued-fraction post-processing, and modular exponentiation through repeated controlled modular multiplications [1, 51, 52]. We omit a detailed account of these standard components and focus on the arithmetic and Fourier-transform constructions used to implement the circuit efficiently.
The accompanying website8 presents the ForShor development as a graph of Lean declarations, files, and their dependencies. Throughout this appendix, we identify selected graph nodes corresponding to the mathematical objects being introduced, allowing readers to follow the construction alongside its formalization. We begin with PhaseProduct, describe its asymptotic improvement using Toom-Cook arithmetic and the corresponding recursive QFT, and then explain the in-place modular multiplier and the gate complexity of the complete order-finding circuit.
PhaseProduct
The controlled in-place modular multiplication of Section A.4 ultimately relies on a multiplication primitive expressed through phases. This operation, called PhaseProduct, applies a phase proportional to the product of the values stored in two registers. On computational-basis states, it has the form
for an appropriate phase parameter . A direct implementation follows from expanding
where here denotes the -th bit. For each pair of bits and , the circuit applies a corresponding controlled phase rotation. Thus, for two -bit registers, the naive construction uses pairwise phase operations. On the ForShor proof graph [53], this construction can be found by following
PhaseProduct Gates NaiveLeaf.
The NaiveLeaf node contains the direct PhaseProduct construction described above.
This quadratic construction is sufficient for correctness, but using it inside modular multiplication is insufficient for achieving the asymptotic improvement targeted by ForShor. The next subsection describes how Toom-Cook multiplication is adapted to obtain a faster PhaseProduct.
Fast PhaseProduct using Toom-Cook Arithmetic
The faster PhaseProduct construction used in ForShor is based on the Toom-Cook multiplication method. We first briefly recall the mathematical idea behind Toom-Cook before describing how it is adapted to PhaseProduct.
Toom-Cook Multiplication
Toom-Cook is a divide-and-conquer method for multiplying large integers [4, 54]. For a splitting parameter , each input is divided into smaller chunks. These chunks are viewed as the coefficients of two polynomials,
Multiplying the original integers can then be reduced to determining the coefficients of the product polynomial , which has degree at most .
Instead of directly multiplying every pair of coefficients, Toom-Cook evaluates and at suitable points, multiplies the corresponding values, and then interpolates these results to recover [4, 54]. Thus, one multiplication problem is reduced to smaller multiplication problems, together with the work required for evaluation and interpolation. Recursively applying this idea gives the recurrence
and therefore an asymptotic multiplication cost of
The purely mathematical part of this construction can also be followed in the ForShor proof graph [53]. Starting from the PhaseProduct node, follow
PhaseProduct Math ToomCook.
The ToomCook node contains the mathematical definitions and results underlying the splitting, evaluation, and interpolation steps described above. These results are independent of the quantum circuit construction. We now explains how this multiplication strategy is adapted to obtain an asymptotically faster implementation of PhaseProduct.
Fast PhaseProduct
The Toom-Cook idea described above can be adapted directly to PhaseProduct, following the construction of KMY [3]. The evaluation points are the same as in Toom-Cook, but instead of explicitly reconstructing the product , the evaluated values are used to break the phase into several smaller phases.
Split and into chunks of width and evaluate the chunk polynomials and at points . The product has degree at most , and substituting gives for its coefficients . The values are evaluations of this polynomial, so for the interpolation matrix of the points, and therefore
Hence
Each factor on the right is itself a PhaseProduct, on values whose sizes are roughly a factor of smaller [3]. The same construction can therefore be applied recursively. At each level, one PhaseProduct is replaced by smaller ones, together with the reversible additions and shifts required to form the evaluations and in place. Once the registers become sufficiently small, the recursion stops and the naive PhaseProduct of Section A.1 is used as the base case.
The case . Figure 5 illustrates one level of this recursion for , the Karatsuba case. Each -bit input is split into a low chunk of bits and a high chunk,

Figure 5. One level of the Toom-Cook PhaseProduct for . The numbered boxes are the steps of Table 1, with , and the coefficients listed there. Each PP box is a single PhaseProduct on the two registers it spans, and each is itself implemented recursively. The two additions of step 3, and the two subtractions of step 5, are drawn one after the other.
and the chunk polynomials are evaluated at the three points , and , giving the pairs , and . A direct calculation shows that
so the phase factors into three smaller PhaseProducts with coefficients
The circuit applies these three PhaseProducts in turn. The products at 0 and act directly on the chunks and . For the product at 1, the high chunk of each input is first added into its low chunk, the PhaseProduct is applied to the sums, and the additions are then undone, so that every register ends in its original state. The sum may need one more bit than . The figure omits this detail, which is handled by the width analysis.
Interpolation tables.Table 1 records the construction as a sequence of steps: which pairs of registers receive a PhaseProduct, at which point, and which reversible arithmetic is performed between them. Nothing in this record depends on the width : the steps for are the same whether the inputs have 8 bits or 8000. We call such a record an interpolation table. In general an interpolation table for a given consists of
| Step | Operation | Acts on | Point | Coefficient |
| 1 | PhaseProduct | 0 | ||
| 2 | PhaseProduct | |||
| 3 | Add | - | - | |
| 4 | PhaseProduct | 1 | ||
| 5 | Subtract | - | - |
Table 1. The Toom-Cook interpolation table for with points , and , corresponding to the circuit in Figure 5. Each arithmetic step is applied to both inputs.
an ordered list of evaluation points, each an integer, the reciprocal of a nonzero integer, or ;
a program of shifts, negations and scaled additions on the chunk registers, in which each of the checkpoints marks the moment a smaller PhaseProduct is applied to the register currently holding the evaluation at the next point, and after which the program restores every chunk to its original value.
The table does not record the phase coefficients. By the identity above the coefficients are determined by the interpolation points, computed by the harness. It also does not record register widths, the extra bits needed to avoid overflow, or the level at which the recursion stops; Appendix § 9.§ 4 explains that these are derived from the table.
A table is therefore a complete specification of the fast PhaseProduct. Figure 5 further highlights this for the example by showing how each step in Table 1 is mapped onto the PhaseProduct circuit.
Cost. Each of the three smaller PhaseProducts in the construction acts on registers of roughly bits and is implemented by the same construction, until the naive base case is reached. This gives the recurrence
and hence a cost of . For general , a table with points gives the same asymptotic recurrence as Toom-Cook multiplication,
and hence a PhaseProduct gate cost of [3]. Since for , this improves asymptotically on the quadratic naive construction.
QFT via Cooley-Tukey Decomposition
The modular-multiplication construction of Section A.4 makes repeated use of the QFT and its inverse. Therefore, accelerating PhaseProduct alone is not sufficient: a quadratic-cost QFT would itself become a bottleneck. Fortunately, the same fast PhaseProduct construction can also be used to obtain a subquadratic exact QFT [3, 55].
The construction follows a recursive Cooley-Tukey style decomposition of the QFT, shown in Figure 6. As in Section A.2.2, consider a -qubit register holding , split into a low chunk of qubits and a high chunk of qubits, so that

Figure 6. One level of the Cooley–Tukey decomposition of the QFT on a -qubit register split into chunks of and qubits. The two smaller QFTs are decomposed in the same way, down to single qubits. The procedure is described in the text.
The QFT maps to . Writing the output in the same way but with the chunk widths exchanged, , the phase separates as
since the remaining term is an integer. Each term corresponds to one operation. The first is a QFT on the -qubit high chunk, which turns into . The second is a cross phase between the low chunk and the transformed high chunk, which is exactly the PhaseProduct of Section A.1 with . The third is a QFT on the -qubit low chunk, which turns into . Because ends up in the wires that held and vice versa, the two chunks are finally exchanged.
Choosing , as in the split of Section A.2.2, makes this construction recursive: each of the two smaller QFTs is decomposed in exactly the same way, until the QFTs are small enough to implement directly. Writing for the cost of the Toom-Cook PhaseProduct on -bit registers, the cost of the QFT therefore satisfies
Since and , the PhaseProduct term dominates, and this exact QFT achieves the same asymptotic gate complexity,
In-place Modular Multiplication
We now turn to the in-place controlled modular multiplication required by the modular-exponentiation circuit. For a classical constant coprime to , the desired operation is
The fast PhaseProduct developed in the previous subsections is the main multiplication primitive used to construct this operation.
To see how PhaseProduct is used, first consider ordinary multiplication by a classical constant. Let an -qubit register hold , with QFT . A PhaseProduct with angle between and the transformed register adds to :
The same idea can be adapted to modular multiplication. The key identity is
The phase therefore automatically discards multiples of : increasing by changes the exponent by an integer multiple of and hence leaves the phase unchanged. To exploit this identity, the phase would need denominator , which would require a QFT over . The QFT on qubits is over instead, so the phases it produces have denominator . Running the construction above in that basis therefore makes the sum wrap around at rather than at : it computes , not . Since is odd, no choice of makes a multiple of , so the reduction modulo has to be done separately. In that basis the construction above adds modulo , not modulo .
KMY uses these observation to construct an in-place modular multiplier from a sequence of QFTs, PhaseProducts, and reversible arithmetic operations [3], and this circuit construction is shown in Figure 7.
The circuit acts on four registers. The input register holds the -bit value , and the work register holds qubits, where is the target error. Two further qubits are used: an overflow qubit , which extends the input register by one bit, and a comparison qubit cmp. Each block is a PhaseProduct which, together with the QFTs on either side of it, adds times the value of one register into the other. The constants are

Figure 7. In-place modular multiplication (Algorithm 1 of [3]). The registers and steps are described in the text.
where denotes the inverse of modulo . The circuit proceeds in five steps:
Compute the fraction. The work register is placed in uniform superposition, is applied between and , and an inverse QFT is applied to . This writes an -bit approximation of into the work register.
Add . On the input register extended by (the carry bit as shown in the figure), a QFT, , and an inverse QFT adds to . Since , the extended register now holds an approximation of either or .
Reduce modulo . A comparison writes into cmp whether the extended register is at least , and is subtracted controlled on cmp. The register now holds , and returns to .
Uncompute the comparison qubit. The subtraction occurred exactly when , so comparing the input register with returns cmp to .
Uncompute the work register. Since the fraction equals , it can be computed from the new contents of the input register. A QFT on , , and an inverse QFT subtract this value, returning the work register to .
Steps 3 and 4 are exact. The only approximation is that the work register holds to bits, while is a fraction with denominator that bits generally cannot represent exactly. The resulting error in is at most about , so each extra bit beyond halves it, and qubits suffice [3].
The important feature for our purposes is that the multiplication-intensive components of this construction are PhaseProducts. The naive PhaseProduct would therefore give a quadratic multiplication cost, whereas replacing it with the recursive Toom-Cook PhaseProduct from Section A.2 yields a subquadratic modular multiplier. For a fixed splitting parameter , its gate cost scales as
The controlled version of this can be implemented by using Controlled-PhaseProducts and leaving the arithmetic operations unchanged would do no harm since they uncompute. Thus, there is only a small constant overhead to this construction. Modular exponentiation applies one such controlled multiplication for each exponent bit. Thus, an -bit exponent requires controlled modular multiplications. The subquadratic improvement obtained for PhaseProduct therefore propagates through modular multiplication and ultimately to the complete modular-exponentiation circuit.
The same construction can be followed in the ForShor graph [53] by opening the top-level ModularExponentiation node. Within this node, the Circuit node contains the concrete implementation of Algorithm 1 from [3]. The Proofs node contains the formal verification of this construction, including several intermediate lemmas establishing the correctness of the individual steps of Algorithm 1. Within Proofs, the FinalModMul node contains the final approximation theorem about the In-Place Controlled Modular Multiplication, which bounds the error between the implemented finite-precision modular multiplication circuit and the corresponding ideal modular multiplication.
Order Finding with gates
The components of the previous subsections combine as follows. For a fixed splitting parameter , the fast PhaseProduct and the recursive QFT each cost gates, the in-place controlled modular multiplier inherits the same bound, and modular exponentiation applies such multiplications, giving for the complete order-finding circuit. Choosing large enough that gives . § 3.2 carries this argument out over the harness’s gate-count function on the lowered circuit.
The final construction and its proof can be followed in the ForShor proof graph [53]. The top-level Shor node contains the complete order-finding circuit and its correctness proof. The resource analysis can be followed through the Gate_Count node. Within it, Shor_GateCount contains the final whole-circuit asymptotic argument establishing the gate bound.
Complexity of the Policy Search
Here we organize the policy search around a classical algorithm that can guarantee an exact, T-optimal policy within the problem’s constraints, alongside an estimate for the cost of running said algorithm for . A recursive PhaseProduct may choose a different Toom-Cook table at every call, with each choice of table changes the arithmetic and the width of lower recursions. The cost of synthesizing the leaf rotations can then be calculated for an entire tree search. The algorithm below optimizes over independent choices at every node, over all finite, legal table programs, and over integer and reciprocal-integer interpolation points (Theorem B.1). The exponential factor resides in constructing the cheapest table at a given width, while everything else scales polynomially in (Section B.5).
Preface: A human summary
A PhaseProduct on -bit registers is split into chunks and evaluated at interpolation points, each evaluation a smaller PhaseProduct. A table is the order of additions, negations and shifts that forms those evaluations in registers, restoring their values at the end. Each addition is charged once at the child width. In a standalone T-gate optimization, shifts are free but widen registers, so a cheaper table can make every descendant more expensive. The recursion therefore couples its levels, with rotation synthesis cost of the leaves coupling the whole tree.
Here, we build an algorithm that decides at each call whether to stop the recursion, or to choose a table over all finite legal tables. An outer layer is a dynamic program over register widths and leaf-rotation count, combining the children of every call and applying the synthesis cost once. This dynamic program is polynomial in and runs in seconds at once the tables are known. The inner layer constructs those tables for each arity and width , finding the cheapest table by exhaustive search in time complexity for a maximum, manually set arity . We benchmark this inner layer, with a flowchart of its process in Figure 8.
Figure 8. Flowchart of the exact planner (Theorem B.1). Step 2, the construction of the cheapest table at each width, is the bottleneck: one call of Algorithm 2 per profile (right). The outer dynamic program (steps 3–5) is polynomial in . The status is OPTIMAL only if the independent replay passes and every arity has a complete catalog (today arity 2); otherwise catalog-OPTIMAL. A timeout or memory exhaustion is reported as incomplete, never as “no table exists”.
We wanted to estimate how long it will take to make a T-gate optimal policy using the algorithm construction given below. As such, we focus on the number of states the search visits, the number of candidate moves per state, and the time per candidate . We model or exactly calculate the number of states visited and the number of candidate moves per state, converted to core-hours by , which we note is both hardware and software dependent. Here, we run GNU Fortran 16.2.0, -O3 -std=f95 on an Apple M5 Pro (18 logical CPUs, 24 GiB, macOS 27.2).
We measured ns at arity 4, where the tables fit in cache, and ns at arity 8, in one run on a shared machine under memory pressure (wall seconds times shards, divided by the candidate evaluations). Using 540 ns, we find that for a maximum arity , the memory and time floors and the estimates for certifying the best-known tree are: needs at least GiB for any search that stores its states, and an estimated core-hours (sensitivity span to ); needs an estimated core hours (span to ).
We do not implement the optimization for freely chosen interpolation points, only covering Appendix F.2 of Kahanamoku-Meyer and Yao [3]. The Fortran 95 implementation covers the closed form and, for , catalogs of tables built from the KMY points, with a projection for unit-weight operations. This preface was written by a human, and the subsequent sections with AI assistance and edited for clarity. We give proofs for the construction along with a Fortran 95 benchmark below, but have not formally verified the proofs themselves. The resulting policies from the Fortran 95 constructions pass the conditions presented in the main text, ensuring validity.
Problem Restatement
Trees and tables
At each “node,” we will have a register width of , which will either be evaluated by a “leaf,” being the schoolbook multiplication method, or it will split according to an arity into children with width , and will have a table () associated with it. Each child continues independently, so siblings and equal widths do not need to agree. Fix , . A table acts on rows , initially the rows of (integer coefficient vectors) and must return them to . Its instructions are , (exact over ), , (). It checkpoints each of projectively distinct tokens (integers, reciprocals of integers, , ) exactly once, in the literal evaluation row , where sign and scale matter and are not free.
Charge and width
The charge is (additions, subtractions as negate-add-negate, negations); shifts and checkpoints are free. For , , the counters start at and update as (shift), (division), (negation), (addition); the child width is of every counter at every instruction boundary, initial and final included.
Cost
An internal node with table and child width pays (two operand registers, four T gates per adder); a leaf of width contributes rotation units. With , , (evaluated in exact integer arithmetic) and ,
For a shared-table policy (one table per arity, uniform levels) this is
The constants are: (four T gates per And, two operand registers); Ands per -bit adder; charges 1, 3, 1 (subtraction is negate-add-negate); the Ross–Selinger rotation cost [32] at , , which gives the 100 and the exact integer form . Using the width-40 tree as an example, pricing its three leaves separately instead of once gives 84,815 in place of the correct 92,750.
Problem Structure and Hardness Context
With tables choosing their own points, , so the language is sparse and NP-hardness under many-one reductions would give P = NP (Mahaney [56]; Mahaney.tableOpt_barrier). With the points supplied as inputs, the structural problem is NP-hard at , by SAT DHC2 EHC POINTSTABLEOPT (Pts.genLang_NPHard); its hard instances use point sets the benchmark does not admit. For the T-count, stopping at the root costs , so the unary decision language is sparse and NP-hardness would imply P = NP. Nowhere in this appendix do we prove T-count optimization is NP-hard, in general or for the KMY points.
End-To-End T-gate Count
Theorem B.1 (Exact free-point independent-tree algorithm). In the model of Section B.2, and given the Lenstra–Kannan integer-feasibility bound (6) for the solver of Algorithm 2, Algorithms 2 and 1 return and an expanded optimal tree with a witness table at every internal node, in
A conservative form is time and bits of storage for a fixed constant . As tested, we use bits.
Remark B.2 (Parameterized, not practical). The theorem is fixed-parameter tractability in for numerical width . It is not jointly polynomial in and , and the factor comes from exhaustive symbolic synthesis. The imported bound is that integer feasibility in variables and binary length is decided in
((Lenstra–Kannan [30]; Goemans–Rothvoß, Sec. 3, Thm. 4 [57]).
The proof has four steps, each using only the previous ones: (1) compress each table to a profile (Theorem B.3, Lemma B.4); (2) synthesize the cheapest table at every profile (Lemma B.5, Algorithm 2), the bottleneck; (3) plan by a dynamic program over (width, leaf-unit count) (Theorem B.6, Algorithm 1); (4) assemble (Section B.5).
A table as a 3-tuple
Theorem B.3 (Two-integer profile). Every arity- table has unique integers , , , with for ; and are the historical peaks of the counters started from and . If componentwise, prefixing , , , yields profile exactly at unchanged charge.
The proof uses the norm invariant : no legal division reaches the clamp at 0. Replacing a table by a minimum-charge table with the same keeps the number and widths of all children, hence every continuation and the count , and weakly lowers ; only matters.
Lemma B.4 (Charge ceiling). Every attainable profile has a representative of charge at most , .
A potential argument gives #charged instructions and ; for the explicit fallback table (charge , profile ) is padded to .
The cheapest table at a profile: the bottleneck
Lemma B.5 (Complete local synthesis). Algorithm 2 returns and an attaining table, in time when the budget is at least and below it.
Why unbounded shifts do not escape the search. Normalize every addition to the macro , , with and primitive rows between macros; this preserves charge, checkpoints, restoration and every peak, and under cap all immediates lie in . High budget (): if the fallback fits; otherwise and skeletons immediates are enumerated, . Low budget (): a skeleton fixes the charged instructions and leaves immediates unknown; every matrix entry is a signed sum of powers of two with affine exponents. Exponents within a gap are resolved exactly; farther clusters have strictly increasing 2-adic valuations, so correctness is a finite union of integer systems. Realizable sign patterns are faces of an arrangement of hyperplanes in dimension , at most , each decided by integer feasibility in variables [5].
Planning the recursion
For let be the least internal cost at width with exactly leaf units; the leaf gives , and for each finite interface , with , ,
Since is nondecreasing, any tree no costlier than the root leaf has and , which bounds the arrays.
Theorem B.6 (Planner correctness). With complete interface minima, Algorithm 1 returns the optimum (4) and an attaining independent-node tree, using arithmetic operations on -bit numbers.
Induction on shows is the least total internal cost of independent children with total count ; induction on covers every feasible tree, and applying once at the root is exact. Dominance pruning of child widths (skip when a smaller width of the same table has a frontier that dominates it pair by pair) is exact and needs no monotonicity of frontiers.
The arity-two optimum
Theorem B.7 (All arity-two profile minima). for and for , attained by the five-event table chk 0, chk ∞, , chk 1, , with profile and child width ; a shrinking split exists iff .
Theorem B.8 (Forced optimal tree). Let . For every , every optimum stops at a width in and otherwise uses charge four and three children of width .
The result holds inside any exterior tree, despite the global price. For the widths are , so there are leaves, , and (width 40 splits and 41 does not: but ).
Inner and Outer Optimization
The inner layer builds the interface minima; the outer layer is the dynamic program (7), operations for any catalog. Both are exact, so the cost of the algorithm is the cost of the inner layer: per profile in the worst case and, as the next section measures, memory-bound well before cryptographic sizes.
We implemented the planner of Theorem B.1 in Fortran 95 (the exact closed form; the dense recurrence (7) for as a value check; a Pareto planner with exact dominance pruning). Interface minima for come from a separate exhaustive engine, so the benchmark has two parts: the planner, which is cheap, and the table construction, which is not. The table programs are checked three ways: an independent big-integer replay that shares no code with the Fortran, compilation of each distinct table in Lean against the benchmark contract, and pricing of the returned tree by the benchmark’s own T-count scorer. STATUS OPTIMAL is printed only after replay and only if every arity has a catalog declared complete (today only arity 2, by Theorem B.7); otherwise the status is catalog_OPTIMAL, optimal relative to the supplied tables and nothing more.
Execution protocol
We define a grid of cases being the union of 60, 65, …, 255, the squares and (50 widths) , each cell three fresh-process repetitions, plus 12 calibration cases. A cell is launched unless a forecast exceeds 24 h or 16 GiB (median pairwise log–log slope over three widths of equal effective arity, with an upper envelope; screening only); a gated cell is reported as gated, never as infeasible, and no cutoff is imposed after launch. Time and peak resident size come from wait4 usage on one macOS/arm64 machine (Apple M5 Pro, 24 GiB); a cell is accepted only after independent replay. A or 5 cell run with an arity-3 catalog records its effective arity, 3, and is an arity-3 result.
Planner results
Table 2 gives the anchor widths for the planner’s results. The optima equal the closed form and an independent oracle. The costs are optimal over all F2 tables of arity (the points and their reciprocals): a relaxation with one fictitious zero-charge table of profile gives lower bounds equal to the upper bounds at all 50 widths, and exhaustive decisions cover the region it does not (no table with at any charge; none with charge and ; exhaustively tested, one engine). The planner’s wall time grows from to 1024 and to 2048 at , below the worst case because of dominance pruning (measured, two ratios are not a law). These times exclude the offline construction of the catalogs.
| status | wall (s) | peak (MiB) | policy | |||
| 512 | 2 | 9,078,996 | optimal | 0.009 | 5 | uniform |
| 512 | 3 | 7,067,876 | catalog | 0.18 | 9 | uniform |
| 1024 | 2 | 29,008,376 | optimal | 0.21 | 17 | uniform |
| 1024 | 3 | 20,631,296 | catalog | 11.0 | 58 | mixed |
| 2048 | 2 | 92,321,820 | optimal | 5.6 | 126 | uniform |
| 2048 | 3 | 62,297,732 | catalog | 241 | 676 | uniform |
Table 2. Planner on the standard grid (report cost model; median of three fresh processes; one machine). , 5 cells equal (effective arity 3).
Projection: the cost of one table construction
Table construction at a cell asks whether a table with at most unit-weight operations exists when every row has weight (child width ). The engine (Algorithm 3) has as state (row matrix, mask of visited points); a move negates a row or adds a shifted row; a state at depth is kept iff for an admissible bound with ; define the slack . Let be the states first reached after operations. Then
Equations (8) and (9) are exact ((9) matches 219 of 219 measured cells, as measured; the layer law (10) has and over (measured). The time per candidate is a necessary factor of every compute-time figure here: and are counts, and only turns them into core-hours. Even though we test a narrow range of values here, we can therefore model and and leave the measurement of as the only hardware- and software-dependent parameter. We measured ns at (best of three, tables in cache) and ns at : the layer-3 run took 19,487 s on two shards for candidates (measured, one run, wall time on a shared machine under memory pressure, so an upper-side value). Because grew from 41 to 540 ns as the working set (and arity) grew, the 41 ns used for the large arity-4 search is probably optimistic: at 540 ns the arity-4 estimate would be core-hours. The law was tested blind, where before any run we wrote down predicted state counts for three cells not used in the fit, and the exhaustive searches returned ( predicted), () and (), all within a factor 1.10 (measured; slack 4–5 only).
What is a bound. Because , every state at depth survives the prune, so any exact state-space search must generate for every cell with , and larger caps only add legal moves. Hence at least candidate evaluations and bytes if states are stored. Table 3 gives the exact : the memory floor exceeds the 16 GiB gate from and reaches GiB at (cap ; candidate evaluations; the run took s on two shards, 10.8 core-hours, under heavy memory pressure). These are measured floors for state-storing search, and we do not extrapolate for layers beyond 3.
| arity | 4 | 5 | 6 | 7 | 8 |
| cell | |||||
| memory (GiB) | 0.09 | 4.7 | 52 |
Table 3. Measured size of the third layer (states first reached after three operations, smallest cap measured per arity; exact counts).
Projection to RSA-2048: floors, estimates and how they are extracted
Scope. An exact optimizer built on this search must decide at least the cells where a relaxation leaves a gap. To estimate this task, we show that an artificially constructed best-known tree (arity ladder , board cost 9,592,816 T, measured by the board’s scorer) is optimal among all policies. This “best-known tree” at is “artificial” in that it takes the charge to be zero i.e. there are no additions or negations, so the dynamic program strictly finds the minimal number of leaf rotations. Therefore, this tree is impossible to achieve, but gives a loose lower-bound on T-gate cost. Without satisfying conditions C1–C4 as given in the main text, such a policy fails formal verification. The charge is unit weight (every add or negate is one op); the report’s weights give charge in , and free (non-F2) points enlarge the state space, so neither is covered. The extraction is Algorithm 4: it prices the best-known tree, finds by free-table relaxation which arities and caps can matter, turns each remaining gap into a cell , closes cells already below a proven bound, and evaluates (7)–(10) for the rest. Arity 3 closes (no table with ops at any cap , every mod ; exhaustive search; arity 4 has the proven bound at caps . The optimizer is certified optimal over all tables for every benchmark width up to ; above that the cost steps up with the arity needed.
Reading Table 4. Arity 8 dominates, requiring about core-hours at ns ( core-years) against for arity 4. Its state count is the peak of the layer law, , so the exponent scales as . The span’s lower end uses the smallest measured over arities 5–8 (the cell itself: , ); its upper end the largest, with multiplied by the largest depth-drift factor measured on exact unpruned layers (1.10, at ). The arity-4-fit scenario (linear-in- fits at extended to ) gives . No coverage probability is claimed: is measured at one transition for , its drift only at , and the dominant arity-8 cell has slack against a calibrated 3–5. A SAT/CP formulation avoids the memory wall but not the growth: core-hours for arity 4 at the first cap (growth per op from four instances, extrapolated). The conclusion is a floor and a bracket: certifying the best-known tree needs at least GiB at arity 8 for any state-storing search and, under the measured growth law, between about and core-hours; the exponent is not pinned, and the time scale is linear in .
| Arity | Decision (dominant cell) | Floor (measured) | Estimate (core-h) | Lower–upper span |
| 3 | none ops, | closed (exhaustive) | 0 | – |
| 4 | none ops, | (0.09 GiB) | – | |
| 8 | none ops, | candidates (10.8 core-h at 540 ns); GiB | – |
Table 4. Certifying the best-known RSA-2048 tree (unit weight, F2 points). Floors are measured and design-relative; estimates are extrapolated; the span is a sensitivity span, not a confidence interval.
For perspective, the memory requirement of 7.3 TiB is high but achievable using a strong computational cluster as of the time of writing. The computation time however, even the lower estimate for arity 4, would take 7.464 wall years with 1024 parallel nodes and instantaneous I/O, and an impossible amount of time for . We motivate the policy-optimization challenge on these lower bounds, wherein agentically-driven policy optimization will approach the true optimum faster than brute-force enumeration.
Algorithm 1 PLANNER(): exact independent-tree optimization (Theorem B.6)
Require: width ; arity bound ; interface minima with witnesses (Algorithm 2)
;
for do
; ▷ schoolbook leaf
for each finite with , do
;
for do ▷ independent children
end for
, keeping backpointers; discard costs
end for
end for
return and the backtrace (tables and children)
Algorithm 2 MINCHARGE(): cheapest arity- table with exact profile (Lemma B.5)
; ; ; ; ;
for do
fallback table if and ; else DIRECTSEARCH() if ; else SYMBOLICSEARCH()
if then replay ; pad to (Theorem B.3); return
end if
end for
return ▷ only after a complete search; a timeout returns INCOMPLETE
Algorithm 3 DECIDE(): is there a table with at most unit-weight ops? (repository engine)
layer ; store states with full-key hashing;
while and and no goal found do
for each (mask) ; each of moves: negate a row, or , do
child ; skip if a row weight (cap)
skip if already stored, or if ▷ admissible,
store the child in ; if and every point is marked then goal found
end for
; write the exact layer size
end while
return FOUND (replay the path) if goal; NOTFOUND only if the graph was exhausted; UNDECIDED if the state limit was reached
Algorithm 4 PROJECT(): floors and estimates for certifying the best-known tree
over the best-known catalog; read the arities used
relevance: for each replace its tables by a free table (charge 0, child width ), keep iff it beats
cap cut: least cap beyond which free tables do not lower the optimum (tested at )
for each relevant , residue , frontier step with do
cell , , slack
if below a proven bound then cost 0 (closed) ▷ arity 3: ; arity 4:
end if
end for
sum over cells; report the dominant cell; span from the extremes of the measured with the measured depth-drift factor; label extrapolated beyond the calibrated slack
References
- [1]Peter W. Shor. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. In: SIAM Journal on Computing 26.5 (1997), pp. 1484–1509. DOI: 10.1137/S0097539795293172.DOI
- [2]Craig Gidney and Martin Ekerå. “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”. In: Quantum 5 (2021), p. 433. DOI: 10.22331/q-2021-04-15-433.DOI
- [3]Gregory D. Kahanamoku-Meyer and Norman Y. Yao. “Fast Quantum Integer Multiplication with Zero Ancillas”. In: arXiv preprint (2024). DOI: 10.48550/arXiv.2403.18006. arXiv: 2403.18006 [quant-ph].
- [4]Richard P. Brent and Paul Zimmermann. Modern Computer Arithmetic. Vol. 18. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, 2010. ISBN: 9780521194693. DOI: 10.1017/CBO9780511921698.DOI
- [5]Yudong Cao, Manuela Rivas, Shangjie Guo, Aleyna Küçükçolak, and Annan Ma. “Detailed Implementation of Quantum Toom-Cook Multiplication Circuits and Resource Estimation”. In: 2025 IEEE International Conference on Quantum Computing and Engineering (QCE). Vol. 2. IEEE. 2025, pp. 424–425.DOI
- [6]Martin Ekerå and Johan Håstad. “Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers”. In: Post-Quantum Cryptography (PQCrypto 2017). Vol. 10346. Lecture Notes in Computer Science. Springer, 2017, pp. 347–363. DOI: 10.1007/978-3-319-59879-6_20. arXiv: 1702.00249.DOI
- [7]Alexander May and Lars Schlieper. “Quantum Period Finding is Compression Robust”. In: IACR Transactions on Symmetric Cryptology 2022.1 (2022), pp. 183–211. DOI: 10.46586/tosc.v2022.i1.183-211.DOI
- [8]Clémence Chevignard, Pierre-Alain Fouque, and André Schottенloher. Reducing the Number of Qubits in Quantum Factoring. Cryptology ePrint Archive, Paper 2024/222. 2024. DOI: 10.1007/978-3-032-01878-6_13. URL: https://eprint.iacr.org/2024/222.DOI
- [9]Axel Pappalardo, Dahmun Goudarzi, Victor Hertz, Hugo Jacinto, Larissa Kroell, André Schottenloher, Peter Shanahan, Élie Gouzien, Rémi de La Vieuville, and Vivien Londe. “Shor’s algorithm compiled on cat qubits: 22 593 qubits for RSA-2048 in 3.14 days”. In: arXiv preprint arXiv:2610.37839 (2026).arxiv.org/abs/2610.37839
- [10]Layr-Labs. The secp256k1 Point-Addition Challenge. GitHub repository. URL: https://github.com/Layr-Labs/ecdsafail-challenge.
- [11]Paureel. Beyond n log n. Research dashboard (GitHub repository). URL: https://github.com/Paureel/beyond-n-log-n.
- [12]Terence Tao. Mathematics in the age of AI. 2026. DOI: 10.48550/arXiv.2608.16753. arXiv: 2608.16753 [math.HO]. URL: https://arxiv.org/abs/2608.16753.
- [13]Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. “Mathematical discoveries from program search with large language models”. In: Nature 625 (2024), pp. 468–475. DOI: 10.1038/s41586-023-06924-6. URL: https://www.nature.com/articles/s41586-023-06924-6.
- [14]Andi Gu, Alek H. Kemeny, Susanne F. Yelin, and Mikhail D. Lukin. Discovering state-of-the-art quantum circuits with large language models. 2026. arXiv: 2610.22367 [quant-ph]. URL: https://arxiv.org/abs/2610.22367.
- [15]Matthew P Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D Malone, Ryan Babbush, and Nicholas C Rubin. “Expressing and analyzing quantum algorithms with qualtran”. In: arXiv preprint arXiv:2409.04643 (2024).arxiv.org/abs/2409.04643
- [16]Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher J. Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D. Nation, Lev S. Bishop, Andrew W. Cross, Blake R. Johnson, and Jay M. Gambetta. Quantum computing with Qiskit. 2024. DOI: 10.48550/arXiv.2405.08810. arXiv: 2405.08810 [quant-ph]. URL: https://arxiv.org/abs/2405.08810.
- [17]Robert Rand, Jennifer Paykin, and Steve Zdancewic. “QWIRE Practice: Formal Verification of Quantum Circuits in Coq”. In: Electronic Proceedings in Theoretical Computer Science 266 (2018), pp. 119–132. DOI: 10.4204/EPTCS.266.8.DOI
- [18]Junyi Liu, Bohua Zhan, Shuling Wang, Shenggang Ying, Tao Liu, Yangjia Li, Mingsheng Ying, and Naijun Zhan. “Formal Verification of Quantum Algorithms Using Quantum Hoare Logic”. In: Computer Aided Verification. Springer International Publishing, 2019, pp. 187–207. DOI: 10.1007/978-3-030-25543-5_12.DOI
- [19]Kesha Hietala, Robert Rand, Shih-Han Hung, Liyi Li, and Michael Hicks. “Proving Quantum Programs Correct”. In: 12th International Conference on Interactive Theorem Proving (ITP 2021). Vol. 193. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021, 21:1–21:19. DOI: 10.4230/LIPIcs.ITP.2021.21.DOI
- [20]Christophe Chareton, Sébastien Bardin, François Bobot, Valentin Perrelle, and Benoît Valiron. “An Automated Deductive Verification Framework for Circuit-building Quantum Programs”. In: Programming Languages and Systems. Springer International Publishing, 2021, pp. 148–177. DOI: 10.1007/978-3-030-72019-3_6.DOI
- [21]Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. “A Verified Optimizer for Quantum Circuits”. In: Proceedings of the ACM on Programming Languages 5.POPL (2021), pp. 1–29. DOI: 10.1145/3434318.DOI
- [22]Liyi Li, Finn Voichick, Kesha Hietala, Yuxiang Peng, Xiaodi Wu, and Michael Hicks. “Verified Compilation of Quantum Oracles”. In: Proceedings of the ACM on Programming Languages 6.OOPSLA2 (2022), pp. 589–615. DOI: 10.1145/3563309.DOI
- [23]Yuxiang Peng, Kesha Hietala, Runzhou Tao, Liyi Li, Robert Rand, Michael Hicks, and Xiaodi Wu. “A formally certified end-to-end implementation of Shor’s factorization algorithm”. In: Proceedings of the National Academy of Sciences 120.21 (2023), e2218775120. DOI: 10.1073/pnas.2218775120.DOI
- [24]Tanuj Khattar, Nicholas C. Rubin, Craig Gidney, Michael Broughton, Guang Hao Low, and Ryan Babbush. Leveraging verifiable structure in quantum circuits to find more efficient compilations with agentic AI. 2026. DOI: 10.48550/arXiv.2610.23832. arXiv: 2610.23832 [quant-ph].DOI
- [25]Marcos Crichigno and Steve Flammia. “Automating quantum circuit optimization with AI agents”. In: arXiv preprint arXiv:2610:31352 (2026).arxiv.org/abs/2610.31352
- [26]OpenAI. On the Navier–Stokes Millennium Prize Problem. Sept. 8, 2026. URL: https://openai.com/index/navier-stokes-solution/.
- [27]OpenAI. Sharing AI progress in mathematics. Updated October 15, 2026. Oct. 6, 2026. URL: https://openai.com/index/sharing-ai-progress-in-mathematics/.
- [28]Sergey Shirobokov, Ben Jaderberg, Katerina Hristova, George Tsoukalas, Johannes Bausch, Eric Wieser, Francisco J. H. Heras, Nicholas C. Rubin, Guang Hao Low, Sébastien Racanière, Nenad Tomašev, Lei M. Zhang, James D. Watson, Tanuj Khattar, Aws Albargouthi, Stavan Jain, Harun Khan, Leopoldo Sarra, Andrew W. Senior, Michael Broughton, Hussain Masoom, Sergio Boixo, Ryan Babbush, Swarat Chaudhuri, and Pushmeet Kohli. Discovering formally verified quantum programs with AI. 2026. arXiv: 2611.09822 [quant-ph]. URL: https://arxiv.org/abs/2611.09822.
- [29]Marcos Crichigno and Steve Flammia. Automating quantum circuit optimization with AI agents. 2026. arXiv: 2610.31352 [quant-ph]. URL: https://arxiv.org/abs/2610.31352.
- [30]Ravi Kannan. “Minkowski’s convex body theorem and integer programming”. In: Mathematics of operations research 12.3 (1987), pp. 415–440.DOI
- [31]Srihari Nanniyur and Siddhartha Jayanti. “Machine-Verifying Toom-Cook Multiplication with Integer Evaluation Points”. In: arXiv preprint arXiv:2603.14038 (2026).
- [32]Neil J Ross and Peter Selinger. “Optimal ancilla-free Clifford+ T approximation of z-rotations”. In: arXiv preprint arXiv:1403.2975 (2014).arxiv.org/abs/1403.2975
- [33]Shuntaro Yamamoto and Nobuyuki Yoshioka. “pygridsynth: A fast numerical tool for ancilla-free Clifford+ T synthesis”. In: arXiv preprint arXiv:2604.21333 (2026).arxiv.org/abs/2604.21333
- [34]Vadym Kliuchnikov, Kristin Lauter, Romy Minko, Adam Paetznick, and Christophe Petit. “Shorter quantum circuits via single-qubit gate approximation”. In: Quantum 7 (2023), p. 1208.
- [35]Matthew Amy, Andrew N Glaudell, Shaun Kelso, William Maxwell, Samuel S Mendelson, and Neil J Ross. “Exact synthesis of multiqubit Clifford-cyclotomic circuits”. In: International Conference on Reversible Computation. Springer. 2024, pp. 238–245.arxiv.org/abs/2311.07741
- [36]Stephane Beauregard. “Circuit for Shor’s algorithm using 2n+ 3 qubits”. In: arXiv preprint quant-ph/0205095 (2002).arxiv.org/abs/quant-ph/0205095
- [37]Thomas Häner, Martin Roetteler, and Krysta M Svore. “Factoring using 2n+ 2 qubits with Toffoli based modular multiplication”. In: arXiv preprint arXiv:1611.07995 (2016).arxiv.org/abs/1611.07995
- [38]Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton. “A new quantum ripple-carry addition circuit”. In: arXiv preprint quant-ph/0410184 (2004).DOI
- [39]Cody Jones. “Low-overhead constructions for the fault-tolerant Toffoli gate”. In: Physical Review A—Atomic, Molecular, and Optical Physics 87.2 (2013), p. 022328.DOI
- [40]Thomas G Draper. “Addition on a quantum computer”. In: arXiv preprint quant-ph/0008033 (2000).DOI
- [41]Daniel Litinski. “Magic state distillation: Not as costly as you think”. In: Quantum 3 (2019), p. 205.DOI
- [42]Craig Gidney, Noah Shutty, and Cody Jones. “Magic state cultivation: growing T states as cheap as CNOT gates”. In: arXiv preprint arXiv:2409.17595 (2024).arxiv.org/abs/2409.17595
- [43]Nathan Constantinides, Ali Fahimniya, Dhruv Devulapalli, Dolev Bluvstein, Michael J Gullans, JV Porto, Andrew M Childs, and Alexey V Gorshkov. “Optimal routing protocols for reconfigurable atom arrays”. In: arXiv preprint arXiv:2411.05061 (2024).arxiv.org/abs/2411.05061
- [44]Yannick Stade, Ludwig Schmid, Lukas Burgholzer, and Robert Wille. “An abstract model and efficient routing for logical entangling gates on zoned neutral atom architectures”. In: 2024 IEEE International Conference on Quantum Computing and Engineering (QCE). Vol. 1. IEEE. 2024, pp. 784–795.DOI
- [45]Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland. “Surface codes: Towards practical large-scale quantum computation”. In: Physical Review A—Atomic, Molecular, and Optical Physics 86.3 (2012), p. 032324.DOI
- [46]Nikolas P Breuckmann and Jens Niklas Eberhardt. “Quantum low-density parity-check codes”. In: PRX quantum 2.4 (2021), p. 040101.DOI
- [47]Oded Regev. “An efficient quantum factoring algorithm”. In: Journal of the ACM 72.1 (2025), pp. 1–13.arxiv.org/abs/2308.06572
- [48]Yunseong Nam, Yuan Su, and Dmitri Maslov. “Approximate quantum Fourier transform with O (n log (n)) T gates”. In: NPJ Quantum Information 6.1 (2020), p. 26.DOI
- [49]Himanshu Thapliyal, Edgard Muñoz-Coreas, and Vladislav Khalus. “Quantum circuit designs of carry lookahead adder optimized for T-count T-depth and qubits”. In: Sustainable Computing: Informatics and Systems 29 (2021), p. 100457.DOI
- [50]Zapata Quantum, Inc. Zapata and University of Maryland Collaborate to Advance New Paradigm in Quantum Software. Press release, January 12. 2026. URL: https://investors.zapataquantum.com/news-releases/news-release-details/zapata-and-university-maryland-collaborate-advance-new-paradigm.
- [51]Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. 10th Anniversary. Cambridge: Cambridge University Press, 2010. DOI: 10.1017/CBO9780511976667.
- [52]David Beckman, Alamovoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill. “Efficient Networks for Quantum Factoring”. In: Physical Review A 54.2 (1996), pp. 1034–1063. DOI: 10.1103/PhysRevA.54.1034.DOI
- [53]VerifiedQC. ForShor: Shor Verification Proof Graph. https://verifiedqc.github.io/ForShor/.
- [54]Marco Bodrato and Alberto Zanoni. “Integer and Polynomial Multiplication: Towards Optimal Toom–Cook Matrices”. In: Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation. 2007. DOI: 10.1145/1277548.1277552.DOI
- [55]Richard Cleve and John Watrous. “Fast Parallel Circuits for the Quantum Fourier Transform”. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 2000, pp. 526–536. DOI: 10.1109/SFCS.2000.892140. arXiv: quant-ph/0006004. URL: https://arxiv.org/abs/quant-ph/0006004.
- [56]Stephen R Malaney. “Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis”. In: Journal of Computer and System Sciences 25.2 (1982), pp. 130–143.


