Quantum Routing Beyond Pathfinding: Multipartite Entanglement Complementation
Pith reviewed 2026-05-10 13:49 UTC · model grok-4.3
The pith
Multipartite entanglement complementation enables simultaneous 1-hop connectivity for all non-adjacent pairs in quantum networks, bypassing pathfinding.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By using multipartite entanglement complementation, the routing framework provides simultaneous 1-hop connectivity among all non-adjacent source-destination pairs. This redefines remoteness in the entanglement graph. The framework is extended to inter-domain quantum networks through a polynomial-time algorithm that selects and parallelizes multiple requests, avoiding NP-complete path discovery.
What carries the argument
Multipartite entanglement complementation, which provides simultaneous 1-hop connectivity among non-adjacent nodes and redefines remoteness in the entanglement graph.
If this is right
- Multiple routing requests can be selected and parallelized without solving path discovery problems.
- Up to 60 percent hop reduction is achieved compared to conventional approaches.
- The polynomial-time algorithm supports efficient parallelism and strong scalability in inter-domain networks.
- Pathfinding, treated as an NP-complete prerequisite, is no longer required for routing.
Where Pith is reading between the lines
- Quantum network designers could prioritize pre-distribution of multipartite entanglement states to achieve a logically complete graph independent of physical adjacency.
- The routing method opens questions about optimal entanglement generation schedules that maximize complementation opportunities rather than pairwise links.
- Hardware experiments measuring actual hop counts under realistic entanglement loss rates would clarify whether the reported 60 percent reduction holds beyond simulations.
Load-bearing premise
Multipartite entanglement can be generated, distributed, and complemented at sufficient fidelity and rate to ensure reliable simultaneous 1-hop connectivity for all non-adjacent pairs.
What would settle it
A simulation comparing hop counts and runtime for routing multiple requests in an inter-domain quantum network using the polynomial-time algorithm versus traditional pathfinding.
Figures
read the original abstract
Conventional quantum routing operates under the entrenched assumption that pathfinding is a prerequisite for routing. This classical-inspired routing model imposes a restricting design option, which prevents scaling the quantumness to the network functioning. In this paper, we proposed a novel entanglement-driven routing framework that exploits multipartite entanglement complementation for enabling simultaneous 1-hop connectivity among all non-adjacent source-destination pairs. This changes the notion of ``remoteness'' in the entanglement graph, activated by entanglement. We extend this framework to inter-domain quantum networks and design a polynomial-time algorithm. Such an algorithm allows to select and parallelize multiple requests, bypassing NP-complete path discovery. Performance analysis shows the proposed routing strategy achieves up to $60\%$ hop reduction, with the algorithm enabling efficient parallelism and strong scalability in inter-domain quantum networks.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims that conventional quantum routing's reliance on pathfinding limits scalability, and proposes a new entanglement-driven framework using multipartite entanglement complementation to enable simultaneous 1-hop connectivity among all non-adjacent source-destination pairs. This redefines remoteness in the entanglement graph. The framework is extended to inter-domain quantum networks with a polynomial-time algorithm that selects and parallelizes multiple requests, bypassing NP-complete path discovery. Performance analysis indicates up to 60% hop reduction and strong scalability.
Significance. Should the claims be validated through detailed derivations and experiments, this work could have high significance by fundamentally altering quantum network routing paradigms, potentially leading to more efficient inter-domain quantum communications. The polynomial-time nature and hop reduction are promising if the entanglement complementation can indeed be realized without reintroducing the complexities it aims to avoid. The paper introduces the concept of 'multipartite entanglement complementation' which, if properly formalized, adds a new tool to quantum information processing.
major comments (2)
- Abstract: the claim of achieving up to 60% hop reduction and polynomial-time scalability supplies no equations, simulation details, data sets, error bars, or verification method, preventing any determination of whether the stated performance is supported by derivation or experiment.
- The entanglement-driven routing framework: the load-bearing assumption that multipartite entanglement can be generated, distributed, and complemented across the network at sufficient fidelity and rate to provide reliable simultaneous 1-hop connectivity for all non-adjacent pairs (replacing classical pathfinding) is not quantified or proven; no analysis addresses whether distribution and complementation operations re-introduce NP-hard routing subproblems or fidelity/rate bottlenecks.
Simulated Author's Rebuttal
We thank the referee for their thorough review and constructive comments on our manuscript. We address each of the major comments point by point below, indicating where revisions will be made to the manuscript.
read point-by-point responses
-
Referee: Abstract: the claim of achieving up to 60% hop reduction and polynomial-time scalability supplies no equations, simulation details, data sets, error bars, or verification method, preventing any determination of whether the stated performance is supported by derivation or experiment.
Authors: We agree that the abstract, as a concise summary, omits supporting details. The 60% hop reduction is obtained from comparative simulations against conventional routing on random and scale-free topologies, presented with explicit metrics in Section 4; the polynomial-time claim follows from the O(n^2) selection algorithm whose correctness is proven in Section 3. To improve transparency, we will revise the abstract to add a short clause referencing this validation (e.g., “validated via simulations on random graphs showing up to 60% hop reduction”). revision: yes
-
Referee: The entanglement-driven routing framework: the load-bearing assumption that multipartite entanglement can be generated, distributed, and complemented across the network at sufficient fidelity and rate to provide reliable simultaneous 1-hop connectivity for all non-adjacent pairs (replacing classical pathfinding) is not quantified or proven; no analysis addresses whether distribution and complementation operations re-introduce NP-hard routing subproblems or fidelity/rate bottlenecks.
Authors: We acknowledge the importance of physical-layer feasibility. The manuscript develops the framework at the graph and algorithmic level, where complementation directly supplies 1-hop links and thereby removes the need to solve per-request shortest-path instances. The polynomial-time procedure selects and parallelizes requests without invoking NP-complete path search. However, the paper does not supply quantitative fidelity or rate models for the complementation operation itself. We will add an explicit “Assumptions and Limitations” subsection that states the ideal-distribution premise, notes that physical bottlenecks remain open, and clarifies that any routing-level complexity is avoided by construction. A full channel-model analysis lies outside the present scope and will be flagged as future work. revision: partial
Circularity Check
No circularity: modeling premise and algorithm design are independent of claimed outputs
full rationale
The paper introduces a routing framework whose core modeling choice is that multipartite entanglement complementation enables simultaneous 1-hop connectivity for non-adjacent pairs, thereby replacing pathfinding. This is presented as a definitional extension of the entanglement graph rather than a quantity derived from prior equations or data within the paper. The polynomial-time algorithm and 60% hop-reduction claim are stated as consequences of this modeling choice and subsequent performance analysis; no equations, fitted parameters, or self-citations are exhibited that would make the outputs equivalent to the inputs by construction. The framework is therefore self-contained against external benchmarks of graph routing complexity.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption Multipartite entanglement can be generated and complemented across non-adjacent nodes to create effective 1-hop connectivity
invented entities (1)
-
Multipartite entanglement complementation
no independent evidence
Reference graph
Works this paper leans on
-
[1]
Beyond traditional quan- tum routing,
S.-Y . Chen, A. S. Cacciapuoti, and M. Caleffi, “Beyond traditional quan- tum routing,” in Proc. of IEEE International Conference on Quantum Computing and Engineering (QCE), 2025
work page 2025
-
[2]
Quantum internet architecture: unlocking quantum-native routing via quantum addressing,
M. Caleffi and A. S. Cacciapuoti, “Quantum internet architecture: unlocking quantum-native routing via quantum addressing,” IEEE Transactions on Communications, 2026
work page 2026
-
[3]
Quantum internet address- ing,
A. S. Cacciapuoti, J. Illiano, and M. Caleffi, “Quantum internet address- ing,” IEEE Network, 2023
work page 2023
-
[4]
Satellite-terrestrial quantum networks and the global quantum internet,
A. Conti, R. Malaney, and M. Z. Win, “Satellite-terrestrial quantum networks and the global quantum internet,” IEEE Communications Magazine, vol. 62, no. 10, pp. 34–39, 2024
work page 2024
-
[5]
Quantum communications and networking: Series 1,
R. Li, P. Narang, M. Aelmans, P. Mueller, and G. Long, “Quantum communications and networking: Series 1,” IEEE Network, vol. 38, no. 1, pp. 77–78, 2024
work page 2024
-
[6]
Fendi: Toward high-fidelity entanglement distribution in the quantum internet,
H. Gu, Z. Li, R. Yu, X. Wang, F. Zhou, J. Liu, and G. Xue, “Fendi: Toward high-fidelity entanglement distribution in the quantum internet,” IEEE/ACM Transactions on Networking, vol. 32, no. 6, pp. 5033–5048, 2024
work page 2024
-
[7]
Entanglement routing in quantum networks: A comprehensive survey,
A. Abane, M. Cubeddu, V . S. Mai, and A. Battou, “Entanglement routing in quantum networks: A comprehensive survey,” IEEE Transactions on Quantum Engineering, 2025
work page 2025
-
[8]
Concurrent entanglement routing for quantum networks: Model and designs,
S. Shi and C. Qian, “Concurrent entanglement routing for quantum networks: Model and designs,” in SIGCOMM ’20, 2020, p. 62–75
work page 2020
-
[9]
Opportunistic routing in quantum net- works,
A. Farahbakhsh and C. Feng, “Opportunistic routing in quantum net- works,” in IEEE INFOCOM 2022 - IEEE Conference on Computer Communications, 2022, pp. 490–499
work page 2022
-
[10]
Optimal routing for quantum networks,
M. Caleffi, “Optimal routing for quantum networks,” IEEE Access, vol. 5, pp. 22 299–22 312, 2017
work page 2017
-
[11]
Quantum network routing design with dynamic re- quests scheduling in multi-user environments,
X. Liu and R. Li, “Quantum network routing design with dynamic re- quests scheduling in multi-user environments,” in International Wireless Communications and Mobile Computing, 2025, pp. 1434–1439
work page 2025
-
[12]
Decentralized base-graph routing for the quantum internet,
L. Gyongyosi and S. Imre, “Decentralized base-graph routing for the quantum internet,” Phys. Rev. A, vol. 98, p. 022310, Aug 2018
work page 2018
-
[13]
Effective routing design for remote entanglement generation on quantum networks,
C. Li, T. Li, Y .-X. Liu, and P. Cappellaro, “Effective routing design for remote entanglement generation on quantum networks,” npj Quantum Information, vol. 7, no. 1, p. 10, 2021
work page 2021
-
[14]
Qubit teleportation between non-neighbouring nodes in a quantum network,
S. Hermans, M. Pompili, H. Beukers, S. Baier, J. Borregaard, and R. Hanson, “Qubit teleportation between non-neighbouring nodes in a quantum network,” Nature, vol. 605, no. 7911, pp. 663–668, 2022
work page 2022
-
[15]
Analysis of quantum network coding for realistic repeater networks,
T. Satoh, K. Ishizaki, S. Nagayama, and R. Van Meter, “Analysis of quantum network coding for realistic repeater networks,” Physical Review A, vol. 93, no. 3, p. 032302, 2016
work page 2016
-
[16]
Distributed quantum computing: a survey,
M. Caleffi, M. Amoretti, D. Ferrari, J. Illiano, A. Manzalini, and A. S. Cacciapuoti, “Distributed quantum computing: a survey,” Computer Networks, vol. 254, p. 110672, 2024
work page 2024
-
[17]
Architectural Principles for a Quantum Internet,
W. Kozlowski, S. Wehner, R. V . Meter, B. Rijsman, A. S. Cacciapuoti, M. Caleffi, and S. Nagayama, “Architectural Principles for a Quantum Internet,” RFC 9340, Mar. 2023
work page 2023
-
[18]
Patterns in network architecture: a return to fundamentals,
D. John, “Patterns in network architecture: a return to fundamentals,” 2007
work page 2007
-
[19]
On the efficient extrac- tion of entangled resources,
S.-Y . Chen, A. S. Cacciapuoti, and M. Caleffi, “On the efficient extrac- tion of entangled resources,” IEEE Transactions on Communications, vol. 74, pp. 3517–3531, 2026
work page 2026
-
[20]
A quantum network stack and protocols for reliable entanglement-based networks,
A. Pirker and W. Dür, “A quantum network stack and protocols for reliable entanglement-based networks,” New Journal of Physics, vol. 21, no. 3, p. 033003, mar 2019
work page 2019
-
[21]
Entanglement- based artificial topology: Neighboring remote network nodes,
S.-Y . Chen, J. Illiano, A. S. Cacciapuoti, and M. Caleffi, “Entanglement- based artificial topology: Neighboring remote network nodes,” IEEE Open Journal of the Communications Society, 2025
work page 2025
-
[22]
Quantum network routing and local complementation,
F. Hahn, A. Pappa, and J. Eisert, “Quantum network routing and local complementation,” npj Quantum Information, vol. 5, no. 1, p. 76, 2019
work page 2019
-
[23]
Scaling quan- tum networks: Inter-qlans artificial connectivity,
S.-Y . Chen, J. Illiano, A. S. Cacciapuoti, and M. Caleffi, “Scaling quan- tum networks: Inter-qlans artificial connectivity,” in IEEE International Conference on Quantum Computing and Engineering, 2024. 16
work page 2024
-
[24]
An entanglement-based wavelength-multiplexed quantum communica- tion network,
S. Wengerowsky, S. K. Joshi, F. Steinlechner, H. Hübel, and R. Ursin, “An entanglement-based wavelength-multiplexed quantum communica- tion network,” Nature, vol. 564, no. 7735, pp. 225–228, 2018
work page 2018
-
[25]
Z. Li, K. Xue et al., “Entanglement-assisted quantum networks: Mechan- ics, enabling technologies, challenges, and research directions,” IEEE Communications Surveys & Tutorials, pp. 2133–2189, 2023
work page 2023
-
[26]
Intra-qlan connectivity via graph states: Beyond the physical topology,
F. Mazza, M. Caleffi, and A. S. Cacciapuoti, “Intra-qlan connectivity via graph states: Beyond the physical topology,” IEEE Transactions on Network Science and Engineering, 2025
work page 2025
-
[27]
Influence of noise in entanglement- based quantum networks,
M. F. Mor-Ruiz and W. Dür, “Influence of noise in entanglement- based quantum networks,” IEEE Journal on Selected Areas in Communications, 2024
work page 2024
-
[28]
Realization of a multinode quantum network of remote solid-state qubits,
M. Pompili, S. L. Hermans, S. Baier, H. K. Beukers, Humphreys et al., “Realization of a multinode quantum network of remote solid-state qubits,” Science, vol. 372, no. 6539, pp. 259–264, 2021
work page 2021
-
[29]
Deterministic delivery of remote entanglement on a quantum network,
P. C. Humphreys, N. Kalb et al., “Deterministic delivery of remote entanglement on a quantum network,” Nature, vol. 558, no. 7709, pp. 268–273, 2018
work page 2018
-
[30]
Architecture and protocols for all-photonic quantum repeaters,
N. Benchasattabuse, M. Hajdušek, and R. Van Meter, “Architecture and protocols for all-photonic quantum repeaters,” in IEEE International Conference on Quantum Computing and Engineering (QCE), 2024
work page 2024
-
[31]
Multiparty entanglement routing in quantum networks,
V . Mannalath and A. Pathak, “Multiparty entanglement routing in quantum networks,” Phys. Rev. A, vol. 108, p. 062614, Dec 2023
work page 2023
-
[32]
J. A. Bondy, U. S. R. Murty et al., Graph theory with applications. Macmillan London, 1976, vol. 290
work page 1976
-
[33]
Np-completeness of some edge-disjoint paths problems,
J. Vygen, “Np-completeness of some edge-disjoint paths problems,” Discrete Applied Mathematics, vol. 61, no. 1, pp. 83–90, 1995
work page 1995
-
[34]
Mapping graph state orbits under local complementation,
J. C. Adcock, S. Morley-Short, A. Dahlberg, and J. W. Silverstone, “Mapping graph state orbits under local complementation,” Quantum, vol. 4, p. 305, 2020
work page 2020
-
[35]
Quantum data centres: why entanglement changes everything,
A. S. Cacciapuoti, C. Pellitteri et al., “Quantum data centres: why entanglement changes everything,” Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 384, no. 2315, 2026
work page 2026
-
[36]
Distributed quantum computing: a survey,
M. Caleffi, M. Amoretti, D. Ferrari, D. Cuomo, J. Illiano, A. Manzalini, and A. S. Cacciapuoti, “Distributed quantum computing: a survey,”arXiv preprint arXiv:2212.10609, 2022
-
[37]
Quantum internet protocol stack: a comprehensive survey,
J. Illiano, M. Caleffi, A. Manzalini, and A. S. Cacciapuoti, “Quantum internet protocol stack: a comprehensive survey,” Computer Networks, vol. 213, 2022
work page 2022
-
[38]
Openflights airport, airline and route data,
OpenFlights.org, “Openflights airport, airline and route data,” https:// openflights.org/data, 2025
work page 2025
-
[39]
Generation of genuine entanglement up to 51 superconducting qubits,
S. Cao, B. Wu, F. Chen, M. Gong, Y . Wu, Y . Ye, C. Zha, H. Qian, C. Ying, S. Guo et al., “Generation of genuine entanglement up to 51 superconducting qubits,” Nature, vol. 619, no. 7971, pp. 738–742, 2023
work page 2023
-
[40]
The impact of the quantum data plane overhead on the throughput,
J. Illiano, A. S. Cacciapuoti, A. Manzalini, and M. Caleffi, “The impact of the quantum data plane overhead on the throughput,” inProc. of ACM NANOCOM ’21, 2021, pp. 1–6
work page 2021
-
[41]
Simulation of the five-qubit quantum error correction code on superconducting qubits,
I. Simakov, I. Besedin, and A. Ustinov, “Simulation of the five-qubit quantum error correction code on superconducting qubits,” Physical Review A, vol. 105, no. 3, p. 032409, 2022
work page 2022
-
[42]
Scalable Multipartite Entanglement Created by Spin Exchange in an Optical Lattice,
W.-Y . Zhang et al., “Scalable Multipartite Entanglement Created by Spin Exchange in an Optical Lattice,” Phys. Rev. Lett., vol. 131, no. 7, p. 073401, 2023
work page 2023
-
[43]
Programmable multi-mode entanglement via dissipative engineering in vibrating trapped ions,
Y . Li et al., “Programmable multi-mode entanglement via dissipative engineering in vibrating trapped ions,” Sci. Adv., vol. 11, no. 27, p. adv7838, 2025
work page 2025
-
[44]
Optical quantum computation using cluster states,
M. A. Nielsen, “Optical quantum computation using cluster states,” Phys. Rev. Lett., vol. 93, p. 040503, Jul 2004
work page 2004
-
[45]
Efficient generation of entangled multiphoton graph states from a single atom,
P. Thomas, L. Ruscio, O. Morin, and G. Rempe, “Efficient generation of entangled multiphoton graph states from a single atom,” Nature, vol. 608, no. 7924, pp. 677–681, 2022
work page 2022
-
[46]
Fusion of deterministically generated photonic graph states,
——, “Fusion of deterministically generated photonic graph states,” Nature, vol. 629, no. 8012, pp. 567–572, 2024
work page 2024
-
[47]
Efficient generation of entangled multiphoton graph states from a single atom,
——, “Efficient generation of entangled multiphoton graph states from a single atom,” Nature, vol. 608, no. 7924, pp. 677–681, 2022
work page 2022
-
[48]
Flexible qubit allocation of network resource states,
F. Mazza, J. Miguel-Ramiro, J. Illiano, A. Pirker, M. Caleffi, A. S. Cacciapuoti, and W. Dür, “Flexible qubit allocation of network resource states,” arXiv preprint arXiv:2510.15776, 2025
-
[49]
Entanglement generation in a quantum network at distance-independent rate,
A. Patil, M. Pant, D. Englund, D. Towsley, and S. Guha, “Entanglement generation in a quantum network at distance-independent rate,” npj Quantum Information, vol. 8, no. 1, p. 51, 2022
work page 2022
-
[50]
Deterministic generation of photonic entangled states using decoherence-free subspaces,
O. Rubies-Bigorda, S. J. Masson, S. F. Yelin, and A. Asenjo- Garcia, “Deterministic generation of photonic entangled states using decoherence-free subspaces,” Physical Review Letters, vol. 134, no. 21, p. 213603, 2025
work page 2025
-
[51]
Quantum-Native Architectural Tenets and Philosophy for the Quantum Internet,
A. S. Cacciapuoti, M. Caleffi, J. Illiano, and C. D. Risi, “Quantum-Native Architectural Tenets and Philosophy for the Quantum Internet,” Internet Engineering Task Force, Internet- Draft draft-cacciapuoti-qirg-quantum-native-architecture-00, Nov. 2025, work in Progress. [Online]. Available: https://datatracker.ietf.org/doc/ draft-cacciapuoti-qirg-quantum-...
work page 2025
-
[52]
Suppressing quantum errors by scaling a surface code logical qubit,
G. Q. AI, “Suppressing quantum errors by scaling a surface code logical qubit,” Nature, vol. 614, no. 7949, pp. 676–681, 2023
work page 2023
-
[53]
IonQ, “Introducing ionq forte,” https://ionq.com/resources/ ionq-forte-first-configurable-quantum-computer, 2023
work page 2023
-
[54]
High-fidelity parallel entangling gates on a neutral-atom quantum computer,
S. Evered, D. Bluvstein et al., “High-fidelity parallel entangling gates on a neutral-atom quantum computer,” Nature, vol. 622, no. 7982, pp. 268–272, Oct. 2023
work page 2023
-
[55]
High-fidelity gates and mid-circuit erasure conversion in an atomic qubit,
S. Ma, G. Liu et al., “High-fidelity gates and mid-circuit erasure conversion in an atomic qubit,” Nature, vol. 622, no. 7982, pp. 279– 284, 2023
work page 2023
-
[56]
M. F. Mor-Ruiz and W. Dür, “Noisy stabilizer formalism,” Phys. Rev. A, vol. 107, p. 032424, Mar 2023
work page 2023
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.