Asynchronous Quantum Distributed Computing: Causality, Snapshots, and Global Operations Siddhartha Visveswara Jayanti (సిదాధ్రథ్ విశేవ్శవ్ర జయంతి) ∗ Dartmouth
arXiv:2604.08298v1 [cs.DC] 9 Apr 2026
Anand Natarajan (ஆனந்த் நடராஜன்) † MIT
April 9, 2026
Abstract We initiate the study of asynchronous quantum distributed systems, focusing on the case of implementing atomic quantum global operations that can be decomposed into a collection of local operations on the components of the system. A simple example of such an operation is a quantum snapshot in which the whole system is instantaneously measured. Based on the classical snapshot algorithm of Chandy and Lamport, we design a quantum distributed algorithm to implement such decomposable global operations, which we call the QGO Algorithm. The analysis of our algorithm shows that arguments based on Lamport’s computational causality remain valid in the quantum world, even though, due to entanglement, causality is not manifest from the standard description of the system in terms of a (global) quantum state. Our other contributions include a formal model of quantum distributed computing, and a formal specification for the desired behavior of a global operation, which may be of interest even in classical settings (such as in the setting of randomized algorithms).
1
Introduction
The analysis of asynchronous distributed computer systems relies on an understanding of locality and causality, creating a link between distributed systems and fundamental physics. This link means that distributed systems could behave in fundamentally different ways in worlds with different physical models of time and causality: for instance, to handle a world described by special relativity (where there is no global time and observers do not agree on the temporal order of events), basic concepts like that of linearizability require modification [GG14], and it was only recently shown that linearizable systems in the “Newtonian” sense remain linearizable in a relativistic world [Jay25]. Could quantum mechanics make a meaningful difference here as well? It is well known that quantum entanglement, as described in the standard “Schrödinger” formalism of quantum mechanics in terms of wave functions and unitary operators, can cause the appearance of instantaneous, nonlocal action. This point was famously raised by Einstein, Podolsky, and Rosen [EPR35], who observed that, in the standard quantum formalism, if two systems A and B are in the “EPR pair state” 1 |ψiAB = √ (|0iA |0iB + |1iA |1iB ), 2 ∗ †
[email protected] [email protected]
1
a measurement of system A will cause both systems to instantaneously collapse to either the state |0iA |0iB or |1iA |1iB , no matter how far system A is from system B. Moreover, Bell’s theorem [Bel64] shows that this apparent nonlocality is in some sense “real”: there are empirically realizable scenarios where entangled quantum systems, through local operations, can produce correlations in their classical measurement outcomes that are impossible to obtain in any classical local system. Quantum nonlocality can even be used to show that constant-depth quantum circuits can solve a computational problem that requires a logarithmic-depth circuit classically [BGK18], which can be viewed as a distributed computational advantage if one imagines the qubits in the circuit to be located on separate processors. Despite this apparent or real nonlocality in quantum mechanics, it is widely known to (or perhaps believed by) quantum information scientists that causality in quantum computational systems works essentially the same way as it does classically: in particular, causal influences spread locally. For instance, entanglement does not permit messages to be sent instantaneously, faster than the speed of light [Ebe78, ER89], and “light-cone” arguments to analyze the spread of causal information in quantum circuits are very common (e.g. [Liu24]). These are specific examples, but what about more complex causal scenarios? In particular, asynchronous distributed systems introduce considerations not present in the previous, essentially synchronous, examples. Unlike a quantum circuit in which the locations and times of operations are fixed, in a distributed system, events can be controlled by an adversarial scheduler that can act arbitrarily, and one wishes to prove that certain properties hold for every possible execution consistent with the adversary’s power. Moreover, a distributed system can receive input and produce output at many different times, unlike a quantum circuit to compute a function which receives its input all at once and produces its output all at once. Do these additional considerations make a material difference to the behavior of causality, and if not, how do we prove mathematically that causality continues to behave as it does classically? Apart from this basic scientific motivation, there are strong practical reasons to study quantum asynchronous distributed systems. Quantum computing hardware is advancing rapidly, and work is already underway to design and build networks of quantum devices, or a “quantum internet” [WEH18]. Such networks are very likely to have a significant space-based component in order to minimize attenuation of the signals, which will likely be sent using photons [KBD+ 21]. In fact, satellites implementing quantum computing hardware are already in orbit as technical demonstrations [RXY+ 17]. Thus, in light of these theoretical and practical motivations, we initiate the study of asynchronous quantum distributed systems in this work. We focus our efforts on constructing and analyzing a quantum analog of the snapshot algorithm of Chandy and Lamport [CL85], which Lamport has described [Lam] as “a straightforward application of the basic ideas from [Lam78].” This algorithm is meant to implement the ideal functionality of taking a global snapshot of a distributed system at a single point in time. In the quantum setting, because quantum states cannot be copied (the “no-cloning theorem”), and measurement disturbs the state, it is not clear what the correct notion of a snapshot should be. We propose that the appropriate generalization is that of a decomposable global operation: a global operation on the system that consists of a tensor product of separate operations on the components. This recovers the classical snapshot functionality when the operation is taken to be measurement (in the computational basis), but can also model many more classical and quantum behaviors—for instance, one may consider the global encryption operation, in which one encrypts the state of all components of the system under a common key. Our main results are the following: • An extension of Lamport’s definition of computational causality to quantum systems (Def2
inition 5.1) and a proof that executions of a system that have the same causality relation (“equicausal”) behave equivalently: in particular, they result in the same final state (Theorem 5.7). • A formal specification of how an atomic global operation should act (Definition 6.2). • An algorithm, which we call the QGO algorithm, and a proof that it implements the specification in the following sense: every execution of the QGO algorithm is equicausal with an execution that is operationally indistinguishable from an execution of the specification (Theorem 8.3). Our proof of Theorem 8.3 is similar to Chandy and Lamport’s analysis of their algorithm, although some extra steps are needed to handle the fact that our global operations modify the state. Nevertheless we view this result as showing that classical causality-based techniques are also applicable to quantum systems. Our work opens up several interesting directions for future work. One direction is in fact purely classical: what is the strongest correctness guarantee we can get for global operations applied to classical randomized systems? In particular, our result shows that any execution of the algorithm can be “matched” by some execution of the specification, but one could hope for a stronger statement relating the entire probability distribution of executions, for a fixed adversary, to the distribution over executions of the specification. It is possible that this will involve issues similar to those which arise in the study of linearizability in randomized algorithms, where it was shown that strong linearizability is the more appropriate concept [GHW11]. Secondly, our work is restricted to quantum systems where an execution specifies the location and time at which each message between processes is sent or received. This corresponds to the typical setting of quantum circuits studied in quantum computing, but one could imagine scenarios in which superpositions over different message histories are permitted. It has been speculated that causality may behave more exotically in these scenarios [Bru14], and it would be interesting to explore this in the context of a distributed algorithm. Finally, what about quantum relativistic distributed systems? We already know that relativity is relevant for space-based systems, and it is likely that a future quantum internet will have a space-based component, so the quantum relativistic setting could be highly relevant in practice.
2
Other Related Work
The most directly related work was discussed in the introduction. There have been several works on quantum distributed computing in synchronous settings, including works that find computational advantages over classical systems or algorithms for tasks that are not classically possible [DP08, DMP25, BBCR+ 25, AG97]. However, to our knowledge, quantum asynchronous systems have not been studied.
3
Quantum Physics and Distributed Systems
We give a very brief and incomplete summary of the formalism and notation of quantum mechanics, in the slightly customized form used in this paper. This section is aimed at a reader with a basic knowledge of quantum computing, say from the first few weeks of an undergraduate class on the subject, and can safely be skimmed by quantum specialists. For a fuller treatment of quantum theory, we recommend standard textbooks [NC10, KSV02]. 3
At any point in time, a quantum system is described by a complex Hilbert space H, which for our purposes can essentially always be thought of as a finite-dimensional complex vector space Cd . The special case of d = 2 is referred to as a qubit. In Dirac’s bra-ket notation—which is not needed for the body of the paper but which we will use for concrete examples in this section—(column) vectors in Cd will be denoted by kets, e.g. |ψi, and dual vectors (i.e. row vectors) will be denoted by bras, e.g. hψ|. This notation yields the pleasing expression hα|βi for the inner product between two vectors |αi and |βi. Matrices will be denoted by Latin or Greek letters: a useful way of writing a matrix in components is X M= mij |ii hj| , ij
where |ii is the ith standard basis vector and mij is the entry in the ith row and jth column of M . The state of a quantum system is a Hermitian positive semidefinite linear operator (i.e. a matrix) ρ over H with trace at most one; such matrices are called (subnormalized) density matrices, and the space of density matrices over H is denoted D(H). We use the notation B(H) to denote the space of bounded linear operators of H, so D(H) ⊂ B(H). This formalism is different from the typical definition of quantum states as unit vectors |ψi in H that is found in introductory treatments of quantum computing. Such states are called pure states, and form a a subset of all possible quantum states: any such state can be captured by the associated rank-one density matrix |ψi hψ|. Pure states include determinsitic classical states: for instance, for a qubit system, the qubit can be in the classical states |0i or |1i. They also capture superpositions, e.g. the state 1 |+i = √ (|0i + |1i). 2 However, the density matrix formalism allows to us to capture quantum states in their full generality: importantly, the state of a subsystem of a larger quantum system can always be described by a density matrix, but not always by a pure state (even if the global state of the entire system is pure). Moreover, a density matrix can describe a classical probability distribution over quantum states. In fact our formalism is slightly more general than even the standard notion of density matrices, which requires that tr[ρ] = 1. We allow for states with tr[ρ] < 1 in order to keep track of probabilities of computational histories. In particular, suppose we imagine a system executing a sequence of operations, some of which are measurements with particular outcomes r1 , r2 , . . . , ending up in state ρ. Then, in our formalism, tr[ρ] will be equal to the probability that the measurements performed in this sequence of operations actually produced the sequence r1 , r2 , . . . of outcomes. If two systems with Hilbert spaces HA , HB are put together, the state space of the composite system is the tensor product HAB = HA ⊗HB . The space of states D(HAB ) over the tensor product space includes matrices that factor as tensor products, i.e. matrices of the form ρA ⊗ ρB , but also many others. All states that are not convex combinations of tensor products are called entangled states. A canonical example of an entangled state is the EPR state on two qubits. ρEP R = |EP Ri hEP R| ,
1 |EP Ri = √ (|0i ⊗ |0i + |1i ⊗ |1i). 2
Going the other way, given a state ρAB ∈ D(HA ⊗ HB ), we can define the reduced state of one of the systems—say, system A—by taking the partial trace: X ρA = trB [ρAB ] = (I ⊗ hi|)ρAB (I ⊗ |ii). i
4
(Note that the subscript of tr is the system to be discarded!) Here |ii is a standard basis vector in HB , and i runs over the dimensions of HB . In our EPR example, 1 ρA = trB [ρEP R ] = (|0i h0| + |1i h1|). 2 The possible operations on quantum systems are quantum operations, which are linear maps acting on quantum states. These maps are required to satisfy certain positivity and normalization conditions, which we will specify below in Definition 3.1, but to start we will explain how these maps act at a basic level. To allow for systems to grow and shrink in size (e.g. by sending or receiving messages, or by initializing fresh qubits or discarding qubits), we allow a quantum operation to change the Hilbert space of the associated system. Thus, if we start with a system corresponding to Hilbert space H, a quantum operation will be described by a linear map Λ : B(H) → B(H′ ), where after the operation the system is now described by Hilbert space H′ : if the system started in state ρ ∈ D(H), it will end up in ρ′ = Λ(ρ) ∈ B(H′ ). A quantum operation can be applied to a subsystem of a composite system by taking its tensor product with the identity map: if we have a ′ ) on the A system alone, composite system HAB = HA ⊗ HB and an operation Λ : B(HA ) → B(HA then the operation acts on states of the composite system by ′ ρ 7→ (Λ ⊗ id)(ρAB ) ∈ B(HA ⊗ HB ).
Any operation on AB that can be written in this way as a tensor product of an operation on A and the identity on B is referred to as being local to A, or as acting trivially on B, and these definitions can be straightforwardly generalized to systems with more components. Often, treatments distinguish between measurements, which act probabilistically and yield a classical outcome visible to classical observers, and other kinds of quantum operations, which act deterministically on the state ρ and do not yield a classical outcome. For us, it will be convenient to unify these objects into the single formalism of a quantum operation with a (possibly empty) classical outcome set R. Definition 3.1 (Quantum operation). A quantum operation with classical outcome set R is a collection of linear maps Λr : D(Hin ) → D(Hout ) for each r ∈ R, satisfying the following conditions: 1. Each Λr is completely positive, meaning that for any ancillary quantum system with Hilbert space H′ , and any state ρ ∈ D(Hin ⊗ H′ ), (Λ ⊗ id)(ρ) is positive semidefinite. P r 2. The Plinearr map r∈R Λ is trace-preserving, meaning that for any ρ ∈ D(H), it holds that tr[ r∈R Λ (ρ)] = 1. Physically, when we apply this operation to a system in state ρ, a random outcome r ∈ R is generated with probability Pr[r] = tr[Λr (ρ)], and the system enters state Λr (ρ). As an example of this formalism in action, let us consider the state ρEP R as defined above, and consider applying a standard basis measurement to the first qubit. The standard basis measurement has outcome set {0, 1}, and corresponds to the maps Λ0 (ρ) = |0i h0| · ρ · |0i h0| Λ1 (ρ) = |1i h1| · ρ · |1i h1| . Applying this operation to ρEP R means we should apply Λr ⊗ id. 1 (Λ0 ⊗ id)(ρEP R ) = (|0i h0|) ⊗ (|0i h0|), 2 1 (Λ1 ⊗ id)(ρEP R ) = (|1i h1|) ⊗ (|1i h1|), 2 5
1 2 1 Pr[1] = . 2 Pr[0] =
So we see that this operation yields a uniformly random outcome r ∈ {0, 1}, and causes both qubits to “collapse” to the classical state |ri.
4
Model
A distributed system S = (Π, Γ) consists of a set of asynchronous processors, Π, that communicate by passing messages, from a universe M, along channels Γ. The processors are asynchronous in the sense that they may spend arbitrary and variable times between computational steps. Message transmission is also asynchronous, meaning that messages may take arbitrarily long to reach their intended recipient, but they eventually arrive. For convenience, we assume that messages are delivered in order, i.e., that the channels are first-in-first-out (FIFO). (If channels are not FIFO, senders can simply tag each message along a channel with sequence number and recipients can wait to process any message until all messages of lower sequence numbers along the channel are already received.) Components and their States In general, a system is composed of several components, C, such as the processors, messages, and channels of a distributed system. To capture systems of full generality, we model all components c ∈ C of our system to have both a classical part cc and a quantum part qc ; thus c = (cc , qc ). (For example, a message µ whose principal contents are quantum must still contain a classical tag in order for the message to be processed by the recipient without collapsing the quantum state.) The state space of the classical part is a set of classical states denoted Σc . We generally use σc ∈ Σc to refer to the state of the classical part of the component. The state space of the quantum part is a Hilbert space Hc . We generally use ρc ∈ Hc to refer to the (local) state of the quantum part of c. It is noteworthy that while the classical state of the system is fully specified as the combination of the classical states of its components, due to entanglement, the quantum state of the entire system cannot simply be expressed as the combination of quantum states of its components. The quantum state of the system must be specified jointly, as a density matrix of the entire quantum part of the system. So, ρc captures the local state of qc and does not capture any entanglements that c has with other parts of the system. Channel States A channel γ has a source π ∈ Π and a destination π ′ ∈ Π. We use the notation γ[π → π ′ ] to refer to the channel whose source is π and destination is π ′ . We assume a single channel from every source to every destination, thus the set of all channels is Γ = {γ[π → π ′ ] | π, π ′ ∈ Π}. Note that we assume a channel from each process to itself. At any point in time a channel γ = γ[π → π ′ ]’s contents are the fixed sequence of messages that been sent by π but yet to be received by π ′ , in the order they were sent. Thus, the channel has a lengthγ.len ∈ N, i.e., the number of messages in the channel, and contents γ.contents = µ1 , . . . , µγ.len . The classical and quantum parts of the channel are cγ ≜ (cµ1 , . . . , cµγ.len ) and qγ ≜ (qµ1 , . . . , qµγ.len ), respectively. Thus, the channel’s classical state is simply the sequence of classical states of the messages in the channel: σγ = σµ1 , . . . , σµγ.len N , and the channel’s Hilbert space is the tensor product of the message Hilbert spaces, i.e., Hγ = µ∈γ.contents Hµ . System State The distributed system S is comprised of its processes Π and channels NΓ. So, the classical state of the system is σS = (σc )c∈Π∪Γ , and the system’s Hilbert space is HS = c∈Π∪Γ Hc . Consequently, the system’s classical state is σS = (σc )c∈Π∪Γ . The system’s quantum state is expressed as a single density matrix ρS over HS . While the global quantum state of the system is not a simple combination of local quantum states of the components of the system (just as a joint 6
distribution cannot be fully described by its marginals), the local quantum states of each component c is well defined, and can be calculated from ρS by taking a partial trace over the complement of the component with respect to the system. That is, for a component c, its quantum state is ρc = trc [ρS ]). The state of the system is ΨS ≜ (σS , ρS ).
4.1
Operations, Algorithms, Transition Systems, and Executions
Definition 4.1 (operations). An operation opc is expressed as a mapping σc 7→ (Cc [σc ], Λc [σc ]), where the first component is a quantum operation that is to be applied to qc to change the quantum state and obtain a measurement outcome rc (which may be ⊥ if no measurement was performed), and the second component is a classical operation that looks at the measurement outcome to determine a new classical state of cc , i.e., Cc (σc , rc ) 7→ σc′ . An operation opc is local to c since it directly touches only cc and qc but acts as identity on the complement of c. Generally, it is only physically permissible for a processor π to affect a system by applying operations that are local to π. We typically refer to operations that act only on a single π and its adjacent channel registers as “local”, and expect that a physically permissible distributed algorithm should consist only of such local operations. In contrast, we use the term global operation to emphasize when an operation may not be local to any processor. These operations will be used in specifications, but will not appear in physically permissible algorithms. Events. The definition of an event in a quantum system requires some thought, as quantum operations involving measurement are inherently probabilistic and produce random outcomes. In this work, we take the point of view that an event is something that definitely happens, and the sequence of what events occurs should constitute the total public information available to the adversary. Thus, when an operation corresponding to a measurement is applied, the corresponding event will specify which outcome is obtained. As an example, an operation could be to measure a qubit in the standard basis, while an event could be to measure that qubit in the standard basis and obtain the outcome 1. With this in mind, we formally define the various types of events that may occur in the following definitions. Definition 4.2 (operation application). Suppose we apply operation opc to a component whose classical state is cc , and obtain the measurement outcome rc . This constitutes an application event ec = Λrcc , where Λrcc corresponds to applying Λc [cc ] and obtaining result rc , as defined in Definition 3.1. Definition 4.3 (message sending). We denote the event of π sending the message µ to π ′ by send(π, µ, π ′ ). We call π the sender and π ′ the intended recipient. The quantum part qµ of the message to be sent must be a tensor factor of qπ , i.e., qπ = qa ⊗ qµ . The action of sending consists of relabeling this tensor factor qµ so that it is part of γ rather than π, without changing the global quantum state1 , and setting the classical part cµ to some value σµ . Letting the contents of the channel γ = γ[π → π ′ ] be γ.contents = (µ1 , . . . , µk ), the sending effects the following change: qπ ← qa , cµ ← σµ , and γ.contents ← (µ1 , . . . , µk , µ). Definition 4.4 (message reception). We denote the event of π receiving the message µ from π ′ by receive(π, µ, π ′ ). We call π the recipient and π ′ the sender. The action of reception consists of popping the first message µ from γ = γ[π → π ′ ], and delivering the classical and quantum parts of µ to π. The delivery of the quantum part of µ consists of relabeling the tensor factor qµ so that it becomes part of qπ , without changing the global quantum state. Thus, letting the 1
One could imagine simply physically transporting the qubits corresponding to the qµ part of π out of the processor.
7
contents γ before the reception be γ.contents = (µ1 , . . . , µk ), the reception changes γ’s contents to γ.contents ← (µ2 , . . . , µk ) and the quantum part of π to qπ ← qπ ⊗ qµ1 , and records cµ in cπ . We model the observable interactions of the distributed system with the outside world through an interface of invocations and corresponding responses. Definition 4.5 (invocation and response). The invocation of a an operation op on process π is modeled by the event invoke(π, op). Upon receiving an invocation, a process may eventually respond to the invocation with a response R, modeled by the event respond(π, R). Definition 4.6 (events). The events of a system are the significant happenings in the distributed system. An event can correspond to either (1) an invocation, (2) a response, (3) the application of an operation, (4) the sending of a message, or (5) the reception of a message. Each event e is labeled by the component c (which is a processor in physically permissible executions) at which it occurs, denoted e.label = c. Definition 4.7 (step). A step is a triple (Ψ, e, Ψ′ ), where Ψ is a pre-event state Ψ, and Ψ′ is the post-event state produced by the occurrence of e in state Ψ. A step is valid if the post-event state Ψ′ is the correct state that would result from e occurring at Ψ. Definition 4.8 (transition system). A transition system (Ψ0 , δ) is defined by an initial state Ψ0 , and a transition function, δ : Σ×E ×Σ → {true, false}. We interpret δ(σ, e, σ ′ ) = true to mean that it is possible in a system whose classical state is σ for event e to occur, transitioning the classical state of the system to σ ′ , as well as modifying the quantum state of the system. Abusing notation, we sometimes think of δ as a predicate on steps, i.e. a map Ψ × E × Ψ → {true, false}, where the predicate is true if δ allows the transition between classical states, and the quantum states evolve according to e. We remark that a transition system is defined this way in terms of the classical states to model the fact that in a distributed system, the decision of what event should happen next is only allowed to depend on classical information. In particular, the quantum state cannot be accessed except through measurement. (This is related to the fact that we do not allow for coherent superpositions of execution histories.) Definition 4.9 (execution). An execution is a triple X = (Ψ0 , E, <X ), where Ψ0 is the initial state, E is a set of events, and <X is a total order over the events of the system that sequences the events ⃗ = e1 , e2 , . . .. The execution is finite or infinite depending on the cardinality of E. Given into E an execution, we can uniquely define, inductively, the states Ψi , such that Ψi−1 , ei , Ψi are valid ⃗ = Ψ0 , Ψ1 , . . . the sequence of states of X. We often use ΨX to refer steps. We call the sequence Ψ to the final state of a finite execution. An execution is well formed if messages satisfy at most-once semantics and FIFO, and if each event is compatible with the state just before it takes place. For a given transition function δ, an execution X is an execution of δ if each step (Ψi−1 , ei , Ψi ) is δ-valid, in the sense that δ(Ψi−1 , ei , Ψi ) = true. Since the ordering <X in an execution is a total order, an equivalent way to specify an execution is simply by an initial state and a sequence of events ⃗ X = (Ψ0 , E). We will occasionally use this more compact notation where convenient. It is especially useful for discussing fragments of executions and their concatenations. 8
Definition 4.10. An execution fragment X is an execution that is viewed as a contiguous subsequence of some larger execution Y . Specifically, if Y = (Ψ0 , (e1 , . . . , en )) is an execution, then for any 1 ≤ i ≤ j ≤ n, we can define an associated fragment Xi:j = (Ψi−1 , (ei , . . . ej )). The concatenation of two execution fragments X1 , X2 is defined in the natural way and denoted using the notation X1 :: X2 , and is only well defined if the final state of the first fragment is equal to the initial state of the second fragment. Thus, the execution Y could be written as Y = X1:i :: Xi+1:n for any i ∈ [n]. Definition 4.11 (algorithm). A distributed algorithm A is a collection of algorithms for each individual processor {Aπ }π∈Π . Each Aπ specifies: • a set of possible initial states Ψ0 • A local transition predicate δπ : Σ × E × Σ → {true, false} such that δπ is a function only of the classical states of the components local to π (i.e. π and any adjacent channels). The associated transition system δ with A is simply the predicate _ δ= δπ . π∈Π
5
Computational Causality
For classical distributed systems, Lamport defined the precedence relation of computational causality between events of a distributed system [Lam78]. This relation is defined as the transitive closure of the relation that (1) totally orders events at a given processor chronologically, and (2) orders the event of message reception after the corresponding send event. Lamport showed that since all interactions between different processors of a distributed system are via message transmissions, chronological orderings between events that are unrelated by the computational causal order are essentially spurious. In quantum distributed systems, due to entanglement, interactions between different processors can be instantaneous even in an asynchronous distributed system. In particular, these quantum interactions are transmitted faster than the transmission speeds of the message passing channels. This puts into question the significance of the computational causality relation in quantum distributed systems. In this section, we define the computational causality relation for quantum distributed systems and prove that even as quantum interactions affect processors and in-flight messages at rates faster than the speeds of channel transmission, the essential equivalence of executions that share a causal skeleton is retained in quantum distributed systems. The goal of the computational causality definition below is to capture only the relevant precedence relationships between steps in an execution. Definition 5.1 (Computational causality). Let X = (Ψ0 , E, <X ) be an execution. We can specify the computational causal relation ≺X as the transitive closure of the relation containing the following primitive relationships between events e, e′ ∈ E: 9
A1: If e and e′ are consecutive events on the same process with e <X e′ , then e ≺X e′ . A2: If e and e′ are, respectively, the sending and reception of the same message, then e ≺X e′ . We call ≺X the causal precedence relation of execution X. Notice that if e ≺X e′ , then it always holds that e <X e′ : this is obvious in the first case, and in the second case, a message can only be received after it is sent. Definition 5.2 (equicausal executions). Let X = (Ψ0 , E, <X ) and X ′ = (Ψ0 , E, <X ′ ) be two executions that share an initial state and set of events (but may be ordered differently). We say that X and X ′ are equicausal, denoted X X ′ , if they share a causal precedence relation, i.e., ≺X =≺X ′ . Lemma 5.3. Let X = X− :: X0 :: X+ be an execution with causal precedence relation ≺X , consisting of three fragments X− , X0 , X+ . Let Y0 be an execution fragment that is equicausal with X0 and which has the same final state. Then Y = X− :: Y0 :: X+ is equicausal with X and has the same final state as X. Moreover, if X, Y0 are execution fragments of a transition system δ, then so is Y . Proof. It is clear that Y has the same final state as X, since by assumption Y0 has the same final state as X0 , and this will feed into X+ in both executions to yield the same final state. Next, for the “moreover”: if X and Y0 are both execution fragments of δ, then this means that X− , Y0 , and X+ are all execution fragments of δ, and thus Y is as well, since it’s the concatenation of these execution fragments. Finally, we show the equivalence, ≺X =≺Y . The relative order of events at any given processor is identical in <X and <Y , since the reordering Y0 of X0 respects ≺X . For each message m that is sent at event e and received at event e′ , e <Y e′ since: (1) if e and e′ occur in different fragments or they both occur in the same fragment X− or X+ , then this follows since e <X e′ , and (2) if e and e′ both occur in X0 , then this follows since Y0 is equicausal to X0 . So, by A1 and A2, ≺X ⊆≺Y . The proof that ≺Y ⊆≺X is symmetric. Fact 1. Let H = HA ⊗ HB ⊗ HC . Suppose ΛrAA is a quantum operation on H acting nontrivially only on the A system and ΛrBB is a quantum operation on H acting nontrivially only on the B system. Then ΛrAA ◦ ΛrBB = ΛrBB ◦ ΛrAA . Proof. If ΛrAA acts nontrivially only on the A system, then it can be written as ΛrAA = TArA ⊗ idB ⊗ idC , where TArA is a quantum operation on HA . Likewise, ΛrBB = idA ⊗ TBrB ⊗ idC , where TBrB is a quantum operation on HB . Thus, rA ΛA ◦ ΛrBB = ΛrBB ◦ ΛrAA = TArA ⊗ TBrB ⊗ idC .
Lemma 5.4. Let X = (Ψ, {e1 , e2 } , {e1 <X e2 }) be an execution fragment of some algorithm A, with e1 <X e2 . Suppose e1 ⊀X e2 , and consider the reordered execution X ′ = (Ψ, {e1 , e2 } , {e2 <X ′ e1 }), in in which the two events have been swapped. Then X ′ is a valid execution fragment of A, X ′ X, and X ′ and has the same final state as X. 10
Proof. We are given that e1 ⊀X e2 . From this it follows that e1 and e2 must be on different processors, and moreover, e1 and e2 cannot be the sending and reception of the same message. Let π1 be the processor on which e1 acts and π2 be the processor on which e2 acts. Then the classical state σπ2 of π2 after e1 in execution X is the same as its value in Ψ, and likewise the classical state σπ1 of π1 after e2 in execution X ′ is the same as its value in Ψ. Thus, both transitions in X ′ are valid for A, since they occur in processors with the same classical states as the corresponding transitions in X. This establishes that X ′ is a valid execution fragment of A. Now, to show that X X ′ , observe that in the reordered execution X ′ , it still holds that e2 ⊀X ′ e1 , since the two events are on separate processors and not connected by a message. Moreover, since e1 <X e2 and e2 <X ′ e1 , it holds that e2 ⊀X e1 and e1 ⊀X ′ e2 . Thus, both X and X ′ have an empty causal precedence relation, and thus X X ′ . Finally, we must show that the final states of X and X ′ are equal. By the above, we have shown that e1 and e2 act on totally disjoint classical and quantum registers of the system. If either e1 or e2 is a message send or reception or invocation or response, then the claim is clearly true, since such an event acts trivially on the quantum part of the system, and the classical operations are on different processors and thus commute. Thus, it suffices to consider the case of e1 , e2 both applications of operations. Here too, the conclusion will follow directly from the commutativity of quantum operations on distinct quantum tensor factors, but we will spell out the details for completeness. Any application of an operation consists of the application of a deterministic transition function to the classical states of the classical registers it touches, together with a quantum operation on the quantum registers it touches. Specifically, recall from above that π1 starts in state σπ1 and π2 starts in state σπ2 in the initial state Ψ; let σrest be the classical state of the rest of the system in Ψ, and ρ0 be the quantum state of the system in Ψ. Then in both X and X ′ , the event e1 consist of π1 performing operation (Cπ1 [σπ1 ], Λπ1 [σπ1 ]), and the event e2 consists of π2 performing operation (Cπ2 [σπ2 ], Λπ2 [σπ2 ]). In X and X ′ the respective final states are ΨX = ((Cπ1 (σπ1 , r1 ), Cπ2 (σπ2 , r2 ), {z } | {z } | state of π1
Ψ
X′
state of π2
= ((Cπ1 (σπ1 , r1 ), Cπ2 (σπ2 , r2 ), {z } | {z } | state of π1
state of π2
σrest |{z} state of rest
σrest |{z} state of rest
), Λrπ22 ◦ Λrπ11 (ρ0 )) {z } |
quantum state ), Λrπ11 ◦ Λrπ22 (ρ0 )).
|
{z
}
(5.1) (5.2)
quantum state
The classical parts of ΨX and ΨX ′ agree by inspection. For the quantum parts, we see from Fact 1 that the two quantum operations commute with each other, so the quantum states agree as well. Therefore, ΨX = ΨX ′ as claimed. Lemma 5.5. Let X = (Ψ0 , E, <X ) be a finite execution. Let the total order of the events induced by ⃗ < = (ei )i∈[k] . Suppose ei ∈ E is an event with no successors under ≺X , and ej ∈ E be an <X be E X event such that ei <X ej . Let <X ′ be the relation corresponding to the same total order as <X , except ⃗ < ′ = (e1 , . . . , ei−1 , ei+1 , . . . , ej , ei , ej+1 , . . . , ek ). that e is reordered to occur right after e′ , i.e., E X Let X ′ = (Ψ0 , E, <X ′ ). Then, X and X ′ are equicausal and have the same final state. Proof. The proof is by induction: we repeatedly apply Lemma 5.3 with the middle fragment X0 taken to be ei and the event immediately after it; we show that swapping ei forward preserves causality and the final state using Lemma 5.4. More precisely, let X ℓ be the execution corresponding to the ordering ⃗ < = (e1 , . . . , ei−1 , ei+1 , . . . , eℓ−1 ei , eℓ , . . . ). E Xℓ 11
The inductive hypothesis is that X ℓ is equicausal with X and that X ℓ has the same final state as X. Our base case is X i+1 = X, where both these properties hold. Now, split the execution X ℓ as X ℓ = X− :: X0 :: X+ . |{z} (ei ,eℓ )
By hypothesis, X ℓ X, so in X ℓ , ei has no successors under ≺X ℓ . Therefore, in the middle segment X0 , it holds that ei ⊀ eℓ . Therefore, we can apply Lemma 5.4 to replace X0 with Y corresponding to the order eℓ <Y ei , and then apply Lemma 5.3 to say that the execution X− :: Y :: X+ is equicausal with and has the same final state as X. But this is exactly X ℓ+1 . Definition 5.6 (Computational Lightcones). Let X = (Ψ0 , E, <X ) be an execution. Then for any set of events D ⊆ E, its computational past (resp. future) lightcone LP (D) (resp. LF (D)) is defined as the set of all events in E that precede (resp. succeed) any event in D under the computational causality order: LP (D) = {e ∈ E : ∃d ∈ D, e ≺X d}
(5.3)
LF (D) = {e ∈ E : ∃d ∈ D, d ≺X e}.
(5.4)
Theorem 5.7 (Equicausal executions have equivalent final states). Let X and X ′ be finite execu′ ′ tions with final states ΨX and ΨX , respectively. If X X ′ , then ΨX = ΨX . Proof. The proof is by induction over the number of events in the executions. For the base case, consider X that has zero events. By equicausality, the initial states of X and X ′ are identical, and since they have no events, this is also the final state. The inductive hypothesis is that all equicausal executions with k or fewer events have identical final states. For the induction step, consider equicausal X = (Ψ0 , E, <X ) and X ′ = (Ψ0 , E, <X ′ ) with k + 1 events. Let e be the last event in X. Let <X ′′ be <X ′ , just with e reordered to be the last event, and define X ′′ = (Ψ0 , E, <X ′′ ). By Lemma 5.5, X ′ and X ′ ′ are equicausal and have the same final state. By transitivity of equicausality, X and X ′′ are also equicausal, and by definition, they share the same last event, e. Let Y and Y ′′ be the prefixes of X and X ′′ , respectively, that are obtained by removing the last event. Y and Y ′′ are equicausal and have only k events, thus they share a final state, ΨY . Since, X and X ′′ are both obtained by event e occurring at ΨY , they share a final state ΨX . Since X ′ and X ′′ are known to share a final state, ΨX is also the final state of X ′′ .
6
Specification of Consistent Quantum Global Operations
Quantum distributed algorithms can only execute atomic operations that are process-local. Nevertheless, we would like to implement systems which simulate atomic global operations. Our algorithm, presented in the next section, will be inspired by the global snapshotting algorithm of Chandy and Lamport [CL85]. Snapshots are among the easiest global operations to define, since they only read the state but do not disturb it. By contrast, the analogous quantum global operation, i.e, the quantum snapshot, must measure the quantum state of the entire system, which alters the state of the underlying system. Such an alteration of the underlying system state is not unique 12
to quantum operations: even classical global operations can be state altering. As an example, a security application may wish to atomically encrypt the global state of a system and substitute operations with their homomorphic equivalents. The specification for global operations that we lay out in this section is applicable both to classical and quantum global operations. Definition 6.1 (Decomposable Global Operations). A decomposable global operation G is an operation such that the following hold. 1. The quantum portion ΛG has outcomes ⃗r consisting of a tuple of outcomes indexed by Π∪M, and can be written as a tensor product of operations over the components of the system: ! O O rµ r π Λ⃗G [σ] = ΛrG,π ΛG,µ [σµ ] . [σπ ] ⊗ π∈Π
µ∈M
2. The classical portion C G factors into maps on the individual components of the system in a similar way: ! ! C G (σ, ⃗r) =
× C (σ , r ) × × C (σ , r ) . G π
π
G µ
π
µ
µ
µ∈M
π∈Π
The set of all global operations is denoted G. Our algorithm, presented in the next section, will implement consistent global operations in the case that: (1) the global operations invoked come from the set G of decomposable operations, i.e., they can be expressed as independently operating on separable components of the system, and (2) global operations are not invoked concurrently. The first condition is met by operations such as snapshots, simultaneous global measurement, global encryption, etc. The latter condition is easily satisfied by ensuring that a single leader process takes charge of all global operations. Let A be an algorithm on system S = (Π, Γ), with associated transition function δ. Definition 6.2 (atomic specification). Let A be an algorithm on system S = (Π, Γ), with associated transition function δ. The atomic specification of δ with global operations in the set G is the transition function δb that is defined as follows: b π = Σπ × Tπ , where Tπ = {⊥} ∪ • The classical state space of each process π ∈ Π is Σ {(op, res) | G × (R ∪ {⊥})}. • The valid transitions under δb correspond to: – Base Events: b δ((σ, τb), e, (σ ′ , τb)), where (σ, e, σ ′ ) is a δ-step. – Invocation of Global Operation: b δ((σ, τb), e, (σ, τb′ )), where e is the invocation of a global operation on a process π whose τbπ = ⊥ and τb′ is defined by τbπ′ = τbπ for each π 6= π, and τbπ′ = (G, ⊥). – Atomic Execution of Global Operation: b δ((σ, τb), e, (σ ′ , τb′ )), where e is the atomic execution of the pending global operation G that is recorded in the state τbπ 6= ⊥ of some leader process π (for which τbπ = (G, ⊥)). The final state of this transition is as follows: ∗ For each processor and message, the associated state σ ′ is the result of the classical portion of the global operation G applied to that component. 13
∗ For each processor π, τbπ′ = (G, Rπ ) where Rπ records the outcomes of the global operation G on that processor π and on all messages that are currently in flight to π but have not been received. – Response to a Global Operation: b δ((σ, τb), e, (σ, τb′ )), where e is the event that some processor π responds with Rπ , τbπ = (G, Rπ ) contains a record of Rπ , and τbπ′ is reset to ⊥. For all other processors π ′ 6= π, τbπ′ ′ = τbπ . Remark 6.3. The definition above is general, allowing processes to invoke global operations concurrently. However, like Chandy and Lamport’s snapshot algorithm, in this paper, we will only be interested in algorithms that do not allow for concurrent invocations of global operations (even by different processes).
7
Quantum Global Operations Algorithm
The Quantum Global Operation (QGO) Algorithm à is defined in terms of a base algorithm A, which can be any quantum distributed algorithm, and a decomposable global operation G ∈ G. The algorithm is closely modeled on the Chandy-Lamport algorithm [CL85]—in fact, all the steps are essentially the same. à consists of A augmented in the following ways. Firstly, each component (processor or message) gets an additional classical register τ̃ , which will be used by the algorithm to store information related to the global operation. Specifically, for a processor π, τ̃π .op will store the global operation currently underway, or ∅ if no operation is underway; τ̃π .res contains a response that is under construction; and τ̃π .waitset contains a list of channels that the processor π is waiting to hear from. For each message, τ̃µ will be used to store a marker indicating the global operation G to be performed, and also to temporarily store the outcome of the global operation on the message before it is transferred to τ̃π .res register of the recipient π. à adds to A three procedures, which are described in pseudocode in Algorithm 1. Before describing them in detail, we sketch the action of the algorithm at a high level. When a new global operation G is invoked on a process π, it applies G.π to its own state, records the outcome, and starts an empty record for every incoming channel: these records are meant to hold messages that are currently “in flight”, and π will apply the global operation G.µ to any message µ received hereafter and record the results, until the stopping condition (to be described) is achieved. Process π then broadcasts a “marker message” to all other processes. Each process that receives a marker behaves exactly as the π did, when it receives the marker for the first time. Whenever a process (including the process on which the global operation was invoked) receives subsequent markers, it marks the record of the corresponding channel as complete and stops recording further messages on that channel. Finally, whenever a process has marked all channels as complete, it responds with its complete record, consisting of the outcome it obtained from its own state as well as all recorded message outcomes. For simplicity, we allow each process to respond separately, and do not require the algorithm to aggregate the responses—the algorithm can easily be modified to do this by having processes send their responses back to the invoking process. Now, in more detail, we describe the three added procedures in Ã. • Ã.Invoke: this takes as an argument a description of a global operation G, and is executed by the leader process π when it receives an invocation of the QGO algorithm on G. This initiates the global operation by calling Ã.ProcessNewGlobalOp on π, with the second
14
argument set to ⊥ to indicate that this is an invocation received from outside the system and not caused by a message from another processor in the system. • Ã.ProcessNewGlobalOp: this takes two arguments G, γ indicating the global operation and the channel on which the marker was received (if any). This perform the steps described above: the processor’s local state is acted on with G, and the result is recorded. Records are then opened for each incoming channel by initializing an empty record in τ̃π .res and adding the channel to τ̃π .waitset, and finally, the processor sends out a marker, i.e. a message with τ̃µ = G, to all other processors. • Ã.Receive: this takes one argument µ, which is a message that has been received. We imagine this procedure as “intercepting” all message receptions before they reach the base algorithm A. Upon receipt of the message, the processor decides if it is a marker message, by checking whether τ̃µ is nonempty. If so, and if this is the first time the marker is being received, then the processor calls Ã.ProcessNewGlobalOp on itself. Otherwise, the processor marks the channel γ on which this marker was received as closed, by removing it from τ̃π .waitset, and if all the waitsets are empty, it sends out its response. If this is not a marker message, but it is received on a channel γ that the processor is waiting for, then the global operation is applied to the message and the results are recorded in τ̃π .res.γ. Finally, in all cases, the message is passed on to the base algorithm A. Finally, we remark on the relation of this algorithm to the events of the system. We assume that each procedure in à is executed atomically, meaning that no other events can occur on the processor π while it is executing Invoke, ProcessNewGlobalOp, or Receive. Each procedure execution can correspond to multiple events, and the line numbers in the pseudocode in Algorithm 1 indicate where a new event starts.
8
Analysis of the algorithm
We will now show that the QGO algorithm is a correct implementation of the specification of an atomic global operation given in Definition 6.2. To state our theorem, we will first need to define the notion of a history of an execution. ⃗ Definition 8.1. Let F be some set of events, called the filter. Then for any execution X = (Ψ0 , E), the history of that execution filtered through F is denoted HF (X), and consists of the linear ⃗ that are contained in F . sequence of events in E In the context our algorithm, we will take the filter set F to be the set of events that are either invocations, responses, or operations of the base algorithm A. The idea is that a history consists of the steps in an execution that have observable external effects that we care about. In what follows, we will fix this filter set and suprress the F subscript, merely writing H (X) for the history. The b next definition allows us to compare histories of our algorithm à with the specification δ. ⃗b ⃗ = (e1 , e2 , . . . )) of à and an execution X b = (Ψ, b E Definition 8.2. For an execution X̃ = (Ψ, Ẽ = ⃗b 1 2 b ⃗ (b e , eb , . . . )) of δ, we say that event e ∈ E and eb ∈ E satisfy e ≃ eb if both events are in F , and e and eb correspond to the same action: either (1) e are eb are both invocations on the same processor π of the same global operation G, or (2) e and eb are response events on the same processor that give the same response, or (3) e and eb are base events corresponding to the same step in the algorithm A. 15
Algorithm 1 Pseudocode description of the Quantum Global Operation Algorithm. 1: Ã.Invokeπ (G):
ProcessNewGlobalOpπ (G, ⊥)
2: Ã.ProcessNewGlobalOpπ (G, γ) 3:
4:
τ̃π .op = G τ̃π .res.π ← Executeπ (G.π) τ̃π .waitset ← Γ∗→π if γ 6= ⊥ then τ̃π .res.γ ← ∅ τ̃π .waitset ← τ̃π .waitset \ {γ} µ ← NewMessage[τ̃µ = G] BroadcastΓπ→∗ (µ)
5: Ã.Receiveπ,γ (µ)
6: 7:
if τ̃µ 6= ∅ then if τ̃π = ∅ then ▷ New global operation ProcessNewGlobalOpπ (τ̃µ , γ) else ▷ Ongoing global operation τ̃π .waitset ← (τ̃π .waitset \ {γ}) if τπ .waitset = ∅ then Respond(b τπ .res) τbπ .res ← ∅ τ̃π ← ∅ else ▷ This is a regular message, not a marker if τ̃π 6= ∅ and γ ∈ τ̃π .waitset then ▷ If a global operation is underway τ̃µ ← Executeµ (τ̃π .op.µ) (b τπ .res.γ) .Append(τ̃µ ) τ̃µ ← ∅ A.Receiveπ,γ (µ) ▷ Receive µ according to the original algorithm
We say that
b H (X) ≃ H (X)
⃗b ⃗ = |E|, and for every i, ei ≃ ebi . if |E| Armed with these definitions, we can now state our theorem about the correctness of our algorithm Ã. Theorem 8.3. Consider any finite execution X̃ = (Ψ̃0 , Ẽ, <X̃ ) of à that has no pending global operation and no concurrent invocations of global operations (i.e every invocation happens after all responses from the previous invocation have been given). There is an execution Ỹ of à and a specification execution Yb of δb such that X̃ Ỹ and H (Ỹ ) ≃ H (Yb ). Before we prove the theorem, let us say a few words about why this is the right correctness condition for the algorithm. The basic message of Chandy and Lamport’s original analysis [CL85] is that the global snapshot obtained by their algorithm in execution X is not guaranteed to be equal to the global state at any given point in time in X, but there is still guaranteed to exist an 16
execution Y that has the same starting and final state as X, and such that the global state of Y at some point in time matches the output of the CL algorithm. In our theorem, we show a slightly stronger guarantee: given an execution X̃ of our algorithm, we show that there exists an execution Ỹ that shares not just its initial and final state with X̃ but is causally equivalent to X̃ (recall that by the definition , this implies that Ỹ and X̃ share the same initial state, and by Theorem 5.7, this implies that the final states of Ỹ and X̃ match). The specification execution Yb in our theorem is a means of formalizing the claim that the output of our snapshot algorithm matches the global state of some point in Ỹ , in a way that generalizes to other types of global operations beyond measurement. Proof of Theorem 8.3. Since global operations are not concurrent, we can decompose the execution i execution fragments correspond to the segment X̃ into the following concatenation, where the X̃main between the ith invocation and the last response it generates. 1 2 k X̃ = (Ψ̃0 , X̃ 0 :: X̃main :: X̃ 1 :: X̃main :: · · · :: X̃main :: X̃ k )
Constructing Ỹ by reordering processor operations: Fix an arbitrary i ∈ [1, k], and coni sider X̃main = X̃main with event set Ẽmain . Our strategy will be to reorder X̃main into an alternate execution Ỹmain while preserving its essence. First, we tripartition the events Ẽmain of X̃main into Ẽpre , Ẽop , and Ẽpost , as we describe below. For each processor π ∈ Π, define Ẽmain,π to be the set of events in Ẽmain occurring at processor π. We note that each processor π ∈ Π executes G.π exactly once in Ẽmain ; let eop π ∈ Ẽmain be the event at which it does so. Also, let erπ be the event at which π first received a marker message indicating this global operation—with erπ̃ = ei —and let Ẽπs be the send events corresponding to π broadcasting the marker. By definition of the algorithm, for each π ∈ Π: erπ immediately precedes of the Ẽπs . For the remainder eop π , which immediately precedes the broadcast n o n argument, we identify o ∗ ∗ these events together as eπ . Ẽpre,π ≜ e ∈ Ẽmain,π | e <X̃ eπ , Ẽpost,π ≜ e ∈ Ẽmain,π | e >X̃ e∗π , S S and Ẽop,π ≜ Ẽmain,π \ Ẽpre,π ∪ Ẽpost,π . Finally, define Ẽpre ≜ π∈Π Ẽpre,π , Ẽop ≜ π∈Π Ẽop,π , S and Ẽpost ≜ π∈Π Ẽpost,π . We call these three sets of events, pre-events, op-events, and postevents. Note that the op-events as defined here only include the global operations as applied to the processors, not the operations on the messages (which will be in the post-events). Note that since the events at each processor were partitioned independently, it is possible that post-events at one processor precede pre-events at another processor. Our goal is to re-order the execution fragment X̃main in an execution Ỹmain , such that all pre-events precede all op-events and all op-events precede all post-events in Ỹmain . We do this inductively by eliminating inversions, as is justified by proving the following claim. Claim 8.1. Consider an execution fragment Ũ = Ψ̃pre , Ẽmain , <Ũ of à in which events e1 and e0 are consecutive with e1 <Ũ e0 . If either: (a) e1 ∈ Ẽpost and e0 ∈ Ẽpre , (b) e1 ∈ Ẽpost and e0 ∈ Ẽop , or (c) e1 ∈ Ẽop and e0 ∈ Ẽpre ; then (1) e1 ⊀ e0 , and thus (2) if we define <Ṽ to be identical to <Ũ except that e0 <Ṽ e1 , then Ṽ = Ψ̃pre , Ẽmain , <Ṽ
Ũ and Ṽ is a valid execution fragment of Ã.
Proof. We prove conclusion (1) by contradiction. Let π0 and π1 be the processes at which events e0 and e1 occur, respectively. By the definition of the tripartition of events at each given process π into pre-, atomic-, and post-events, it is clear that π0 6= π1 if any of (a), (b), or (c) holds. Thus, by the definition of ≺ and the fact that these
17
two events e1 and e0 are adjacent in the total ordering <Y , e1 must be the sending of a message m, which is received at e0 . We conclude the proof in cases based on which hypothesis holds. • Case (a): e1 ∈ Ẽpost and e0 ∈ Ẽpre : All marker send events are in Ẽop , thus the message sent in e1 must be a non-marker message. By the definition of post-events, e∗π1 <Ũ e1 , and by the definition of pre-events, e0 <Ũ e∗π0 . However, by the FIFO property of the channel γ[π1 → π0 ], any message sent by π1 after e∗π1 must be received by π0 after e∗π0 —since e∗π0 corresponds with π0 ’s first receipt of the marker. Consequently, we conclude that e∗π0 <Ũ e0 , which is a contradiction. • Case (b) e1 ∈ Ẽpost and e0 ∈ Ẽop : The only receive events in Ẽop are of the marker. Thus e1 must be the sending of the marker by π1 to π0 and e0 must be its reception. However, markers are only sent in events in Ẽop , which is a contradiction. • Case (c) e1 ∈ Ẽop and e0 ∈ Ẽpre : The only send events in Ẽop are of the marker. However, by the definition of pre-events, π0 cannot receive the marker before e∗π0 —since that event is the first receipt of the marker by π0 . Thus, we reach a contradiction. That finishes the proof of (1). Since e1 ⊀ e0 , conclusion (2) follows by Lemma 5.4. Since X̃main is a finite run, we can induct on the claim to remove all inversions and conclude that there is a re-ordering of Ỹmain of X̃main , such that Ỹmain X̃main and all pre-events precede all op-events and all op-events precede all post-events in Ỹmain . In other words, there exist execution fragments Ỹpre , Ỹop , Ỹpost consisting solely of events of the appropriate type, such that Ỹmain = Ỹpre :: Ỹop :: Ỹpost . i i Thus, by repeated application of Lemma 5.3 we can substitute each X̃main with Ỹmain to get 1 2 k Ỹ = (Ψ̃0 , X̃ 0 :: Ỹmain :: X̃ 1 :: Ỹmain :: · · · :: Ỹmain :: X̃ k ) X̃.
Constructing Z̃ by reordering message operations: i i i i Ỹmain = Ỹpre :: Ỹop :: Ỹpost i :: Ỹ i i pre be We are going to replace the fragment Ỹop post by a reordered fragment Z̃op,post . Let Ψ the initial state of Ỹop , and let i i i Ỹop,post = Ỹop :: Ỹpost .
⃗ be the sequence of i ⃗ be the sequence of all messages µ with a eop Let M µ event in Ỹmain . Let ẼM ⃗ ⃗ op ⃗ ⃗ e events in order of M . Let Ẽ be the prefix of the first j events in M . Let Ẽ be the µ
post,−j
⃗ ,j M
⃗ sequence of of events in Ẽpost without the events of Ẽ ⃗ ,j . Then define M ⃗ :: Ẽ ⃗ ⃗ i Z̃op,post = (Ψop , Ẽ op ⃗ ,|M ⃗ | :: Ẽpost,−|M ⃗ | ). M i i The following claim will show that Z̃op,post behaves as Ỹop,post .
18
⃗ :: Ẽ ⃗ ⃗ i i Claim 8.2. Let W̃j = (Ψop , Ẽ op ⃗ ,j :: Ẽpost,−j ), and note that W̃0 = Ỹop,post and W̃|M ⃗ | = Z̃op,post . M ⃗ |], W̃j is a well-formed execution with the same final state as Ỹ i For each j ∈ [0, |M . op,post
i Proof. The base case of j = 0 follows, since W̃0 = Ỹop,post . The inductive hypothesis is that the ⃗ claim is true for some j ∈ [0, |M |). ⃗ . The event just preceding eop For the induction step, let µ be the (j + 1)st message of M µ in W̃j is the reception erµ of µ by its receiver process π. Since applying G.µ to µ does not affect τµ , and the reception event acts as identity qµ , the net effect of the reception and eop µ is equivalent to the application of G.γ on µ occurring before the reception, while the message is still in flight. Let op r W̃j′ be the resultant execution obtained by swapping the events eop µ and eµ , so that the event eµ occurs on the message while it is in flight, immediately before it is received at erµ . The execution W̃j′ , thus, has the same final state as W̃j . Note that it is not true that W̃j′ is equicausal to W̃j : this ′ is because we are inverting causally related events erµ ≺W̃j eop µ . Nevertheless, the fact that W̃j and
W̃j have the same final state indicates that this causal relation is somewhat “illusory.” ⃗ . Each such swap Now, we take W̃ ′ and further swap eop backwards until it is adjacent to Ẽ µ
j
M,j
can be done equicausally by using Lemma 5.4, since eop µ acts only the message in flight and thus has no causal relationship to the event it is being swapped with. The final execution reached after performing these swaps is precisely W̃j+1 . This shows that W̃j+1 W̃j′ , and thus, by Theorem 5.7, W̃j+1 has the same final state as W̃j′ and therefore W̃j . i i :: Z̃ i i i ). Thus, Z̃main = Ỹpre ) = H (Ỹop,post We remark that by construction H (Z̃op,post op,post is a i well-formed execution with the same final state as Ỹmain . i i Inductively replacing each Ỹmain with the corresponding Z̃main , we get 1 2 k Z̃ = (Ψ̃0 , X̃ 0 :: Z̃main :: X̃ 1 :: Z̃main :: · · · :: Z̃main :: X̃ k ),
and note that H (Z̃) = H (Ỹ ). Constructing specification fragment Yb : We now construct a specification execution fragment i Yb with H (Yb ) ≃ H (Z̃). The key idea is to exploit the fact that we can write each Z̃op,post as a concatenation i i i Z̃op,post = Z̃op,M :: Z̃post , i ∪ Ẽ i and Z̃ i i where Z̃op,M contains exactly the events in Ẽop post contains exactly the events in ⃗ M Ẽ i . We use this to construct Yb by (1) replacing all the events in each Z̃ i block by a op,M
⃗| post,−|M
single event that atomically applies the global operation, and (2) omitting all other events that are not contained in our filter set F (i.e. events associated with the “paraphernalia” of the algorithm, such as receiving marker messages). We now spell this out in slightly more detail. We want to construct a Yb that is an execution for δb while having the same history as Z̃. Recall that the history is simply the temporal sequence of events that lie in the filter set F : in our case, events apart from the G operations and associated paraphernalia in the algorithm (e.g. the marker messages). In order to preserve this history, we will construct Yb by going through the events in Z̃ in temporal order and producing corresponding events in Yb . Each event that passes the filter F corresponds to either a transition from the underlying algorithm A, or an invocation or response event. All of these have straightforward corresponding b So for every such event, we simply append the corresponding event to Yb . transition in δ.
19
The case of events that do not pass the filter F is a bit more complicated, and it is here that we exploit the structure of Z̃. Recall that in Z̃, for each invocation i, all G operations on all processors i and channels are grouped together into a block Z̃op,M . We will replace this entire block with b the corresponding transition δ implementing the global operation G atomically. Apart from these events, the only other events in Z̃ that do not pass the filter F are the events where a processor records a message received along a channel before the marker message, and the events where the processor receives a marker message. We simply drop these events from the definition of Yb . It is clear to see that this construction produces a Yb whose history matches that of Z̃—this b follows from the linear order in which we process events. To show that Yb is a valid execution for δ, we argue that each transition in Yb is valid. This follows because the atomic global transition in δb i accurately simulates the events in Z̃op,M , while the events that we omit have no effect on the state outside of τ̃ .
9
Final Remarks
The basic take-away message we see from the proof of Theorem 8.3 is that classical causality-based arguments are effective for analyzing quantum distributed systems. However, a reader familiar with Chandy and Lamport’s original analysis might ask why our proof is longer and more involved than theirs. Interestingly, the answer to this is because of an essentially classical phenomenon which the quantum setting surfaces to our attention. Essentially, the main additional complication in our argument that is not present in [CL85] is the reordering of the global operations on messages, which is performed in Claim 8.2. This step is actually implicit in [CL85], but passes unnoticed because the classical recording operation does not disturb the state, so it can be freely imagined to have occurred at any point in the message’s history. In contrast, a general classical or quantum global operation will disturb the state of the message, so its ordering relative to other events is consequential. Moreover, the reason why special reasoning had to be performed for message operations is because of the “syntactic” nature of the definition of computational causality, which leads to an apparent causal relation between the global operation on the message in flight and the reception of the message. As remarked in the proof of Claim 8.2, this causal relation is illusory because the reception event does not touch the state of the message. We conjecture that a more “semantic” notion of causality could automatically recognize this and simplify this argument. Another point that deserves further study is the interpretation of our theorem in terms of probabilities, an issue that once again is relevant classically but unavoidable in the quantum setting. In our theorem, the executions X̃ and Ỹ are equicausal, which by Theorem 5.7 means that X̃ and Ỹ have the same final state. Because of our use of subnormalized density matrices, this means that in both X̃ and Ỹ , the probability that all measurements performed along the way produced the outcomes appearing in the execution must be equal. It is tempting to conclude from this that the distribution over responses produced by running à matches the distribution produced by running the specification δb in some sense. However, this does not follow: suppose we fix an algorithm for the adversarial scheduler and then run Ã. Each possible sequence of measurement outcomes ⃗r from this experiment corresponds to a different execution X̃⃗r , and all our theorem says is that each one b of these executions can be mapped to an equicausal execution Ỹ⃗r , and an associated δ-execution Yb⃗r . However, it is not clear that all these executions correspond to a meaningful experiment in which δb is run in interaction with a fixed adversary. We leave this question open for future work: perhaps ideas from the literature on linearizability and randomized algorithms [GHW11] will be relevant to solving it. 20
References [AG97]
Martín Abadi and Andrew D. Gordon. A calculus for cryptographic protocols: The spi calculus. In Proceedings of the 4th ACM Conference on Computer and Communications Security, CCS ’97, pages 36–47, New York, NY, USA, 1997. ACM.
[BBCR+ 25] Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d’Amore, Massimo Equi, François Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, MarcOlivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren. Distributed quantum advantage for local problems. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC ’25, page 451–462, New York, NY, USA, 2025. Association for Computing Machinery. [Bel64]
John S Bell. On the Einstein Podolsky Rosen paradox. Physics Physique Fizika, 1(3):195, 1964.
[BGK18]
Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308–311, 2018.
[Bru14]
Časlav Brukner. Quantum causality. Nature Physics, 10(4):259–263, 2014.
[CL85]
K. Mani Chandy and Leslie Lamport. Distributed snapshots: Determining global states of distributed systems. ACM Trans. Comput. Syst., 3(1):63–75, 1985.
[DMP25]
Fabien Dufoulon, Frédéric Magniez, and Gopal Pandurangan. Quantum communication advantage for leader election and agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, page 230–240, New York, NY, USA, 2025. Association for Computing Machinery.
[DP08]
Vasil S. Denchev and Gopal Pandurangan. Distributed quantum computing: a new frontier in distributed systems or science fiction? SIGACT News, 39(3):77–95, September 2008.
[Ebe78]
Philip Herbert Eberhard. Bell’s theorem and the different concepts of locality. Il Nuovo Cimento B (1971-1996), 46(2):392–419, 1978.
[EPR35]
Albert Einstein, Boris Podolsky, and Nathan Rosen. Can quantum-mechanical description of physical reality be considered complete? Physical Review, 47(10):777, 1935.
[ER89]
Phillippe H Eberhard and Ronald R Ross. Quantum field theory cannot provide faster-than-light communication. Foundations of Physics Letters, 2(2):127–149, 1989.
[GG14]
Seth Gilbert and Wojciech M. Golab. Making sense of relativistic distributed systems. In Fabian Kuhn, editor, Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings, volume 8784 of Lecture Notes in Computer Science, pages 361–375. Springer, 2014.
[GHW11]
Wojciech M. Golab, Lisa Higham, and Philipp Woelfel. Linearizable implementations do not suffice for randomized distributed computation. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 373–382. ACM, 2011. 21
[Jay25]
Siddhartha Visveswara Jayanti. On interplanetary and relativistic distributed computing. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, page 192–202, New York, NY, USA, 2025. Association for Computing Machinery.
[KBD+ 21]
Sumeet Khatri, Anthony J Brady, Renée A Desporte, Manon P Bart, and Jonathan P Dowling. Spooky action at a global distance: analysis of space-based entanglement distribution for the quantum internet. npj Quantum Information, 7(1):4, 2021.
[KSV02]
Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation. Number 47. American Mathematical Soc., 2002.
[Lam]
Leslie Lamport. My writings. https://lamport.azurewebsites.net/pubs/pubs. html#chandy. Accessed: 2026-02-16.
[Lam78]
Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Commun. ACM, 21(7):558–565, 1978.
[Liu24]
Yunchao Liu. Shallow Quantum Circuits: Algorithms, Complexity, and Fault Tolerance. PhD thesis, UC Berkeley, 2024.
[NC10]
Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge University Press, 2010.
[RXY+ 17]
Ji-Gang Ren, Ping Xu, Hai-Lin Yong, Liang Zhang, Sheng-Kai Liao, Juan Yin, WeiYue Liu, Wen-Qi Cai, Meng Yang, Li Li, et al. Ground-to-satellite quantum teleportation. Nature, 549(7670):70–73, 2017.
[WEH18]
Stephanie Wehner, David Elkouss, and Ronald Hanson. Quantum internet: A vision for the road ahead. Science, 362(6412):eaam9288, 2018.
22