Formal Verification of Quantum Programs

108 concepts64 papers2 proposals

In classical software engineering, we reason about program correctness by tracking discrete state transitions. A variable $x$ holds a specific value, and a statement updates that value deterministically or probabilistically. We can verify these programs using well-established frameworks like Hoare logic, which uses assertions to define subsets of valid states at any given point in execution.

Quantum software upends this paradigm. A quantum state does not consist of discrete assignments, but rather continuous complex-valued amplitudes across an exponentially large Hilbert space. Phenomena like superposition mean a program exists in multiple states simultaneously, while entanglement prevents us from verifying individual qubits in isolation. Furthermore, physical execution is inherently probabilistic and destructive due to measurement collapse, making traditional testing methods like state tomography computationally prohibitive.

To build trustworthy quantum software, researchers are developing formal verification frameworks that translate quantum mechanics into rigorous, automated mathematical logics. Instead of executing code on physical hardware or simulating it exponentially, these techniques mathematically prove that a quantum program satisfies its specifications for all possible inputs.

From Classical Assertions to Quantum Predicates

To verify a program, we must first define what it means to assert a property about a quantum state. In classical logic, an assertion like $\{x > 0\}$ acts as a filter on a set of discrete states. In the quantum realm, states are represented as density matrices, and assertions are replaced by quantum predicates—typically represented as Hermitian operators or projection matrices onto specific subspaces of a Hilbert space.

The foundation of this approach adapts Dijkstra’s classical "weakest precondition" framework. As shown by Ellie D'Hondt in Quantum weakest preconditions, instead of transforming boolean conditions, a quantum predicate transformer propagates physical observables backward through unitary operations. This establishes a formal duality between the forward evolution of a quantum state and the backward transformation of its measurable properties.

Classical:  {Precondition}  ---> [Statement] ---> {Postcondition}
Quantum:    [Pre-Observable] <--- [Unitary Op] <--- [Post-Observable]

Building upon this predicate-transformer semantics, Mingsheng Ying introduced Quantum Hoare Logic in Toward automatic verification of quantum programs. This framework introduces "proof outlines" that intersperse quantum predicates directly within the program text. By breaking down complex quantum control flows into a structured sequence of localized predicate transformations, developers can systematically verify that an algorithm preserves its intended quantum properties from input to output.

Bridging Classical Control and Quantum States

Practical quantum applications are rarely purely quantum. Instead, they are hybrid systems where classical control logic (such as loops and conditional branches) orchestrates quantum gate operations and processes measurement outcomes. This interplay introduces a major challenge: how do we reason about deterministic classical variables and probabilistic quantum states within the same logic?

Traditional quantum logics often struggle with this boundary, limiting their scope to fixed-depth circuits without complex control flow. To bridge this gap, Feng et al. developed a unified framework in Quantum Hoare Logic with Classical Variables. By explicitly modeling the joint state of classical variables and quantum density matrices, the authors provided the first formal verification of the entire Shor’s factorization algorithm, proving the correctness of both its quantum order-finding subroutine and its classical post-processing steps.

To simplify the mathematics of these hybrid structures, Yuxin Deng introduced a "satisfaction-based" Hoare logic in Formal Semantics of a Classical-Quantum Language. Rather than relying on expectation values that require complex, infinite sequences of assertions to handle loops, this logic maps quantum states to familiar logical operators like "and" and "or." This allows developers to reason about iterative structures using standard inductive techniques, significantly reducing the mathematical overhead of verifying quantum loops.

Push-Button Automation via SMT Solvers

While formal logics provide the mathematical rules for verification, constructing proofs manually remains a tedious and error-prone task. To make verification practical for software developers, recent work focuses on automation by compiling quantum programs into logical constraints that can be solved by classical Satisfiability Modulo Theories (SMT) solvers.

The core mechanism relies on symbolic execution. Instead of tracking concrete state vectors, an automated verifier treats the input states and classical control signals as symbols. For example, Bauer-Marquart et al. developed symQV in symQV: Automated Symbolic Verification of Quantum Programs. By encoding quantum circuits into SMT formulas and utilizing a "unit box" abstraction to encapsulate gate operations, symQV can automatically verify that algorithms like Grover's search or the Quantum Fourier Transform conform to their specifications for any possible input state.

[High-Level Quantum Code] 
          │
          ▼ (Symbolic Execution / SSA Transformation)
[Mathematical Proof Obligations] 
          │
          ▼ 
[Classical SMT Solver (e.g., Z3)] ───> [Success / Counterexample]

Similarly, Lewis et al. introduced SilVer in Automated Verification of Silq Quantum Programs using SMT Solvers. SilVer automatically translates high-level quantum code written in the Silq language into Static Single Assignment (SSA) form. This conversion generates precise verification conditions regarding measurement probabilities, passing them to an off-the-shelf SMT solver to automatically validate program requirements without requiring manual proof construction from the user.

Scaling State Spaces with Decision Diagrams

When moving from isolated circuits to full transition systems or network protocols, explicit state representation encounters an exponential bottleneck. To model long-term behaviors like reachability, safety, and liveness, researchers represent quantum programs as Quantum Markov Chains (qMCs).

As demonstrated by Duan et al. in Verification of quantum programs, leveraging the Schrödinger-Heisenberg duality allows for a complete verification framework over qMCs, reducing complex program properties to verifiable relations between Hermitian operators. However, computing reachable states (image computation) within these chains remains computationally demanding on classical machines.

To mitigate this, Ying et al. proposed representing quantum transition systems as tensor networks in Image Computation for Quantum Transition Systems. By utilizing Tensor Decision Diagrams (TDDs), the authors compress the state space representation, drastically accelerating the calculation of reachable states.

Hong et al. extended this concept in Decision Diagrams for Symbolic Verification of Quantum Circuits by introducing Symbolic TDDs (symTDDs). By treating inputs and control signals symbolically within the decision diagram itself, the authors demonstrated that massive quantum circuits—such as a 160-qubit Quantum Fourier Transform—can have their functional equivalence verified in a matter of minutes on standard classical hardware. This combination of symbolic logic and compressed diagrammatic representations provides the scalability required to verify the next generation of quantum software.

Key Foundational Work

The Measurement Calculus (2004) — contributed 2 concept elements to this direction.
Proof rules for purely quantum programs (2005) — contributed 1 concept elements to this direction.
Semantics of a purely quantum programming language (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_automated_formal_verification_421b916d,
  title = {automated formal verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/automated-formal-verification/rdr_421b916d60f7475c8d29ac818d6ca715},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_automated_formal_verification_421b916d_v1,
  title = {automated formal verification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/automated-formal-verification/rdr_421b916d60f7475c8d29ac818d6ca715/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake