acceptodds
Under review as a conference paper at ICLR 2027

Agentic Autoresearch with Formal Verification for Quantum Algorithms

Abstract

Here we present a scheme of autoresearch leveraging AI agents for quantum algorithms, using as an example the implementation of recursive Toom-Cook multiplication circuits due to Kahanamoku-Meyer & Yao (2024) inside the order finding circuit for Shor's algorithm. The recursive scheme allows for asymptotically more efficient circuits than schoolbook multiplication, but the design landscape for detailed implementations of the recursive circuitry is complex. Here we expose this landscape for AI agents to explore, while constraining such exploration within the confines of formal verification. We report that the agentic exploration so far has yielded a meaningful reduction in arithmetic operation count with respect to the previously published constructions (26.7%-34.5% reduction in arithmetic operations across different circuit families). The formally verified harness that we publish is open to receive further contribution from any agents that one may deploy towards this problem.

Primary area:
applications to physical sciences (physics, chemistry, biology, etc.)
Keywords:
formal verification, Lean, program synthesis, LLM agents, quantum computing

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_Gb2JOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper explores the use of AI agents to optimize interpolation schedules in quantum arithmetic. The agents submit candidate programs along with Lean proofs; the system verifies these proofs against a fixed correctness contract, then scores, archives, and filters the validated solutions. Building upon the existing recursive Toom-Cook construction, the work optimizes the arrangement of arithmetic operations for PhaseProduct and PhaseTripleProduct.

The paper reports a 26.7%–34.5% reduction in arithmetic operations across three established baselines. For PhaseProduct (with k=3k=3), under a specified recursive strategy and logical gate model, a 6.6%–12.6% reduction in gate count is also achieved. While these results demonstrate component-level optimization within a specific model, they do not yet represent end-to-end gains for the full Shor’s algorithm.

Critical strengths
  • The framework decouples candidate generation from correctness verification. Results submitted by an agent must pass checks involving a fixed contract, the Lean kernel, and an audit of axioms. This design ensures that the credibility of the results does not rely on the agent’s own judgment, while also allowing for the independent re-examination of stored proofs—a key value of this framework.

  • Concrete optimization outcomes have been achieved. By aligning the number of phase-products with the product layers, the new schedules reduce the total count of arithmetic operations. The paper further demonstrates the benefits of certain approaches within a specified logical gate model, providing empirical evidence for this optimization direction.

Critical weaknesses
  • The actual contribution of the agent to the search and proof-generation processes remains unclear. The paper fails to present a representative Lean proof generated by the agent, nor does it specify the respective roles played by existing lemmas, automated tools, and human interventions. Furthermore, the search process and the computational budget are not fully documented. Consequently, it is difficult for readers to discern the nature of the proposed "agentic" methodology or to identify the primary factors driving the reported results. The fact that the final output is verified does not, in itself, substantiate the specific contribution of the agentic autoresearch approach.

  • There is also a missing link in the argument connecting the verified high-level schedules to the actual gains in quantum algorithms. Section 7 explicitly states that "circuit-level lowering" falls outside the scope of the formal contract; therefore, the conditions under which the new schedules can replace the original circuit modules must be clarified. Moreover, the number of arithmetic operations does not always correlate with the gate cost—a discrepancy illustrated by the counterexamples provided in Section 6.3. While the paper reports improvements under a specific gate model, the Introduction characterizes the 6.6%–12.6% figures as improvements to the total operational cost of Shor’s algorithm, whereas Appendix A explicitly clarifies that these do not represent end-to-end reductions. This inconsistency significantly complicates the assessment of the paper’s practical implications.

Questions for authors
  1. Please provide a representative agent submission, including the candidate program, the theorem statement, and the actual Lean proof. Which proof steps were proposed by the agent, and which were derived from existing lemmas or automated tools? Was any manual intervention or modification required?

  2. Beyond allowing the agent to submit programs and invoke Lean for verification, what additional mechanisms does this paper introduce into the agent’s search strategy? What evidence is currently available to demonstrate the effectiveness of these mechanisms?

  3. Once a schedule satisfies the symbolic contract, what further conditions must it meet to qualify as a valid, finite-precision quantum circuit? Are these conditions already guaranteed by the theoretical results cited in the paper?

  4. Please clarify the scope of the 6.6%–12.6% improvement in resource efficiency. How does the statement in the Introduction regarding the total operational cost of Shor’s algorithm align with the specific evaluation scope defined in §4.2 and Appendix A?

