A new harness verifies quantum factoring circuits with fewer than n^3 gates

Anirudh Suresh, Joshua M. Courtney, Runzhou Tao, and Yudong Cao have created a formally verified harness designed to assess the efficiency of quantum factoring circuits. The work addresses a key challenge in quantum computing by offering a way to automatically check both the mathematical correctness and circuit-level implementation of Shor’s algorithm, potentially reducing the gate count needed to factor large numbers to O(n^(2 + ε)).

This represents an improvement over the traditionally understood O(n^3) gate requirement when using standard arithmetic. The harness is released as an open challenge, inviting researchers and AI agents to design even more efficient circuits while maintaining machine-checked guarantees of correctness and complexity.

Recursive Toom-Cook Multiplication Achieves O(n^(2 + ε)) Gate Cost

Recent advances in quantum arithmetic circuits have achieved a gate cost of O(n^(2 + ε)) for Shor’s order finding algorithm, a significant reduction from the traditionally understood requirement of O(n^3) gates when factoring n-bit biprimes. This improvement stems from the implementation of recursive Toom-Cook schemes, which offer a wide range of potential design choices for optimizing multiplication steps.

The value of ε is greater than zero and is dependent on specific algorithm implementation details, allowing for further refinement of the gate count. To rigorously evaluate these complex circuits, the team created a formally verified harness that accepts a design specification, termed a “policy,” from an external source, potentially including an AI agent.

This harness then generates formalized proofs confirming the mathematical correctness of the algorithm, the asymptotic scaling of the total gate cost, and the accurate translation of the verified algorithm into a detailed circuit implementation using an intermediate representation. The system builds on work from Kahanamoku-Meyer and Yao, who in 2024 developed a phase-based multiplication scheme using recursive Toom-Cook multiplication to achieve the O(n^(2 + ε)) gate count.

The harness addresses a critical gap in evaluating the practical benefits of this construction, determining whether it offers a gate count advantage at relevant input sizes and identifying the point at which the improved scaling becomes apparent. The verification process focuses on gate count, as the current construction does not improve upon previously achieved logical qubit counts for RSA factoring.

The system recursively decomposes gate-level Quantum Fourier Transforms and Phase Products into smaller instances, relying on the correctness of these decompositions to ensure the overall algorithm functions as intended. Previous work by Nanniyur and Jayanti formalized classical Toom-Cook multiplication, providing a foundation for this quantum verification process.

Kahanamoku-Meyer and Yao Construction for Improved Factoring

The Kahanamoku-Meyer and Yao construction, developed in 2024, offers a potential pathway to factoring large numbers with fewer quantum gates than previously understood, and a new formally verified harness now allows for rigorous assessment of its efficiency. While standard implementations of Shor’s algorithm for factoring n-bit biprimes typically require O(n^3) gates, using recursive Toom-Cook schemes within the KMY construction can reduce this cost to O(n^(2 + ε)).

This improvement hinges on the careful design of recursive multiplication steps, creating a broad design space where even small optimizations can yield substantial gains. At n = 2048 bits, initial testing with a custom program yielded 1.685 x 1012 T-gates, demonstrating the scale of computation involved and the need for efficient optimization. The authors note, “can lower the total cost, but more pieces or costlier recombination can erase the gain,” highlighting the delicate balance required for optimization.

ForShor Harness Verifies Designs with Lean Formal Proofs

The ForShor harness not only confirms the mathematical accuracy of quantum factoring algorithms, but also validates the translation to a detailed circuit implementation, a step often absent in quantum algorithm development. The system’s capabilities extend beyond simple validation. It constructs the order-finding circuit and lowers it to Qualtran, an intermediate representation suitable for logical resource estimation. Participants in the open challenge submit policies through a dedicated interface at https://forshor.ai, where the harness assesses validity and, if accepted, applies pre-proven theorems regarding correctness and cost to the resulting circuit without further proof.

The harness’s design explicitly addresses challenges common in algorithm descriptions, such as finite-width signed arithmetic and padded registers within recursive operators. “The harness checks validity, preserves circuit semantics, and writes an intermediate representation that can be read into Qualtran for logical resource estimation,” according to documentation accompanying the release.

Lean development resources and an interactive graph of declarations are available at https://verifiedqc.github.io/ForShor/, encouraging contributions and optimizations to the underlying algorithms. The open challenge framework positions ForShor as a tool for heuristic search, with the harness serving as an impartial arbiter of algorithmic integration and performance.

Policy-Based Input for Arithmetic Circuit Specifications

This verification extends to establishing guarantees for success, approximation bounds, and circuit identities, all while tracking asymptotic gate counts. The system’s design ensures that any submitted “policy”, a design specification for a recursive circuit, proven legitimate within the Lean formal verification system yields a correct order-finding circuit, regardless of its origin, be it human design or artificial intelligence.

This process relies on arithmetic instructions including scaled addition, negation and shifts, all operating on registers with defined precision to minimize error accumulation. The system’s compiler, itself proven correct, operates within a recursive construction framework, where submitted tables define the design of the Kahanamoku-Meyer construction’s recursive multiplication subroutine, known as PhaseProduct.

This compiler generates a “lowered gate layer” consisting of elementary gates and width-indexed arithmetic, against which the gate-count theorem is proven, and from which an intermediate representation is extracted. Regardless of how the policy was produced, this demonstrates a robust and verifiable approach to quantum circuit design. The harness’s ability to establish guarantees at the gate level and transfer them to the lowered circuit is a key feature, enabling the search for factoring circuits with fewer than n3 gates.

