arXiv:2610.17708
QEDIA: Quantum Program Verification in Lean
Yuanjie, Ren, Zhicheng Zhang, Junyi Liu, Jinzheng Li, Yidi Qi, Mingsheng Ying
Abstract
Practical quantum programs interleave quantum and classical computation: classical data shape the quantum operations that are performed, and measurement outcomes shape the classical computation that follows. Formal verification of such programs in a proof assistant requires mechanizing a program logic that handles this interplay consistently at every level, from the mathematics of quantum mechanics, through program syntax and semantics, to specifications and proof rules. Such mechanizations, along with the program proofs built on them, typically require substantial manual effort. We present QEDIA, a framework for verifying quantum programs with classical variables in Lean 4. At its foundation is an open library that formalizes the quantum Hoare logic QHL+ across all these levels and proves the logic sound for both partial and total correctness. We construct the library and the program proofs, under human supervision, using an LLM-based prover agent, whose general-purpose core we extend for quantum program verification. We illustrate QEDIA with verified programs including the quantum Fourier transform, phase estimation, repeat-until-success circuits, and Hamiltonian simulation.
AI Summary
QEDIA addresses machine-checked verification of quantum programs in which classical variables select qubits, parameterize gates, and control execution using measurement outcomes. It mechanizes the existing quantum Hoare logic QHL+ in Lean 4, covering mathematical foundations, program syntax and execution semantics, classical–quantum assertions, and proof rules. The library proves soundness for both partial and total correctness. Denotational semantics are represented by sums over finite terminating execution paths; soundness follows by induction on derivations, with loop termination established using integer-valued ranking functions. The soundness theorem depends only on Lean’s standard axioms. The library contains 2,475 theorem/lemma declarations and 673 definitions. Eleven verified examples include QFT and inverse QFT, exact-eigenphase estimation, bounded repeat-until-success circuits, Trotter simulation, and Bravyi–Kitaev, LCU, and QSP constructions for a 1D spinless Fermi–Hubbard model. Guarantees include RUS success probability at least $1-4^{-N}$ and Trotter output fidelity at least $1-\varepsilon$ when $\varepsilon\ge\theta^2\|[H_X,H_{ZZ}]\|/(2N)$. QFT verification extends beyond basis-state projectors by establishing consistency of relative phases. Human-supervised LLM agents construct the library and program proofs, using Lean feedback and reviews intended to preserve specifications and exclude vacuous guarantees. This workflow is described without quantitative automation benchmarks. The formalization uses finite-dimensional quantum systems; its language lacks quantum-controlled flow and procedure calls. Quantum error correction, recursion, and parallel or distributed programs are identified as future extensions.
We also used AI assistance during the later stages of the project to organize data and improve the clarity and language of the manuscript.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.