betaFeedback

WorksPhysics and Astronomy

Formally verified harness for Shor's order finding algorithm with O(n2+ε)O(n^{2+ε}) gate cost

Abstract

It is commonly understood that factoring a general nn-bit biprime via Shor's order finding algorithm requires O~(n3)\widetilde{O}(n^3) 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 O(n2+ε)O(n^{2+ε}). Here ε>0ε>0 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 nn-bit RSA integer scales as O~(n3)\widetilde{O}(n^3) with schoolbook arithmetic, where O~\widetilde{O} 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 O(n2+ϵ)O(n^{2+\epsilon}) logical gate count for Shor’s algorithm, for every fixed ϵ>0\epsilon> 0 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 n/2+o(n)n/2 + o(n) 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:

  1. 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.

  1. 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 kk), and which operations to perform on those parts (the program, denoted as Π\Pi). 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 88 and n=2048n = 2048 the third layer of its search graph alone holds 2.9×10102.9 \times10^{10} states (7.5×1037.5 \times10^{3} GiB), and at the measured 540 ns per candidate with O(K4)O(K^{4}) candidates per state, we estimate 3.2×10513.2 \times10^{51} 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 O(n)O(n) controlled modular multiplications on an nn-bit register (Appendix § 8). Each multiplier and QFT is built from the PhaseProduct (PP) primitive [3], acting as ∣x⟩∣z⟩↦eiϕxz∣x⟩∣z⟩|x\rangle|z\rangle\mapsto e^{i\phi xz}|x\rangle|z\rangle on ww-bit registers. Splitting each register into k≥2k \ge2 chunks of width h=⌊w/k⌋h = \lfloor w/k\rfloor (the top chunk absorbs the remainder r=w−khr = w-kh), x=∑j<k2jhxjx = \sum_{j<k}2^{jh}x_j and z=∑j<k2jhzjz = \sum_{j<k}2^{jh}z_j, gives x=X(2h)x = X(2^h) and z=Z(2h)z = Z(2^h) for the chunk polynomials X(t)=∑jxjtjX(t) = \sum_j x_jt^j and Z(t)=∑jzjtjZ(t) = \sum_j z_jt^j. Their product C(t)=X(t)Z(t)=∑j=02k−2cjtjC(t) = X(t)Z(t) = \sum_{j=0}^{2k-2}c_jt^j has degree 2k−22k-2, so its 2k−12k-1 coefficients are fixed by its values at any 2k−12k-1 distinct points p0,…,p2k−2p_0,\ldots,p_{2k-2} (with p=∞p=\infty standing for the leading coefficient xk−1zk−1x_{k-1}z_{k-1}). The coefficient vector c=V−1(C(pℓ))ℓ=V−1(X(pℓ)Z(pℓ))ℓc = V^{-1}(C(p_\ell))_\ell= V^{-1}(X(p_\ell)Z(p_\ell))_\ell for the Vandermonde interpolation matrix VV of the points with Vij=pij−1V_{ij}=p_i^{j-1}, i,j∈{1,2,…,2k−1}i,j\in\{1,2,\ldots,2k-1\}. Substituting t=2ht=2^h,

ϕxz=ϕC(2h)=∑ℓ=02k−2ϕℓX(pℓ)Z(pℓ),ϕℓ=ϕ∑j2jh(V−1)jℓ,(1)\phi xz = \phi C(2^h) = \sum_{\ell=0}^{2k-2}\phi_\ell X(p_\ell)Z(p_\ell), \qquad\phi_\ell= \phi\sum_j 2^{jh}(V^{-1})_{j\ell}, \tag*{(1)}

so eiϕxze^{i\phi xz} factors into 2k−12k-1 PhaseProducts with classically precomputed angles ϕℓ\phi_\ell. Each acts on evaluations only a few bits wider than hh, formed in place from the chunks by reversible additions, negations and shifts and undone afterwards, at O(w)O(w) cost, so the recursion G(w)=(2k−1)G(w/k+O(1))+O(w)G(w)=(2k-1)G(w/k+O(1))+O(w) gives O(wlog⁡k(2k−1))O(w^{\log_k(2k-1)}) (see Appendix § 8.2.2).

Definition 2.1 (Interpolation table). An interpolation table T=(k,p,Π)T=(k,\mathbf{p},\Pi) consists of an arity k≥2k\ge2, an ordered list p=(p0,…,p2k−2)\mathbf{p}=(p_0,\ldots,p_{2k-2}) of evaluation points in U:=Z∪{1/m:m∈Z∖{0}}∪{∞}U:=\mathbb{Z}\cup\{1/m:m\in\mathbb{Z}\setminus\{0\}\}\cup\{\infty\}, where evaluation at ∞\infty selects the leading coefficient, and a program Π\Pi of arithmetic operations (including shifts, negations, and scaled additions, as explained below), and 2k−12k-1 checkpoints on kk registers. The ℓ\ell-th checkpoint applies the child PhaseProduct with angle ϕℓ\phi_\ell.

Definition 2.2 (Policy). A policy is an ordered list of pairs (w1,T(1)),…,(wm,T(m))(w_1,T^{(1)}),\ldots,(w_m,T^{(m)}), where each T(j)T^{(j)} is an interpolation table and the register-width thresholds satisfy w1>⋯>wmw_1>\cdots>w_m. For a PhaseProduct on ww-bit registers, the policy selects the first table T(j)T^{(j)} with w≥wjw\ge w_j. If no such table exists, it selects the schoolbook construction.

To define the basic arithmetic operations that constitute a program Π\Pi in a table, write r0,…,rk−1r_0,\ldots,r_{k-1} for the current register values, each an integer linear combination of the initial chunks xjx_j or zjz_j. The arithmetic instructions act as

addScaled⁡(i,j,η,s):ri←ri+η2srj,negate⁡(i):ri←−ri,shiftL⁡(i,s):ri←2sri,shiftR⁡(i,s):ri←ri/2s.\begin{aligned} \operatorname{addScaled}(i,j,\eta,s)&:\quad r_i\leftarrow r_i+\eta2^s r_j,\\ \operatorname{negate}(i)&:\quad r_i\leftarrow-r_i,\\ \operatorname{shiftL}(i,s)&:\quad r_i\leftarrow2^s r_i,\\ \operatorname{shiftR}(i,s)&:\quad r_i\leftarrow r_i/2^s. \end{aligned}

where i,j∈{0,…,k−1}i,j\in\{0,\ldots,k-1\}, i≠ji\ne j for scaled addition, η∈{−1,+1}\eta\in\{-1,+1\}, and ss 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 rir_i is divisible by 2s2^s, ensuring exact division for every input without discarding nonzero bits. The program starts with ri=xir_i=x_i and is applied identically to the chunks of the other operand zz. 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 ((40,T(1)),(14,T(2)))((40,T^{(1)}),(14,T^{(2)})), where T(1)T^{(1)} and T(2)T^{(2)} are interpolation tables of arity 3 and 2, respectively. It selects T(1)T^{(1)} for w≥40w \ge40, T(2)T^{(2)} for 14≤w<4014 \le w < 40, and the schoolbook construction for w<14w < 14. 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 nn, all PhaseProduct operations at recursion depth ii share width wiw_i. A legitimate policy must ensure that each table satisfies

C1 there are exactly 2k−12k - 1 points, one per coefficient of C(t)=X(t)Z(t)C(t) = X(t)Z(t)

C2 the points are distinct, so the interpolation matrix VV is invertible and (1) holds

C3 running the program from the initial state, each instruction ensures no right shift discards a nonzero bit, the ℓ\ell-th checkpoint finds its register holding exactly the evaluation row of pℓ\mathbf{p}_\ell, and every point is consumed, in order

C4 the program returns every register to its initial value

and that its thresholds satisfy w1>⋯>wmw_1 > \cdots> w_m. Thus, the recursive steps induce an arity sequence k0,…,kD−1k_0,\ldots,k_{D-1}, with w0=nw_0 = n and wi+1<wiw_{i+1} < w_i, terminating in the schoolbook construction at recursion depth DD. Figure 2 shows a k=3k = 3 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).

Schematic recursive PhaseProduct policy

