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

ACM Transactions on Software Engineering and Methodology

Structured Theorem for Quantum Programs and its Applications

Nengkun Yu

Published Mar 10, 2023• 4 citations
Publisher

Abstract

This article proves a structured program theorem for flowchart quantum programs. The theorem states that any flowchart quantum program is equivalent to a single quantum program that repeatedly executes a quantum measurement and a subprogram, so long as the measurement outcome is true. Moreover, their expected runtime, variance, and general moments are the same. This theorem simplifies the quantum program’s verification significantly. – We derive an analytical characterization of the termination problem for quantum programs in polynomial time. Our procedure is more efficient and accurate with much simpler techniques than the analysis of this problem, as described in [ 29 ]. – We compute the expected runtime analytically and exactly for quantum programs in polynomial time. This result improves the methods based on the weakest precondition calculus for the question recently developed in [ 31 , 34 ]. – We show that a single loop rule is a relatively complete Hoare logic for quantum programs after applying our structured theorem. Although using fewer rules, our method verifies a broader class of quantum programs, compared with the results in [ 45 ] and [ 56 ].

DOI
10.1145/3587154

Related papers

Runtime Analysis of Quantum Programs: A Formal Approach

Federico Olmedo, Alejandro Díaz-Caro

In this abstract we study the resource consumption of quantum programs. Specifically, we focus on the expected runtime of programs and, inspired by recent methods for probabilistic programs, we develop a calculus à la weakest precondition to formally and systematically derive the (exact) expected runtime of quantum programs. Notably, the calculus admits a notion of loop runtime invariant that can be readily used to derive upper bounds of their runtime. Finally, we show the applicability of our calculus analyzing the runtime of (a simplified version of) the BB84 quantum key distribution protocol.

arXiv:1911.11247•Nov 25, 2019•13 citations

A Logic for Recursive Quantum Programs

Zhaowei Xu, Mingsheng Ying, Shenggang Ying

Most modern (classical) programming languages support recursion. Recursion has also been successfully applied to the design of several quantum algorithms and introduced in a couple of quantum programming languages. So, it can be expected that recursion will become one of the fundamental paradigms of quantum programming. Several program logics have been developed for verification of non-recursive quantum programs. However, there are as yet no general methods for reasoning about recursive procedures in quantum computing. We fill the gap in this paper by presenting a logic for recursive quantum programs. This logic is an extension of quantum Hoare logic for quantum While-programs. The (relative) completeness of the logic is proved, and its effectiveness is shown by a running example: fixed-point Grover's search.

arXiv:1812.00349•Dec 2, 2018•1 citation

Quantum Weakest Preconditions for Reasoning about Expected Runtimes of Quantum Programs

Junyi Liu, Li Zhou, Gilles Barthe +1 more

We study expected runtimes for quantum programs. Inspired by recent work on probabilistic programs, we first define expected runtime as a generalisation of quantum weakest precondition. Then, we show that the expected runtime of a quantum program can be represented as the expectation of an observable (in physics). A method for computing the expected runtimes of quantum programs in finite-dimensional state spaces is developed. Several examples are provided as applications of this method, including computing the expected runtime of quantum Bernoulli Factory – a quantum algorithm for generating random numbers. In particular, using our new method, an open problem of computing the expected runtime of quantum random walks introduced by Ambainis et al. (STOC 2001) is solved.

ACM/IEEE Symposium on Logic in Computer Science (LICS)•Aug 2, 2022•20 citations

Reasoning about Recursive Quantum Programs

Zhaowei Xu, Mingsheng Ying, Benoît Valiron

Most modern (classical) programming languages support recursion. Recursion has also been successfully applied to the design of several quantum algorithms and introduced in a couple of quantum programming languages. So, it can be expected that recursion will become one of the fundamental paradigms of quantum programming. Several program logics have been developed for verification of quantum while-programs. However, there are as yet no general methods for reasoning about (mutual) recursive procedures and ancilla quantum data structure in quantum computing (with measurement). We fill the gap in this paper by proposing a parameterized quantum assertion logic and, based on which, designing a quantum Hoare logic for verifying parameterized recursive quantum programs with ancilla data and probabilistic control. The quantum Hoare logic can be used to prove partial, total, and even probabilistic correctness (by reducing to total correctness) of those quantum programs. In particular, two counterexamples for illustrating incompleteness of non-parameterized assertions in verifying recursive procedures, and, one counterexample for showing the failure of reasoning with exact probabilities based on partial correctness, are constructed. The effectiveness of our logic is shown by three main examples -- recursive quantum Markov chain (with probabilistic control), fixed-point Grover's search, and recursive quantum Fourier sampling.

arXiv:2107.11679•Jul 24, 2021•10 citations

Quantum Weakest Preconditions for Reasoning about Expected Runtimes of Quantum Programs

Junyi Liu, Li Zhou, Gilles Barthe +1 more

We study expected runtimes for quantum programs. Inspired by recent work on probabilistic programs, we first define expected runtime as a generalisation of quantum weakest precondition . Then, we show that the expected runtime of a quantum program should be represented as the expectation of an observable (in physics). A method for computing the expected runtimes of quantum programs in finite-dimensional state spaces is developed. Several examples are provided as applications of this method, including computing the expected runtime of quantum Bernoulli Factory – a quantum algorithm for generating random numbers. In particular, using our new method, an open problem of computing the expected runtime of quantum random walks introduced by Ambainis et al. ( STOC 2001) is solved.

arXiv:1911.12557•Journal of the ACM•May 6, 2025•5 citations

Quantum Weakest Preconditions Revisited: Pre-expectations for Expected Runtime Analysis

Christina Gehnen, Dominique Unruh, Joost-Pieter Katoen

Quantum weakest preconditions are a fundamental tool for program verification of quantum programs. Many variations have been reported in the literature. We revisit quantum weakest preconditions from the perspective of expected runtime analysis of quantum programs and introduce a novel pre-expectation framework that enables to reason about the preconditions of quantum programs without the need of an upper bound. This is particularly interesting for quantum programs involving reward statements. The overall goal is to analyze runtime behavior even in the case of programs with potentially infinite expected runtime. This paper presents several ways to do so, e.g., a program transformation such that the expected runtime of a quantum program can be expressed using the weakest pre-expectation calculus with rewards.

cs.LOCross-listedarXiv:2607.12532•Jul 15, 2026•0 citations
This article proves a structured program theorem for flowchart quantum programs. The theorem states that any flowchart quantum program is equivalent to a single quantum program that repeatedly executes a quantum measurement and a subprogram, so long as the measurement outcome is true. Moreover, their expected runtime, variance, and general moments are the same. This theorem simplifies the quantum program’s verification significantly. – We derive an analytical characterization of the termination problem for quantum programs in polynomial time. Our procedure is more efficient and accurate with much simpler techniques than the analysis of this problem, as described in [ 29 ]. – We compute the expected runtime analytically and exactly for quantum programs in polynomial time. This result improves the methods based on the weakest precondition calculus for the question recently developed in [ 31 , 34 ]. – We show that a single loop rule is a relatively complete Hoare logic for quantum programs after applying our structured theorem. Although using fewer rules, our method verifies a broader class of quantum programs, compared with the results in [ 45 ] and [ 56 ].
In this abstract we study the resource consumption of quantum programs. Specifically, we focus on the expected runtime of programs and, inspired by recent methods for probabilistic programs, we develop a calculus à la weakest precondition to formally and systematically derive the (exact) expected runtime of quantum programs. Notably, the calculus admits a notion of loop runtime invariant that can be readily used to derive upper bounds of their runtime. Finally, we show the applicability of our calculus analyzing the runtime of (a simplified version of) the BB84 quantum key distribution protocol.
Most modern (classical) programming languages support recursion. Recursion has also been successfully applied to the design of several quantum algorithms and introduced in a couple of quantum programming languages. So, it can be expected that recursion will become one of the fundamental paradigms of quantum programming. Several program logics have been developed for verification of non-recursive quantum programs. However, there are as yet no general methods for reasoning about recursive procedures in quantum computing. We fill the gap in this paper by presenting a logic for recursive quantum programs. This logic is an extension of quantum Hoare logic for quantum While-programs. The (relative) completeness of the logic is proved, and its effectiveness is shown by a running example: fixed-point Grover's search.
We study expected runtimes for quantum programs. Inspired by recent work on probabilistic programs, we first define expected runtime as a generalisation of quantum weakest precondition. Then, we show that the expected runtime of a quantum program can be represented as the expectation of an observable (in physics). A method for computing the expected runtimes of quantum programs in finite-dimensional state spaces is developed. Several examples are provided as applications of this method, including computing the expected runtime of quantum Bernoulli Factory – a quantum algorithm for generating random numbers. In particular, using our new method, an open problem of computing the expected runtime of quantum random walks introduced by Ambainis et al. (STOC 2001) is solved.
Most modern (classical) programming languages support recursion. Recursion has also been successfully applied to the design of several quantum algorithms and introduced in a couple of quantum programming languages. So, it can be expected that recursion will become one of the fundamental paradigms of quantum programming. Several program logics have been developed for verification of quantum while-programs. However, there are as yet no general methods for reasoning about (mutual) recursive procedures and ancilla quantum data structure in quantum computing (with measurement). We fill the gap in this paper by proposing a parameterized quantum assertion logic and, based on which, designing a quantum Hoare logic for verifying parameterized recursive quantum programs with ancilla data and probabilistic control. The quantum Hoare logic can be used to prove partial, total, and even probabilistic correctness (by reducing to total correctness) of those quantum programs. In particular, two counterexamples for illustrating incompleteness of non-parameterized assertions in verifying recursive procedures, and, one counterexample for showing the failure of reasoning with exact probabilities based on partial correctness, are constructed. The effectiveness of our logic is shown by three main examples -- recursive quantum Markov chain (with probabilistic control), fixed-point Grover's search, and recursive quantum Fourier sampling.
We study expected runtimes for quantum programs. Inspired by recent work on probabilistic programs, we first define expected runtime as a generalisation of quantum weakest precondition . Then, we show that the expected runtime of a quantum program should be represented as the expectation of an observable (in physics). A method for computing the expected runtimes of quantum programs in finite-dimensional state spaces is developed. Several examples are provided as applications of this method, including computing the expected runtime of quantum Bernoulli Factory – a quantum algorithm for generating random numbers. In particular, using our new method, an open problem of computing the expected runtime of quantum random walks introduced by Ambainis et al. ( STOC 2001) is solved.
Quantum weakest preconditions are a fundamental tool for program verification of quantum programs. Many variations have been reported in the literature. We revisit quantum weakest preconditions from the perspective of expected runtime analysis of quantum programs and introduce a novel pre-expectation framework that enables to reason about the preconditions of quantum programs without the need of an upper bound. This is particularly interesting for quantum programs involving reward statements. The overall goal is to analyze runtime behavior even in the case of programs with potentially infinite expected runtime. This paper presents several ways to do so, e.g., a program transformation such that the expected runtime of a quantum program can be expressed using the weakest pre-expectation calculus with rewards.