Laws of Quantum Programming
Mingsheng Ying, Li Zhou, Gilles Barthe · 2024
Read Laws of Quantum Programming by Mingsheng Ying, Li Zhou, Gilles Barthe (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-19463.txt.
Introduction
Mingsheng Ying, Li Zhou, and Gilles Barthe set out laws of quantum programming in a 2024 arXiv paper. Classical programming has basic algebraic laws, first framed by Hoare and others. The team extends a full set of those laws to quantum programs.
The laws cover how sequences interact with quantum if-statements and how nested choices unfold. The authors flag subtle points where quantum laws differ from classical ones. They also give a fixpoint account of quantum while-loops and two normal form theorems. All laws are machine-checked in the Coq proof assistant. As a sample use, they derive the rule for deferred measurement in dynamic circuits.
Catalog record
| CREATOR | Mingsheng Ying, Li Zhou, Gilles Barthe |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-19463
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Laws of Quantum Programming Mingsheng Ying, Li Zhou, Gilles Barthe Abstract . In this paper, we investigate the fundamental laws of quantum programming. We extend a comprehensive set of Hoare et al.’s basic laws of classical programming to the quantum setting. These laws characterise the algebraic properties of quantum programs, such as the distributivity of sequential composition over (quantum) 𝐢𝐟 {\mathbf{if}} -statements and the unfolding of nested (quantum) 𝐢𝐟 {\mathbf{if}} -statements. At the same time, we clarify some subtle differences between certain laws of classical programming and their quantum counterparts. Additionally, we derive a fixpoint characterisation of quantum 𝐰𝐡𝐢𝐥𝐞 {\mathbf{while}} -loops and a loop-based realisation of tail recursion in quantum programming. Furthermore, we establish two normal form theorems: one for quantum circuits and one for finite quantum programs. The theory in which these laws are established is formalised in the Coq proof assistant, and all of these laws are mechanically verified. As an application case of our laws, we present a formal derivation of the principle of deferred measurements in dynamic quantum circuits. We expect that these laws can be utilised in correctness-preserving transformation, compilation, and automatic code optimisation in quantum programming. In particular, because these laws are formally verified in Coq, they can be confidently applied in quantum program development. Journal: TOSEM CCS: Software and its engineering Functionality CCS: Software and its engineering Automated static analysis CCS: Theory of computation Algebraic semantics 1. Introduction It is widely accepted that scientists and mathematicians uncover the fundamental laws of nature and mathematical structures, respectively, while engineers leverage these discoveries to address practical problems. This fundamental concept spurred Hoare et al. ( Hoare87 ; Hoare88 ; Hoare93 ) to pose a crucial question: • What are the laws governing computer programming that establish the formal foundation for the field of software engineering? Their argument, rooted in the perspective that computer programs are essentially mathematical expressions, led them to establish a series of algebraic laws for programming, ranging from sequential to concurrent processes. The foundational laws articulated in ( Hoare87 ; Hoare88 ; Hoare93 ) serve as a cornerstone in the establishment of the science of computer programming. Simultaneously, they prove invaluable in the realm of software engineering, encompassing tasks such as compilation, optimisation, and program transformation. For instance, during program development, a programmer may create a program aligning with end-user requirements. Utilising these laws, an optimising compiler can then transform it into an efficient program that effectively exploits the underlying architecture of the target machine (refer to ( Hoare93 ) for a detailed example). This strategic approach has the advantage of ensuring correctness by construction during compilation. Each transformation within the process is mathematically proven based on these laws, providing a robust framework for the development and optimisation of computer programs. The past decade has witnessed remarkable advancements in quantum computer hardware, leading to a surge in research on quantum programming languages and platforms ( Qiskit ; Cirq ; ProjectQ ; Omer05 ; LanQ ; GKMW10 ; GP13 ; Qsharp ; Quipper ; Scaffold ; TKet ; isQ ) . The research on quantum programming also spans from theoretical aspects, such as formal semantics, program logic, static analysis, and verification, to more practical considerations like compilation, optimisation, testing, and debugging. Despite this progress, the knowledge base of quantum programming as a scientific discipline remains fragmented and disjointed. Consequently, two fundamental questions naturally arise: • What are the foundational laws that underpin the methodologies and techniques of quantum programming? • Are there discernible differences between these laws and those governing classical programming, as established in works like ( Hoare87 ; Hoare88 ; Hoare93 ) ? Addressing these questions is crucial for consolidating the understanding of quantum programming as a coherent and well-defined field, bridging the gap between theoretical insights and practical applications. \begin{array}[]{ccccc}\mbox{Classical-Quantum\ Hybrid\ Programs}\\ \Uparrow\\ {\rm Purely\ Quantum\ Programs}\\ \Uparrow\\ {\rm Quantum\ Circuits}\end{array} Figure 1 . Three-Layer Framework for Quantum Programming. The objective of this paper is to delve into fundamental inquiries and identify key laws that can establish an indispensable scientific foundation for quantum programming. To accomplish this, we present a comprehensive three-layer framework for quantum programming in Figure 1 , with each layer intricately embedded into the one above: • Quantum Circuits Description Layer : At the bottom is a description language for quantum circuits. Assuming a set of basic gates, any quantum circuit can be defined using sequential composition and a quantum {\mathbf{if}} -statement ( Alt05 ; Ying12 ; Yuan ; Bich ; Voi23 ) . • Purely Quantum Programs Layer : The middle layer introduces a language for writing purely quantum programs (without classical variables). Building upon quantum circuits, an {\mathbf{if}} -statement with the outcome of a quantum measurement as its condition is introduced. This layer also defines the loop and recursion of quantum programs (with classical control flow). Nondeterministic choice is added for the specification and refinement of quantum programs. • Classical-Quantum Hybrid Programming Layer : At the top is the classical-quantum hybrid programming layer, where purely quantum programs are embedded into a classical programming language. This integration enables the programming of classical and quantum computation together, a necessity for most practical quantum algorithms. While the components of this framework are not novel and have been extensively studied in previous literature, we organise them into a unified framework that clearly delineates the application of each law of quantum programming. Within this three-layer framework, we establish a comprehensive set of basic laws of quantum programming. This includes two subsets of laws: • The first subset is proven for quantum circuits at the bottom layer of Figure 1 . Among them, several laws about the distributivity of quantum {\mathbf{if}} -statements are particularly useful. • The second subset is established for purely quantum programs at the middle layer of Figure 1 . A congruence property is introduced, facilitating the lifting of laws for quantum circuits to quantum programs. Then a diverse range of laws governing {\mathbf{if}} -statements, loops, recursion, and nondeterministic choice are derived. These quantum programming laws can be further integrated with existing laws for classical (and probabilistic) programs ( Hoare87 ; Hoare88 ; Hoare93 ; He97 ) . This integration enhances the framework’s utility for reasoning about classical-quantum hybrid programs at the top layer of Figure 1 . Noteworthy technical contributions of this paper encompass: • Normal forms : We prove that every quantum circuit is equivalent to a normal form featuring a sequential composition of flat (but large) quantum {\mathbf{if}} -statements. A similar normal form (with an {\mathbf{if}} -statement) is presented for finite quantum programs. The significance of the normal forms lies in their applications, including providing a compilation strategy of quantum programs as a generalisation of that given in ( Hoare93 ) and offering a method for checking the equivalence of two quantum programs by reducing them to a normal form. • Tail Recursion : It is well-known in classical programming that tail recursion can be realised using loops. We prove that this result holds true for recursive quantum programs with classical control flow. A practical implication of this finding is that quantum programs with tail recursion can be easily implemented and optimised during compilation. • Verification in Coq : We formalise the theory in which