Figure 2. Schematic recursive PhaseProduct policy. (1) An policy P=((w1,T(1)),(w2,T(2)),…)P = ((w_1,T^{(1)}),(w_2,T^{(2)}),\ldots) (Definition 2.2) pairs register width thresholds w1>w2>⋯w_1 > w_2 > \cdots with interpolation tables T=(k,p,Π)T = (k,\mathbf{p},\Pi) (Definition 2.1), specifying one recursion level number of chunks (arity) kk, ordered interpolation points p\mathbf{p} and a program Π\Pi of scaled additions, negations, and shifts. The first table decomposes a PhaseProduct on ww-bit registers with w≥wjw \ge w_j, so widths wi+1=WTki(wi)<wiw_{i+1} = W_{T_{k_i}}(w_i) < w_i from w0=nw_0 = n induce an arity sequence k0,…,kD−1k_0,\ldots,k_{D-1} down to a base level DD. For n=128n = 128 as shown here, thresholds (40,14)(40,14) with tables of arity 3 and 2 (the latter from Appendix § 8.2.2) give an arity sequence (3,3,2,2)(3,3,2,2) and D=4D = 4. (2) A Lean-verified k=3k = 3 table T(1)T^{(1)} is decomposed with interpolation points p=(0,1,∞,−2,−1)\mathbf{p} = (0,1,\infty,-2,-1). The table uses 11 scaled additions within program blocks Π(0),Π(1),Π(2)\Pi^{(0)},\Pi^{(1)},\Pi^{(2)}. (3) At each (numbered) checkpoint, a child PhaseProduct of width wi+1w_{i+1} is instantiated and decomposed by the width-selected table, recursing until the MDM_D 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 TkT_k for each arity 2≤K2 \le K for some maximum arity KK given a priori. For a table within a policy, for a given kk we fix the set Ek\mathcal{E}_k of 2k−12k - 1 interpolation points to that of KMY [3], so a table chooses only their traversal order p\mathbf{p} within Ek\mathcal{E}_k and its program Π\Pi. We further take each child width WpW_{\mathbf{p}} to be the same given a parent width ww. 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 TT associated with arity kk determines a child width function denoted as WT(w)W_T(w), whose value is approximately w/kw/k plus ancillary bits accounting for register growth during its program. Starting from w0=nw_0=n, a policy selects arity kik_i at level ii and sets wi+1=WTki(wi)w_{i+1}=W_{T_{k_i}}(w_i). We require wi+1<wiw_{i+1}<w_i at every recursive level. At depth DD, the remaining products are computed by the schoolbook method, with O(wD2)O(w_D^2) operations per product. As we detail below, we consider a restricted family of PhaseProduct schedules, retaining a constant kk at a given recursion level, with interpolation points defined from KMY [3 Appendix F. 2].

For each selected table TkT_k, define its arithmetic charge as χk:=A+(Tk)+3A−(Tk)+ν(Tk)\chi_k:=A_+(T_k)+3A_-(T_k)+\nu(T_k), where A+A_+, A−A_-, and ν\nu 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

TPP=∑i=0D−18Mi(wi+1−1)χki+leaf⁡(MD,wD),Mi=∏j<i(2kj−1),(2)\mathrm{T}_{\mathrm{PP}}=\sum_{i=0}^{D-1}8M_i(w_{i+1}-1)\chi_{k_i}+\operatorname{leaf}(M_D,w_D), \qquad M_i=\prod_{j<i}(2k_j-1), \tag*{(2)}

where M0=1M_0=1 and MiM_i is the number of PhaseProduct instances at level ii. Here, leaf⁡(N,w)\operatorname{leaf}(N,w) is the total base-case T-count for MM schoolbook products of width ww, including the synthesis cost of Mw2Mw^2 rotations and their associated logical ANDs (Eq. (5)).

