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

Bounds for quantum weakest preconditions

Jonas Deutsch

Published Jan 1, 2025• 0 citations
Publisher

Abstract

This thesis presents multiple proof rules for bounds on weakest (liberal) preconditions of quantum loops. It adapts Park induction as a basic mechanism for establishing upper bounds of weakest preconditions and lower bounds of weakest liberal preconditions. Building on Park induction, it discusses k-induction and derives the related approach chain comparison as further techniques for reasoning about upper bounds. Finally, it introduces guard strengthening as a mechanism to prove the correctness of lower bounds on weakest preconditions.

DOI
10.18154/rwth-2026-06831

Related papers

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

A formal language for expressing quantum predicates

Umut Yiğit Dural

We develop a formal language, a syntax, for specifying quantum predicates, which are yes/no properties of quantum systems. Specifically we study classical-quantum predicates using projector-based Birkhoff-von Neumann quantum logic. We give an extensional definition of a weakest precondition calculus that preserves projector-based predicates fora simple loop-free classical-quantum programming language. We prove that our weakest precondition calculus is relatively complete in the sense of Cook for the classical-quantum programming language we specify. To achieve this, we show that for any post condition expressible in our formal language, the corresponding weakest precondition with respect to any program is also expressible in our formal language. This result establishes a foundation for reasoning about classical-quantum programs using an intensional approach.

•Jan 1, 2025•0 citations

Quantum weakest preconditions

Ellie D’Hondt, Prakash Panangaden

We develop a notion of predicate transformer and, in particular, the weakest precondition, appropriate for quantum computation. We show that there is a Stone-type duality between the usual state-transformer semantics and the weakest precondition semantics. Rather than trying to reduce quantum computation to probabilistic programming, we develop a notion that is directly taken from concepts used in quantum computation. The proof that weakest preconditions exist for completely positive maps follows immediately from the Kraus representation theorem. As an example, we give the semantics of Selinger's language in terms of our weakest preconditions. We also cover some specific situations and exhibit an interesting link with stabilisers.

arXiv:quant-ph/0501157•Mathematical Structures in Computer Science•Jun 1, 2006•158 citations

Simple characterizations for commutativity of quantum weakest preconditions

Tianrong Lin

In a recent letter [Information Processing Letters~104 (2007) 152-158], it has shown some sufficient conditions for commutativity of quantum weakest preconditions. This paper provides some alternative and simple characterizations for the commutativity of quantum weakest preconditions, i.e., Theorem 3.1, Theorem 3.2 and Proposition 3.3 in what follows. We also show that to characterize the commutativity of quantum weakest preconditions in terms of $[M,N]$ ($=MN-NM$) is hard in the sense of Proposition 4.1 and Proposition 4.2.

arXiv:1108.4607•Aug 23, 2011•0 citations

Proof rules for purely quantum programs

Yuan Feng, Runyao Duan, Zhengfeng Ji +1 more

We apply the notion of quantum predicate proposed by D'Hondt and Panangaden to analyze a purely quantum language fragment which describes the quantum part of a future quantum computer in Knill's architecture. The denotational semantics, weakest precondition semantics, and weakest liberal precondition semantics of this language fragment are introduced. To help reasoning about quantum programs involving quantum loops, we extend proof rules for classical probabilistic programs to our purely quantum programs.

arXiv:cs/0507043•Jul 18, 2005•6 citations

Predicatet transformers for nondeterministic quantum programs

Xi Wang

Nondeterminism has been introduced into quantum programming languages to model, for example, unspecified behavior. Weakest precondition transformers provide a formal framework for reasoning about program correctness with respect to a given postcondition. This thesis combines these ideas by introducing demonic and angelic interpretations of nondeterminism for quantum programs, together with corresponding weakest liberal precondition transformers. To capture angelic nondeterminism in a qualitative setting, we introduce predicates represented by sets of subspaces, where each subspace is represented by a projection. Such a predicate is satisfied whenever the quantum state belongs to one of the represented subspaces. We show, however, that natural definitions of the weakest liberal precondition transformer based on these predicates do not behave as desired for measurements and loops in the demonic setting. For this reason, the demonic weakest liberal precondition transformer is restricted to singleton postconditions. We further investigate the corresponding non-liberal weakest precondition transformers using termination spaces. This yields transformer rules for all language constructs except loops, for which deriving a transformer rule remains an open problem. Finally, we show that the resulting weakest precondition variants have the same relations as in the classical case.

•Jan 1, 2026•0 citations
This thesis presents multiple proof rules for bounds on weakest (liberal) preconditions of quantum loops. It adapts Park induction as a basic mechanism for establishing upper bounds of weakest preconditions and lower bounds of weakest liberal preconditions. Building on Park induction, it discusses k-induction and derives the related approach chain comparison as further techniques for reasoning about upper bounds. Finally, it introduces guard strengthening as a mechanism to prove the correctness of lower bounds on weakest preconditions.
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.
We develop a formal language, a syntax, for specifying quantum predicates, which are yes/no properties of quantum systems. Specifically we study classical-quantum predicates using projector-based Birkhoff-von Neumann quantum logic. We give an extensional definition of a weakest precondition calculus that preserves projector-based predicates fora simple loop-free classical-quantum programming language. We prove that our weakest precondition calculus is relatively complete in the sense of Cook for the classical-quantum programming language we specify. To achieve this, we show that for any post condition expressible in our formal language, the corresponding weakest precondition with respect to any program is also expressible in our formal language. This result establishes a foundation for reasoning about classical-quantum programs using an intensional approach.
We develop a notion of predicate transformer and, in particular, the weakest precondition, appropriate for quantum computation. We show that there is a Stone-type duality between the usual state-transformer semantics and the weakest precondition semantics. Rather than trying to reduce quantum computation to probabilistic programming, we develop a notion that is directly taken from concepts used in quantum computation. The proof that weakest preconditions exist for completely positive maps follows immediately from the Kraus representation theorem. As an example, we give the semantics of Selinger's language in terms of our weakest preconditions. We also cover some specific situations and exhibit an interesting link with stabilisers.
In a recent letter [Information Processing Letters~104 (2007) 152-158], it has shown some sufficient conditions for commutativity of quantum weakest preconditions. This paper provides some alternative and simple characterizations for the commutativity of quantum weakest preconditions, i.e., Theorem 3.1, Theorem 3.2 and Proposition 3.3 in what follows. We also show that to characterize the commutativity of quantum weakest preconditions in terms of [M,N][M,N][M,N] (=MN−NM=MN-NM=MN−NM) is hard in the sense of Proposition 4.1 and Proposition 4.2.
We apply the notion of quantum predicate proposed by D'Hondt and Panangaden to analyze a purely quantum language fragment which describes the quantum part of a future quantum computer in Knill's architecture. The denotational semantics, weakest precondition semantics, and weakest liberal precondition semantics of this language fragment are introduced. To help reasoning about quantum programs involving quantum loops, we extend proof rules for classical probabilistic programs to our purely quantum programs.
Nondeterminism has been introduced into quantum programming languages to model, for example, unspecified behavior. Weakest precondition transformers provide a formal framework for reasoning about program correctness with respect to a given postcondition. This thesis combines these ideas by introducing demonic and angelic interpretations of nondeterminism for quantum programs, together with corresponding weakest liberal precondition transformers. To capture angelic nondeterminism in a qualitative setting, we introduce predicates represented by sets of subspaces, where each subspace is represented by a projection. Such a predicate is satisfied whenever the quantum state belongs to one of the represented subspaces. We show, however, that natural definitions of the weakest liberal precondition transformer based on these predicates do not behave as desired for measurements and loops in the demonic setting. For this reason, the demonic weakest liberal precondition transformer is restricted to singleton postconditions. We further investigate the corresponding non-liberal weakest precondition transformers using termination spaces. This yields transformer rules for all language constructs except loops, for which deriving a transformer rule remains an open problem. Finally, we show that the resulting weakest precondition variants have the same relations as in the classical case.