Distributed Quantum Computing (DQC) offers a promising path toward scalable quantum computation by connecting multiple quantum processors through quantum and classical communication channels, helping overcome the limited qubit counts and noise of individual Noisy Intermediate-Scale Quantum (NISQ) devices. Beyond scaling, DQC has been shown to provide a provable computational advantage: Balliu et al. (STOC 2025) proved that certain locally checkable labeling problems require Ω(Δ) rounds classically in the LOCAL model, where Δ is the maximum degree of the graph, yet only a single round in the quantum-LOCAL model. This separation is unconditional, but a practical demonstration on real hardware had not previously been carried out. This thesis addresses that gap through two contributions. First, it covers the background needed to understand distributed quantum computing: quantum gates, entanglement and the GHZ state, classical distributed models such as LOCAL and CONGEST, locally checkable labeling problems, and the operating principles of superconducting quantum computers, including the practical challenges of connecting them across distances. Second, it presents a practical demonstration of the iterated GHZ game, the locally checkable labeling problem underlying the separation above. The quantum-LOCAL winning strategy is proven correct and implemented as a quantum circuit, executed on IQM’s superconducting quantum computers Garnet and Emerald via the IQM Resonance cloud service. Since physically distributed superconducting hardware is not yet publicly available, a chip-partitioning scheme is used, treating regions of a single chip as independent quantum nodes to emulate a distributed network. The results show that Round 1 games consistently exceed the 75% classical winning bound of the GHZ game, confirming that this win-rate quantum advantage is detectable under NISQ-era noise. In a deeper 3-round demonstration, performance degrades in later rounds, suggesting that demonstrating the advantage consistently across deeper circuits will require longer coherence times, higher gate fidelities, or error correction.
Distributed Quantum Computing (DQC) offers a promising path toward scalable quantum computation by connecting multiple quantum processors through quantum and classical communication channels, helping overcome the limited qubit counts and noise of individual Noisy Intermediate-Scale Quantum (NISQ) devices. Beyond scaling, DQC has been shown to provide a provable computational advantage: Balliu et al. (STOC 2025) proved that certain locally checkable labeling problems require Ω(Δ) rounds classically in the LOCAL model, where Δ is the maximum degree of the graph, yet only a single round in the quantum-LOCAL model. This separation is unconditional, but a practical demonstration on real hardware had not previously been carried out. This thesis addresses that gap through two contributions. First, it covers the background needed to understand distributed quantum computing: quantum gates, entanglement and the GHZ state, classical distributed models such as LOCAL and CONGEST, locally checkable labeling problems, and the operating principles of superconducting quantum computers, including the practical challenges of connecting them across distances. Second, it presents a practical demonstration of the iterated GHZ game, the locally checkable labeling problem underlying the separation above. The quantum-LOCAL winning strategy is proven correct and implemented as a quantum circuit, executed on IQM’s superconducting quantum computers Garnet and Emerald via the IQM Resonance cloud service. Since physically distributed superconducting hardware is not yet publicly available, a chip-partitioning scheme is used, treating regions of a single chip as independent quantum nodes to emulate a distributed network. The results show that Round 1 games consistently exceed the 75% classical winning bound of the GHZ game, confirming that this win-rate quantum advantage is detectable under NISQ-era noise. In a deeper 3-round demonstration, performance degrades in later rounds, suggesting that demonstrating the advantage consistently across deeper circuits will require longer coherence times, higher gate fidelities, or error correction.
We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph problem with an inherently global definition [Le Gall et al. 2019]. We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm. We show that in graphs of maximum degree Δ, any classical (deterministic or randomized) LOCAL model algorithm will require Ω(Δ) rounds to solve the iterated GHZ problem, while the problem can be solved in 1 round in quantum-LOCAL. We use the round elimination technique to prove that the iterated GHZ problem requires Ω(Δ) rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner.
Quantum computers in the noisy intermediate-scale quantum (NISQ) era are constrained by limited qubit counts, imperfect gate fidelities, and short coherence times. NISQ-era computers often have too few qubits to run many algorithms, and those that do run often have limited quantum advantage. Distributed quantum computing (DQC) is a promising approach to overcome this, where multiple quantum processors are interconnected through shared entanglement. This work serves as a system overview of an entanglement distribution system. We achieve this by examining a zero-added loss multiplexing (ZALM) entanglement generation source, simulating multi-hop, repeater-less networks, and various routing algorithms to distribute entanglement, and real-hardware quantum experiments that reconstruct entanglement links of degraded fidelity and simulate classical-communication delay. Network simulations evaluate routing and spectrum-allocation algorithms under entanglement-generation-imposed rate constraints, by evaluating both fairness and throughput across network sizes and topologies. We identify two polynomial-time approximation algorithms that perform well, or better than others under these metrics. Using both simulations and quantum hardware, we evaluate how degraded entanglement and communication latency affect teleportation-based distributed multipartite-entanglement-state construction. The results reveal the coupled influence of source rate, routing efficiency, fidelity, and classical delay on networked entanglement distribution and DQC performance, providing a reproducible framework for both experimental and simulated studies of near-term DQC.
We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prior work, such a separation was known only for an artificial graph problem with an inherently global definition [Le Gall et al. 2019]. We present a problem that we call iterated GHZ, which is defined using only local constraints. Formally, it is a family of locally checkable labeling problems [Naor and Stockmeyer 1995]; in particular, solutions can be verified with a constant-round distributed algorithm. We show that in graphs of maximum degree Δ, any classical (deterministic or randomized) LOCAL model algorithm will require Ω(Δ) rounds to solve the iterated GHZ problem, while the problem can be solved in 1 round in quantum-LOCAL. We use the round elimination technique to prove that the iterated GHZ problem requires Ω(Δ) rounds for classical algorithms. This is the first work that shows that round elimination is indeed able to separate the two models, and this also demonstrates that round elimination cannot be used to prove lower bounds for quantum-LOCAL. To apply round elimination, we introduce a new technique that allows us to discover appropriate problem relaxations in a mechanical way; it turns out that this new technique extends beyond the scope of the iterated GHZ problem and can be used to e.g. reproduce prior results on maximal matchings [FOCS 2019, PODC 2020] in a systematic manner.
Quantum computers offer computational advantages for specific problems over classical systems [8], but today's devices are limited by qubit counts and susceptibility to noise. Distributed quantum computing (DQC) addresses these constraints by interconnecting quantum processors via quantum networks to enable cooperative execution of quantum algorithms [4]. DQC can be realized either through quantum teleportation [3], which transfers qubit states across nodes, or through remote gates [7], which enact quantum operations between spatially separated qubits while preserving their physical allocation. Both approaches depend on pre-shared entanglement, which must be distributed across potentially multi-hop quantum networks via entanglement swapping [11]. In realistic settings, DQC performance is influenced by factors such as entanglement fidelity, quantum memory coherence time, and routing path length, yet the impact of these parameters on computational fidelity remains insufficiently understood. This work investigates these effects through simulation of distributed Grover circuits executed over quantum networks with 1-4 routers, incorporating entanglement swapping, network delays, and varying physical constraints to assess how network-level properties affect circuit-level performance.
As quantum computing transitions into the Noisy Intermediate-Scale Quantum (NISQ) era, scaling monolithic quantum processors remains a significant challenge due to decoherence and operational noise. This dissertation proposes enhancing the connectivity of distributed quantum systems as a scalable solution, focusing on three major research tasks: architectural co-design, operation scheduling optimization, and network topology design. First, to address the physical qubit limits of single-chip processors, we investigate the co-design of network topology and logical qubit allocation for Distributed Quantum Computing (DQC). By modeling qubit interaction as a graph partition problem, we propose a joint optimization framework to minimize inter-QPU communication overhead. Our results demonstrate that the proposed linearized formulation, TACO-L, significantly outperforms traditional two-stage methods in executing complex quantum circuits. Second, we address the challenge of maintaining high-fidelity long-distance entanglements through the optimization of Swapping and Purification Schemes (SPS). We prove that in Binary systems, any optimal swapping and purification tree (OSPT) must follow a Restricted SPT (RT) pattern, where purification is integrated at the link level prior to swapping. Furthermore, we introduce the gradient-based GradTree algorithm, which enables an efficient search for low-cost, high-fidelity scheduling in complex noise environments. Finally, this dissertation formulates the first general Topology Design Problem (TDP) for quantum networks, jointly optimizing quantum memory allocation, optical channel deployment, and entanglement scheduling. By analyzing flow-based and path-based formulations, we prove the optimality of the Relaxed Complete Swapping Tree (RCST) in minimizing the expected cost of entanglement distribution. Collectively, these contributions provide a comprehensive theoretical and algorithmic framework for building scalable, cost-effective global quantum internet architectures.
Distributed quantum computing (DQC) combines the computing power of multiple networked quantum processing modules, ideally enabling the execution of large quantum circuits without compromising performance or connectivity. Photonic networks are well-suited as a versatile and reconfigurable interconnect layer for DQC; remote entanglement shared between matter qubits across the network enables all-to-all logical connectivity via quantum gate teleportation (QGT). For a scalable DQC architecture, the QGT implementation must be deterministic and repeatable; until now, no demonstration has satisfied these requirements. In this thesis, we report the first experimental demonstration of distributed quantum computing across a quantum network of two photonically interconnected trapped-ion modules. Our experimental apparatus comprises two trapped-ion modules, separated by ∼ 2 m, each co-trapping one 43Ca+ ion and one 88Sr+ ion. The 43Ca+ ions provide a robust quantum memory for the modules, while the 88Sr+ ions provide an interface to the optical quantum network, enabling the remote entanglement of 88Sr+ ions in separate modules. Using local mixed-species operations, we demonstrate the enhanced functionality of the mixed-species trapped-ion quantum network by creating more complex remotely entangled states. These include remote 88Sr+- 43Ca+ and 43Ca+-43Ca+ entanglement, as well as 3- and 4-qubit mixed-species GHZ states. Additionally, we demonstrate the storage of remote entanglement in the 43Ca+ ions for up to 10 s. Utilising these techniques, we demonstrate the distribution of quantum computations across the mixed-species trapped-ion quantum network. Using heralded remote entanglement between the 88Sr+ ions, we deterministically teleport controlled Z gates between two 43Ca+ ions in separate modules, achieving a fidelity of 86 %. We then implement distributed iSWAP and SWAP circuits, compiled with 2 and 3 instances of QGT, respectively, demonstrating the ability to distribute arbitrary two-qubit operations. Finally, we execute Grover’s search algorithm – the first implementation of a distributed quantum algorithm comprising multiple non-local two-qubit gates – and measure a success rate of 71 %. These results represent a significant step towards realising a large-scale distributed quantum computer.