⚛️ quantum physics

DisQ: A Model of Distributed Quantum Processors (Extended Version)

This paper introduces DisQ, the first formal model for distributed quantum processors, which combines Chemical Abstract Machine and Markov Decision Process concepts to enable the analysis of distributed quantum programs and verify the equivalence between sequential algorithms and their distributed versions via simulation.

Original authors: Le Chang, Saitej Yavvari, Rance Cleaveland, Samik Basu, Runzhou Tao, Liyi Li

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Le Chang, Saitej Yavvari, Rance Cleaveland, Samik Basu, Runzhou Tao, Liyi Li

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, incredibly complex puzzle. In the world of quantum computing, this puzzle is so big that a single computer (even a super-fast quantum one) doesn't have enough pieces to finish it. Current quantum computers are like small, isolated islands; they can hold about 50 puzzle pieces (qubits) in a tightly connected group, but the big algorithms we need (like breaking codes or simulating molecules) require thousands of pieces all working together.

The Problem:
We can't just build one giant island with thousands of pieces yet; the physics just doesn't allow it. So, scientists are trying to build a "quantum archipelago"—connecting many small islands (processors) together with bridges (quantum networks) so they can share their pieces.

The Challenge:
Writing a program for this archipelago is a nightmare. It's like trying to write a recipe where the ingredients are scattered across different kitchens, and you have to teleport them between ovens without losing their flavor. If you try to copy an ingredient to send it, the laws of physics say you destroy the original (the "No-Cloning" rule). Plus, because quantum mechanics is weird, sometimes things happen randomly, and sometimes they happen in a specific order. It's a chaotic mix of "maybe this happens" and "maybe that happens."

The Solution: DisQ
The authors of this paper created DisQ, which is essentially a new language and a rulebook for building these distributed quantum programs. Think of it as a universal translator and a project manager rolled into one.

Here is how DisQ works, using some everyday analogies:

1. The "Chemical Kitchen" (The Membranes)

Imagine each quantum processor (QPU) is a separate kitchen in a restaurant.

The Membrane: In DisQ, each kitchen is a "membrane." Inside the kitchen, chefs (processes) can work together or get in each other's way.
The Airlock: If a chef needs to pass a hot dish to the next kitchen, they can't just walk through the wall. They have to go through an "airlock." This represents the quantum network. You can't just copy the dish; you have to physically move the plate (the qubit) from one kitchen to another.

2. The "Teleportation Courier"

In the real world, if you want to send a secret letter to a friend in another city, you mail it. In the quantum world, you can't mail a qubit because you can't copy it.

DisQ's Magic: DisQ treats Quantum Teleportation like a special courier service. You don't send the qubit itself; you send the instructions to rebuild the qubit at the destination, using a pre-shared "magic link" (entanglement) between the two kitchens. DisQ makes sure the language understands that once the qubit leaves Kitchen A, it no longer exists there. It's a "one-way ticket."

3. The "Traffic Cop" (The Type System)

Because quantum rules are strict (you can't clone, you can't touch two things at once if they are linked), it's easy to write a program that crashes the universe.

The Guardrails: DisQ has a built-in "Traffic Cop" (a type system). Before you run your program, the Cop checks your map. It asks: "Do you have a qubit here? Are you trying to use it in two places at once? Did you already send it away?" If you try to break the rules (like cloning a qubit), the Cop stops you before you even start. This ensures the program is physically possible.

4. The "Simulator" (The Proof)

The biggest fear for a programmer is: "I split my program across five computers. Did I break the logic? Is the result the same as if I ran it on one giant computer?"

The Double-Check: DisQ includes a special "Simulator." It takes your complex, split-up program and runs it side-by-side with the original, simple version. It doesn't just check the final answer; it checks the path taken.
The Analogy: Imagine you have a recipe for a cake. The original recipe says "Mix, bake, frost." Your new distributed recipe says "Mix in Kitchen A, send batter to Kitchen B, bake in Kitchen C, send to Kitchen D to frost." The DisQ simulator acts like a food critic who tastes the cake from both methods to prove they are identical, even though the steps were different. It handles the randomness (probabilities) by checking if the odds of getting a good cake are the same in both versions.

Why This Matters

This paper is a blueprint. Before DisQ, trying to write software for a network of quantum computers was like trying to build a skyscraper without blueprints, using only intuition. DisQ provides the blueprints, the safety codes, and the inspection tools.

It allows scientists to take a program designed for a single, perfect quantum computer and automatically "translate" it into a version that can run across a network of smaller, imperfect computers. This is the key to unlocking the next generation of quantum computing, turning a dream of a "quantum internet" into a reality we can actually program.

1. Problem Statement

Current Near-Term Intermediate-Scale Quantum (NISQ) devices face severe scalability limitations. While quantum algorithms like Shor's require thousands of entangled qubits, existing single-location quantum computers can only sustain roughly 50 coherent qubits. The primary bottleneck is the inability to maintain large-scale entanglement within a single hardware unit.

Distributed Quantum Computing (DQC) has emerged as a solution, connecting multiple Quantum Processing Units (QPUs) via photonic links (quantum networking) to share entanglement. However, developing and verifying distributed quantum programs presents three major challenges:

