arXiv:2611.04274
Reasoning about Shared-Qubit Concurrency in Quantum Computing
Mingsheng Ying
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.
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.