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

arXiv:2102.00329 · ACM/IEEE Symposium on Logic in Computer Science (LICS)

A Quantum Interpretation of Bunched Logic & Quantum Separation Logic

Li Zhou, Gilles Barthe, Justin Hsu, Mingsheng Ying, Nengkun Yu

Published Jun 29, 2021• 32 citations
arXivHTMLPDF

Abstract

We propose a model of the substructural logic of Bunched Implications (BI) that is suitable for reasoning about quantum states. In our model, the separating conjunction of BI describes separable quantum states. We develop a program logic where pre- and post-conditions are BI formulas describing quantum states—the program logic can be seen as a counterpart of separation logic for imperative quantum programs. We exercise the logic for proving the security of quantum one-time pad and secret sharing, and we show how the program logic can be used to discover a flaw in Google Cirq’s tutorial on the Variational Quantum Algorithm (VQA).

DOI
10.1109/lics52264.2021.9470673

Related papers

An Interpretation of Bunched Logic for Reasoning about Heap-Manipulating Quantum Programs

Su Bonan, Li Jun Zhou, Yuan Feng +1 more

We introduce heap manipulation into quantum programming languages to enable flexible quantum memory management, which in turn poses new challenges for reasoning about program correctness. To address these challenges, we develop a novel quantum interpretation of bunched logic by extending Birkhoff--von Neumann quantum logic to Hilbert spaces whose dimensions vary to accommodate the dynamic allocation and deallocation of variables on the quantum heap. Beyond the separating conjunction ($*$), we present, for the first time, a quantum interpretation of the separating implication ($-\mkern-3mu*$) to support backward reasoning. This interpretation preserves the adjunction between ($*$) and ($-\mkern-3mu*$), ensuring that both operators capture spatial properties and are precisely aligned with the semantics of quantum heap manipulations. Building on this foundation, we establish a quantum separation logic that supports local reasoning and is relatively complete.

arXiv:2409.10153•Sep 16, 2024•3 citations

A Quantum interpretation of separating conjunction for local reasoning of Quantum programs based on separation logic

Xuan-Bach D. Le, Shang‐Wei Lin, Jun Sun +1 more

It is well-known that quantum programs are not only complicated to design but also challenging to verify because the quantum states can have exponential size and require sophisticated mathematics to encode and manipulate. To tackle the state-space explosion problem for quantum reasoning, we propose a Hoare-style inference framework that supports local reasoning for quantum programs. By providing a quantum interpretation of the separating conjunction, we are able to infuse separation logic into our framework and apply local reasoning using a quantum frame rule that is similar to the classical frame rule. For evaluation, we apply our framework to verify various quantum programs including Deutsch–Jozsa’s algorithm and Grover's algorithm.

Proceedings of the ACM on Programming Languages•Jan 12, 2022•23 citations

Reasoning About Imperative Quantum Programs

Rohit Chadha, Paulo Mateus, Amílcar Sernadas

A logic for reasoning about states of basic quantum imperative programs is presented. The models of the logic are ensembles obtained by attaching probabilities to pairs of quantum states and classical states. The state logic is used to provide a sound Hoare-style calculus for quantum imperative programs. The calculus is illustrated by proving the correctness of the Deutsch algorithm.

Electronic Notes in Theoretical Computer Science•May 1, 2006•69 citations

Relational proofs for quantum programs

Gilles Barthe, Justin Hsu, Mingsheng Ying +2 more

Relational verification of quantum programs has many potential applications in quantum and post-quantum security and other domains. We propose a relational program logic for quantum programs. The interpretation of our logic is based on a quantum analogue of probabilistic couplings. We use our logic to verify non-trivial relational properties of quantum programs, including uniformity for samples generated by the quantum Bernoulli factory, reliability of quantum teleportation against noise (bit and phase flip), security of quantum one-time pad and equivalence of quantum walks.

arXiv:1901.05184•Proceedings of the ACM on Programming Languages•Dec 20, 2019•57 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

