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

Non-deterministic quantum programming

Paolo Zuliani

Published Dec 31, 2004• 19 citations
Publisher

Abstract

In standard computation, non-determinism is used for specifying programs’ behaviour, without having to specify details of implementation. In quantum computation, non-determinism is either meant to be “classical” probabilism or it is not considered at all, since quantum computation is the physical theory of computation and thus it does not deal with non-implementable features. In this work we will instead show that non-determinism may be useful also in quantum computation. In particular, we consider non-determinism embedded in a programming language for quantum computation, the quantum Guarded-Command Language (qGCL), and use that for describing and reasoning about counterfactual computation and mixed-state systems.

DOI
10.25405/ncl.34193379

Related papers

Procedural Quantum Programming

Bernhard Ömer

While classical computing science has developed a variety of methods and programming languages around the concept of the universal computer, the typical description of quantum algorithms still uses a purely mathematical, non‐constructive formalism which makes no difference between a hydrogen atom and a quantum computer. This paper investigates, how the concept of procedural programming languages, the most widely used classical formalism for describing and implementing algorithms, can be adopted to the field of quantum computing, and how non‐classical features like the reversibility of unitary transformations, the non‐observability of quantum states or the lack of copy and erase operations can be reflected semantically. It introduces the key concepts of procedural quantum programming (hybrid target architecture, operator hierarchy, quantum data types, memory management, etc.) and presents the experimental language QCL, which implements these principles.

AIP conference proceedings•Jan 1, 2002•11 citations

Non-determinism and quantum information

Marriott, Chris

In this thesis we study the union of two tools of computation: quantum information and non-determinism.We begin by showing that the class of languages QMA, which characterizes bounded error non-deterministic quantum polynomial time, is robust in a stronger sense, and we present some applications of this result.Second we will show how the quantifier characterization of non-determinism can be extended into the quantum realm, by treating both classical and quantum non-determinism.To make this extension we will shift our focus to promise problems instead of the standard decision problems.In order to characterize quantum non-determinism we will introduce the concept of quantum sets, an analogue of classical languages.Finally we will show new oracle separations regarding the quantum non-deterministic classes that we consider.1'1 List of Figures 1.1.The classical class structure 1.2 The quantum and classical class structure.2.1 Specification of verification procedure W. 2.2 Example circuit diagram for verification procedure W. 2.3 Transition probabilities for verification procedure M. 2.4 Specification of quantum circuit W for log length proof simulation.4.1 Construction of an oracle A for Theorem 19 76 4.2 Construction of an oracle A for Theorem 20 78 4.3 Construction of an oracle A for Theorem 21 81 v List of Tables vi

•Jan 1, 2003•1 citation

A Procedural Formalism for Quantum Computing

Bernhard Ömer

Despite many common concepts with classical computer science, quantum computing is still widely considered as a special discipline within the broad field of theoretical physics. One reason for the slow adoption of QC by the computer science community is the confusing variety of formalisms (Dirac notation, matrices, gates, operators, etc.), none of which has any similarity with classical programming languages, as well as the rather “physical” terminology in most of the available literature. QCL (Quantum Computation Language) tries to fill this gap: QCL is a hight level, architecture independent programming language for quantum computers, with a syntax derived from classical procedural languages like C or Pascal. This allows for the complete implementation and simulation of quantum algorithms (including classical components) in one consistent formalism. Chapter 1 is an introduction into the basic concepts of quantum programming,

•Jan 1, 2002•85 citations

Verification of Nondeterministic Quantum Programs

Yuan Feng, Yingte Xu

Nondeterministic choice is a useful program construct that provides a way to describe the behaviour of a program without specifying the details of possible implementations. It supports the stepwise refinement of programs, a method that has proven useful in software development. Nondeterminism has also been introduced in quantum programming, and termination of nondeterministic quantum programs has been extensively analysed. In this paper, we go beyond termination analysis to investigate the verification of nondeterministic quantum programs where properties are given by sets of hermitian operators on the associated Hilbert space. Hoare-type logic systems for partial and total correctness are proposed which turn out to be both sound and relatively complete with respect to their corresponding semantic correctness. To show the utility of these proof systems, we analyse some quantum algorithms such as quantum error correction scheme, Deutsch algorithm, and a nondeterministic quantum walk. Finally, a proof assistant prototype is implemented to aid in the automated reasoning of nondeterministic quantum programs.

arXiv:2302.07973•International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)•Mar 20, 2023•17 citations

Predicative Quantum Programming

Anya Tafliovich

This work presents Quantum Predicative Programming --- a theory ofquantum programming that encompasses many aspects of quantum computation and quantum communication. The theory provides a methodology to specify, implement, and analyse quantum algorithms, the paradigm of quantum non-locality, quantum pseudotelepathy games, computing with mixed states, and quantum communication protocols that use both quantum and classical communication channels.

•Sep 1, 2010•1 citation

Defining Quantum Control Flow

Mingsheng Ying, Nengkun Yu, Yuan Feng

A remarkable difference between quantum and classical programs is that the control flow of the former can be either classical or quantum. One of the key issues in the theory of quantum programming languages is defining and understanding quantum control flow. A functional language with quantum control flow was defined by Altenkirch and Grattage [\textit{Proc. LICS'05}, pp. 249-258]. This paper extends their work, and we introduce a general quantum control structure by defining three new quantum program constructs, namely quantum guarded command, quantum choice and quantum recursion. We clarify the relation between quantum choices and probabilistic choices. An interesting difference between quantum recursions with classical control flows and with quantum control flows is revealed.

arXiv:1209.4379•Sep 19, 2012•23 citations
In standard computation, non-determinism is used for specifying programs’ behaviour, without having to specify details of implementation. In quantum computation, non-determinism is either meant to be “classical” probabilism or it is not considered at all, since quantum computation is the physical theory of computation and thus it does not deal with non-implementable features. In this work we will instead show that non-determinism may be useful also in quantum computation. In particular, we consider non-determinism embedded in a programming language for quantum computation, the quantum Guarded-Command Language (qGCL), and use that for describing and reasoning about counterfactual computation and mixed-state systems.
While classical computing science has developed a variety of methods and programming languages around the concept of the universal computer, the typical description of quantum algorithms still uses a purely mathematical, non‐constructive formalism which makes no difference between a hydrogen atom and a quantum computer. This paper investigates, how the concept of procedural programming languages, the most widely used classical formalism for describing and implementing algorithms, can be adopted to the field of quantum computing, and how non‐classical features like the reversibility of unitary transformations, the non‐observability of quantum states or the lack of copy and erase operations can be reflected semantically. It introduces the key concepts of procedural quantum programming (hybrid target architecture, operator hierarchy, quantum data types, memory management, etc.) and presents the experimental language QCL, which implements these principles.
In this thesis we study the union of two tools of computation: quantum information and non-determinism.We begin by showing that the class of languages QMA, which characterizes bounded error non-deterministic quantum polynomial time, is robust in a stronger sense, and we present some applications of this result.Second we will show how the quantifier characterization of non-determinism can be extended into the quantum realm, by treating both classical and quantum non-determinism.To make this extension we will shift our focus to promise problems instead of the standard decision problems.In order to characterize quantum non-determinism we will introduce the concept of quantum sets, an analogue of classical languages.Finally we will show new oracle separations regarding the quantum non-deterministic classes that we consider.1'1 List of Figures 1.1.The classical class structure 1.2 The quantum and classical class structure.2.1 Specification of verification procedure W. 2.2 Example circuit diagram for verification procedure W. 2.3 Transition probabilities for verification procedure M. 2.4 Specification of quantum circuit W for log length proof simulation.4.1 Construction of an oracle A for Theorem 19 76 4.2 Construction of an oracle A for Theorem 20 78 4.3 Construction of an oracle A for Theorem 21 81 v List of Tables vi
Despite many common concepts with classical computer science, quantum computing is still widely considered as a special discipline within the broad field of theoretical physics. One reason for the slow adoption of QC by the computer science community is the confusing variety of formalisms (Dirac notation, matrices, gates, operators, etc.), none of which has any similarity with classical programming languages, as well as the rather “physical” terminology in most of the available literature. QCL (Quantum Computation Language) tries to fill this gap: QCL is a hight level, architecture independent programming language for quantum computers, with a syntax derived from classical procedural languages like C or Pascal. This allows for the complete implementation and simulation of quantum algorithms (including classical components) in one consistent formalism. Chapter 1 is an introduction into the basic concepts of quantum programming,
Nondeterministic choice is a useful program construct that provides a way to describe the behaviour of a program without specifying the details of possible implementations. It supports the stepwise refinement of programs, a method that has proven useful in software development. Nondeterminism has also been introduced in quantum programming, and termination of nondeterministic quantum programs has been extensively analysed. In this paper, we go beyond termination analysis to investigate the verification of nondeterministic quantum programs where properties are given by sets of hermitian operators on the associated Hilbert space. Hoare-type logic systems for partial and total correctness are proposed which turn out to be both sound and relatively complete with respect to their corresponding semantic correctness. To show the utility of these proof systems, we analyse some quantum algorithms such as quantum error correction scheme, Deutsch algorithm, and a nondeterministic quantum walk. Finally, a proof assistant prototype is implemented to aid in the automated reasoning of nondeterministic quantum programs.
A remarkable difference between quantum and classical programs is that the control flow of the former can be either classical or quantum. One of the key issues in the theory of quantum programming languages is defining and understanding quantum control flow. A functional language with quantum control flow was defined by Altenkirch and Grattage [\textit{Proc. LICS'05}, pp. 249-258]. This paper extends their work, and we introduce a general quantum control structure by defining three new quantum program constructs, namely quantum guarded command, quantum choice and quantum recursion. We clarify the relation between quantum choices and probabilistic choices. An interesting difference between quantum recursions with classical control flows and with quantum control flows is revealed.