1 comment

We thank the reviewer for noting that the credibility of results never rests on the agent's judgment and that stored proofs can be re-examined independently. We would like to address each point below.

  1. A submission is a policy containing tables and thresholds. The harness automatically generates the Lean file, then the Lean kernel will try to prove the correctness of the tables by decide. No human intervention is required.

  2. Beyond submission and verification, the harness provides an archive that can be re-ranked under other cost models, a planner, and two-tier verification.

  3. The condition is the same as in the paper, and we are the first to formally verify it in Lean and develop a harness to automatically verify it for any agent submission.

  4. Algorithm gains. We revised the Introduction: the 6.6%6.6\%–12.6%12.6\% is on gate counts of one n-bit multiplication (n = 1,024–16,384) under our gate model, compared to the published k=3 table in fixed-k=3 self-recursion (Table 2), not end-to-end Shor costs.

Reviewer_dNaSOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This is an interesting paper that publishes an agentic AI framework for auto research on quantum algorithms. The focus is on recursive multiplication circuits and this area is exposed to AI agents for exploration while constraining the results using formal verification. This is sort of a super intelligence applied to quantum approach, with agentic AI making advances and a formal methods engine ensuring they cannot inject error into the whole approach.

Critical strengths

Strengths:

  1. Formal verification allows this super intelligence approach to remain provably correct.
  2. There is an open harness that others can build upon.
Critical weaknesses

Weaknesses:

  1. The lean proof is not completely aligned with the natural language text. Can you please verify and update the Lean proof? Also, could you prove the result without the companion paper ForShor?
  2. There is only 1 baseline being reported?
  3. Agentic auto research usually reports agent prompts, budgets, trajectories and so on. I do not find such discussion in the paper.
Questions for authors

Question: Please give me the main correctness theorem and its proof. Please also provide a complete discussion of the agents.

1 comment

We thank the reviewer for recognizing that formal verification keeps accepted results correct and that the harness is open for others to build on. We believe that several of the concerns can be resolved by clarifying the scope of our contribution, and we hope the responses below, including new experiments, help the reviewer reassess the submission.

1. Correctness theorem and Lean alignment. It is not entirely clear to us what it means for the Lean proof to be “not completely aligned with the natural language text”. The Lean proof passes and we have made sure that the statements proven in Lean are consistent with our understanding of the quantum algorithm. It would be useful if the reviewer can clarify where precisely the natural language text fails to align with the Lean codebase.

2. Baselines. The policy search is a highly structured problem that can be solve with many different approaches. In addition to AI agents, one can design various tailored heuristics for the problem such as Monte Carlo methods. A comprehensive benchmark of agents versus the other methods is beyond the timeframe of this particular rebuttal, but within scope of our general effort in this direction.

In the paper we compare against tables in the original Kahanamoku-Meyer & Yao paper (PhaseProduct at k=3 and PhaseTripleProduct at k=3,4). We also compared against an agent-free bounded exhaustive search (k=2,3) and an agent-free heuristic search (simulated annealing with beam-search synthesis, k=2 to 10). The exhaustive search proves that 21 is the least Eq. 1 score at k=3 within its bounds, which our reported k=3 table attains. On QT at n=2048, every agent run beat the exhaustive search by using larger k, while the heuristic was 0.3%0.3\% below the best agent run.

3. Agent details. We ran Claude Sonnet 5.5 with a 90-minute budget and no human input for eight runs; four runs had the published tables and four had all table-bearing files removed. All eight produced fully verified policies beating the reference (6.141010) and the published-table starting policy (5.881010); the best is 29%29\% below the reference. All 20 complete verifications were accepted, and 8 invalid policies were caught by a fast check. The median run used 51–66 minutes and 4.6–5.9M input tokens. Prompts, every verification attempt, token counts and transcripts will be added in an appendix.