Foundations of logic programming in hybrid-dynamic quantum logic

Daniel Găină

The main contribution of the present paper is the introduction of a simple yet expressive hybrid-dynamic logic for describing quantum programs. This version of quantum logic can express quantum measurements and unitary evolutions of states in a natural way based on concepts advanced in (hybrid and dynamic) modal logics. We then study Horn clauses in the hybrid-dynamic quantum logic proposed, and develop a series of results that lead to an initial semantics theorem for sets of clauses that are satisfiable. This shows that a significant fragment of hybrid-dynamic quantum logic has good computational properties, and can serve as a basis for defining executable languages for specifying quantum programs. We set the foundations of logic programming in this fragment by proving a variant of Herbrand's theorem, which reduces the semantic entailment of a logic-programming query by a program to the search of a suitable substitution.

arXiv:2406.02085•Jun 4, 2024•2 citations
We propose a model of the substructural logic of Bunched Implications (BI) that is suitable for reasoning about quantum states. In our model, the separating conjunction of BI describes separable quantum states. We develop a program logic where pre- and post-conditions are BI formulas describing quantum states—the program logic can be seen as a counterpart of separation logic for imperative quantum programs. We exercise the logic for proving the security of quantum one-time pad and secret sharing, and we show how the program logic can be used to discover a flaw in Google Cirq’s tutorial on the Variational Quantum Algorithm (VQA).
We introduce heap manipulation into quantum programming languages to enable flexible quantum memory management, which in turn poses new challenges for reasoning about program correctness. To address these challenges, we develop a novel quantum interpretation of bunched logic by extending Birkhoff--von Neumann quantum logic to Hilbert spaces whose dimensions vary to accommodate the dynamic allocation and deallocation of variables on the quantum heap. Beyond the separating conjunction (∗*∗), we present, for the first time, a quantum interpretation of the separating implication (− ⁣∗-\mkern-3mu*−∗) to support backward reasoning. This interpretation preserves the adjunction between (∗*∗) and (− ⁣∗-\mkern-3mu*−∗), ensuring that both operators capture spatial properties and are precisely aligned with the semantics of quantum heap manipulations. Building on this foundation, we establish a quantum separation logic that supports local reasoning and is relatively complete.
It is well-known that quantum programs are not only complicated to design but also challenging to verify because the quantum states can have exponential size and require sophisticated mathematics to encode and manipulate. To tackle the state-space explosion problem for quantum reasoning, we propose a Hoare-style inference framework that supports local reasoning for quantum programs. By providing a quantum interpretation of the separating conjunction, we are able to infuse separation logic into our framework and apply local reasoning using a quantum frame rule that is similar to the classical frame rule. For evaluation, we apply our framework to verify various quantum programs including Deutsch–Jozsa’s algorithm and Grover's algorithm.
Relational verification of quantum programs has many potential applications in quantum and post-quantum security and other domains. We propose a relational program logic for quantum programs. The interpretation of our logic is based on a quantum analogue of probabilistic couplings. We use our logic to verify non-trivial relational properties of quantum programs, including uniformity for samples generated by the quantum Bernoulli factory, reliability of quantum teleportation against noise (bit and phase flip), security of quantum one-time pad and equivalence of quantum walks.
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.
The main contribution of the present paper is the introduction of a simple yet expressive hybrid-dynamic logic for describing quantum programs. This version of quantum logic can express quantum measurements and unitary evolutions of states in a natural way based on concepts advanced in (hybrid and dynamic) modal logics. We then study Horn clauses in the hybrid-dynamic quantum logic proposed, and develop a series of results that lead to an initial semantics theorem for sets of clauses that are satisfiable. This shows that a significant fragment of hybrid-dynamic quantum logic has good computational properties, and can serve as a basis for defining executable languages for specifying quantum programs. We set the foundations of logic programming in this fragment by proving a variant of Herbrand's theorem, which reduces the semantic entailment of a logic-programming query by a program to the search of a suitable substitution.