Equivalence Verification: There is a lack of formal mechanisms to prove that a distributed version of a sequential quantum program is equivalent to the original.
Complexity of Behavior: Distributed systems exhibit both nondeterminism (due to scheduling across different QPUs) and probabilistic behavior (due to quantum measurements and local parallelism).
Resource Constraints: Quantum resources are constrained by the no-cloning theorem and locality; qubits cannot be copied, and operations must respect physical location and entanglement boundaries.

Existing quantum process algebras often diverge from classical foundations, making it difficult to leverage established classical verification tools.

2. Methodology: The DisQ Framework

The authors propose DisQ, a formal model and programming language framework designed to model DQC systems. DisQ integrates concepts from the Chemical Abstract Machine (CHAM) and Markov Decision Processes (MDP) to create a unified framework for reasoning about distributed quantum behaviors.

Core Components:

Membrane-Based Architecture:
- DisQ models QPUs as membranes (local clusters of qubits).
- Processes within a membrane interact concurrently.
- Airlocks allow processes to temporarily isolate themselves to synchronize with processes in other membranes, modeling quantum communication (teleportation).
Semantic Model (MDP View):
- DisQ treats the execution of distributed programs as a Markov Decision Process.
- Nondeterminism: Arises from the choice of which membrane (QPU) executes a step next.
- Probabilism: Arises from quantum measurements and the probabilistic selection of processes within a membrane (single-location parallelism).
- This separation allows the use of classical probabilistic verification techniques without conflating the two phenomena.
Syntax and Semantics:
- The language uses a process-algebraic style with explicit locations ( $l, r, u$ ).
- It supports quantum channels (created via $\partial c(n)$ ) and quantum teleportation as the primary mechanism for moving qubit ownership between membranes.
- Operational Semantics: Defined via a labeled transition system where transitions are labeled with location and probability (e.g., $l.r.1$ for inter-membrane communication, $l.1/2$ for intra-membrane probabilistic choice).
Type System and Loci:
- DisQ introduces a locus structure ( $\langle \kappa \rangle_l$ ) to track sets of potentially entangled qubits and their locations.
- A location-aware type system enforces:
  - No-Cloning: Ensures a qubit is moved, not copied.
  - Resource Locality: Ensures operations only access qubits within the same membrane or via valid channels.
  - Channel Well-formedness: Ensures channels are initialized before use and used exactly once.
- The type system guides equivalence rewrites, allowing the system to rearrange qubit positions in the state representation to match operational requirements without changing the underlying physics.

3. Key Contributions

First Formal Model of DQC: DisQ is the first formal calculus that explicitly models distributed quantum processors with explicit locations, separating quantum operation probabilities from communication nondeterminism.
MDP-Based Semantics: By modeling the system as an MDP, DisQ enables the application of classical probabilistic simulation techniques to verify quantum programs, bridging the gap between quantum and classical verification infrastructure.
Observable Simulation Relation: The authors developed a new observational simulation relation. Unlike traditional bisimulation, this relation:
- Groups internal communication steps as $\tau$ -moves (silent steps).
- Matches the probability mass of reaching corresponding configurations at user-defined synchronization points.
- Allows for the verification of refinement (i.e., proving a distributed implementation correctly refines a sequential specification).
Type-Guided State Rewriting: The framework includes a mechanism to rewrite quantum states based on type equivalence, ensuring that operations can be applied correctly even when entangled qubits are distributed across different membranes.
Prototype Implementation: The authors implemented a DisQ interpreter in Java and a simulation checker to validate the theory.

4. Results and Evaluation

The framework was evaluated on several representative case studies, demonstrating its ability to model complex distributed algorithms and verify their equivalence to sequential versions:

Distributed Shor's Algorithm: The authors successfully distributed the order-finding subroutine across three QPUs. They proved that the distributed version simulates the sequential version, handling the complexity of entanglement swapping and teleportation.
Quantum Teleportation: Verified that quantum teleportation correctly refines an abstract quantum channel, preserving entanglement information during the transfer.
Parallel Adders: Modeled parallel quantum addition circuits, demonstrating how DisQ handles probabilistic interleaving of processes within a single membrane.
Distributed QFT Adder & Hidden Subgroup: Successfully modeled algorithms involving repeat-until-success schemes (probabilistic loops) and Quantum Fourier Transforms across distributed nodes.
Verification: The authors used the Coq proof assistant and their custom Java simulation checker to automatically validate the simulation relations (e.g., $Dis\text{-}Shor \sqsubseteq Shor$ ). The checker successfully handled the probabilistic branching and nondeterministic scheduling inherent in these distributed systems.

5. Significance

Bridging Theory and Practice: DisQ provides a practical pathway for developing distributed quantum programs on near-term hardware, addressing the critical scalability gap of NISQ devices.
Leveraging Classical Infrastructure: By staying close to classical non-deterministic bi-simulation and MDPs, DisQ allows researchers to reuse mature classical verification tools (like model checkers) for quantum systems, rather than building entirely new, unproven quantum verification theories from scratch.
Formal Guarantees: It offers the first rigorous method to ensure that distributing a quantum algorithm (splitting it across multiple machines) does not alter its logical correctness or probabilistic outcomes.
Resource Management: The explicit handling of the no-cloning theorem and locality constraints ensures that generated distributed programs are physically realizable on actual quantum hardware.

In summary, DisQ establishes a foundational theoretical and practical framework for the next generation of quantum computing, enabling the systematic transformation of sequential quantum algorithms into distributed realizations with formal guarantees of correctness.