Formal Verification of End-to-End Asymptotic Complexity

The newly released harness allows both researchers and AI agents to explore factoring circuit designs while guaranteeing machine-checked correctness and asymptotic complexity, according to its creators. This open challenge, hosted at ForShor.ai, aims to accelerate the search for more efficient quantum algorithms beyond the traditionally understood O(n^3) gate requirement for factoring n-bit biprimes. The system’s intermediate representation, derived directly from verified definitions, ensures the circuit priced by Qualtran is the same one proven correct, a key link often missing in quantum algorithm development.

The harness translates verified algorithms into a detailed circuit implementation using a small language of primitive operations, register expressions and recursive calls, then emits this to Qualtran for resource estimation. Phase rotations are converted to T-gate estimates, allocating a per-rotation error and charging a mean cost of 3.075 log2(1/εrot) + 0.86 per rotation, providing an upper-bounded T-gate count.

While the current implementation limits interpolation points to the K=2 closed form, with tables used for K ≥ 3, the system demonstrates an asymptotic complexity of O(n^(2 + ε)) in Lean, as proven within the formal verification process. “ForShor focuses on accessibility and optimization of the design space,” the researchers state, “supporting agentic search for improvement while ensuring fast, formally verified algorithmic correctness.”

Connecting Arithmetic Design with Machine-Checked Certification

This verification extends to guaranteeing end-to-end asymptotic complexity, meaning the system can predict how the computational cost will scale with increasing problem size. This approach addresses a critical need for reusable proofs as arithmetic designs evolve, supporting ongoing efforts to optimize quantum algorithms. Peng et al. have previously demonstrated correctness, success guarantees, and executable circuit generation for Shor’s algorithm, but maintaining proof reusability with changing arithmetic designs presents a unique challenge.

Recent advances in AI-assisted mathematics and quantum circuit optimization further emphasize the demand for tools that can inspect, check assumptions, and integrate new results into larger constructions. The harness’s arithmetic instructions, addScaled, negate, shiftL, and shiftR, operate on registers and are subject to specific conditions, such as ensuring exact division during right shifts. Any policy proven legitimate within Lean yields a correct order-finding circuit, with proofs tracing a hierarchy from factoring through modular exponentiation to the underlying arithmetic gates. The researchers state, emphasizing the system’s rigorous validation process.

Open Challenge Facilitates AI and Human Circuit Contributions

The efficiency of quantum factoring circuits hinges on navigating a vast design space within recursive multiplication steps, where the parameter ε, greater than zero, dictates the precise gate cost beyond the standard O(n^2) scaling. This inherent flexibility, while promising, introduces a challenge in identifying optimal circuit configurations, prompting a new approach to quantum software engineering that embraces both human expertise and artificial intelligence. Researchers have developed a formally verified harness capable of ingesting a “policy”, a design specification for recursive circuits, from any source, including AI agents, and generating machine-checked proofs of correctness.

The system’s ability to assess and validate these designs is now being offered as an open challenge, accessible at ForShor.ai, inviting contributions from both researchers and AI agents seeking to minimize gate counts while maintaining rigorous verification. The open challenge addresses a potential imbalance in an era where automated research could generate results exceeding human comprehension.

The harness’s output is designed to be interpretable, mitigating the risk of accumulating autoformalized results without adequate human understanding. “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,” according to the researchers, emphasizing the collaborative potential of this new framework.

Qualtran Integration for Circuit Generation and Resource Estimation

The verified circuit produced by the new harness is not confined to mathematical proof; it is translated into a format compatible with Qualtran, a system for scalable resource estimation. This export relies on a lowered order-finding circuit, transforming the Lean-based verification into an intermediate representation that Qualtran can process.

Qualtran’s prior use in resource estimation allows for symbolic gate calculation, a critical component for assessing the efficiency of the Toom-Cook multiplication central to this work. The system overcomes this limitation by exporting a compact symbolic description of the circuit, detailing recursive components like the PhaseProduct and Quantum Fourier Transform (QFT) as lookup tables.

Qualtran then uses this description to evaluate the circuit and estimate resource requirements, bypassing the need to simulate a full, concrete circuit within Lean. These Lean-centric circuit primitives, termed ‘Bloqs,’ are sequences of operations on a quantum register, enabling scalable resource estimation without requiring a complete circuit traversal. By composing these Bloqs according to the pattern emitted by Lean, the system estimates the number of phase rotations, Clifford gates, and Toffoli gates required.

Verification within Qualtran extends to numerical checks for small instances, comparing the output of the Bloq-based algorithm to classical implementations and tracking accumulated phase and gate count alignment upon decomposition. These details often pose challenges in traditional manuscript-level algorithm descriptions. This integration of formal verification with resource estimation represents a step towards more reliable and efficient quantum algorithm development.

👉 More information
🗞 Formally verified harness for Shor's order finding algorithm with $O(n^{2+ε})$ gate cost
✍️ Anirudh Suresh and Runzhou Tao (University of Maryland); Joshua M. Courtney and Yudong Cao
🧠 ArXiv: https://arxiv.org/abs/2611.20342

Stay current

See today’s quantum computing news on Quantum Zeitgeist for the latest breakthroughs in qubits, hardware, algorithms, and industry deals.

Avatar of Dr. Donovan

Latest Posts by Dr. Donovan: