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:2611.04274

Reasoning about Shared-Qubit Concurrency in Quantum Computing

Mingsheng Ying

quant-phcs.DCcs.LOcs.PLSubmitted Nov 3, 2026• Announced Nov 4, 2026• 0 citations
arXivHTMLPDF

Abstract

In this paper, we develop a semantic model for the parallel execution of quantum circuits, providing a formal foundation for studying shared-qubit concurrency in quantum computing. As in classical shared-memory concurrency, parallel quantum circuits may interfere with one another through operations on shared qubits. However, quantum entanglement and the noncommutativity of quantum operations introduce additional challenges for reasoning about their correctness. To address these challenges, we generalise the classical Owicki-Gries method to quantum computing at the level of quantum circuits. Our approach enables compositional reasoning about parallel quantum circuits by separating the verification of individual components from the analysis of interference between them. We formulate proof rules for establishing the correctness of parallel quantum circuits and prove their soundness with respect to the proposed semantic model.

AI Summary

The paper studies how to specify and verify quantum circuits whose concurrently executing components access shared qubits. Its question is whether componentwise correctness proofs can be combined despite schedule-dependent effects from noncommuting operations and entanglement. The setting is finite-dimensional, unitary circuits without mid-circuit measurements. It defines an interleaving semantics in which basic gates, or explicitly designated multi-gate atomic regions, execute indivisibly. A parallel circuit maps each input state to the set of outputs obtainable under permitted schedules. Correctness is expressed through Hoare triples $\{X\}C\{Y\}$ with subspace assertions: every output from an input in $X$ must lie in $Y$. Assertions on overlapping registers are combined by tensoring with unrestricted environments and intersecting on a common register. The main construction adapts Owicki–Gries reasoning: verify components separately, then check that other components’ atomic actions preserve their proof assertions. Sequential, atomic-region and parallel-composition rules are presented with soundness proofs based on lifting lemmas and induction over executions. A six-qubit syndrome-extraction example combines two five-step components, covering $\binom{10}{5}=252$ interleavings through 60 directed preservation checks. It establishes syndrome correlations despite potentially noncommuting logical rotations, while illustrating why atomicity matters. The stated scope excludes measurement-dependent conditionals and loops. Extending the approach to general quantum programs with observable-valued assertions remains open, particularly because an appropriate conjunction for those assertions is not supplied. A rely–guarantee extension is proposed as future work.

Little sign of AI-generated textPossible errorStrong assumptions

Central claim may not hold: The formally defined interference-freedom condition omits preservation of completed components' postconditions, making the central parallel rule unsound, as demonstrated by the X/CNOT counterexample. The case study checks 60 directed preservation obligations, whereas the formal definition requires only 50; the additional ten protect terminal assertions omitted from the general rule's premises.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Reasoning about Parallel Quantum Programs

Mingsheng Ying, Li Zhou, Yangjia Li

We initiate the study of parallel quantum programming by defining the operational and denotational semantics of parallel quantum programs. The technical contributions of this paper include: (1) find a series of useful proof rules for reasoning about correctness of parallel quantum programs; (2) prove a (relative) completeness of our proof rules for partial correctness of disjoint parallel quantum programs; and (3) prove a strong soundness theorem of the proof rules showing that partial correctness is well maintained at each step of transitions in the operational semantics of a general parallel quantum program (with shared variables). This is achieved by partially overcoming the following conceptual challenges that are never present in classical parallel programming: (i) the intertwining of nondeterminism caused by quantum measurements and introduced by parallelism; (ii) entanglement between component quantum programs; and (iii) combining quantum predicates in the overlap of state Hilbert spaces of component quantum programs with shared variables. Applications of the techniques developed in this paper are illustrated by a formal verification of Bravyi-Gosset-König's parallel quantum algorithm solving a linear algebra problem, which gives for the first time an unconditional proof of a computational quantum advantage.

arXiv:1810.11334•Oct 26, 2018•21 citations

Quantum circuits and parallelism

Pawan Kumar Verma, Mohit Kumar, Saurabh Singhal +1 more

This chapter develops the quantum circuit model as the operational core of gate-based quantum computation, framing circuits as structured compositions of unitary transformations acting on qubits and quantum registers. It begins by formalizing qubits as normalized state vectors in Hilbert space and extends to multi-qubit registers via tensor products, emphasizing the exponential growth of representable basis amplitudes and the resulting capacity for entanglement. Building on these foundations, this chapter details circuit design as an algorithm-engineering discipline that must balance mathematical correctness with resource efficiency under hardware and noise constraints, including circuit depth, gate count, qubit connectivity, control bandwidth, and crosstalk. Circuit construction is presented through sequential composition and parallel execution on disjoint qubit subsets, motivating scheduling methods such as dependency-graph analysis, critical-path identification, and time-slice (layer) formation under platform-imposed concurrency limits. This chapter then addresses quantum circuit decomposition as the bridge from abstract algorithmic operators to implementable gate sets, highlighting universal synthesis principles (including Solovay–Kitaev guarantees) and standard decompositions for single-qubit unitaries (Euler-angle forms) and controlled multi-qubit operations. Finally, quantum parallelism is treated as a distinctly quantum computational resource arising from superposition over 2.

CRC Press eBooks•Nov 6, 2026•0 citations

Quantum Principles in Concurrency: Toward Resolving Classical Synchronization Problems

Yuanjie Li, Jinsuk Baek, Minho Jo

This paper investigates the application of quantum principles -most notably superposition and entanglement -to reframe classical concurrency problems in software engineering.While other research has explored quantum concepts primarily as tools for parallelization, this work advances the discourse by proposing quantum-inspired abstractions for reasoning about mutual exclusion, race conditions, deadlocks, and the producer-consumer problem.By treating threads and shared resources as qubits and modeling their interactions via correlated quantum states within an abstract state-space, we present a framework that illustrates how quantum formalisms can conceptually model concurrency patterns, supported by mathematical formulations in Dirac notation and circuit representations.Superposition naturally models multiple execution paths, while entanglement provides symbolic global correlations rather than operational synchronization, offering new perspectives on longstanding concurrency challenges.Our simulations across four scenarios demonstrate that these quantum-inspired formulations can highlight order-sensitivity and contention patterns in a unified mathematical setting.These results do not constitute practical concurrency mechanisms, but they suggest how quantum principles may inform future hybrid quantumclassical analysis tools.We also conclude with a discussion on potential integration into hybrid systems, highlighting both practical benefits and open challenges.

KSII Transactions on Internet and Information Systems•May 31, 2026•0 citations

Formal Specification and Verification of Quantum Computing Algorithms

Jincheng Zhang

The verification of quantum computing algorithms presents a significant hurdle due to the probabilistic nature of quantum mechanics and the complex entanglement inherent in quantum computations. This paper proposes a novel approach to address this challenge by developing a formal language and a corresponding verification tool tailored explicitly for quantum algorithm specification and verification. The system leverages concepts from quantum information theory and formal methods to provide a rigorous framework for ensuring the correctness of quantum algorithms. We introduce a new formalism that allows for precise description of quantum circuits and their operations, combined with automated theorem proving techniques to systematically verify the algorithm's behavior against a given specification. The key innovation lies in the ability to reason about quantum states and measurements within a formal setting, enabling a more comprehensive understanding and validation of these algorithms. This work lays the foundation for increased confidence in the development and deployment of quantum computing technologies.

•Sep 2, 2026•0 citations

A Review of Formal Methods in Quantum-Circuit Verification

Arun Govindankutty

Quantum computing exploits the principles of quantum mechanics to perform computation. Information is stored in qubits and processed with a sequence of quantum gates arranged as circuits. Verifying the correctness of quantum circuits is becoming essential as hardware scales in qubit count and architectural complexity. Traditional testing and naive simulation do not scale and quickly become computationally infeasible because the state space grows exponentially. This creates a strong need for more powerful and scalable verification techniques. Formal methods offer a viable solution by providing mathematically rigorous and scalable verification techniques that address these scalability challenges through abstraction, symbolic reasoning, and probabilistic guarantees. This study examines how formal methods are applied to quantum-circuit verification. Specifically, four families of formal techniques: barrier certificates, abstract interpretation, model checking, and theorem proving are examined, along with the theoretical foundations and practical applications of these techniques. Finally, the study highlights open challenges and identifies promising directions for future research. An extensive set of references is included to support further study and exploration.