The policy search problem is the following constrained optimization problem. Given an input register width nn, a maximum arity KK, 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 nn-bit registers. The optimization jointly chooses (i) which arities k∈{2,…,K}k\in\{2,\ldots,K\} to use; (ii) for each chosen arity, an ordering pkp_k of its fixed point set and an admissible program Πk\Pi_k, defining a table Tk=(k,pk,Πk)T_k=(k,p_k,\Pi_k); 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 kk 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 nn increases. For example, with K=3K=3 the exact optimum over independent trees uses arity 2 at n=60n = 60, arity 3 at n=61n = 61, 6262 and 6363, arity 2 at n=64n = 64, arity 3 at n=65n = 65 and arity 2 again at n=66n = 66.

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 2κ−12\kappa- 1 children for each call and apply the price over register widths and number of rotations. We find this program to scale as O(κ2n6)O(\kappa^{2n^6}) arithmetic operations, polynomial in nn, where κ=min⁡(K,n)\kappa= \min(K,n). Integer feasibility inside the inner layer is solved by the Lenstra–Kannan algorithm [30]. We recover an exact, deterministic algorithm running in time 2O(κ4)poly⁡(n)2^{O(\kappa^4)}\operatorname{poly}(n) (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 K=2K = 2 closed form and, for K≥3K \ge3, tables built by exhaustive search over the KMY points. Each returned tree and table is re-verified by an independent replay. At n=2048n = 2048 it returns the exact K=2K = 2 optimum in 5.6 s and the K=3K = 3 optimum over its tables in about four minutes. The cost lies in table construction, where for one arity-8 table at n=2048n = 2048 the third layer of the search graph holds 2.9×10102.9 \times10^{10} states (7.5×1037.5 \times10^3 GiB, about 470×470\times a 16 GiB machine), and certifying the best known n=2048n = 2048 policy is estimated at 3.2×10513.2 \times10^{51} core-hours (sensitivity span 3.2×10513.2 \times10^{51} to 4.9×10804.9 \times10^{80}) at a measured 540 ns per candidate, against 3.2×10123.2 \times10^{12} core-hours for the arity-4 decision. At K=3K = 3 the exact optimal trees reach depth 4 at n=1024n = 1024 and n=2048n = 2048, and at K=2K = 2 depth 6 at n=2048n = 2048. 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 n=2048n = 2048, 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 kk, 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 PP and an order-finding instance (N,a)(N, a), the harness builds an order-finding circuit CP(N,a)C_P(N, a). The following theorems are proved once for every valid policy.

Theorem 3.1 (Correctness, generic in the policy). Let PP be any valid policy and (N,a)(N, a) any order-finding instance (0<a<N,gcd⁡(a,N)=1)(0 < a < N, \operatorname{gcd}(a,N) = 1). Let CP(N,a)C_P(N, a) be run at any precision η≤ηN\eta\leq\eta_N, where ηN\eta_N is the threshold fixed by the harness, which costs O(log⁡n)O(\log n) extra work qubits. Then

Pr⁡[successful order recovery from CP(N,a)]≥κ2ln⁡(⌊log⁡2N⌋+1),κ=1π2.\Pr\left[\text{successful order recovery from }C_P(N,a)\right] \geq\frac{\kappa}{2\ln\left(\left\lfloor\log_2 N\right\rfloor+1\right)}, \qquad\kappa= \frac{1}{\pi^2}.

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 O(log⁡n)O(\log n) extra work qubits (leaving the total O(n)O(n) work qubits count unchanged).

The second theorem bounds the size of the same circuit. The lowered gate count of CP(N,a)C_{\mathrm{P}}(N,a) 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 P=((w1,T(1)),…,(wm,T(m)))P=((w_1,T^{(1)}),\ldots,(w_m,T^{(m)})) be any valid policy with m≥1m\geq1, and let k1k_1 be the number of chunks of T(1)T^{(1)}. At every precision at which the work register has O(n)O(n) qubits, the lowered gate count of CP(N,a)C_{\mathrm{P}}(N,a) is O(n1+log⁡k1(2k1−1))O\left(n^{1+\log_{k_1}(2k_1-1)}\right), where nn is the bit length of NN. In particular this holds at the precision of Theorem 3.1.

Corollary 3.3. For every ϵ>0\epsilon>0 there is a kk such that every valid policy whose first table has kk chunks yields an order-finding circuit with O(n2+ϵ)O(n^{2+\epsilon}) 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 O(log⁡n)O(\log n) 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-kk 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 ∣x⟩∣z⟩↦eiϕxz∣x⟩∣z⟩|x\rangle|z\rangle\mapsto e^{i\phi xz}|x\rangle|z\rangle. 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 2k−12^k-1 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 PP be any valid policy and GG a Gate circuit of the order-finding construction. For every state ∣ψ⟩|\psi\rangle whose ancilla qubits are clean,

eval⁡(lower⁡P(G),∣ψ⟩)=eval⁡(G,∣ψ⟩).\operatorname{eval}(\operatorname{lower}_{P}(G),|\psi\rangle)=\operatorname{eval}(G,|\psi\rangle).

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 nn 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 ∣Ubloq−Uclassical∣|U_{\mathrm{bloq}} - U_{\mathrm{classical}}|, 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 δ=0.01\delta= 0.01 for the order-finding algorithm, partitioning half (δsynth=0.005\delta_{\mathrm{synth}} = 0.005) to rotation angle synthesis. Logical T-gate count uses Ross-Selinger synthesis [32]. With a per-rotation error allocation ϵrot=δsynth/Nrot\epsilon_{\mathrm{rot}} = \delta_{\mathrm{synth}}/N_{\mathrm{rot}} for the NrotN_{\mathrm{rot}} rotations of the whole order-finding circuit, each rotation is charged 3.075log⁡2(1/ϵrot)+0.863.075\log_2(1/\epsilon_{\mathrm{rot}}) + 0.86 T-gates, the mean Ross-Selinger cost (confirmed with pygridsynth [33] on sampled angles). Logical T-gate count therefore has an additional log⁡2(1/ϵrot)\log_2(1/\epsilon_{\mathrm{rot}}) scaling due to rotation synthesis.

For a given kk and nn, the recursion depth is optimized for a minimum T-count, and is compared to a custom policy with varying kk at each level in the recursion, reoptimized at each nn. At n=2048n = 2048 the main product is decomposed as k=(6,5,3)k = (6,5,3) over three recursive layers. This policy is not proven optimal and is the focus of future research (§ 2). For constant kk, we vary integer size n∈[4,50000]n \in[4,50000], performing a least-squares fit on a range of integer sizes n=[40000,50000]n = [40000,50000] to represent an ‘asymptotic region,’ fitting Anlog⁡k(2k−1)log⁡(1/ϵrot)A n^{\log_k(2k-1)} \log(1/\epsilon_{\mathrm{rot}}) with some constant AA, compounding constant factors from additions, multiplications, and synthesis. Results are presented in Figure 4.

Logical T-gate count of Shor’s order-finding algorithm using a PhaseProduct construction of Toom-Cook multiplication and QFT

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 kk-arity brings a best-found T-gate count at k=4k = 4 with 1.820×10121.820 \times10^{12} T-gates, with asymptotic improvements for larger nn favoring higher kk. Upon using a varying-kk policy for PhaseProduct (different kk at different levels in the recursion), a lower T-gate count is identified with 1.685×10121.685 \times10^{12} T-gates. Least-squares fits assert the derived exponent and fit a constant prefactor to each curve in an asymptotic region n=[40000,50000]n = [40000, 50000]. 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 3.8×1063.8 \times10^{6} 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 n=2048n = 2048. 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 O(n2+ϵ)O(n^{2+\epsilon}) 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 3.075log⁡2(1/εrot)+0.863.075\log_{2}(1/\varepsilon_{\mathrm{rot}}) + 0.86 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 nn 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 K=2K = 2 closed form and, for K≥3K \ge3, tables built from the KMY points. The n=2048n = 2048 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 τ\tau was even one picosecond (the timescale for a transistor to flip a zero to a one), it would still take an estimated 5.9×10455.9 \times10^{45} core hours to exactly enumerate all candidates for k=8k = 8.

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 O(n3/2)O(n^{3/2}) base gate complexity, requiring O(n)O(\sqrt{n}) iterations with efficient post-processing, giving a baseline O(n2)O(n^2) total quantum complexity. This is attractive when compared to the O(n3)O(n^3) base complexity of other integer factorization algorithms and questions the applicability of O(n2+ϵ)O(n^{2+\epsilon}) 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 2k−12k - 1 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 O(n2+ϵ)O(n^{2+\epsilon}). 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 n=2048n = 2048, Ross-Selinger synthesis results in 1.685×10121.685 \times10^{12} T-gates with a custom program with varying kk in the recursive definition. Toom-Cook kk-arity varies with modulus size nn, 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 k∈{2,3}k \in\{2, 3\} 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

∣x⟩∣z⟩⟼eiϕxz∣x⟩∣z⟩,\lvert x\rangle\lvert z\rangle\longmapsto e^{i\phi xz}\lvert x\rangle\lvert z\rangle,

for an appropriate phase parameter ϕ\phi. A direct implementation follows from expanding

xz=∑i,j2i+jxizj,xz = \sum_{i,j} 2^{i+j}x_i z_j,

where xix_i here denotes the ii-th bit. For each pair of bits xix_i and zjz_j, the circuit applies a corresponding controlled phase rotation. Thus, for two ww-bit registers, the naive construction uses Θ(w2)\Theta(w^2) pairwise phase operations. On the ForShor proof graph [53], this construction can be found by following

PhaseProduct ⟶\longrightarrow Gates ⟶\longrightarrow 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 kk, each input is divided into kk smaller chunks. These chunks are viewed as the coefficients of two polynomials,

X(t)=∑i=0k−1xiti,Z(t)=∑i=0k−1ziti.X(t) = \sum_{i=0}^{k-1} x_i t^i,\qquad Z(t) = \sum_{i=0}^{k-1} z_i t^i.

Multiplying the original integers can then be reduced to determining the coefficients of the product polynomial C(t)=X(t)Z(t)C(t) = X(t)Z(t), which has degree at most 2k−22k-2.

Instead of directly multiplying every pair of coefficients, Toom-Cook evaluates XX and ZZ at 2k−12k-1 suitable points, multiplies the corresponding values, and then interpolates these results to recover CC [4, 54]. Thus, one multiplication problem is reduced to 2k−12k-1 smaller multiplication problems, together with the work required for evaluation and interpolation. Recursively applying this idea gives the recurrence

Gk(w)=(2k−1)Gk(wk)+O(w),G_k(w) = (2k-1)G_k\left(\frac{w}{k}\right) + O(w),

and therefore an asymptotic multiplication cost of

Gk(w)=O(wlog⁡k(2k−1)).G_k(w) = O\left(w^{\log_k(2k-1)}\right).

The purely mathematical part of this construction can also be followed in the ForShor proof graph [53]. Starting from the PhaseProduct node, follow

PhaseProduct ⟶\longrightarrow Math ⟶\longrightarrow 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 xzxz, the evaluated values are used to break the phase ϕxz\phi xz into several smaller phases.

Split xx and zz into kk chunks of width hh and evaluate the chunk polynomials XX and ZZ at 2k−12k-1 points p0,…,p2k−2p_0,\ldots,p_{2k-2}. The product X(t)Z(t)X(t)Z(t) has degree at most 2k−22k-2, and substituting t=2ht=2^h gives xz=∑j2jhcjxz=\sum_j 2^{jh}c_j for its coefficients cjc_j. The values X(pℓ)Z(pℓ)X(p_\ell)Z(p_\ell) are evaluations of this polynomial, so c=(c0,…,c2k−2)=V−1(X(pℓ)Z(pℓ))ℓc=(c_0,\ldots,c_{2k-2})=V^{-1}(X(p_\ell)Z(p_\ell))_\ell for the interpolation matrix VV of the points, and therefore

ϕxz=∑ℓ=02k−2ϕℓX(pℓ)Z(pℓ),ϕℓ=ϕ∑j2jh(V−1)ℓj.\phi xz=\sum_{\ell=0}^{2k-2}\phi_\ell X(p_\ell)Z(p_\ell),\qquad\phi_\ell=\phi\sum_j2^{jh}(V^{-1})_{\ell j}.

Hence

eiϕxz=∏ℓ=02k−2eiϕℓX(pℓ)Z(pℓ).e^{i\phi xz}=\prod_{\ell=0}^{2k-2}e^{i\phi_\ell X(p_\ell)Z(p_\ell)}.

Each factor on the right is itself a PhaseProduct, on values whose sizes are roughly a factor of kk smaller [3]. The same construction can therefore be applied recursively. At each level, one PhaseProduct is replaced by 2k−12k-1 smaller ones, together with the reversible additions and shifts required to form the evaluations X(pℓ)X(p_\ell) and Z(pℓ)Z(p_\ell) 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 k=2k=2. Figure 5 illustrates one level of this recursion for k=2k=2, the Karatsuba case. Each ww-bit input is split into a low chunk of h=⌊w/2⌋h=\lfloor w/2\rfloor bits and a high chunk,

One level of the Toom-Cook PhaseProduct for $k = 2$

Figure 5. One level of the Toom-Cook PhaseProduct for k=2k = 2. The numbered boxes are the steps of Table 1, with ϕ(0)\phi_{(0)}, ϕ(∞)\phi_{(\infty)} and ϕ(1)\phi_{(1)} 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.

x=x0+2hx1,z=z0+2hz1,x=x_0+2^h x_1,\qquad z=z_0+2^h z_1,

and the chunk polynomials are evaluated at the three points 00, 11 and ∞\infty, giving the pairs (x0,z0)(x_0,z_0), (x0+x1,z0+z1)(x_0+x_1,z_0+z_1) and (x1,z1)(x_1,z_1). A direct calculation shows that

xz=(1−2h)x0z0+2h(x0+x1)(z0+z1)+(22h−2h)x1z1,(3)xz=(1-2^h)x_0z_0+2^h(x_0+x_1)(z_0+z_1)+(2^{2h}-2^h)x_1z_1, \tag*{(3)}

so the phase eiϕxze^{i\phi xz} factors into three smaller PhaseProducts with coefficients

ϕ(0)=ϕ(1−2h),ϕ(1)=ϕ2h,ϕ(∞)=ϕ(22h−2h).\phi_{(0)} = \phi\left(1 - 2^{h}\right), \qquad\phi_{(1)} = \phi2^{h}, \qquad\phi_{(\infty)} = \phi\left(2^{2h} - 2^{h}\right).

The circuit applies these three PhaseProducts in turn. The products at 0 and ∞\infty act directly on the chunks (x0,z0)(x_0,z_0) and (x1,z1)(x_1,z_1). 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 x0+x1x_0+x_1 may need one more bit than x0x_0. The figure omits this detail, which is handled by the width analysis.

Interpolation tables.Table 1 records the k=2k = 2 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 ww: the steps for k=2k = 2 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 kk consists of

StepOperationActs onPointCoefficient ϕ(p)\phi_{(p)}
1PhaseProduct(x0,z0)(x_0,z_0)0ϕ(1−2h)\phi(1-2^h)
2PhaseProduct(x1,z1)(x_1,z_1)∞\inftyϕ(22h−2h)\phi(2^{2h}-2^h)
3Addx0←x0+x1, z0←z0+z1x_0 \leftarrow x_0+x_1,\ z_0 \leftarrow z_0+z_1--
4PhaseProduct(x0+x1,z0+z1)(x_0+x_1,z_0+z_1)1ϕ2h\phi2^h
5Subtractx0←x0−x1, z0←z0−z1x_0 \leftarrow x_0-x_1,\ z_0 \leftarrow z_0-z_1--

Table 1. The Toom-Cook interpolation table for k=2k=2 with points 00, ∞\infty and 11, corresponding to the circuit in Figure 5. Each arithmetic step is applied to both inputs.

  • an ordered list of 2k−12k - 1 evaluation points, each an integer, the reciprocal of a nonzero integer, or ∞\infty;

  • a program of shifts, negations and scaled additions on the kk chunk registers, in which each of the 2k−12k - 1 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 k=2k = 2 example by showing how each step in Table 1 is mapped onto the PhaseProduct circuit.

Cost. Each of the three smaller PhaseProducts in the k=2k=2 construction acts on registers of roughly w/2w/2 bits and is implemented by the same construction, until the naive base case is reached. This gives the recurrence

G2(w)=3G2(⌊w2⌋+1)+O(w),G_2(w)=3G_2\left(\left\lfloor\frac{w}{2}\right\rfloor+1\right)+O(w),

and hence a cost of O(wlog⁡23)O(w^{\log_2 3}). For general kk, a table with 2k−12k-1 points gives the same asymptotic recurrence as Toom-Cook multiplication,

Gk(w)=(2k−1)Gk(wk+O(1))+O(w),G_k(w)=(2k-1)G_k\left(\frac{w}{k}+O(1)\right)+O(w),

and hence a PhaseProduct gate cost of Gk(w)=O(wlog⁡k(2k−1))G_k(w)=O(w^{\log_k(2k-1)}) [3]. Since log⁡k(2k−1)<2\log_k(2k-1)<2 for k≥2k\geq2, 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 ww-qubit register holding xx, split into a low chunk of hh qubits and a high chunk of w−hw-h qubits, so that

One level of the Cooley–Tukey decomposition of the QFT

Figure 6. One level of the Cooley–Tukey decomposition of the QFT on a ww-qubit register split into chunks of hh and w−hw-h qubits. The two smaller QFTs are decomposed in the same way, down to single qubits. The procedure is described in the text.

x=x0+2hx1.x=x_0+2^h x_1.

The QFT maps ∣x⟩\lvert x\rangle to 2−w/2∑ye2πixy/2w∣y⟩2^{-w/2}\sum_y e^{2\pi ixy/2^w}\lvert y\rangle. Writing the output in the same way but with the chunk widths exchanged, y=y0+2w−hy1y=y_0+2^{w-h}y_1, the phase separates as

xy2w≡x1y02w−h+x0y02w+x0y12h(mod1),\frac{xy}{2^w}\equiv\frac{x_1y_0}{2^{w-h}}+\frac{x_0y_0}{2^w}+\frac{x_0y_1}{2^h}\pmod{1},

since the remaining term x1y1x_1y_1 is an integer. Each term corresponds to one operation. The first is a QFT on the (w−h)(w-h)-qubit high chunk, which turns x1x_1 into y0y_0. The second is a cross phase between the low chunk and the transformed high chunk, which is exactly the PhaseProduct PPϕ\mathrm{PP}_{\phi} of Section A.1 with ϕ=2π/2w\phi=2\pi/2^w. The third is a QFT on the hh-qubit low chunk, which turns x0x_0 into y1y_1. Because y0y_0 ends up in the wires that held x1x_1 and vice versa, the two chunks are finally exchanged.

Choosing h=⌊w/2⌋h=\lfloor w/2\rfloor, as in the k=2k=2 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 Gk(w)G_k(w) for the cost of the Toom-Cook PhaseProduct on ww-bit registers, the cost of the QFT therefore satisfies

GQFT(w)=2GQFT(w2)+Gk(w2).G_{\mathrm{QFT}}(w)=2G_{\mathrm{QFT}}\left(\frac{w}{2}\right)+G_k\left(\frac{w}{2}\right).

Since Gk(w)=O(wlog⁡k(2k−1))G_k(w)=O\left(w^{\log_k(2k-1)}\right) and log⁡k(2k−1)>1\log_k(2k-1)>1, the PhaseProduct term dominates, and this exact QFT achieves the same asymptotic gate complexity,

GQFT(w)=O(wlog⁡k(2k−1)).G_{\mathrm{QFT}}(w)=O\left(w^{\log_k(2k-1)}\right).

In-place Modular Multiplication

We now turn to the in-place controlled modular multiplication required by the modular-exponentiation circuit. For a classical constant cc coprime to NN, the desired operation is

∣x⟩↦∣cx mod N⟩.\lvert x\rangle\mapsto\lvert cx\bmod N\rangle.

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 mm-qubit register hold yy, with QFT ∣y⟩=2−m/2∑z<2me2πiyz/2m∣z⟩\lvert y\rangle=2^{-m/2}\sum_{z<2^m}e^{2\pi i yz/2^m}\lvert z\rangle. A PhaseProduct with angle 2πc/2m2\pi c/2^m between ∣x⟩\lvert x\rangle and the transformed register adds cxcx to yy:

∣x⟩∣y⟩→QFT∣x⟩12m∑z<2me2πiyz/2m∣z⟩→PP2πc/2m∣x⟩12m∑z<2me2πi(y+cx)z/2m∣z⟩=∣x⟩QFT∣y+cx mod 2m⟩→QFT−1∣x⟩∣y+cx mod 2m⟩.\lvert x\rangle\lvert y\rangle \xrightarrow{\mathrm{QFT}} \lvert x\rangle\frac{1}{\sqrt{2^m}}\sum_{z<2^m}e^{2\pi i yz/2^m}\lvert z\rangle \xrightarrow{\mathrm{PP}_{2\pi c/2^m}} \lvert x\rangle\frac{1}{\sqrt{2^m}}\sum_{z<2^m}e^{2\pi i(y+cx)z/2^m}\lvert z\rangle =\lvert x\rangle\mathrm{QFT}\lvert y+cx\bmod2^m\rangle \xrightarrow{\mathrm{QFT}^{-1}} \lvert x\rangle\lvert y+cx\bmod2^m\rangle.

The same idea can be adapted to modular multiplication. The key identity is

e2πi(cx mod N)z/N=e2πicxz/N.e^{2\pi i(cx\bmod N)z/N}=e^{2\pi i cxz/N}.

The phase therefore automatically discards multiples of NN: increasing cxcx by NN changes the exponent by an integer multiple of 2πi2\pi i and hence leaves the phase unchanged. To exploit this identity, the phase would need denominator NN, which would require a QFT over ZN\mathbb{Z}_N. The QFT on mm qubits is over Z2m\mathbb{Z}_{2^m} instead, so the phases it produces have denominator 2m2^m. Running the construction above in that basis therefore makes the sum wrap around at 2m2^m rather than at NN: it computes y+cx mod 2my+cx\bmod2^m, not y+cx mod Ny+cx\bmod N. Since NN is odd, no choice of mm makes 2m2^m a multiple of NN, so the reduction modulo NN has to be done separately. In that basis the construction above adds cxcx modulo 2m2^m, not modulo NN.

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 xx holds the nn-bit value xx, and the work register ff holds m=n+O(log⁡(1/εmm))m=n+O(\log(1/\varepsilon_{\mathrm{mm}})) qubits, where εmm\varepsilon_{\mathrm{mm}} is the target error. Two further qubits are used: an overflow qubit oo, which extends the input register by one bit, and a comparison qubit cmp. Each block PP⁡α\operatorname{PP}_{\alpha} is a PhaseProduct which, together with the QFTs on either side of it, adds α\alpha times the value of one register into the other. The constants are

Circuit for in-place modular multiplication with five steps

Figure 7. In-place modular multiplication ∣x⟩↦∣cx mod N⟩\lvert x\rangle\mapsto\lvert cx \bmod N\rangle (Algorithm 1 of [3]). The registers and steps are described in the text.

α1=c−1N,α2=N,α3=−1−c−1N.\alpha_1 = \frac{c-1}{N}, \qquad\alpha_2 = N, \qquad\alpha_3 = -\frac{1-c^{-1}}{N}.

where c−1c^{-1} denotes the inverse of cc modulo NN. The circuit proceeds in five steps:

  1. Compute the fraction. The work register is placed in uniform superposition, PP⁡α1\operatorname{PP}_{\alpha_1} is applied between xx and ff, and an inverse QFT is applied to ff. This writes an mm-bit approximation of f=((c−1)x mod N)/Nf = ((c-1)x \bmod N)/N into the work register.

  1. Add NfNf. On the input register extended by oo (the carry bit as shown in the figure), a QFT, PP⁡α2\operatorname{PP}_{\alpha_2}, and an inverse QFT adds NfNf to xx. Since x+Nf=x+((c−1)x mod N)x + Nf = x + ((c-1)x \bmod N), the extended register now holds an approximation of either cx mod Ncx \bmod N or (cx mod N)+N(cx \bmod N) + N.

  1. Reduce modulo NN. A comparison writes into cmp whether the extended register is at least NN, and NN is subtracted controlled on cmp. The register now holds cx mod Ncx \bmod N, and oo returns to ∣0⟩\lvert0\rangle.

  1. Uncompute the comparison qubit. The subtraction occurred exactly when cx mod N<Nfcx \bmod N < Nf, so comparing the input register with NfNf returns cmp to ∣0⟩\lvert0\rangle.

  1. Uncompute the work register. Since the fraction ff equals ((1−c−1)(cx) mod N)/N((1-c^{-1})(cx) \bmod N)/N, it can be computed from the new contents of the input register. A QFT on ff, PP⁡α3\operatorname{PP}_{\alpha_3}, and an inverse QFT subtract this value, returning the work register to ∣0⟩⊗m\lvert0\rangle^{\otimes m}.

Steps 3 and 4 are exact. The only approximation is that the work register holds ff to mm bits, while ff is a fraction with denominator NN that mm bits generally cannot represent exactly. The resulting error in NfNf is at most about 2n−m2^{n-m}, so each extra bit beyond nn halves it, and m=n+O(log⁡(1/εmm))m = n + O(\log(1/\varepsilon_{\mathrm{mm}})) 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 kk, its gate cost scales as

O(nlog⁡k(2k−1)).O\left(n^{\log_k(2k-1)}\right).

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 O(n)O(n)-bit exponent requires O(n)O(n) 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 O(n2+ϵ)O(n^{2+\epsilon}) gates

The components of the previous subsections combine as follows. For a fixed splitting parameter kk, the fast PhaseProduct and the recursive QFT each cost O(nlog⁡k(2k−1))O(n^{\log_k(2k-1)}) gates, the in-place controlled modular multiplier inherits the same bound, and modular exponentiation applies O(n)O(n) such multiplications, giving O(n1+log⁡k(2k−1))O(n^{1+\log_k(2k-1)}) for the complete order-finding circuit. Choosing kk large enough that log⁡k(2k−1)≤1+ϵ\log_k(2k-1) \leq1+\epsilon gives O(n2+ϵ)O(n^{2+\epsilon}). § 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 O(n2+ϵ)O(n^{2+\epsilon}) 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 n=2048n = 2048. 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 nn (Section B.5).

Preface: A human summary

A PhaseProduct on ww-bit registers is split into kk chunks and evaluated at 2k−12k-1 interpolation points, each evaluation a smaller PhaseProduct. A table is the order of additions, negations and shifts that forms those evaluations in kk 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 nn and runs in seconds at n=2048n = 2048 once the tables are known. The inner layer constructs those tables for each arity kk and width ww, finding the cheapest table by exhaustive search in time complexity 2O(K4)2^{O(K^4)} for a maximum, manually set arity KK. 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 (k,A,B)(k,A,B) (right). The outer dynamic program (steps 3–5) is polynomial in nn. The status is OPTIMAL only if the independent replay passes and every arity ≤K\le K 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 τ\tau. We model or exactly calculate the number of states visited and the number of candidate moves per state, converted to core-hours by τ\tau, 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 τ=41\tau= 41 ns at arity 4, where the tables fit in cache, and τ=540\tau= 540 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 KK, the memory and time floors and the estimates for certifying the best-known n=2048n = 2048 tree are: K=8K = 8 needs at least 7.5×1037.5 \times10^3 GiB for any search that stores its states, and an estimated 3.2×10513.2 \times10^{51} core-hours (sensitivity span 3.2×10513.2 \times10^{51} to 4.9×10804.9 \times10^{80}); K=4K = 4 needs an estimated 3.2×10123.2 \times10^{12} core hours (span 2.1×10112.1 \times10^{11} to 8.8×10158.8 \times10^{15}).

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 K=2K = 2 closed form and, for K≥3K \ge3, 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 ww, which will either be evaluated by a “leaf,” being the schoolbook multiplication method, or it will split according to an arity kk into 2k−12k - 1 children with width u<wu < w, and will have a table (2≤k≤K2 \le k \le K) associated with it. Each child continues independently, so siblings and equal widths do not need to agree. Fix q=k−1q = k - 1, Q=2k−1Q = 2k - 1. A table acts on kk rows X0,…,XqX_0, \ldots, X_q, initially the rows of IkI_k (integer coefficient vectors) and must return them to IkI_k. Its instructions are Xi←2eXiX_i \leftarrow2^e X_i, Xi←Xi/2eX_i \leftarrow X_i/2^e (exact over Z\mathbb{Z}), Xi←−XiX_i \leftarrow-X_i, Xi←Xi±2eXjX_i \leftarrow X_i \pm2^e X_j (i≠ji \ne j). It checkpoints each of QQ projectively distinct tokens (integers, reciprocals of integers, 00, ∞\infty) exactly once, in the literal evaluation row vq(p,s)=(sq,psq−1,…,pq)v_q(p,s) = (s^q, ps^{q-1}, \ldots, p^q), where sign and scale matter and are not free.

Charge and width

The charge is χ=A++3A−+ν\chi= A_{+} + 3A_{-} + \nu (additions, subtractions as negate-add-negate, negations); shifts and checkpoints are free. For w=kL+rw = kL + r, 0≤r<k0 \le r < k, the counters hih_i start at (L,…,L,L+r)(L,\ldots,L,L+r) and update as hi+eh_i+e (shift), max⁡(0,hi−e)\max(0,h_i-e) (division), hi+1h_i+1 (negation), 1+max⁡(hi,hj+e)1+\max(h_i,h_j+e) (addition); the child width is WT(w)=1+max⁡W_{\mathrm{T}}(w) = 1 + \max of every counter at every instruction boundary, initial and final included.

Cost

An internal node vv with table PvP_v and child width uvu_v pays 8(uv−1)χ(Pv)8(u_v-1)\chi(P_v) (two operand registers, four T gates per adder); a leaf of width ww contributes w2w^2 rotation units. With D(T)=∑v8(uv−1)χ(Pv)D(T)=\sum_v 8(u_v-1)\chi(P_v), R(T)=∑leaveswℓ2R(T)=\sum_{\mathrm{leaves}}w_\ell^2, τrot(R)=round⁡(3.075log⁡2(100R)+0.86)\tau_{\mathrm{rot}}(R)=\operatorname{round}(3.075\log_2(100R)+0.86) (evaluated in exact integer arithmetic) and f(R)=R[4+τrot(R)]f(R)=R[4+\tau_{\mathrm{rot}}(R)],

opt⁡(n,K)=min⁡TD(T)+f(R(T)).(4)\operatorname{opt}(n,K)=\min_T D(T)+f(R(T)). \tag*{(4)}

For a shared-table policy (one table per arity, uniform levels) this is

TPP=∑i<D8Mi(wi+1−1)χki+leaf⁡(MD,wD),Mi+1=Mi(2ki−1),leaf⁡(M,w)=f(Mw2).(5)T_{\mathrm{PP}}=\sum_{i<D}8M_i(w_{i+1}-1)\chi_{k_i}+\operatorname{leaf}(M_D,w_D),\qquad M_{i+1}=M_i(2k_i-1),\qquad\operatorname{leaf}(M,w)=f(Mw^2). \tag*{(5)}

The constants are: 8=4⋅28=4\cdot2 (four T gates per And, two operand registers); u−1u-1 Ands per uu-bit adder; charges 1, 3, 1 (subtraction is negate-add-negate); the Ross–Selinger rotation cost [32] at ε=δ/2R\varepsilon=\delta/2R, δ=0.005\delta=0.005, which gives the 100 and the exact integer form τrot(R)=⌊(⌊log⁡2(100R)⌋615+272)/200⌋\tau_{\mathrm{rot}}(R)=\left\lfloor\left(\left\lfloor\log_2(100R)\right\rfloor^{615}+272\right)/200\right\rfloor. 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, OPT⁡(k)≤15k(2k−1)\operatorname{OPT}(k)\le15k(2k-1), so the language LS\mathcal{L}_{S} 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 k=2k=2, by SAT ≤p\le_p DHC2 ≤p\le_p EHC ≤p\le_p POINTSTABLEOPT (Pts.genLang_NPHard); its hard instances use point sets the benchmark does not admit. For the T-count, stopping at the root costs f(n2)=O(n2log⁡n)f(n^2)=O(n^2\log n), 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 opt⁡(n,K)\operatorname{opt}(n,K) and an expanded optimal tree with a witness table at every internal node, in

O(∣K∣+2O(κ4))poly⁡(n) bit operations,κ=min⁡(K,n).O\left(|K|+2^{O(\kappa^4)}\right)\operatorname{poly}(n)\ \text{bit operations},\qquad\kappa=\min(K,n).

A conservative form is O(∣K∣+2O(κ4)(n+2)2h+16)O\left(|K|+2^{O(\kappa^4)}(n+2)^{2h+16}\right) time and 2O(κ4)(n+2)h+82^{O(\kappa^4)}(n+2)^{h+8} bits of storage for a fixed constant h≥2h\ge2. As tested, we use O(n2[κ3log⁡(n+2)+n])O\left(n^2[\kappa^3\log(n+2)+n]\right) bits.

Remark B.2 (Parameterized, not practical). The theorem is fixed-parameter tractability in κ\kappa for numerical width nn. It is not jointly polynomial in nn and KK, and the factor 2O(κ4)2^{O(\kappa^4)} comes from exhaustive symbolic synthesis. The imported bound is that integer feasibility in vv variables and binary length ℓ\ell is decided in

2O(vlog⁡(v+2))(ℓ+1)β bit operations for a fixed constant β(6)2^{O(v\log(v+2))}(\ell+1)^\beta\ \text{bit operations for a fixed constant }\beta \tag*{(6)}

((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-kk table has unique integers (a,b)(a,b), a≥0a \ge0, max⁡(0,a−q)≤b≤a\max(0,a-q) \le b \le a, with WT(kL+r)=L+1+max⁡(a,r+b)W_T(kL+r)=L+1+\max(a,r+b) for 0≤r≤q0 \le r \le q; aa and b+qb+q are the historical peaks of the counters started from (0,…,0)(0,\ldots,0) and (0,…,0,q)(0,\ldots,0,q). If (A,B)≥(a,b)(A,B)\ge(a,b) componentwise, prefixing X0←2AX0X_0\leftarrow2^A X_0, X0←X0/2AX_0\leftarrow X_0/2^A, Xq←2BXqX_q\leftarrow2^B X_q, Xq←Xq/2BX_q\leftarrow X_q/2^B yields profile exactly (A,B)(A,B) at unchanged charge.

The proof uses the norm invariant 0<∥Xi∥1≤2hi0<\lVert X_i\rVert_1\le2^{h_i}: no legal division reaches the clamp at 0. Replacing a table by a minimum-charge table with the same (w,k,u)(w,k,u) keeps the number and widths of all children, hence every continuation and the count RR, and weakly lowers DD; only c(w,k,u)=min⁡{ck(A,B):L+1+max⁡(A,r+B)=u}c(w,k,u)=\min\{c_k(A,B):L+1+\max(A,r+B)=u\} matters.

Lemma B.4 (Charge ceiling). Every attainable profile has a representative of charge at most C=3kH0=O(k3)C=3kH_0=O(k^3), H0=2q(2q−1)H_0=2q(2q-1).

A potential argument gives #charged instructions ≤ka\le ka and χ≤3ka\chi\le3ka; for a>H0a>H_0 the explicit fallback table (charge C0=2H0C_0=2H_0, profile (H0,H0−q+1)(H_0,H_0-q+1)) is padded to (a,b)(a,b).

The cheapest table at a profile: the bottleneck

Lemma B.5 (Complete local synthesis). Algorithm 2 returns ck(A,B)c_k(A,B) and an attaining table, in 2O(k3log⁡k)2^{O(k^3\log k)} time when the budget is at least C0C_0 and 2O(k4)poly⁡(log⁡(A+k+2))2^{O(k^4)}\operatorname{poly}(\log(A+k+2)) below it.

Why unbounded shifts do not escape the search. Normalize every addition to the macro Yi←2pYiY_i\leftarrow2^pY_i, Yi←Yi±2sYjY_i\leftarrow Y_i\pm2^sY_j, Yi←Yi/2rY_i\leftarrow Y_i/2^r with min⁡(p,s)=0\min(p,s)=0 and primitive rows between macros; this preserves charge, checkpoints, restoration and every peak, and under cap AA all immediates lie in [0,A][0,A]. High budget (γ≥C0\gamma\ge C_0): if A≥max⁡(a0,b0+d)A\ge\max(a_0,b_0+d) the fallback fits; otherwise A=O(k2)A=O(k^2) and skeletons ×\times immediates are enumerated, (6k2)C+Q+1(A+1)2C=2O(k3log⁡k)(6k^2)^{C+Q+1}(A+1)^{2C}=2^{O(k^3\log k)}. Low budget (γ<C0\gamma<C_0): a skeleton fixes the charged instructions and leaves p=O(k2)p=O(k^2) immediates unknown; every matrix entry is a signed sum of powers of two with affine exponents. Exponents within a gap H=2c+3H=2c+3 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 N=2O(k2)N=2^{O(k^2)} hyperplanes in dimension pp, at most (p+1)[2(N+1)]p=2O(k4)(p+1)[2(N+1)]^p=2^{O(k^4)}, each decided by integer feasibility in v=O(k3)v=O(k^3) variables [5].

Planning the recursion

For 1≤w≤n1 \le w \le n let Fw(r)F_w(r) be the least internal cost at width ww with exactly rr leaf units; the leaf gives Fw(w2)=0F_w(w^2)=0, and for each finite interface (w,k,u)(w,k,u), with G0(0)=0G_0(0)=0, Gj(r)=min⁡1≤s≤rGj−1(r−s)+Fu(s)G_j(r)=\min_{1 \le s \le r} G_{j-1}(r-s)+F_u(s),

Fw(r)←min⁡{Fw(r),  8(u−1)c(w,k,u)+GQ(r)},opt⁡(n,K)=min⁡1≤r≤n2Fn(r)+f(r).(7)F_w(r) \leftarrow\min\{F_w(r),\; 8(u-1)c(w,k,u)+G_Q(r)\}, \qquad\operatorname{opt}(n,K)=\min_{1 \le r \le n^2} F_n(r)+f(r). \tag*{(7)}

Since f(r)/r≥4f(r)/r \ge4 is nondecreasing, any tree no costlier than the root leaf has R≤n2R \le n^2 and D≤V=f(n2)D \le V=f(n^2), 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 O(κ2n6)O(\kappa^2 n^6) arithmetic operations on O(log⁡n)O(\log n)-bit numbers.

Induction on jj shows Gj(r)G_j(r) is the least total internal cost of jj independent children with total count rr; induction on ww covers every feasible tree, and applying ff once at the root is exact. Dominance pruning of child widths (skip uu 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). c2(a,b)=4c_2(a,b)=4 for b≥2b \ge2 and +∞+\infty for b<2b<2, attained by the five-event table chk 0, chk ∞, X0←X0+X1X_0 \leftarrow X_0+X_1, chk 1, X0←X0−X1X_0 \leftarrow X_0-X_1, with profile (2,2)(2,2) and child width g(w)=⌈w/2⌉+3g(w)=\lceil w/2\rceil+3; a shrinking split exists iff w≥8w \ge8.

Theorem B.8 (Forced optimal K=2K=2 tree). Let B={1,…,39,41,43,45}B=\{1,\ldots,39,41,43,45\}. For every nn, every optimum stops at a width in BB and otherwise uses charge four and three children of width g(w)g(w).

The result holds inside any exterior tree, despite the global price. For n=2048n=2048 the widths are 2048→1027→517→262→134→70→382048 \to1027 \to517 \to262 \to134 \to70 \to38, so there are 36=7293^6=729 leaves, R∗=1,052,676R^*=1,052,676, D∗=739,008D^*=739,008 and opt⁡(2048,2)=92,321,820\operatorname{opt}(2048,2)=92,321,820 (width 40 splits and 41 does not: 92,750<92,80092,750<92,800 but 97,498≤100,96097,498 \le100,960).

Inner and Outer Optimization

The inner layer builds the interface minima; the outer layer is the dynamic program (7), O(κ2n6)O(\kappa^2 n^6) operations for any catalog. Both are exact, so the cost of the algorithm is the cost of the inner layer: 2O(κ4)2^{O(\kappa^4)} 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 K=2K=2 closed form; the dense recurrence (7) for n≤160n \le160 as a value check; a Pareto planner with exact dominance pruning). Interface minima for k≥3k \ge3 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 ≤K\le K 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 82,…,1628^2,\ldots,16^2 and 28,…,2112^8,\ldots,2^{11} (50 widths) ×K=2,…,5\times K=2,\ldots,5, 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 K=4K=4 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 K=2K=2 optima equal the closed form and an independent oracle. The K=3K=3 costs are optimal over all F2 tables of arity ≤3\le3 (the points ±2e\pm2^e and their reciprocals): a relaxation with one fictitious zero-charge table of profile (14,12)(14,12) gives lower bounds equal to the upper bounds at all 50 widths, and exhaustive decisions cover the region it does not (no table with a≤4a\le4 at any charge; none with charge ≤9\le9 and a≤13a\le13; exhaustively tested, one engine). The planner’s wall time grows ×61\times61 from n=512n=512 to 1024 and ×22\times22 to 2048 at K=3K=3, below the worst case n6n^6 because of dominance pruning (measured, two ratios are not a law). These times exclude the offline construction of the catalogs.

nnKKopt⁡(n,K)\operatorname{opt}(n,K)statuswall (s)peak (MiB)policy
51229,078,996optimal0.0095uniform
51237,067,876catalog0.189uniform
1024229,008,376optimal0.2117uniform
1024320,631,296catalog11.058mixed
2048292,321,820optimal5.6126uniform
2048362,297,732catalog241676uniform

Table 2. Planner on the standard grid (report cost model; median of three fresh processes; one machine). K=4K = 4, 5 cells equal K=3K = 3 (effective arity 3).

Projection: the cost of one table construction

Table construction at a cell (k,w,G,cmax⁡)(k, w, G, c_{\max}) asks whether a table with at most cmax⁡c_{\max} unit-weight operations exists when every row has weight W≤2GW \le2^{G} (child width u=⌊w/k⌋+G(w,k)u = \lfloor w/k \rfloor+ G(w,k)). 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 dd is kept iff d+h≤cmax⁡d + h \le c_{\max} for an admissible bound h≤2kh \le2k with h(Ik)=2k−2h(I_k) = 2k - 2; define the slack s=cmax⁡−(2k−2)s = c_{\max} - (2k - 2). Let LdL_d be the states first reached after dd operations. Then

B(k,G)=k+2k(k−1)(2G+1)candidates per expanded state,(8)B(k,G) = k + 2k(k - 1)(2G + 1)\quad\text{candidates per expanded state,} \tag*{(8)}
∣L1∣=4k(k−1)(G−1)+k−4(k−1)×w mod k,(9)|L_1| = 4k(k - 1)(G - 1) + k - 4(k - 1) \times w \bmod k, \tag*{(9)}
∣Ld+1∣=∣Ld∣r1λd−1(layer law),S≈∑d≤s∣Ld∣,(10)|L_{d+1}| = |L_d| r_1 \lambda^{d-1}\quad\text{(layer law)},\qquad S \approx\sum_{d \le s} |L_d|, \tag*{(10)}
time=τSB,memory=bkS,bk=2k2+24 (int16) or 4k2+24 (int32) bytes.(11)\text{time} = \tau S B,\qquad\text{memory} = b_k S,\qquad b_k = 2k^2 + 24\ \text{(int16) or }4k^2 + 24\ \text{(int32) bytes.} \tag*{(11)}

Equations (8) and (9) are exact ((9) matches 219 of 219 measured cells, as measured; the layer law (10) has r1/∣L1∣∈[0.57,0.59]r_1/|L_1| \in[0.57, 0.59] and λ∈[0.70,0.75]\lambda\in[0.70, 0.75] over k=4,…,8k = 4,\ldots,8 (measured). The time per candidate τ\tau is a necessary factor of every compute-time figure here: SS and BB are counts, and only τ\tau turns them into core-hours. Even though we test a narrow range of values here, we can therefore model SS and BB and leave the measurement of τ\tau as the only hardware- and software-dependent parameter. We measured τ=41\tau= 41 ns at k=4k = 4 (best of three, tables in cache) and τ=540\tau= 540 ns at k=8k = 8: the layer-3 run took 19,487 s on two shards for (1+∣L1∣+∣L2∣)B=7.3×1010(1 + |L_1| + |L_2|)B = 7.3 \times10^{10} candidates (measured, one run, wall time on a shared machine under memory pressure, so an upper-side value). Because τ\tau 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 4.2×10134.2 \times10^{13} 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 1.564×1071.564 \times10^7 (1.607×1071.607 \times10^7 predicted), 8.285×1078.285 \times10^7 (8.452×1078.452 \times10^7) and 9.194×1079.194 \times10^7 (1.011×1081.011 \times10^8), all within a factor 1.10 (measured; slack 4–5 only).

What is a bound. Because h≤2kh \le2k, every state at depth d≤cmax⁡−2kd \le c_{\max} - 2k survives the prune, so any exact state-space search must generate L1,…,L3L_1,\ldots,L_3 for every cell with cmax⁡≥2k+3c_{\max} \ge2k + 3, and larger caps only add legal moves. Hence at least B∣L2∣B|L_2| candidate evaluations and bk∣L3∣b_k|L_3| bytes if states are stored. Table 3 gives the exact ∣L3∣|L_3|: the memory floor exceeds the 16 GiB gate from k=6k = 6 and reaches 7.5×1037.5 \times10^3 GiB at k=8k = 8 (cap G=23G = 23; 7.3×10107.3 \times10^{10} candidate evaluations; the run took 1.9×1041.9 \times10^4 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 kk45678
cell (k,w,G)(k,w,G)(0,5)(0,5)(0,9)(0,9)(0,12)(0,12)(0,19)(0,19)(0,23)(0,23)
∣L3∣|L_3|1.7×1061.7 \times10^{6}6.8×1076.8 \times10^{7}5.8×1085.8 \times10^{8}6.8×1096.8 \times10^{9}2.9×10102.9 \times10^{10}
memory (GiB)0.094.7521.4×1031.4 \times10^{3}7.5×1037.5 \times10^{3}

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 8→4→38 \to4 \to3, board cost 9,592,816 T, measured by the board’s scorer) is optimal among all F2\mathrm{F}_2 policies. This “best-known tree” at n=2048n = 2048 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 [c,3c][c,3c], 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 (k,w,Gtop,cmax⁡=c−1)(k,w,G_{\mathrm{top}},c_{\max}=c-1), closes cells already below a proven bound, and evaluates (7)–(10) for the rest. Arity 3 closes (no table with ≤7\leq7 ops at any cap ≤15\leq15, every ww mod kk; exhaustive search; arity 4 has the proven bound c≥10c \geq10 at caps Glb…Glb+3G_{\mathrm{lb}} \ldots G_{\mathrm{lb}}+3. The optimizer is certified optimal over all F2\mathrm{F}_2 tables for every benchmark width up to n=81n = 81; above that the cost steps up with the arity needed.

Reading Table 4. Arity 8 dominates, requiring about 3.2×10513.2 \times10^{51} core-hours at τ=540\tau= 540 ns (≈3.7×1047\approx3.7 \times10^{47} core-years) against 3.2×10123.2 \times10^{12} for arity 4. Its state count is the peak of the layer law, log⁡10∣L∣max⁡≈(log⁡10r1)/(2∣log⁡10λ∣)\log_{10}|L|_{\max} \approx(\log_{10} r_1)/(2|\log_{10}\lambda|), so the exponent scales as 1/∣log⁡λ∣1/|\log\lambda|. The span’s lower end uses the smallest measured (λ,r1/∣L1∣)(\lambda,r_1/|L_1|) over arities 5–8 (the k=8k=8 cell itself: λ=0.745\lambda= 0.745, r1/∣L1∣=0.566r_1/|L_1| = 0.566); its upper end the largest, with λ\lambda multiplied by the largest depth-drift factor measured on exact unpruned layers (1.10, at k=3k = 3). The arity-4-fit scenario (linear-in-GG fits at k=4k = 4 extended to G=31G = 31) gives 1.1×10641.1 \times10^{64}. No coverage probability is claimed: λ\lambda is measured at one transition for k≥5k \ge5, its drift only at k=3k = 3, and the dominant arity-8 cell has slack 109−14=95109 - 14 = 95 against a calibrated 3–5. A SAT/CP formulation avoids the memory wall but not the growth: 6.7×1076.7 \times10^{7} core-hours for arity 4 at the first cap (growth ×4.7\times4.7 per op from four instances, extrapolated). The conclusion is a floor and a bracket: certifying the best-known tree needs at least 7.5×1037.5 \times10^{3} GiB at arity 8 for any state-storing search and, under the measured growth law, between about 3×10513 \times10^{51} and 5×10805 \times10^{80} core-hours; the exponent is not pinned, and the time scale is linear in τ\tau.

ArityDecision (dominant cell)Floor (measured)Estimate (core-h)Lower–upper span
3none ≤7\leq7 ops, G≤15G \leq15closed (exhaustive)0–
4none <20< 20 ops, G≤7G \leq7∣L3∣=1.7×106|L_3| = 1.7 \times10^{6} (0.09 GiB)3.2×10123.2 \times10^{12}2.1×10112.1 \times10^{11}–8.8×10158.8 \times10^{15}
8none <110< 110 ops, G≤31G \leq31≥7.3×1010\geq7.3 \times10^{10} candidates (10.8 core-h at 540 ns); ≥7.5×103\geq7.5 \times10^{3} GiB3.2×10513.2 \times10^{51}3.2×10513.2 \times10^{51}–4.9×10804.9 \times10^{80}

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 k=8k = 8. 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(n,Kn, K): exact independent-tree optimization (Theorem B.6)

Require: width n≥1n \ge1; arity bound K≥2K \ge2; interface minima c(w,k,u)c(w,k,u) with witnesses (Algorithm 2)

  1. Rmax⁡←n2R_{\max} \leftarrow n^{2}; V←f(Rmax⁡)V \leftarrow f(R_{\max})

  2. for w=1,…,nw = 1,\ldots,n do

  3. Fw[1..Rmax⁡]←+∞F_w[1..R_{\max}] \leftarrow+\infty; Fw(w2)←0F_w(w^{2}) \leftarrow0 ▷ schoolbook leaf

  4. for each finite (w,k,u)(w,k,u) with 2≤k≤min⁡(K,w)2 \le k \le\min(K,w), u<wu < w do

  5. G0(0)←0G_0(0) \leftarrow0; G0(r>0)←+∞G_0(r > 0) \leftarrow+\infty

  6. for j=1,…,2k−1j = 1,\ldots,2k - 1 do Gj(r)←min⁡1≤s≤r{Gj−1(r−s)+Fu(s)}G_j(r) \leftarrow\min_{1 \le s \le r}\{G_{j-1}(r-s) + F_u(s)\} ▷ independent children

  7. end for

  8. Fw(r)←min⁡{Fw(r),8(u−1)c(w,k,u)+G2k−1(r)}F_w(r) \leftarrow\min\{F_w(r), 8(u-1)c(w,k,u) + G_{2k-1}(r)\}, keeping backpointers; discard costs >V> V

  9. end for

  10. end for

  11. r∗←arg⁡min⁡rFn(r)+f(r)r^{*} \leftarrow\arg\min_r F_n(r) + f(r) return Fn(r∗)+f(r∗)F_n(r^{*}) + f(r^{*}) and the backtrace (tables and children)

Algorithm 2 MINCHARGE(k,A,Bk,A,B): cheapest arity-kk table with exact profile (A,B)(A,B) (Lemma B.5)

  1. q←k−1q \leftarrow k-1; d←A−Bd \leftarrow A-B; H0←2q(2q−1)H_0 \leftarrow2q(2q-1); C0←2H0C_0 \leftarrow2H_0; C←3kH0C \leftarrow3kH_0; Td←H0+max⁡(0,d−q+1)T_d \leftarrow H_0 + \max(0,d-q+1)

  2. for γ=0,…,C\gamma= 0,\ldots,C do

  3. P←P \leftarrow fallback table if γ≥C0\gamma\ge C_0 and A≥TdA \ge T_d; else DIRECTSEARCH(k,γ,A,dk,\gamma,A,d) if γ≥C0\gamma\ge C_0; else SYMBOLICSEARCH(k,γ,A,dk,\gamma,A,d)

  4. if P≠noneP \ne\text{none} then replay PP; pad to (A,B)(A,B) (Theorem B.3); return (γ,P)(\gamma,P)

  5. end if

  6. end for

  7. return +∞+\infty ▷ only after a complete search; a timeout returns INCOMPLETE

Algorithm 3 DECIDE(k,w,G,cmax⁡k,w,G,c_{\max}): is there a table with at most cmax⁡c_{\max} unit-weight ops? (repository engine)

  1. layer L0←{(Ik, marks of 0,∞)}L_0 \leftarrow\{(I_k,\text{ marks of }0,\infty)\}; store states with full-key hashing; d←0d \leftarrow0

  2. while Ld≠∅L_d \ne\varnothing and d<cmax⁡d < c_{\max} and no goal found do

  3. for each AA (mask) ∈Ld\in L_d; each of Bk(G)B_k(G) moves: negate a row, or Xi←2pXi±2qXjX_i \leftarrow2^p X_i \pm2^q X_j, min⁡(p,q)=0\min(p,q)=0 do

  4. child (M′,mask′)(M',\text{mask}'); skip if a row weight 2max⁡(P,N)+∣top∣2w mod k>2G2\max(P,N) + \lvert\text{top}\rvert2^w \bmod k > 2^G (cap)

  5. skip if already stored, or if d+1+h(M′,mask′)>cmax⁡d+1+h(M',\text{mask}') > c_{\max} ▷ admissible, h≤2kh \le2k

  6. store the child in Ld+1L_{d+1}; if M′=IkM' = I_k and every point is marked then goal found

  7. end for

  8. d←d+1d \leftarrow d+1; write the exact layer size ∣Ld∣\lvert L_d\rvert

  9. end while

  10. return FOUND (replay the path) if goal; NOTFOUND only if the graph was exhausted; UNDECIDED if the state limit was reached

Algorithm 4 PROJECT(nn): floors and estimates for certifying the best-known tree

  1. (T∗,ladder)←PLANNER(T^*,\text{ladder}) \leftarrow\text{PLANNER} over the best-known catalog; read the arities used

  2. relevance: for each k≤16k \le16 replace its tables by a free table (charge 0, child width ≥ulb(k,w)\ge u_{\mathrm{lb}}(k,w)), keep kk iff it beats T∗T^*

  3. cap cut: Gcut←G_{\mathrm{cut}} \leftarrow least cap beyond which free tables do not lower the optimum (tested at n=512,1024,2048n = 512, 1024, 2048)

  4. for each relevant kk, residue wmodkw \mathbin{\mathrm{mod}} k, frontier step (Gfirst,c)(G_{\mathrm{first}},c) with Gfirst≤GcutG_{\mathrm{first}} \le G_{\mathrm{cut}} do

  5. cell ←(k,w,Gtop,cmax⁡=c−1)\leftarrow(k,w,G_{\mathrm{top}},c_{\max}=c-1), Gtop←min⁡(next Gfirst−1,Gcut)G_{\mathrm{top}} \leftarrow\min(\text{next }G_{\mathrm{first}}-1,G_{\mathrm{cut}}), slack s←cmax⁡−(2k−2)s \leftarrow c_{\max}-(2k-2)

  6. if cmax⁡c_{\max} below a proven bound then cost 0 (closed) ▷ arity 3: ≥8\ge8; arity 4: ≥10\ge10

  7. else floor ←(B∣L2∣,bk∣L3∣)\leftarrow(B\lvert L_2\rvert,b_k\lvert L_3\rvert) from the measured prefix; estimate ←τSB,bkS\leftarrow\tau S B,b_kS by (8)–(11)

  8. end if

  9. end for

  10. sum over cells; report the dominant cell; span from the extremes of the measured (λ,r1/∣L1∣)(\lambda,r_1/\lvert L_1\rvert) with the measured depth-drift factor; label extrapolated beyond the calibrated slack

References

  1. [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. [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. [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. [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. [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. [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. [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. [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. [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. [10]Layr-Labs. The secp256k1 Point-Addition Challenge. GitHub repository. URL: https://github.com/Layr-Labs/ecdsafail-challenge.
  11. [11]Paureel. Beyond n log n. Research dashboard (GitHub repository). URL: https://github.com/Paureel/beyond-n-log-n.
  12. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [26]OpenAI. On the Navier–Stokes Millennium Prize Problem. Sept. 8, 2026. URL: https://openai.com/index/navier-stokes-solution/.
  27. [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. [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. [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. [30]Ravi Kannan. “Minkowski’s convex body theorem and integer programming”. In: Mathematics of operations research 12.3 (1987), pp. 415–440.DOI
  31. [31]Srihari Nanniyur and Siddhartha Jayanti. “Machine-Verifying Toom-Cook Multiplication with Integer Evaluation Points”. In: arXiv preprint arXiv:2603.14038 (2026).
  32. [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. [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. [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. [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. [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. [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. [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. [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. [40]Thomas G Draper. “Addition on a quantum computer”. In: arXiv preprint quant-ph/0008033 (2000).DOI
  41. [41]Daniel Litinski. “Magic state distillation: Not as costly as you think”. In: Quantum 3 (2019), p. 205.DOI
  42. [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. [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. [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. [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. [46]Nikolas P Breuckmann and Jens Niklas Eberhardt. “Quantum low-density parity-check codes”. In: PRX quantum 2.4 (2021), p. 040101.DOI
  47. [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. [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. [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. [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. [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. [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. [53]VerifiedQC. ForShor: Shor Verification Proof Graph. https://verifiedqc.github.io/ForShor/.
  54. [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. [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. [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.

Paper details

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

views · 0

downloads · 0

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

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents