Distributed measurement-based quantum computation

Danos, Vincent, Ellie D’Hondt, Elham Kashefi, Prakash Panangaden

Abstract

Measurement-based quantum computation (MBQC) offers a unique paradigm where computation is driven by local measurements on a global entangled state. As quantum systems scale toward distributed networks, a formal language is required to describe the interactions between independent agents. This paper introduces an agent-based "assembly language" for distributed MBQC, modeling local actions within a global quantum context. By defining operational semantics through probabilistic transition systems and establishing a notion of bisimilarity, we demonstrate that complex distributed protocols, such as quantum teleportation, are functionally equivalent to direct quantum channels.

Introduction

The transition from theoretical quantum circuits to physical, networked implementations necessitates a shift in how we model quantum computation. While the standard circuit model focuses on unitary gates, Measurement-Based Quantum Computation (MBQC) utilizes a highly entangled resource state (such as a cluster state) and proceeds via a sequence of local measurements and classical feed-forward corrections. Because MBQC inherently relies on local operations and classical communication, it is naturally suited for distributed environments. However, a formal mathematical framework to describe these macroscopic, multi-party interactions has been lacking.

This work addresses this gap by extending the Measurement Calculus (MC) into a distributed, multi-agent framework. We treat participants as independent agents acting on a shared entangled state, providing a rigorous "assembly language" for distributed quantum protocols.

The Distributed MBQC Model

Our framework adopts an agent-based view where each participant in the network is defined by a sequence of local events. These events include:

  • Local Measurement Patterns: The core computational steps derived from the Measurement Calculus.
  • Classical Communication: Sending and receiving classical bits to coordinate measurement bases and corrections.
  • Quantum Communication: The physical transfer of qubits between agents.

A central challenge in modeling distributed quantum systems is the non-local nature of entanglement. To address this, we model the network's quantum state as a "global memory." While agents perform actions locally, their effects are reflected in this shared global structure, mirroring how classical agent systems interact with shared memory.

Formal Semantics and Bisimilarity

To reason about the behavior of these systems, we define two types of semantics:

  1. Operational Semantics: A step-by-step probabilistic transition system that models the evolution of the network as agents perform actions and communicate.
  2. Denotational Semantics: A high-level mapping that relates classical inputs to quantum operations and outputs, abstracting away the specific timing of internal events.

The core of our equivalence proof relies on bisimilarity. Two quantum networks are considered bisimilar if they produce identical observable behaviors—specifically, the same outputs and probability distributions for any given input—regardless of their internal complexity or the number of intermediate steps.

Key Insights: Schedule Independence and Teleportation

A critical finding of this framework is schedule independence. We prove that the specific order in which independent agents perform local operations does not alter the final quantum outcome. This result is vital for asynchronous distributed systems, ensuring that "race conditions" in classical communication do not corrupt the underlying quantum logic.

Furthermore, we utilize this framework to provide a formal proof of the equivalence of quantum teleportation. By applying our notion of bisimilarity, we demonstrate that a teleportation protocol—involving Bell measurements, classical message passing, and Pauli corrections—is mathematically identical to a direct quantum wire (an identity channel). While this equivalence is a cornerstone of quantum information theory, our framework provides the formal logic to prove it within a complex, distributed context.

Conclusion and Future Work

This research establishes a robust foundation for describing distributed MBQC. By treating the system as a collection of agents acting on a global entangled state, we provide the tools necessary to prove the compositionality and equivalence of quantum protocols.

As an "assembly language," this model focuses on description rather than automated verification. Future work will involve developing higher-level verification techniques to ensure programs are free of deadlocks and exploring more complex protocols, such as entanglement swapping and leader election, within this formal logic.

Summary updated

Abstract

We develop a formal model for distributed measurement-based quantum computations, adopting an agent-based view, such that computations are described locally where possible. Because the network quantum state is in general entangled, we need to model it as a global structure, reminiscent of global memory in classical agent systems. Local quantum computations are described as measurement patterns. Since measurement-based quantum computation is inherently distributed, this allows us to extend naturally several concepts of the measurement calculus, a formal model for such computations. Our goal is to define an assembly language, i.e. we assume that computations are well-defined and we do not concern ourselves with verification techniques. The operational semantics for systems of agents is given by a probabilistic transition system, and we define operational equivalence in a way that it corresponds to the notion of bisimilarity. With this in place, we prove that teleportation is bisimilar to a direct quantum channel, and this also within the context of larger networks.
BibTeX
@article{vincent2005distributed,
  author = {Danos, Vincent and Ellie D’Hondt and Elham Kashefi and Prakash Panangaden},
  title = {{Distributed measurement-based quantum computation}},
  journal = {QPL},
  year = {2005},
  doi = {10.1016/j.entcs.2006.12.012},
}
Figure