Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.11665

The Time-Space Complexity of Checking Multiple Assertions in Quantum Programs

Shengyuan Yang, Charles Yuan

cs.PLquant-phSubmitted Jul 13, 2026• Announced Jul 14, 2026• 0 citations
arXivHTMLPDF

Abstract

Runtime assertions are a promising mechanism for testing and debugging quantum programs. But unlike the classical world, checking a quantum program that contains multiple assertions often requires using additional space or running the program additional times. For example, on current quantum hardware where mid-circuit measurement is restricted or costly, an assertion's pass/fail outcome cannot be revealed immediately. Instead, it is routed into an ancilla qubit during execution and read out by a terminal measurement. For a program with $n$ assertions, a naive strategy uses $n$ ancillas to learn all $n$ outcomes, while an alternative uses one ancilla but repeats program execution over $n$ rounds, checking one assertion per round. Both satisfy $S \cdot T = O(n)$, where $S$ is the number of ancillas and $T$ the number of executions: a fundamental time-space trade-off. Can one do asymptotically better? We reveal that the answer depends sharply on the information to be learned. Reporting the outcomes of all assertions requires linear complexity, but two partial-information tasks of detecting whether any assertion fails, and of identifying the first failing assertion, require only logarithmic complexity -- an asymptotic improvement. Moreover, the checking strategies for these tasks can trade time for space in useful ways. In this work, we formalize the complexity of checking multiple assertions in a quantum program. Using this definition, we establish its landscape of asymptotic lower bounds and constructive upper bounds. We confirm via a case study on Grover's algorithm that the resource costs of constructed strategies match theoretical predictions, illustrating the practical design space for quantum programmers.

Comments
28 pages

Related papers

Optimizing Run-Time Assertions for Quantum Circuit Debugging: A Depth–Ancilla Tradeoff

Karl Aaron Rudkowski, Abhoy Kole, Rolf Drechsler

Debugging quantum circuits is inherently challenging due to the probabilistic nature of quantum computation and the inability to directly observe intermediate states without disturbing the computation. Run-time assertion-based debugging is a promising approach to provide partial visibility into quantum programs by validating expected properties during execution. However, existing approaches often incur significant overhead in terms of gate count, circuit depth, and auxiliary qubits, limiting their applicability on resource-constrained quantum hardware. In this work, we propose a framework for optimizing run-time assertions in quantum circuits using dynamic circuit capabilities. Our approach leverages classically conditioned operations and repeated measurement-reset patterns to implement assertions efficiently while preserving the state of data qubits. Furthermore, we explore the tradeoff between circuit depth and the number of auxiliary qubits by dynamically distributing assertion components across a limited set of ancilla, enabling scalable assertion insertion while balancing hardware constraints such as measurement latency and reset overhead. Experimental evaluation on Quantum Phase Estimation (QPE) circuits demonstrates that our approach significantly reduces auxiliary qubit usage and gate overhead compared to existing methods, while maintaining effective fault detection and localization capabilities.

Proceedings•Sep 1, 2026•0 citations

Projection-based runtime assertions for testing and debugging Quantum programs

Gushu Li, Li Zhou, Nengkun Yu +3 more

In this paper, we propose Proq, a runtime assertion scheme for testing and debugging quantum programs on a quantum computer. The predicates in Proq are represented by projections (or equivalently, closed subspaces of the state space), following Birkhoff-von Neumann quantum logic. The satisfaction of a projection by a quantum state can be directly checked upon a small number of projective measurements rather than a large number of repeated executions. On the theory side, we rigorously prove that checking projection-based assertions can help locate bugs or statistically assure that the semantic function of the tested program is close to what we expect, for both exact and approximate quantum programs. On the practice side, we consider hardware constraints and introduce several techniques to transform the assertions, making them directly executable on the measurement-restricted quantum computers. We also propose to achieve simplified assertion implementation using local projection technique with soundness guaranteed. We compare Proq with existing quantum program assertions and demonstrate the effectiveness and efficiency of Proq by its applications to assert two sophisticated quantum algorithms, the Harrow-Hassidim-Lloyd algorithm and Shor’s algorithm.

arXiv:1911.12855•Proceedings of the ACM on Programming Languages•Nov 13, 2020•159 citations

A Framework for the Efficient Evaluation of Runtime Assertions on Quantum Computers

Damian Rovara, Lukas Burgholzer, Robert Wille

The continuous growth of quantum computing and the increasingly complex quantum programs resulting from it lead to unprecedented obstacles in ensuring program correctness. Runtime assertions are, therefore, becoming a crucial tool in the development of quantum programs. They assist developers in the debugging process and help to test and verify the program. However, while assertions can be implemented in a straightforward manner on classical computers, physical limitations of quantum computers pose considerable challenges for the evaluation of quantum assertions. Access to the quantum state of a program is limited, execution time is expensive and noise can significantly distort measurement outcomes. To address these problems, this work proposes a framework that assists developers in the evaluation of runtime assertions on real quantum computers. It translates a variety of assertions into sets of measurements, reduces execution overhead where possible and evaluates the measurement results after the execution even in the presence of noise. This approach substantially aids developers in the debugging process, enabling efficient assertion-driven debugging even in large programs. The proposed framework is available as an open-source implementation at https://github.com/munich-quantum-toolkit/debugger

arXiv:2505.03885•IEEE International Conference on Quantum Software (QSW)•Jul 1, 2026•6 citations

Quantum Circuits for Dynamic Runtime Assertions in Quantum Computation

Ji Liu, Gregory T. Byrd, Huiyang Zhou

In this paper, we propose quantum circuits for runtime assertions, which can be used for both software debugging and error detection. Runtime assertion is challenging in quantum computing for two key reasons. First, a quantum bit (qubit) cannot be copied, which is known as the non-cloning theorem. Second, when a qubit is measured, its superposition state collapses into a classical state, losing the inherent parallel information. In this paper, we overcome these challenges with runtime computation through ancilla qubits, which are used to indirectly collect the information of the qubits of interest. We design quantum circuits to assert classical states, entanglement, and superposition states. Our experimental results show that they are effective in debugging as well as improving the success rate for various quantum algorithms on IBM Q quantum computers.

International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)•Mar 9, 2020•97 citations

Systematic Approaches for Precise and Approximate Quantum State Runtime Assertion

Ji Liu, Huiyang Zhou

With the rapid growth of quantum computing technology, programmers need new tools for debugging quantum programs. Recent works show that assertions are a promising way for debugging quantum programs. However, there are two main drawbacks with the existing schemes. First, the existing schemes, including both statistical and dynamic assertions are only capable of asserting limited types of states, namely classical, superposition, and specific entanglement states. Second, the use cases of these assertions are limited, since the programmer has to know the exact/precise state to assert.In this work, we propose two systematic approaches for dynamic quantum state assertion and they can assert a much broader range of quantum states including both pure states and mixed states. We also introduce the idea of approximate quantum state assertion for the cases where the programmers only have limited knowledge of the quantum states. Approximate assertion is capable of checking membership in a set of states {|Ψ〉,|Φ〉,...}. While precise quantum state assertion can check a specific quantum state, approximate assertion enables a way to check whether the qubits of interest are in a super-set of some expected states, which is analogous to the well-known Bloom filter for membership checking in classical computing. Our experiments demonstrate that our systematic approaches can assert many more quantum states and can be used in various assertion locations for qubit state checking.

IEEE International Symposium on High-Performance Computer Architecture (HPCA)•Feb 1, 2021•42 citations

Statistical assertions for validating patterns and finding bugs in quantum programs

Yipeng Huang, Margaret Martonosi