Electronics•Mar 9, 2026•5 citations

Modular Logic for Parallel Quantum Computing

Jincheng Zhang

This paper investigates the potential of modular logic to revolutionize parallel quantum computing, addressing the challenges of scalability and fault tolerance. We propose a novel system leveraging formal language and reasoning to design and orchestrate quantum computations, promoting independent and verifiable execution of computational modules within a quantum circuit. The core mechanism centers around a language that explicitly defines the logical relationships between modules, enabling automated circuit design and optimization. This approach seeks to overcome the limitations of traditional quantum programming by enhancing expressiveness, simplifying verification, and facilitating a more robust and scalable approach to quantum computation. The paper details the proposed system, its reasoning framework, and preliminary results demonstrating improvements in circuit design and verification.

•Sep 5, 2026•0 citations
In this paper, we develop a semantic model for the parallel execution of quantum circuits, providing a formal foundation for studying shared-qubit concurrency in quantum computing. As in classical shared-memory concurrency, parallel quantum circuits may interfere with one another through operations on shared qubits. However, quantum entanglement and the noncommutativity of quantum operations introduce additional challenges for reasoning about their correctness. To address these challenges, we generalise the classical Owicki-Gries method to quantum computing at the level of quantum circuits. Our approach enables compositional reasoning about parallel quantum circuits by separating the verification of individual components from the analysis of interference between them. We formulate proof rules for establishing the correctness of parallel quantum circuits and prove their soundness with respect to the proposed semantic model.
The paper studies how to specify and verify quantum circuits whose concurrently executing components access shared qubits. Its question is whether componentwise correctness proofs can be combined despite schedule-dependent effects from noncommuting operations and entanglement. The setting is finite-dimensional, unitary circuits without mid-circuit measurements.
It defines an interleaving semantics in which basic gates, or explicitly designated multi-gate atomic regions, execute indivisibly. A parallel circuit maps each input state to the set of outputs obtainable under permitted schedules. Correctness is expressed through Hoare triples {X}C{Y}\{X\}C\{Y\}{X}C{Y} with subspace assertions: every output from an input in XXX must lie in YYY. Assertions on overlapping registers are combined by tensoring with unrestricted environments and intersecting on a common register.
The main construction adapts Owicki–Gries reasoning: verify components separately, then check that other components’ atomic actions preserve their proof assertions. Sequential, atomic-region and parallel-composition rules are presented with soundness proofs based on lifting lemmas and induction over executions. A six-qubit syndrome-extraction example combines two five-step components, covering (105)=252\binom{10}{5}=252(510​)=252 interleavings through 60 directed preservation checks. It establishes syndrome correlations despite potentially noncommuting logical rotations, while illustrating why atomicity matters.
The stated scope excludes measurement-dependent conditionals and loops. Extending the approach to general quantum programs with observable-valued assertions remains open, particularly because an appropriate conjunction for those assertions is not supplied. A rely–guarantee extension is proposed as future work.
We initiate the study of parallel quantum programming by defining the operational and denotational semantics of parallel quantum programs. The technical contributions of this paper include: (1) find a series of useful proof rules for reasoning about correctness of parallel quantum programs; (2) prove a (relative) completeness of our proof rules for partial correctness of disjoint parallel quantum programs; and (3) prove a strong soundness theorem of the proof rules showing that partial correctness is well maintained at each step of transitions in the operational semantics of a general parallel quantum program (with shared variables). This is achieved by partially overcoming the following conceptual challenges that are never present in classical parallel programming: (i) the intertwining of nondeterminism caused by quantum measurements and introduced by parallelism; (ii) entanglement between component quantum programs; and (iii) combining quantum predicates in the overlap of state Hilbert spaces of component quantum programs with shared variables. Applications of the techniques developed in this paper are illustrated by a formal verification of Bravyi-Gosset-König's parallel quantum algorithm solving a linear algebra problem, which gives for the first time an unconditional proof of a computational quantum advantage.
This chapter develops the quantum circuit model as the operational core of gate-based quantum computation, framing circuits as structured compositions of unitary transformations acting on qubits and quantum registers. It begins by formalizing qubits as normalized state vectors in Hilbert space and extends to multi-qubit registers via tensor products, emphasizing the exponential growth of representable basis amplitudes and the resulting capacity for entanglement. Building on these foundations, this chapter details circuit design as an algorithm-engineering discipline that must balance mathematical correctness with resource efficiency under hardware and noise constraints, including circuit depth, gate count, qubit connectivity, control bandwidth, and crosstalk. Circuit construction is presented through sequential composition and parallel execution on disjoint qubit subsets, motivating scheduling methods such as dependency-graph analysis, critical-path identification, and time-slice (layer) formation under platform-imposed concurrency limits. This chapter then addresses quantum circuit decomposition as the bridge from abstract algorithmic operators to implementable gate sets, highlighting universal synthesis principles (including Solovay–Kitaev guarantees) and standard decompositions for single-qubit unitaries (Euler-angle forms) and controlled multi-qubit operations. Finally, quantum parallelism is treated as a distinctly quantum computational resource arising from superposition over 2.
This paper investigates the application of quantum principles -most notably superposition and entanglement -to reframe classical concurrency problems in software engineering.While other research has explored quantum concepts primarily as tools for parallelization, this work advances the discourse by proposing quantum-inspired abstractions for reasoning about mutual exclusion, race conditions, deadlocks, and the producer-consumer problem.By treating threads and shared resources as qubits and modeling their interactions via correlated quantum states within an abstract state-space, we present a framework that illustrates how quantum formalisms can conceptually model concurrency patterns, supported by mathematical formulations in Dirac notation and circuit representations.Superposition naturally models multiple execution paths, while entanglement provides symbolic global correlations rather than operational synchronization, offering new perspectives on longstanding concurrency challenges.Our simulations across four scenarios demonstrate that these quantum-inspired formulations can highlight order-sensitivity and contention patterns in a unified mathematical setting.These results do not constitute practical concurrency mechanisms, but they suggest how quantum principles may inform future hybrid quantumclassical analysis tools.We also conclude with a discussion on potential integration into hybrid systems, highlighting both practical benefits and open challenges.
The verification of quantum computing algorithms presents a significant hurdle due to the probabilistic nature of quantum mechanics and the complex entanglement inherent in quantum computations. This paper proposes a novel approach to address this challenge by developing a formal language and a corresponding verification tool tailored explicitly for quantum algorithm specification and verification. The system leverages concepts from quantum information theory and formal methods to provide a rigorous framework for ensuring the correctness of quantum algorithms. We introduce a new formalism that allows for precise description of quantum circuits and their operations, combined with automated theorem proving techniques to systematically verify the algorithm's behavior against a given specification. The key innovation lies in the ability to reason about quantum states and measurements within a formal setting, enabling a more comprehensive understanding and validation of these algorithms. This work lays the foundation for increased confidence in the development and deployment of quantum computing technologies.
Quantum computing exploits the principles of quantum mechanics to perform computation. Information is stored in qubits and processed with a sequence of quantum gates arranged as circuits. Verifying the correctness of quantum circuits is becoming essential as hardware scales in qubit count and architectural complexity. Traditional testing and naive simulation do not scale and quickly become computationally infeasible because the state space grows exponentially. This creates a strong need for more powerful and scalable verification techniques. Formal methods offer a viable solution by providing mathematically rigorous and scalable verification techniques that address these scalability challenges through abstraction, symbolic reasoning, and probabilistic guarantees. This study examines how formal methods are applied to quantum-circuit verification. Specifically, four families of formal techniques: barrier certificates, abstract interpretation, model checking, and theorem proving are examined, along with the theoretical foundations and practical applications of these techniques. Finally, the study highlights open challenges and identifies promising directions for future research. An extensive set of references is included to support further study and exploration.
This paper investigates the potential of modular logic to revolutionize parallel quantum computing, addressing the challenges of scalability and fault tolerance. We propose a novel system leveraging formal language and reasoning to design and orchestrate quantum computations, promoting independent and verifiable execution of computational modules within a quantum circuit. The core mechanism centers around a language that explicitly defines the logical relationships between modules, enabling automated circuit design and optimization. This approach seeks to overcome the limitations of traditional quantum programming by enhancing expressiveness, simplifying verification, and facilitating a more robust and scalable approach to quantum computation. The paper details the proposed system, its reasoning framework, and preliminary results demonstrating improvements in circuit design and verification.