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

Cambridge University Press eBooks

Predicate Transformer Semantics of Quantum Programs

Mingsheng Ying, Runyao Duan, Yuan Feng, Zhengfeng Ji

Published Nov 30, 2009• 35 citations
Publisher

Abstract

This chapter presents a systematic exposition of predicate transformer semantics for quantum programs. It is divided into two parts: The first part reviews the state transformer (forward) semantics of quantum programs according to Selinger's suggestion of representing quantum programs by superoperators and elucidates D'Hondt-Panangaden's theory of quantum weakest preconditions in detail. In the second part, we develop a quite complete predicate transformer semantics of quantum programs based on Birkhoff-von Neumann quantum logic by considering only quantum predicates expressed by projection operators. In particular, the universal conjunctivity and termination law of quantum programs are proved, and Hoare's induction rule is established in the quantum setting. 8.1 Introduction In the mid-1990s Shor and Grover discovered, respectively, the famous quantum factoring and searching algorithms. Their discoveries indicated that in principle quantum computers offer a way to accomplish certain computational tasks much more efficiently than classical computers, and thus stimulated an intensive investigation in quantum computation. Since then a substantial effort has been made to develop the theory of quantum computation, to find new quantum algorithms, and to exploit the physical techniques needed in building functional quantum computers, including in particular fault tolerance techniques. Currently, quantum algorithms are expressed mainly at the very low level of quantum circuits. In the history of classical computation, however, it was realized long time ago that programming languages provide a technique that allows us to think about a problem that we intend to solve in a high-level, conceptual way, rather than the details of implementation.

DOI
10.1017/cbo9781139193313.009

Related papers

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

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

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 constraint programming.

Alessandra Di Pierro, Herbert Wiklicky

Abstract Quantum computers are hypothetical machines which can perform many calculations simultaneously based on quantum-mechanical principles that allows a single bit to coexist in many states at once. This enormous potential of quantum computing has attracted substantial interest, especially during the last decade, and initiated a whole new field of research. As a contribution to this research we address the problem of the design of high level languages for programming quantum computers, and the definition of an appropriate formal semantics for such languages. To this purpose we consider the Constraint Programming paradigm and we show how computations in this paradigm can be seen as physical processes obeying the laws of quantum mechanics. 1 Introduction Quantum Computing is currently one of the hottest topics in computer science, physics and engineering. One of the reason for such an interest is the dramatic miniaturisation in computer technology over the past 40 years, which will inevitably force (if the trend continues) the use of quantum physics to describe the elementary operations of a computer. The by now already flourishing research in quantum computing has arisen in anticipation of this inevitable step. If technological issues have started the studies of the new computational model, the discovery of its potential has made the interest continuously increasing, especially after the presentation of Shor's quantum factorisation algorithm [30], and Grover's search algorithm [14]. These algorithms heavily exploits quantum mechanical phenomena. Thanks to quantum effects like superposition and entanglement, a function can be evaluated on a quantum machine so as all the outputs are computed in the time taken to evaluate just one output classically. Although a measurement of the final superposed state can yield only one output, it is still possible to obtain certain joint properties of all the outputs. As a consequence of this quantum parallelism, Shor and Grover's algorithms are faster than any known classical algorithm designed for solving the same problems.

APPIA-GULP-PRODE•Jan 1, 2001•3 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

Natural Quantum Operational Semantics with Predicates

Marek Sawerwain, Roman Gielerak

Natural Quantum Operational Semantics with Predicates A general definition of a quantum predicate and quantum labelled transition systems for finite quantum computation systems is presented. The notion of a quantum predicate as a positive operator-valued measure is developed. The main results of this paper are a theorem about the existence of generalised predicates for quantum programs defined as completely positive maps and a theorem about the existence of a GSOS format for quantum labelled transition systems. The first theorem is a slight generalisation of D'Hondt and Panagaden's theorem about the quantum weakest precondition in terms of discrete support positive operator-valued measures.

International Journal of Applied Mathematics and Computer Science•Sep 1, 2008•10 citations
This chapter presents a systematic exposition of predicate transformer semantics for quantum programs. It is divided into two parts: The first part reviews the state transformer (forward) semantics of quantum programs according to Selinger's suggestion of representing quantum programs by superoperators and elucidates D'Hondt-Panangaden's theory of quantum weakest preconditions in detail. In the second part, we develop a quite complete predicate transformer semantics of quantum programs based on Birkhoff-von Neumann quantum logic by considering only quantum predicates expressed by projection operators. In particular, the universal conjunctivity and termination law of quantum programs are proved, and Hoare's induction rule is established in the quantum setting. 8.1 Introduction In the mid-1990s Shor and Grover discovered, respectively, the famous quantum factoring and searching algorithms. Their discoveries indicated that in principle quantum computers offer a way to accomplish certain computational tasks much more efficiently than classical computers, and thus stimulated an intensive investigation in quantum computation. Since then a substantial effort has been made to develop the theory of quantum computation, to find new quantum algorithms, and to exploit the physical techniques needed in building functional quantum computers, including in particular fault tolerance techniques. Currently, quantum algorithms are expressed mainly at the very low level of quantum circuits. In the history of classical computation, however, it was realized long time ago that programming languages provide a technique that allows us to think about a problem that we intend to solve in a high-level, conceptual way, rather than the details of implementation.
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.
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.
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.
Abstract Quantum computers are hypothetical machines which can perform many calculations simultaneously based on quantum-mechanical principles that allows a single bit to coexist in many states at once. This enormous potential of quantum computing has attracted substantial interest, especially during the last decade, and initiated a whole new field of research. As a contribution to this research we address the problem of the design of high level languages for programming quantum computers, and the definition of an appropriate formal semantics for such languages. To this purpose we consider the Constraint Programming paradigm and we show how computations in this paradigm can be seen as physical processes obeying the laws of quantum mechanics. 1 Introduction Quantum Computing is currently one of the hottest topics in computer science, physics and engineering. One of the reason for such an interest is the dramatic miniaturisation in computer technology over the past 40 years, which will inevitably force (if the trend continues) the use of quantum physics to describe the elementary operations of a computer. The by now already flourishing research in quantum computing has arisen in anticipation of this inevitable step. If technological issues have started the studies of the new computational model, the discovery of its potential has made the interest continuously increasing, especially after the presentation of Shor's quantum factorisation algorithm [30], and Grover's search algorithm [14]. These algorithms heavily exploits quantum mechanical phenomena. Thanks to quantum effects like superposition and entanglement, a function can be evaluated on a quantum machine so as all the outputs are computed in the time taken to evaluate just one output classically. Although a measurement of the final superposed state can yield only one output, it is still possible to obtain certain joint properties of all the outputs. As a consequence of this quantum parallelism, Shor and Grover's algorithms are faster than any known classical algorithm designed for solving the same problems.
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.
Natural Quantum Operational Semantics with Predicates A general definition of a quantum predicate and quantum labelled transition systems for finite quantum computation systems is presented. The notion of a quantum predicate as a positive operator-valued measure is developed. The main results of this paper are a theorem about the existence of generalised predicates for quantum programs defined as completely positive maps and a theorem about the existence of a GSOS format for quantum labelled transition systems. The first theorem is a slight generalisation of D'Hondt and Panagaden's theorem about the quantum weakest precondition in terms of discrete support positive operator-valued measures.