In support of the growing interest in quantum computing experimentation, programmers need new tools to write quantum algorithms as program code. Compared to debugging classical programs, debugging quantum programs is difficult because programmers have limited ability to probe the internal states of quantum programs; those states are difficult to interpret even when observations exist; and programmers do not yet have guidelines for what to check for when building quantum programs. In this work, we present quantum program assertions based on statistical tests on classical observations. These allow programmers to decide if a quantum program state matches its expected value in one of classical, superposition, or entangled types of states. We extend an existing quantum programming language with the ability to specify quantum assertions, which our tool then checks in a quantum program simulator. We use these assertions to debug three benchmark quantum programs in factoring, search, and chemistry. We share what types of bugs are possible, and lay out a strategy for using quantum programming patterns to place assertions and prevent bugs.

arXiv:1905.09721•Proceedings - International Symposium on Computer Architecture/Proceedings•Jun 14, 2019•191 citations
Runtime assertions are a promising mechanism for testing and debugging quantum programs. But unlike the classical world, checking a quantum program that contains multiple assertions often requires using additional space or running the program additional times. For example, on current quantum hardware where mid-circuit measurement is restricted or costly, an assertion's pass/fail outcome cannot be revealed immediately. Instead, it is routed into an ancilla qubit during execution and read out by a terminal measurement. For a program with nnn assertions, a naive strategy uses nnn ancillas to learn all nnn outcomes, while an alternative uses one ancilla but repeats program execution over nnn rounds, checking one assertion per round. Both satisfy S⋅T=O(n)S \cdot T = O(n)S⋅T=O(n), where SSS is the number of ancillas and TTT the number of executions: a fundamental time-space trade-off.
Can one do asymptotically better? We reveal that the answer depends sharply on the information to be learned. Reporting the outcomes of all assertions requires linear complexity, but two partial-information tasks of detecting whether any assertion fails, and of identifying the first failing assertion, require only logarithmic complexity -- an asymptotic improvement. Moreover, the checking strategies for these tasks can trade time for space in useful ways. In this work, we formalize the complexity of checking multiple assertions in a quantum program. Using this definition, we establish its landscape of asymptotic lower bounds and constructive upper bounds. We confirm via a case study on Grover's algorithm that the resource costs of constructed strategies match theoretical predictions, illustrating the practical design space for quantum programmers.
Debugging quantum circuits is inherently challenging due to the probabilistic nature of quantum computation and the inability to directly observe intermediate states without disturbing the computation. Run-time assertion-based debugging is a promising approach to provide partial visibility into quantum programs by validating expected properties during execution. However, existing approaches often incur significant overhead in terms of gate count, circuit depth, and auxiliary qubits, limiting their applicability on resource-constrained quantum hardware. In this work, we propose a framework for optimizing run-time assertions in quantum circuits using dynamic circuit capabilities. Our approach leverages classically conditioned operations and repeated measurement-reset patterns to implement assertions efficiently while preserving the state of data qubits. Furthermore, we explore the tradeoff between circuit depth and the number of auxiliary qubits by dynamically distributing assertion components across a limited set of ancilla, enabling scalable assertion insertion while balancing hardware constraints such as measurement latency and reset overhead. Experimental evaluation on Quantum Phase Estimation (QPE) circuits demonstrates that our approach significantly reduces auxiliary qubit usage and gate overhead compared to existing methods, while maintaining effective fault detection and localization capabilities.
In this paper, we propose Proq, a runtime assertion scheme for testing and debugging quantum programs on a quantum computer. The predicates in Proq are represented by projections (or equivalently, closed subspaces of the state space), following Birkhoff-von Neumann quantum logic. The satisfaction of a projection by a quantum state can be directly checked upon a small number of projective measurements rather than a large number of repeated executions. On the theory side, we rigorously prove that checking projection-based assertions can help locate bugs or statistically assure that the semantic function of the tested program is close to what we expect, for both exact and approximate quantum programs. On the practice side, we consider hardware constraints and introduce several techniques to transform the assertions, making them directly executable on the measurement-restricted quantum computers. We also propose to achieve simplified assertion implementation using local projection technique with soundness guaranteed. We compare Proq with existing quantum program assertions and demonstrate the effectiveness and efficiency of Proq by its applications to assert two sophisticated quantum algorithms, the Harrow-Hassidim-Lloyd algorithm and Shor’s algorithm.
The continuous growth of quantum computing and the increasingly complex quantum programs resulting from it lead to unprecedented obstacles in ensuring program correctness. Runtime assertions are, therefore, becoming a crucial tool in the development of quantum programs. They assist developers in the debugging process and help to test and verify the program. However, while assertions can be implemented in a straightforward manner on classical computers, physical limitations of quantum computers pose considerable challenges for the evaluation of quantum assertions. Access to the quantum state of a program is limited, execution time is expensive and noise can significantly distort measurement outcomes. To address these problems, this work proposes a framework that assists developers in the evaluation of runtime assertions on real quantum computers. It translates a variety of assertions into sets of measurements, reduces execution overhead where possible and evaluates the measurement results after the execution even in the presence of noise. This approach substantially aids developers in the debugging process, enabling efficient assertion-driven debugging even in large programs. The proposed framework is available as an open-source implementation at https://github.com/munich-quantum-toolkit/debugger
In this paper, we propose quantum circuits for runtime assertions, which can be used for both software debugging and error detection. Runtime assertion is challenging in quantum computing for two key reasons. First, a quantum bit (qubit) cannot be copied, which is known as the non-cloning theorem. Second, when a qubit is measured, its superposition state collapses into a classical state, losing the inherent parallel information. In this paper, we overcome these challenges with runtime computation through ancilla qubits, which are used to indirectly collect the information of the qubits of interest. We design quantum circuits to assert classical states, entanglement, and superposition states. Our experimental results show that they are effective in debugging as well as improving the success rate for various quantum algorithms on IBM Q quantum computers.
With the rapid growth of quantum computing technology, programmers need new tools for debugging quantum programs. Recent works show that assertions are a promising way for debugging quantum programs. However, there are two main drawbacks with the existing schemes. First, the existing schemes, including both statistical and dynamic assertions are only capable of asserting limited types of states, namely classical, superposition, and specific entanglement states. Second, the use cases of these assertions are limited, since the programmer has to know the exact/precise state to assert.In this work, we propose two systematic approaches for dynamic quantum state assertion and they can assert a much broader range of quantum states including both pure states and mixed states. We also introduce the idea of approximate quantum state assertion for the cases where the programmers only have limited knowledge of the quantum states. Approximate assertion is capable of checking membership in a set of states {|Ψ〉,|Φ〉,...}. While precise quantum state assertion can check a specific quantum state, approximate assertion enables a way to check whether the qubits of interest are in a super-set of some expected states, which is analogous to the well-known Bloom filter for membership checking in classical computing. Our experiments demonstrate that our systematic approaches can assert many more quantum states and can be used in various assertion locations for qubit state checking.
In support of the growing interest in quantum computing experimentation, programmers need new tools to write quantum algorithms as program code. Compared to debugging classical programs, debugging quantum programs is difficult because programmers have limited ability to probe the internal states of quantum programs; those states are difficult to interpret even when observations exist; and programmers do not yet have guidelines for what to check for when building quantum programs. In this work, we present quantum program assertions based on statistical tests on classical observations. These allow programmers to decide if a quantum program state matches its expected value in one of classical, superposition, or entangled types of states. We extend an existing quantum programming language with the ability to specify quantum assertions, which our tool then checks in a quantum program simulator. We use these assertions to debug three benchmark quantum programs in factoring, search, and chemistry. We share what types of bugs are possible, and lay out a strategy for using quantum programming patterns to place assertions and prevent bugs.