Quantum-network routing protocols based on n-fusion — swapping that fuses n simultaneously successful entanglement links via Greenberger-Horne-Zeilinger (GHZ) measurements — were recently shown to substantially raise end-to-end entanglement rates for multiple user pairs on general network topologies, but only in an idealized setting: every switch has the same fusion success probability qq, user memories are effectively unlimited, a centralized classical server computes routes from global network state, and the proposed route-selection and qubit-allocation algorithms are validated purely by simulation. The open problem is to build a routing theory for n-fusion quantum networks under realistic conditions: per-node heterogeneous fusion reliabilities and memory limits with jointly constrained link and swap resources, distributed or partially informed operation in dynamically changing networks, analytical optimality guarantees quantifying the gap of practical algorithms to globally optimal routing, and a characterization of when the distance-independent rates and GHZ-over-BSM advantage observed on special topologies and single user pairs persist on arbitrary topologies and multiple pairs.

Background

A quantum network distributes entanglement — correlated quantum states such as two-qubit Bell pairs — between distant nodes, enabling quantum key distribution, distributed quantum sensing, and distributed quantum computing. Because the probability that photon transmission over a fiber of length LL succeeds decays as P=e−αLP=e^{-\alpha L}, direct long-distance entanglement generation is exponentially suppressed, and networks rely on quantum repeaters (intermediate “switch” nodes with quantum memory) and entanglement swapping: two short Bell pairs sharing a middle node are measured there (a Bell-state measurement, BSM, which fuses two links), leaving the end nodes entangled. A Greenberger-Horne-Zeilinger (GHZ) state is the multipartite generalization of a Bell pair, and a GHZ measurement on nn qubits fuses up to nn successful links at once (“n-fusion”), which can be far more efficient than chained pairwise BSMs. Entanglement routing is the network-layer problem of choosing which links to build and which switches fuse, subject to node memory (qubit) capacities, so as to maximize the entanglement rate — the expected number of shared quantum states per round between requesting quantum-user pairs.

Two lines define the frontier. Patil et al. proved that on grid/lattice networks with percolation structure (percolation: the study of connectivity of random subgraphs, here the random subgraph of links that succeeded in a round), GHZ-measurement protocols yield an end-to-end entanglement rate that does not decay with distance, provided fusion success probabilities exceed a threshold; but that analysis assumed a uniform success probability for all GHZ measurement sizes, special topologies, and a single user pair. Zeng et al. then gave the first general routing model and concrete heuristics for n-fusion over arbitrary topologies with multiple simultaneous user pairs, where the entanglement rate of a route is a recursive, nonlinear expression over the flow-like graphs that n-fusion creates, and switch qubit capacity — not link capacity — is the binding constraint; they proved complexity bounds for their algorithms and demonstrated large simulated gains over BSM protocols such as Q-Cast (a representative BSM-based entanglement routing protocol). Their model, however, assumes all switches share one fusion success probability qq, that user memories are effectively unbounded (users may act as virtual machines aggregating many processors), and that a centralized classical center server pre-computes all routes from global topology and switch-state information; no approximation ratios, optimality gaps, or analytical performance characterizations accompany the heuristics. The question is what survives when these idealizations are removed.

Problem Statement

Develop entanglement routing for quantum networks whose switches perform GHZ-measurement-based n-fusion swapping, on general topologies and for multiple simultaneous quantum-user pairs, beyond the idealized model of Zeng et al. (ICDCS 2023) — replacing the assumptions of homogeneous fusion success probability, ample user memory, and centralized route computation with realistic conditions, and replacing purely numerical evaluation with analytical performance guarantees. Concretely, the open problem comprises four jointly linked questions whose common objective is a provably good and realistic routing theory for n-fusion networks: (1) Model and algorithm redesign when switching reliability is heterogeneous across nodes, user memory is limited, and link and swap resources are jointly constrained — how should route selection and switch-qubit allocation be performed, and how does the optimal solution change relative to the homogeneous, switch-capacity-only model? (2) Decentralized operation — design routing that works when no center server has global network information, when nodes act on partial or local knowledge, or when the network changes dynamically; quantify the performance loss relative to centralized routing. (3) Analytical guarantees — prove approximation ratios, optimality-gap bounds, or tight competitive bounds for route-selection and qubit-allocation algorithms under n-fusion's recursive, nonlinear entanglement-rate objective, thereby characterizing the gap between practical heuristics and globally optimal n-fusion routing. (4) Distance-independence — determine analytically for which network topologies, fusion-reliability regimes, and numbers of user pairs GHZ-based routing retains distance-independent end-to-end rates and an advantage over BSM-based routing, generalizing the grid-topology, single-pair percolation results of Patil et al. beyond special structures. Answers may take the form of algorithms with proven guarantees, impossibility or separation results (e.g., topologies or reliability profiles where n-fusion routing cannot beat BSM routing, or where distance-independence provably fails), or analytical characterizations of the phase boundary between distance-decaying and distance-independent behavior; these forms are illustrative rather than exhaustive. The four questions are jointly required to resolve the task: a complete answer reaches the common objective across all of (1)-(4), while a result confined to a single one of them is a partial contribution rather than a complete answer. A complete answer to (1) supplies both the route-selection and the switch-qubit-allocation algorithms for the heterogeneous, memory-limited, jointly-constrained regime, together with the comparison to the homogeneous, switch-capacity-only model; to (2) addresses all three listed decentralization conditions — operation with no global center server, partial or local knowledge, and dynamic network change — and quantifies the loss relative to centralized routing; and to (3) proves its bound for each algorithm class treated in (1), i.e. for both route selection and qubit allocation. For question (4), a complete answer is a criterion that decides, for every network topology, fusion-reliability regime, and number of user pairs, whether distance-independent end-to-end rates and the GHZ-over-BSM advantage are retained, or a proof that no such criterion exists; a single separating example, or distance-independence established for one topology family, delineates only part of that boundary rather than completing the characterization asked for in question (4).

