Efficient Formal Verification of Quantum Error Correcting Programs

Qifan Huang, Li Zhou, Wang Fang, Mengyu Zhao, Mingsheng Ying

TL;DR

This paper introduces an efficient formal verification framework for quantum error correction (QEC) programs, enabling rigorous proof of their correctness. By developing a novel hybrid assertion and program logic, and an efficient method for handling verification conditions, they provide both a formally verified QEC verifier in Coq and an automated tool, Veri-QEC, that significantly speeds up verification for complex QEC codes.

What Problem Does This Paper Address?

Quantum error correction (QEC) is crucial for building fault-tolerant quantum computers, but the complexity of QEC protocols makes verifying their correctness before deployment a significant challenge. Existing methods like numerical simulation require vast numbers of test cases, while symbolic execution struggles with non-Clifford gates and error propagation. While program logic approaches have shown promise, they haven't scaled to large-scale QEC codes with realistic error scenarios. This paper addresses the need for an efficient and scalable formal verification framework that can handle complex QEC programs and various error types.

Methods

The authors propose a formal verification framework built on a hybrid classical-quantum assertion logic and a program logic specifically designed for QEC. Key technical contributions include:

  • Assertion and Program Logic: They define an assertion logic that uses Pauli expressions as atomic propositions and interprets logical connectives based on quantum logic (e.g., disjunction as subspace sum). This allows for simultaneous reasoning about subspaces and quantum states, and the modeling of error conditions not previously addressable.
  • Efficient Verification Condition Handling: For Pauli errors, verification conditions are reduced to classical assertions solvable by SMT solvers. For non-Pauli errors, a heuristic algorithm is developed to handle them.
  • Verified QEC Verifier (Coq-based): They formalize their program logic in the Coq proof assistant, providing a mechanically verified QEC verifier that enhances confidence in the logic.
  • Automated QEC Verifier (Veri-QEC): An automated tool implemented in Python using Z3 and CVC5 SMT solvers is developed. Veri-QEC handles various verification scenarios, including standard and propagation errors, and correction steps.

Datasets

Not discussed in the paper. The paper focuses on developing a framework and tool for verifying QEC programs, using examples like the Steane code and surface codes for evaluation.

Key Insights and Ideas

  • Hybrid Logic for QEC: The integration of classical variables and quantum logic in their assertion language is key to reasoning about complex QEC properties, such as the maximum number of correctable errors, which was difficult with previous approaches.
  • Efficient VC Reduction: The method for reducing verification conditions for Pauli errors to classical assertions solvable by SMT solvers is a significant step towards automation.
  • Heuristic for Non-Pauli Errors: Developing a heuristic algorithm for non-Pauli errors demonstrates a practical approach to handling these more complex scenarios.
  • Coq Formalization for Trust: Mechanically verifying the program logic in Coq provides a high degree of assurance in the soundness of their verification framework.
  • Scalability through Parallelization: The parallelization strategy in Veri-QEC is crucial for tackling the exponential complexity of verifying larger QEC codes.

Key Results

  • Veri-QEC Performance: Veri-QEC demonstrates significant efficiency improvements, especially with user-provided error constraints. For instance, verifying a d=19 surface code (361 qubits) with combined locality and discreteness constraints took approximately 100 minutes.
  • Scalability: The parallel verification approach allows for the verification of QEC codes with up to 121 qubits within ~200 minutes for general properties, and up to 361 qubits with user-provided error constraints within ~100 minutes.
  • Precise Error Detection: The tool can effectively verify precise error detection properties, identifying minimum weight undetectable errors.
  • Benchmark: A benchmark of 14 verified stabilizer codes is presented, showcasing the tool's functionality across various QEC code families.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • Completeness for Loops: While the proof system is sound and relatively complete for finite QEC programs without loops, its completeness for programs with while-loops remains an open question.
  • Gate Set Expressivity: The current program logic is restricted to the Clifford + T gate set. Extending the logic to handle gate sets beyond Clifford + T is desirable.
  • Probabilistic Reasoning: The current projection-based logic cannot directly reason about probabilities. Generalizing the logic to a satisfaction-based approach could address this.
  • Unified Solution: Exploring approaches to integrate the verified verifier and the automatic verifier into a single unified solution is a future goal.

Summary updated

Abstract

Quantum error correction (QEC) is fundamental for suppressing noise in quantum hardware and enabling fault-tolerant quantum computation. In this paper, we propose an efficient verification framework for QEC programs. We define an assertion logic and a program logic specifically crafted for QEC programs and establish a sound proof system. We then develop an efficient method for handling verification conditions (VCs) of QEC programs: for Pauli errors, the VCs are reduced to classical assertions that can be solved by SMT solvers, and for non-Pauli errors, we provide a heuristic algorithm. We formalize the proposed program logic in Coq proof assistant, making it a verified QEC verifier. Additionally, we implement an automated QEC verifier, Veri-QEC, for verifying various fault-tolerant scenarios. We demonstrate the efficiency and broad functionality of the framework by performing different verification tasks across various scenarios. Finally, we present a benchmark of 14 verified stabilizer codes.
BibTeX
@article{huang2025efficient,
  author = {Qifan Huang and Li Zhou and Wang Fang and Mengyu Zhao and Mingsheng Ying},
  title = {{Efficient Formal Verification of Quantum Error Correcting Programs}},
  journal = {Proc. ACM Program. Lang},
  year = {2025},
  doi = {10.1145/3729293},
}
Figure