Lean-QuantumAlg: A Framework for AI Agents to Produce Quantum Algorithms that Humans Can Trust
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.
Related
- A unifying framework for quantum algorithms for time-dependent non-unitary dynamics
- oracq: A Modular Framework for Implementing and Analyzing Quantum Scientific Computing Algorithms
- Accelerating noisy variational quantum algorithms with physics-informed denoising networks
- Tight Communication Bounds for Distributed Algorithms in the Quantum Routing Model
- Imaginary-time-enhanced feedback-based quantum algorithms for ground-state preparation
BibTeX
@misc{zhang2026leanquantumalg,
title = {{Lean-QuantumAlg: A Framework for AI Agents to Produce Quantum Algorithms that Humans Can Trust}},
author = {Lei Zhang and Mingrui Jing and Yusheng Zhao and Jiahong Liu and Xin Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.30216},
eprint = {2610.30216},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.30216},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Lean-QuantumAlg: A Framework for AI Agents to Produce Quantum Algorithms that Humans Can Trust
AU - Lei Zhang
AU - Mingrui Jing
AU - Yusheng Zhao
AU - Jiahong Liu
AU - Xin Wang
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.30216
UR - https://arxiv.org/abs/2610.30216
AB - 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.
ER -