Lean-QuantumAlg: A Framework for AI Agents to Produce Quantum Algorithms that Humans Can Trust

arXiv:2610.30216 · quant-ph · Submitted 2026-10-21 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Lean-QuantumAlg: A Framework for AI Agents to Produce Quantum Algorithms that Humans Can Trust".

Mira: Here's the gist of the paper. The gist Lean-QuantumAlg introduces a Lean 4 framework that establishes an Algorithm–Solves–Problem contract to provide trustworthy AI-assisted development of quantum algorithms by binding correctness, success probability, borrowed-state restoration, and resource bounds to a single execution The Framework Contract Lean-QuantumAlg is a Lean 4 framework for trustworthy AI-assisted development of quantum algorithms that binds correctness, success probability, borrowed-state restoration and quantum and classical resource bounds to a single execution.

Kai: Its Algorithm–Solves–Problem contract binds correctness, success probability, borrowed-state restoration and quantum and classical resource bounds to a single execution.

Mira: The Problem states all problem settings independently of a candidate implementation, an Algorithm supplies a candidate implementation, and the framework derives the relevant probabilities, states and resource use from its execution.

Kai: The semantic relation Solves requires that this algorithm satisfy the problem, restore borrowed systems and meet the resource bounds, with every guarantee referring to the same execution.

Title and authors: Kai: We’re moving on to the title and who wrote this. The paper is titled "Lean-QuantumAlg: A Framework for AI Agents to Produce Quantum Algorithms that Humans Can Trust." It sounds very direct about the goal they are tackling.

Mira: It’s a framework, which means it’s not just one specific quantum algorithm; it's a system designed to handle the whole process of trustworthy AI-assisted development >

Lev: I see "for AI Agents" in there. That implies the system is designed to work with agents that are capable of constructing complex logic and proofs, which is a lot to take on >

Kai: Right. And then they immediately follow up by saying "that Humans Can Trust." That’s the central promise—moving beyond just functional code to something verifiable >

Mira: The implication here is that we're moving toward a system where the trust isn't just in the AI’s output, but in this formal contract that governs how that algorithm relates to the problem and its execution constraints >

Lev: So they are trying to create a bridge between the creative power of generative AI and the rigorous demands of quantum hardware constraints >

Kai: It sets up a really specific kind of problem for AI: not just "find an algorithm," but "find an algorithm that satisfies this entire contract" in one go >

Mira: And they immediately show off how they apply this to concrete things, like Grover search and attacks on RSA-two thousand forty-eight which gives the framework some immediate weight > <ref:2610.30216#pg1>

Lev: It shows the authors aren't just theorizing about abstract quantum complexity; they are grounding this in actual problems we see researchers working on >

Kai: So basically, this isn't just a theoretical exercise; it’s a practical tool to guide how we use AI to design quantum computation >

Mira: And they are making sure the contract is robust enough that the guarantees hold across different problem settings and execution models, which is a big technical hurdle >

The paper's summary: Kai: So, let’s talk about what this paper actually summarizes. It lays out this Algorithm–Solves–Problem contract as the central mechanism for building that trust we talked about earlier >

Mira: Essentially, they are defining the relationship between the problem setting, the algorithm implementation, and all those derived quantities like success probability and resource usage >

Lev: The key is that all those guarantees—correctness, restoration, resource bounds—are bound to a single execution. That means you can’t have a separate proof for correctness and another proof for resource use >

Kai: It formalizes the idea that we need every guarantee to refer to the same thing, which makes the whole structure much tighter than what we see in current verification tools >

Mira: And they detail those seven obligations within Solves: success, states, borrowed systems, events, resident space and auxiliary space and time >

Lev: That’s a lot of things to track simultaneously. For me, the fact that they quantify these fields identically over every environment and every value of the problem’s witness type is what makes it meaningful for real-world complexity >

Kai: It means you can’t just pick some arbitrary input or environment; the resource bound applies universally to that specific execution >

Mira: And they show how this works on nine algorithms, demonstrating that even complex ones are amenable to this formalization when structured correctly >

Lev: So they're showing that the structure itself is powerful enough to capture the necessary constraints for any problem we feed it, which is a strong statement about the framework’s generality >

Kai: It moves us from just checking if code runs to formally proving that the *intended* problem is solved under specific constraints >

The paper's improvements: Mira: Now they talk about how this framework improves upon existing tools. They show a comparison with other formal tools that certify quantum programs or bound their resources >

Lev: They compare it to tools like those in Table two and show that Lean-QuantumAlg supports correctness, success probability, mid-circuit measurement with classical feedback inside the certified program and a single run for all obligations > <ref:2610.30216#pg1>

Kai: The main improvement they highlight is bringing both correctness and resource constraints into one algorithm statement >

Mira: They are essentially summarizing the correctness, final state, borrowed restoration, and resource obligations into one cohesive algorithm statement >

Lev: That consolidation is key. It stops you from having to stitch together multiple separate formal proofs that might not align perfectly with the actual implementation details of the circuit >

Kai: And they show how this helps in terms of human review. The fraction of code requiring human review is less than one percent once the shared framework has been audited >

Mira: That points toward scalable AI discovery because AI agents can generate algorithms, and humans can perform a lightweight audit of their statements >

Lev: That means we don't have to manually verify every single line of generated code if the framework is sound, because the framework itself handles most of the heavy lifting >

Kai: And they give us a mechanism for explicit auditing based on different trust levels—you can choose to read everything, or just core modules >

Mira: It gives users control over how much effort they put into verification depending on their trust level in the AI agent’s output >

Conclusion: Kai: So to wrap up this paper, the main point is that Lean-QuantumAlg provides a unified way to ensure that AI-generated quantum algorithms meet a comprehensive set of requirements before they are even run >

Mira: It achieves this by creating that Algorithm–Solves–Problem contract where correctness, success probability, borrowed state restoration, and resource bounds all live in one place >

Lev: For real hardware development, the biggest implication is that we get a formal structure for checking resource usage and time budgets directly tied to the algorithm’s execution path >

Kai: And it allows us to generate algorithms where every single field is a statement about that single run algorithm, which means resource bounds apply to every path of positive probability >

Mira: It moves the focus toward scalable AI discovery where agents build, and humans audit the framework definition itself, rather than line-by-line code generation >

Lev: I just want to say that for us working on error correction, this contract gives us a formal language to discuss exactly how much overhead we’d expect when running these complex structures on actual superconducting qubits >

Kai: It’s about building systems where the verification process is tightly coupled with the physical realities of what we can actually build and measure >

Mira: So, Lean-QuantumAlg is a framework that aims to make AI assistance in quantum algorithm development more reliable by formalizing the promises an algorithm makes to us >

QudeLeap Research

quant-ph

Submitted: 2026-10-21

Updated: 2026-10-23

Comments: 22 pages including appendix; 4 figures

Code: https://github.com/QudeLeap/Lean-QuantumAlg

License: http://creativecommons.org/licenses/by/4.0/

The gist: The gist Lean-QuantumAlg introduces a Lean 4 framework that establishes an Algorithm–Solves–Problem contract to provide trustworthy AI-assisted development of quantum algorithms by binding

Key concepts

Algorithm–Solves–Problem Contract: This is the core agreement for the framework. The Problem defines what needs to be solved independently of any code. The Algorithm proposes a solution, and the framework verifies if that solution meets all required conditions (correctness, success probability, etc.) based on one execution.
Solves Obligations: The 'Solves' proposition contains seven specific guarantees: success, states (final state), borrowed systems (restoration), events (budgets), resident space, auxiliary space, and time. These are all checked simultaneously against the single execution path.
Execution Model: This defines the environment for computation by fixing four alphabets: native gates, quantum oracles, classical operations, and classical oracles. It specifies how tokens are used and how event budgets (like gate counts and space limits) are calculated based on the circuit's structure.
Division of Labor: The design separates tasks: AI agents construct the Algorithm and prove it satisfies Solves. Humans review high-level statements, the Problem definition, and execution models. This ensures human review focuses on critical definitions rather than every line of code.

Terminology

AI Agents — 1× in this paper · explained in 2 episodes

Summary

The gist Lean-QuantumAlg introduces a Lean 4 framework that establishes an Algorithm–Solves–Problem contract to provide trustworthy AI-assisted development of quantum algorithms by binding correctness, success probability, borrowed-state restoration, and resource bounds to a single execution

The Framework Contract

Lean-QuantumAlg is a Lean 4 framework for trustworthy AI-assisted development of quantum algorithms that binds correctness, success probability, borrowed-state restoration and quantum and classical resource bounds to a single execution. Its Algorithm–Solves–Problem contract binds correctness, success probability, borrowed-state restoration and quantum and classical resource bounds to a single execution. The Problem states all problem settings independently of a candidate implementation, an Algorithm supplies a candidate implementation, and the framework derives the relevant probabilities, states and resource use from its execution. The semantic relation Solves requires that this algorithm satisfy the problem, restore borrowed systems and meet the resource bounds, with every guarantee referring to the same execution.

Formal Structure of Guarantees

The framework organizes guarantees into seven obligations within a single proposition called Solves. These obligations are success, states, borrowed, events, resident space and auxiliary space and time. The success field reads the relational distribution derived from it, the state and restoration fields read its final state, and the four resource fields read the paths of its circuit. A resource bound in a Solves certificate is therefore a bound on the circuit whose success probability was proved, on the same inputs, and no field admits a separate account of the run.

Execution Model and Resource Accounting

The execution model fixes four alphabets: native gates, quantum oracles, classical operations and the classical oracles. A token is an element of one of these alphabets, and each alphabet is a type owned by its declaration. The atomic unitary operations of a circuit are the leaves of Listing 6. The event budgets are given by explicit formulas for gate counts, resident space, and auxiliary space. Quantum time uses the dependency structure of the same complete execution path.

Division of Labor for Human Review

The design fixes who reads what: The human reads the statement of main, the Problem it names and the execution model, and, once for the whole framework, the shared definitions that give these words their meaning. AI agents construct the Algorithm and prove that it satisfies Solves. The fraction of code requiring human review accounts for less than 1% of the lines of code in the import closure of every algorithm once the shared framework has been audited.

Comparison with Existing Tools

Table 2 compares representative tools, showing that Lean-QuantumAlg supports correctness, success probability, mid-circuit measurement with classical feedback inside the certified program and a single run for all obligations. The framework brings both goals into one algorithm statement, summarizing the correctness, final-state, borrowed-restoration and resource obligations.

Final Theorem and Review Process

The final theorem main asserts the existence of an implementation satisfying every obligation of the stated problem. The reviewer compares that problem and the definitions used to construct it with the source claim, checking its Witness type, how valid relates witnesses to admitted environments, and resource limits. Once this correspondence has been established, Lean checks that the implementation supplied by the proof satisfies all seven obligations on the same admitted inputs.

The paper's page 5 shows a schematic illustration of three ways to prove correctness and resources of the statement “a SWAP gate can be implemented by 3 CNOT gates”, by a human, artificial intelligence (AI), and AI with a proof framework, respectively. The paper's page 8 shows Figure 2 illustrating relationships among the objects used to certify an algorithm. The paper's page 9 shows Listing 5, which is the final theorem for quantum phase estimation (proof omitted). The paper's page 13 shows the final theorem for quantum phase estimation (proof omitted). The paper's page 18 shows Table 1 reporting the source lines requiring human review under three conditions. The paper's page 20 shows Listing 8, which is measured in-place multiplication: algorithm and final theorem (proof omitted). The paper's page 21 shows the comparison of formal tools, and the row for Lean-QuantumAlg. The paper's page 24 shows a comparison of some packages for the formal verification or resource analysis of quantum algorithms. The paper's page 5 shows the relation Solves in Listing 4. The paper's page 8 shows the seven fields of Solves quantified identically over every environment, every value of the problem’s Witness type, every external reference register and every normalized input. The paper's page 4 shows that a resource count for another circuit thus cannot discharge these bounds. The paper's page 7 shows the event budgets are given by explicit formulas. The paper's page 8 shows the joint comparison is what makes the obligation meaningful. The paper's page 9 shows Listing 7, which is Borrowed restoration and paths with positive probability. The paper's page 4 shows the joint comparison is what makes the obligation meaningful. The paper's page 8 shows that a resource bound in a Solves certificate is therefore a bound on the circuit whose success probability was proved. The paper's page 9 shows the final theorem for quantum phase estimation (proof omitted). The paper's page 4 shows that a resource count for another circuit thus cannot discharge these bounds. The paper's page 8 shows the joint comparison is what makes the obligation meaningful. The paper's page 9 shows Listing 7, which is Borrowed restoration and paths with positive probability. The paper's page 4 shows that a resource count for another circuit thus cannot discharge these bounds. The paper's page 8 shows the joint comparison is what makes the obligation meaningful. The paper's page 9 shows Listing 7, which is Borrowed restoration and paths with positive probability. The paper's page 4 shows that a resource count for another circuit thus cannot discharge these bounds. The paper's page 8 shows the joint comparison is what makes the obligation meaningful. The paper's page 9 shows Listing 7, which is Borrowed restoration and paths with positive probability. The paper's page 4 shows that a resource count for another circuit thus cannot discharge these bounds. The paper's page 8 shows the joint comparison is what makes the obligation meaningful. The paper's page 9 shows Listing 7, which is Borrowed restoration and paths with positive probability. The paper's page 4 shows that a resource count for another circuit thus cannot discharge these bounds.

Improvements for AI systems

AI agents can construct algorithms that satisfy a contract binding correctness, success probability, borrowed-state restoration, and quantum and classical resource bounds to a single execution. This allows for verifiable algorithm generation rather than just producing code or proofs in isolation.
The framework enables the separation of guarantees: separating the guarantees that Lean checks from the problem specifications and execution models that humans review. This clarifies the human review focus to the problem and the execution model, including which operations the model grants as primitives and whether the problem requires the final answer.
AI agents can produce quantum algorithm statements where every one of the seven fields is a statement about the single run algorithm, ensuring that resource bounds apply to every path of positive probability and that restoration compares the complete borrowed classical–quantum–reference state after execution with the one before.
The system provides a mechanism for scalable AI-driven discovery by allowing AI agents to generate algorithms, and humans to perform a lightweight audit of their statements, as the framework ensures that once the shared framework has been audited, the code requiring human review accounts for less than 1% of the lines of code.
The framework allows for explicit auditing based on different trust levels: a reviewer can choose between reading every definition, only core and utilized modules, or only algorithm-specific modules to determine what requires human review.

Abstract

AI agents are increasingly capable of constructing quantum algorithms and proofs, yet machine-checked proofs alone cannot guarantee that the intended problem is solved or that resource claims match the verified computation.Here we introduce Lean-QuantumAlg, a Lean 4 framework for trustworthy AI-assisted development of quantum algorithms.Its Algorithm-Solves-Problem contract binds correctness, success probability, borrowed-state restoration and quantum and classical resource bounds to a single execution, while separating the guarantees that Lean checks from the problem specifications and execution models that humans review. We demonstrate the framework on nine AI-formalized quantum algorithms, from Grover search to quantum attacks on RSA-2048 and P-256, with less than 1% of each algorithm's imported source code requiring statement-level human review once the shared framework has been audited. By integrating reusable mathematical foundations, certified algorithmic primitives and execution-grounded verification, Lean-QuantumAlg provides a basis for AI agents to construct and certify quantum algorithms, opening a path toward scalable AI-driven discovery of quantum algorithms.