A Coalgebraic Model of Quantum Bisimulation

Lorenzo Ceragioli, Elena Di Lavore, Giuseppe Lomurno, Gabriele Tedeschi · 2025

Read A Coalgebraic Model of Quantum Bisimulation by Lorenzo Ceragioli, Elena Di Lavore, Giuseppe Lomurno, Gabriele Tedeschi (2025) 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-2509-20933.txt.

Introduction

Deciding when two quantum processes behave the same is harder than it sounds. Lorenzo Ceragioli and three co-authors build a coalgebraic model of quantum bisimulation in a paper from the ACT 2024 proceedings. Their framework handles systems that are quantum, concurrent, and nondeterministic at once.

The model uses coalgebras over distributions whose weights come from a general effect algebra, covering both probability and quantum effects. To respect the no-cloning rule of quantum theory, composition is graded by a resource monoid: processes may combine only when they use different quantum resources. The authors study how an open quantum system relates to its probabilistic counterpart. The work aims at a behavioral equivalence matching what observers can actually detect.

Catalog record

CREATORLorenzo Ceragioli, Elena Di Lavore, Giuseppe Lomurno, Gabriele Tedeschi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-20933

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Coalgebraic Model of Quantum Bisimulation Lorenzo Ceragioli, Elena Di Lavore, Giuseppe Lomurno, Gabriele Tedeschi Abstract Recent works have shown that defining a behavioural equivalence that matches the observational properties of a quantum-capable, concurrent, non-deterministic system is a surprisingly difficult task. We explore coalgebras over distributions taking weights from a generic effect algebra, which subsumes probabilities and quantum effects , a physical formalism that represents the probabilistic behaviour of an open quantum system. To abide by the properties of quantum theory, we introduce monads graded on a partial commutative monoid, intuitively allowing composition of two processes only if they use different quantum resources, as prescribed by the no-cloning theorem . We investigate the relation between an open quantum system and its probabilistic counterparts obtained when instantiating the input with a specific quantum state. We consider Aczel-Mendler and kernel bisimilarities, advocating for the latter as it characterizes quantum systems that exhibit the same probabilistic behaviour for all input states. Finally, we propose operators on quantum effect labelled transition systems, paving the way for a process calculi semantics that is parametric over the quantum input. 1 Introduction The recent development of quantum technologies calls for grounded methods for modelling and verifying computing systems that exploit quantum phenomena like superposition and entanglement. In particular, concurrent processes are of main interest, like communication protocols [ 35 , 4 , 31 , 18 ] and distributed implementations of algorithms via the Quantum Internet [ 8 , 39 ] . Such systems are essentially composed by a set of non-deterministic agents that run in parallels, can communicate, and have access to a quantum memory over which they can perform operations. The simplest quantum memory is the qubit, which takes values from a complex vector space: it can be in one of two standard basis states \ket{0} and \ket{1} , as well as in any linear combination of them. Agents can observe the state of a qubit only through a measurement on a chosen basis, a special kind of quantum operation that destroys the qubit and returns a probabilistic classical outcome, which depends on the qubit state. As an additional constraint, the no-cloning theorem forbids copying qubits, which thus cannot be shared by multiple agents [ 34 ] . Despite the considerable effort [ 30 , 13 , 17 , 14 , 11 ] , there is still no clear notion of behavioural equivalence for such systems, and most of the proposed ones lack a decision procedure. In [ 9 ] , the authors have proposed a new semantic model for quantum protocols, namely quantum effect labelled transition systems (qLTSs). These use quantum effects as weights, in the same way probabilities are used in a probabilistic labelled transition system (pLTS). Coming from quantum measurement theory, quantum effects represent the observable probabilistic properties that a quantum system expresses when initialized with a given input quantum state. This indeed allows modelling the agents in quantum protocols: they are essentially non-deterministic procedures acting on an initial quantum state, which is known only when a specific implementation is used in a concrete setting. Roughly, qLTSs model processes that are parametric over their quantum input. In this paper we build on this concept, characterizing quantum effects and probabilities as effect algebras. We investigate their (sub)distributions, and we give effect labelled transition systems ( \mathbb{E} LTSs), a uniform coalgebraic framework encompassing non-deterministic, probabilistic and quantum concurrent systems. The coalgebraic language is well suited to treat dynamical systems in their essential features, and allows us to extend properties and constructs of probabilistic systems to quantum ones. We introduce monads graded on a partial commutative monoid (PCM), allowing us to grade effect distributions over their quantum resources, the copy of which is forbidden by the no-cloning theorem. Transition systems graded over this PCM intuitively represent quantum computations that consume some quantum resources: only computations using disjoint resources can be composed. Besides, thanks to our peculiar grading, we define a commutative Kronecker product of effects, and thus a commutative multiplication of effect distributions, generalizing the joint distribution operator of the probabilistic case [ 3 ] . We investigate kernel and Aczel-Mendler (AM) bisimilarities for \mathbb{E} LTSs, and relate them by generalizing previous results. By applying our findings to the quantum setting, we prove that each quantum state \rho defines a functor from qLTSs to pLTSs that “instantiates” a quantum process to the probabilistic behaviour it exhibits when the measured quantum state is \rho . We study which equivalences are preserved and/or reflected by these functors, giving us a categorical way to pinpoint the correct notion of equivalence for quantum systems, i.e. the one that equates all and only the processes that exhibit the same observable probabilistic behaviour. Both AM and kernel bisimilarities correctly relate indistinguishable quantum processes only. However, only the latter is complete and relates all the indistinguishable processes, given that the weights of the qLTS are taken from a finite effect algebra of quantum effects. Finally, we investigate operators over \mathbb{E} LTSs, paving the way for an \mathbb{E} LTS semantics of quantum process calculi. We provide a generalized, compositional parallel operator which can model different notions of synchronization (CCS, CSP, ACT) and different kinds of “weights” (nondeterministic, probabilistic or quantum systems). In addition, we introduce a purely quantum operator of “partial evaluation” of qLTSs that instantiates the value of some of the qubits. These operators are defined as functors between \mathbb{E} LTSs, thus they preserve bisimilarity. While similar operators in the literature typically act on the final coalgebra, treating them as functors allows for “multi sorted” operators: partial evaluation reduces the resources used by the computation; parallel composition joins them by increasing the number of qubits (only if they are compatible, i.e. of different quantum systems). A qLTS semantics for quantum processes would reduce the problem of deciding probabilistic bisimilarity of two protocols for all possible input quantum states to just checking kernel bisimilarity of two given qLTSs, which can be solved via standard techniques [ 27 ] . Related Works. Usually, works from the process algebra literature [ 30 , 15 , 13 , 14 , 11 , 10 ] define the semantics of quantum processes via pLTSs, and strive to adapt probabilistic bisimilarity to capture the peculiar observable properties of quantum values. The defined pLTSs are made of configurations, i.e. pairs of quantum values and syntactic processes, impeding algorithmic verification of processes when the quantum input is not given (the only symbolic approach [ 16 ] has been proved too strict [ 11 ] ). We instead introduce a purely quantum transition system: we do not represent directly quantum values but only their observable probabilistic features in the form of effects. This work builds on [ 9 ] : we use the language of distribution monads, their coalgebras and their coalgebraic bisimilarity to generalize the concepts of quantum distribution, quantum transition systems and Larsen-Skou bisimilarity presented there. Noticeably, our effect distribution monad subsumes both the probability distribution monad, the quantum effect distributions of [ 9 ] and the quantum monad of [ 2 ] , which is based on projectors, a subset of quantum effects. Our graded monad definition extends the non-graded effect monad presented in [ 25 ] , which takes

Read the complete text