Reviewer_AKsSOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the agentic autoresearch for quantum algorithm implementation. More concretely, as example, this paper aims to improve the arithmetic inside Shor's algorithm with AI agents while keeping every accepted design correct. The target is the recursive PhaseProduct circuit of Kahanamoku-Meyer & Yao (2024), which, as in Toom-Cook multiplication, splits each operand into k chunks and replaces one product by 2k-1 smaller ones. Built on a theorem from an unpublished manuscript, which states that any interpolation table meeting four conditions gives a correct PhaseProduct, the authors propose an autoresearch harness. In it, agents search for tables, and the Lean kernel checks their proofs that the four conditions hold. The proposed methods work as follows. Tables are Lean programs over five instructions that must meet the four conditions (valid distinct points, each used once, the required row at each phaseProduct, restoration of the initial state). The harness keeps submissions from changing the verifier, the contract or the scoring, adds an axiom audit, scores tables by arithmetic operations plus five times product layers (Eq. 1), and keeps the lowest-cost table per target. A planner (Eq. 2) estimates logical gate counts for one nn-bit multiplication in the paper's gate model.

Critical strengths
  1. The search problem is precisely defined. A circuit family whose width nn is a formal parameter (Figure 1) becomes a search over small programs with exact semantics and four conditions that can be checked (Sections 3.1–3.3). Since the archive stores verified tables, it can be re-ranked without re-verification.

  2. The agents cannot change the checks. Preflight blocks changes to the verifier, the contract and the scoring; the axiom audit allows only propext, so sorry, native_decide and declared axioms fail; promotion checks each champion again (lines 254–292).

Critical weaknesses
  1. Regev's factoring algorithm is not considered. The paper considers its tables only for Shor's algorithm, where each of the t=O(n)t = O(n) multiplications "multiplies a quantum register by a known integer" (Appendix A). Regev (An Efficient Quantum Factoring Algorithm, 2025) factors nn-bit integers by running a circuit of O~(n3/2)\tilde O(n^{3/2}) gates n+4\sqrt{n}+4 times; in each of its O(n)O(\sqrt n) steps, an nn-bit register is squared and then multiplied by a product of small numbers selected by the exponent register. Kahanamoku-Meyer & Yao (2024), whose circuits the paper builds on, already give a gate count of O(n1.5+ϵ)O(n^{1.5+\epsilon}) for their multiplication in Regev's algorithm, against O(n2+ϵ)O(n^{2+\epsilon}) in Shor's algorithm.

  2. The agentic part is not evaluated. Section 5.1 names only the machine, the models and the workspace. There are no counts of submissions, rejections per stage, token budgets or human input (lines 378–379, 470–473, 512–515), and no comparison with a search without agents, e.g., a bounded search over small programs of the five instructions, or the superoptimization of Xu et al. (2022). As the contract and Eq. 1 are exact and fast to evaluate, this should be feasible at least for k=3k=3. Without it, nothing shows that the agents add anything to search,

  3. The Introduction claims more than the paper shows. It reports reductions "for the same subroutine in Shor's algorithm by 26.7-34.5%" and "a total 6.6-12.6% improvement on the total running cost of Shor's algorithm for solving RSA" (lines 88–91), which should be corrected. Only PhaseProduct is used in order finding (line 392); the 29.6% and 34.5% are for PhaseTripleProduct. Table 2 counts gates for a single nn-bit multiplication in the paper's gate model, with each k=3k=3 table recursing only on itself, a kk the planner never selects at the root; Appendix A states that these "are not end-to-end percentage reductions for Shor's algorithm" (lines 774–776).

Questions for authors
  1. Please explain why only Shor's algorithm is considered, or report planner gate counts for the squarings and multiplications in Regev's circuit.

  2. Were the agents shown the published tables?

  3. What are the agents' k=3k=3 table, its points, and the overheads of both k=3k=3 tables? How much of the 6.6–12.6% remains at equal widths?

1 comment
AuthorsOpenReview ↗

Response to Reviewer AKsS

We appreciate that the reviewer recognizes the precise formulation of our search problem and the safeguards protecting the verification pipeline. However, we believe the low rating undervalues our contribution and has discouraged us from further work. After consideration, we regard our additional results as outside this rebuttal’s scope. This submission contributes a search environment for parameterized quantum arithmetic schedules and concrete improvements over published schedules.

1. Relevance to Regev. Indeed, the PhaseTripleProduct circuit by Kahanamoku-Meyer and Yao can be used for Regev’s factoring algorithm. However, our goal in this paper is not to show the asymptotically smallest circuit for integer factorization. Instead, our goal is to show the formally verified harness and the agentic architecture. The optimized PhaseProduct subroutine enables the classical-quantum multiplication circuit for Shor’s algorithm, while the optimized PhaseTripleProduct enables the quantum-quantum multiplication used in Regev’s algorithm.

2. Role of agentic search. We conducted eight unattended coding-agent runs, four with published-table examples and four with those examples and table-bearing files removed. Each had a stated 90-minute budget and no human input after launch; verification outcomes, tokens, and timing were recorded. All eight beat the fixed reference, and seven improved on the unchanged starter policy. Of 21 verification attempts, 17 were accepted and four rejected for disallowed points. An agent-free bounded exhaustive search covered k=2,3k=2,3. At k=3k=3, it established the minimum Eq. 1 score of 2121 within its bounds; no agent matched this. An agent-produced k=3k=3 policy achieved 1.4%1.4\% lower Q×TQ\times T, but the baseline priced only Eq.-1-optimal tables, so this is not a direct comparison of search methods optimizing Q×TQ\times T. Agents also produced verified policies for k≥4k\geq4, outside the baseline’s range. This new evaluation demonstrates unattended verified improvement, not general superiority over non-agent search, and is limited by sample size, differing objectives, search bounds, and shared verification queues.

3. Introduction. We revised the Introduction to clarify that 26.7%26.7\% concerns PhaseProduct arithmetic operations; 29.6%29.6\% and 34.5%34.5\% concern PhaseTripleProduct, not Shor’s order finding. The 6.6%6.6\%-12.6%12.6\% savings concern multiplication gate counts at 1,024–16,384 bits under the paper’s gate model, replacing the published k=3k=3 table in fixed-k=3k=3 self-recursion (Table 2), not end-to-end Shor costs or planner-selected mixed-kk recursion.

Questions. To address the reviewer's questions:

  1. We focus on Shor’s algorithm as a concrete application with published interpolation tables enabling comparisons under matched structural conditions. The verification framework concerns arithmetic sequences and is not restricted to Shor. Regev’s algorithm is another relevant application, but estimating its modular squarings and multiplications requires mapping those operations to the supported primitives and accounting for modular corrections, precision, and uncomputation. Our planner evaluates recursive PhaseProduct schedules; the reported improvements therefore concern these primitives, not end-to-end resource reductions or a comparison between the two factoring algorithms.

  2. Published-table exposure. Yes, in the full starter-pack setting: agents received executable published tables for PhaseProduct at k=3k=3 and PhaseTripleProduct at k=3,4k=3,4, plus templates they were instructed to use. The additional evaluation included four full-pack runs and four with table-bearing materials removed. All full-pack runs first verified the unchanged starting policy. This documents access to published constructions in the additional evaluation, but does not establish per-run exposure during the original manuscript’s search.

  3. k=3k=3 table. Both schedules use {0,1,∞,−1,−2}\{0,1,\infty,-1,-2\}. Starting from ri=xir_i=x_i, execute these updates sequentially on each operand:

  • r1←r1+r0r_1\leftarrow r_1+r_0; r1←r1+r2r_1\leftarrow r_1+r_2. Apply products at registers 0,1,20,1,2 (points 0,1,∞0,1,\infty).
  • r0←r0−r1r_0\leftarrow r_0-r_1; r1←r1+2r2r_1\leftarrow r_1+2r_2; r1←r1+2r0r_1\leftarrow r_1+2r_0; r0←r0+r1r_0\leftarrow r_0+r_1; r0←r0+4r2r_0\leftarrow r_0+4r_2. Apply products at registers 0,10,1 (points −2,−1-2,-1).
  • Restore: r1←r1−r2r_1\leftarrow r_1-r_2; r0←r0−4r2r_0\leftarrow r_0-4r_2; r1←r1−r0r_1\leftarrow r_1-r_0; r0←r0+2r1r_0\leftarrow r_0+2r_1.

For initial widths (b,b,b+r)(b,b,b+r), n=3b+rn=3b+r, the estimator gives

W_{\mathrm{agent}}=b+\max(2,r+1)+10.$$ Equal-chunk overheads are therefore 14 versus 12 bits. **Equal widths.** Fixing the published width ladder and recursion tree leaves **1.6-3.3%** savings from removing negations. This is an analytical reconstruction, not a fresh planner run. The reported **6.6-12.6%** also incorporates smaller widths and possible stopping-depth changes instead of end-to-end Shor savings.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.