References

  1. Yiming Zeng, Jiarui Zhang, Ji Liu, Zhenhua Liu, Yuanyuan Yang, 'Entanglement Routing Over Quantum Networks Using Greenberger-Horne-Zeilinger Measurements', 2023 IEEE 43rd International Conference on Distributed Computing Systems (ICDCS), 2023, DOI: 10.1109/ICDCS57875.2023.00010 (preprint arXiv:2306.16671), https://arxiv.org/abs/2306.16671
  2. Yiming Zeng, Jiarui Zhang, Ji Liu, Zhenhua Liu, Yuanyuan Yang, 'Multi-Entanglement Routing Design Over Quantum Networks Using Greenberger-Horne-Zeilinger Measurements', IEEE Transactions on Networking, 2026, DOI: 10.1109/TON.2025.3608121, https://doi.org/10.1109/TON.2025.3608121
  3. Ashlesha Patil, Mihir Pant, Dirk Englund, Don Towsley, Saikat Guha, 'Entanglement generation in a quantum network at distance-independent rate', npj Quantum Information 8, 51 (2022), DOI: 10.1038/s41534-022-00536-0 (preprint arXiv:2005.07247), https://arxiv.org/abs/2005.07247
  4. Ashlesha Patil, Eliana S. Jacobson, Emily Van Milligen, Don Towsley, Saikat Guha, 'Distance-Independent Entanglement Generation in a Quantum Network using Space-Time Multiplexed Greenberger-Horne-Zeilinger (GHZ) Measurements', 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), 2021, DOI: 10.1109/QCE52317.2021.00050 (preprint arXiv:2108.09352), https://arxiv.org/abs/2108.09352
  5. Xin-An Chen, Caitao Zhan, Joaquin Chung, Jeffrey Larson, 'Routing Entanglement in Complex Quantum Networks Using GHZ States', 2026, arXiv:2604.03155, https://arxiv.org/abs/2604.03155
  6. Connor Clayton, Xiaodi Wu, Bobby Bhattacharjee, 'Efficient Routing on Quantum Networks using Adaptive Clustering', 2024 IEEE 32nd International Conference on Network Protocols (ICNP), 2024, DOI: 10.1109/ICNP61940.2024.10858533 (preprint arXiv:2410.23007), https://arxiv.org/abs/2410.23007
  7. Sounak Kar, Arpan Mukhopadhyay, 'On Utility-optimal Entanglement Routing in Quantum Networks', 2026, arXiv:2603.01197, https://arxiv.org/abs/2603.01197
  8. Tu N. Nguyen, Dung H. P. Nguyen, Dang H. Pham, Bing-Hong Liu, Hoa N. Nguyen, 'Maximizing Entanglement Routing Rate in Quantum Networks: Approximation Algorithms', 2022, arXiv:2207.11821, https://arxiv.org/abs/2207.11821
  9. Zebo Yang, Ali Ghubaish, Raj Jain, Hassan Shapourian, Alireza Shabani, 'Asynchronous Entanglement Routing for the Quantum Internet', AVS Quantum Science 6(1), 2024, DOI: 10.1116/5.0172819 (preprint arXiv:2312.14300), https://arxiv.org/abs/2312.14300
  10. Wan-Ting Ho, Cheng-Yang Cheng, Jian-Jhih Kuo, 'Trading Demand Saturation for Efficiency in Near-Optimal Quantum Entanglement Routing', IEEE INFOCOM 2026, DOI: 10.1109/INFOCOM59046.2026.11571546, https://doi.org/10.1109/INFOCOM59046.2026.11571546
  11. Amar Abane, Michael Cubeddu, Van Sy Mai, Abdella Battou, 'Entanglement Routing in Quantum Networks: A Comprehensive Survey', 2024, arXiv:2408.01234, https://arxiv.org/abs/2408.01234
  12. Nirupam Basak, Goutam Paul, 'Improved Routing of Multiparty Entanglement over Quantum Networks', 2024, arXiv:2409.14694, https://arxiv.org/abs/2409.14694
  13. Shao-Min Huang, Ching-Ting Wei, Kai-Xu Zhan, Juliette Chou Le Touze, Jian-Jhih Kuo, Chih-Yu Wang, 'Authorizable Tripartite Entanglement Routing via 3-GHZ State in Quantum Networks', IEEE Global Communications Conference (GLOBECOM) 2024, DOI: 10.1109/GLOBECOM52923.2024.10901779, https://doi.org/10.1109/GLOBECOM52923.2024.10901779
  14. Yiming Zeng, Jiarui Zhang, Ji Liu, Zhenhua Liu, Yuanyuan Yang, 'Multi-Entanglement Routing Design over Quantum Networks', IEEE INFOCOM 2022, DOI: 10.1109/INFOCOM48880.2022.9796810 (preprint arXiv:2205.15501), https://arxiv.org/abs/2205.15501