- 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 ), 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
-
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?
-
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?
-
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?
-
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?
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.
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.Beyond submission and verification, the harness provides an archive that can be re-ranked under other cost models, a planner, and two-tier verification.
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.
Algorithm gains. We revised the Introduction: the 6.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.