Reasoning about quantum programs remains a fundamental challenge, regardless of the programming model or computational paradigm. Existing verification techniques are insufficient—even for quantum circuits, a deliberately restricted model that lacks classical control, but still underpins many current quantum algorithms. Many existing formal methods require exponential time and space to represent and manipulate (representations of) assertions and judgments, making them impractical for quantum circuits with many qubits. This paper presents SAQR-QC, a logic for S calable but A pproximate Q uantitative R easoning about Q uantum C ircuits. SAQR-QC has three characteristics: (i) some deliberate loss of precision is built into it; (ii) it has a mechanism to help the accumulated loss of precision during a sequence of reasoning steps remain small; and (iii) every reasoning step is local—involving just a small number of qubits—making reasoning scalable. We demonstrate the effectiveness of SAQR-QC via two case studies: the verification of GHZ circuits involving non-Clifford gates, and the analysis of quantum phase estimation—a core subroutine in Shor’s factoring algorithm.
Reasoning about quantum programs remains a fundamental challenge, regardless of the programming model or computational paradigm. Existing verification techniques are insufficient—even for quantum circuits, a deliberately restricted model that lacks classical control, but still underpins many current quantum algorithms. Many existing formal methods require exponential time and space to represent and manipulate (representations of) assertions and judgments, making them impractical for quantum circuits with many qubits. This paper presents SAQR-QC, a logic for S calable but A pproximate Q uantitative R easoning about Q uantum C ircuits. SAQR-QC has three characteristics: (i) some deliberate loss of precision is built into it; (ii) it has a mechanism to help the accumulated loss of precision during a sequence of reasoning steps remain small; and (iii) every reasoning step is local—involving just a small number of qubits—making reasoning scalable. We demonstrate the effectiveness of SAQR-QC via two case studies: the verification of GHZ circuits involving non-Clifford gates, and the analysis of quantum phase estimation—a core subroutine in Shor’s factoring algorithm.
Quantum circuit verification is a critical yet notoriously challenging task in quantum computing. Full simulation of quantum circuits scales exponentially with the number of qubits and circuit depth, rendering it impractical for even moderately sized circuits. This paper proposes a novel approach to automated theorem proving for quantum circuit verification leveraging abstract interpretation. Our core idea is to approximate the behavior of quantum circuits using abstract interpretations, significantly reducing the computational complexity of the verification process. We outline a framework where abstract domains are constructed to represent the key properties of quantum circuits, such as qubit state fidelities and gate operations. The framework then employs logical reasoning and inference rules based on these abstract representations to automatically determine the correctness of a circuit against a given specification. We demonstrate the feasibility of this approach and discuss its potential to dramatically improve the efficiency and scalability of quantum circuit verification. The key benefit lies in shifting the verification burden from exact simulation to a more tractable abstract analysis.
Quantum computing exploits the principles of quantum mechanics to perform computation by manipulating qubit states through sequences of quantum gates, known as quantum circuits. As quantum hardware continues to scale in both complexity and qubit count, conventional verification techniques quickly become computationally impractical, motivating the need for more advanced verification approaches. Formal methods, including theorem proving, model checking, and symbolic reasoning, offer systematic and mathematically rigorous techniques for verifying functional correctness, equivalence, and implementation, while enabling early detection of design errors. This review explores how formal methods are currently applied to the verification of quantum circuits, with a particular focus on barrier certificates, abstract interpretation, model checking, theorem proving, and emerging hybrid approaches. Examining the theoretical foundations and practical applications of these techniques, discussing their strengths, limitations, and comparative effectiveness through representative case studies, review hopes to provide a holistic understanding of the topic. Highlighting the open challenges and outlining promising directions for future research, the review aims to provide a roadmap towards more scalable and robust verification frameworks for quantum computing. For readers seeking deeper engagement, the review offers an extensive set of references to support further study and exploration.
The field of quantum mechanics predates computer science by at least ten years, the time between the publication of the Schrodinger equation and the Church-Turing thesis. It took another fifty years for Feynman to recognize that harnessing quantum mechanics is necessary to efficiently simulate physics and for David Deutsch to propose the quantum Turing machine. After thirty more years, we are finally getting close to the first general-purpose quantum computers based upon prototypes by IBM, Intel, Google and others.\nWhile physicists and engineers have worked on building scalable quantum computers, theoretical computer scientists have made their own advances. Complexity theorists introduced quantum complexity classes like BQP and QMA; Shor and Grover developed their famous algorithms for factoring and unstructured search. Programming languages researchers pursued two main research directions: Small-scale languages like QPL and the quantum lambda-calculi for reasoning about quantum computation and large-scale languages like Quipper and Q# for industrial-scale quantum software development. This thesis aims to unify these two threads while adding a third one: formal verification.\nWe argue that quantum programs demand machine-checkable proofs of correctness. We justify this on the basis of the complexity of programs manipulating quantum states, the expense of running quantum programs, and the inapplicability of traditional debugging techniques to programs whose states cannot be examined. We further argue that the existing mathematical models of quantum computation make this an easier task than one could reasonably expect. In light of these observations we introduce QWIRE, a tool for writing verifiable, large scale quantum programs.\nQWIRE is not merely a language for writing and verifying quantum circuits: it is a verified circuit description language. This means that the semantics of QWIRE circuits are verified in the Coq proof assistant. We also implement verified abstractions, like ancilla management and reversible circuit compilation. Finally, we turn QWIRE and Coq's abilities outwards, towards verifying popular quantum algorithms like quantum teleportation. We argue that this tool provides a solid foundation for research into quantum programming languages and formal verification going forward.
Formal verification of quantum circuits is a crucial step towards building reliable quantum computers. However, the exponential scaling of quantum states makes traditional formal verification methods impractical for anything beyond small circuits. This paper proposes a novel approach leveraging self-referential quantum circuits for verification. The core idea is to create a verification circuit that recursively simulates and verifies the behavior of the original circuit. This self-referential process allows for a more efficient exploration of the state space, mitigating the exponential growth problem. We define the key components of this system, including the self-referential circuit architecture and the underlying mathematical framework. The paper outlines the potential for this approach to overcome limitations of existing techniques and represents a significant advancement in the field of quantum verification. The primary mathematical challenge addressed is the efficient simulation of quantum circuits within a self-referential structure.
This paper presents a novel approach to verifying the correctness of quantum circuits using temporal logic. Traditional verification methods often rely on gate-level simulation, which can be computationally expensive and insufficient for complex quantum algorithms. This work addresses this limitation by formally modeling quantum circuits as temporal logic systems. We leverage the expressive power of temporal logic to capture the desired behavior of quantum algorithms, including their evolution over time and the effects of quantum phenomena like superposition and entanglement. The core of our method involves mapping the circuit's operations onto temporal logic specifications and utilizing automated theorem proving and model checking techniques, tailored to the probabilistic nature of quantum systems. We demonstrate that this approach provides a more rigorous and scalable verification framework compared to existing methods, offering a pathway to ensuring the reliability of quantum computations. The key contributions of this work are the formalization of quantum circuits with temporal logic, the adaptation of theorem proving and model checking techniques for quantum systems, and the potential for significantly improving the trustworthiness of quantum algorithms.
While recent progress in quantum hardware open the door for significant speedup in certain key areas, quantum algorithms are still hard to implement right, and the validation of such quantum programs is a challenge. Early attempts either suffer from the lack of automation or parametrized reasoning, or target high-level abstract algorithm description languages far from the current de facto consensus of circuit-building quantum programming languages. As a consequence, no significant quantum algorithm implementation has been currently verified in a scale-invariant manner. We propose Qbricks, the first formal verification environment for circuit-building quantum programs, featuring clear separation between code and proof, parametric specifications and proofs, high degree of proof automation and allowing to encode quantum programs in a natural way, i.e. close to textbook style. Qbricks builds on best practice of formal verification for the classical case and tailor them to the quantum case: we bring a new domain-specific circuit-building language for quantum programs, namely Qbricks-DSL, together with a new logical specification language Qbricks-Spec and a dedicated Hoare-style deductive verification rule named Hybrid Quantum Hoare Logic. Especially, we introduce and intensively build upon HOPS, a higher-order extension of the recent path-sum symbolic representation, used for both specification and automation. To illustrate the opportunity of Qbricks, we implement the first verified parametric implementations of several famous and non-trivial quantum algorithms, including the quantum part of Shor integer factoring (Order Finding - Shor-OF), quantum phase estimation (QPE) - a basic building block of many quantum algorithms, and Grover search. These breakthroughs were amply facilitated by the specification and automated deduction principles introduced within Qbricks.