Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2406.13452

Multipartite Entanglement Routing as a Hypergraph Immersion Problem

Yu Tian, Yuefei Liu, Xiangyi Meng

Published Jun 19, 2024• 0 citations
arXivHTMLPDF

Abstract

Multipartite entanglement, linking multiple nodes simultaneously, is a higher-order correlation that offers advantages over pairwise connections in quantum networks (QNs). Creating reliable, large-scale multipartite entanglement requires entanglement routing, a process that combines local, short-distance connections into a long-distance connection, which can be considered as a transformation of network topology. Here, we address the question of whether a QN can be topologically transformed into another via entanglement routing. Our key result is an exact mapping from multipartite entanglement routing to Nash-Williams's graph immersion problem, extended to hypergraphs. This generalized hypergraph immersion problem introduces a partial order between QN topologies, permitting certain topological transformations while precluding others, offering discerning insights into the design and manipulation of higher-order network topologies in QNs.

DOI
10.48550/arxiv.2406.13452

Related papers

Improved Routing of Multiparty Entanglement over Quantum Networks

Nirupam Basak, Goutam Paul

The effective routing of entanglement over a quantum network is a fundamental problem in quantum communication. The distribution and reshaping of multipartite entanglement over a quantum network requires scalable protocols that adapt to the underlying topology. Graph states provide a convenient framework for this challenging task, as they encode global entanglement in a structured way that can be locally manipulated to produce a variety of target states, without requiring additional long-distance quantum operations. In this article, we propose graph-state-based routing protocols for sharing GHZ states, achieving larger sizes than those achieved in the existing works for given network topologies. For this improvement, we consider tree structures connecting the users participating in the final GHZ states, as opposed to the linear configurations used in the earlier works. In particular, for grid networks, we show special constructions of such trees that achieve larger GHZ states than the prior works. Moreover, if the user nodes along which the entanglement is to be routed are pre-specified, a strategy is proposed to accomplish this routing.

arXiv:2409.14694•ACM Transactions on Quantum Computing•Apr 22, 2026•0 citations

Shortcuts to quantum network routing

Eddie Schoute, Laura Mančinska, Tanvirul Islam +2 more

A quantum network promises to enable long distance quantum communication, and assemble small quantum devices into a large quantum computing cluster. Each network node can thereby be seen as a small few qubit quantum computer. Qubits can be sent over direct physical links connecting nearby quantum nodes, or by means of teleportation over pre-established entanglement amongst distant network nodes. Such pre-shared entanglement effectively forms a shortcut - a virtual quantum link - which can be used exactly once. Here, we present an abstraction of a quantum network that allows ideas from computer science to be applied to the problem of routing qubits, and manage entanglement in the network. Specifically, we consider a scenario in which each quantum network node can create EPR pairs with its immediate neighbours over a physical connection, and perform entanglement swapping operations in order to create long distance virtual quantum links. We proceed to discuss the features unique to quantum networks, which call for the development of new routing techniques. As an example, we present two simple hierarchical routing schemes for a quantum network of N nodes for a ring and sphere topology. For these topologies we present efficient routing algorithms requiring O(log N) qubits to be stored at each network node, O(polylog N) time and space to perform routing decisions, and O(log N) timesteps to replenish the virtual quantum links in a model of entanglement generation.

arXiv:1610.05238•Oct 17, 2016•95 citations

Entanglement Percolation in Quantum Hypergraphs

Mohadeseh Azari, Anoosha Fayyaz, Kaushik Parasuram Seshadreesan

Percolation theory is widely used to analyze the robustness of quantum networks. However, most studies focus on site-bond percolation in quantum network graphs based on bipartite entanglement and entanglement swapping, overlooking the higher-order interactions necessary to model dynamic quantum networks that include propagating multipartite entangled states. Integrating these elements into a hypergraph percolation framework represents a current gap in the scholarly literature. In hypergraphs, while hyperedge percolation generally results in larger giant components than node percolation, we hypothesize that multipartite (hyperedge) percolation can achieve greater connectivity than bipartite (edge) percolation under suitable conditions. Our results show that when the probability of multipartite entanglement remaining intact is low, distributing only bipartite entanglement provides better connectivity due to lower memory overhead. Conversely, when hyperedge generation is reliable and measurements at repeaters are probabilistic, multipartite entanglement enables networks to achieve full connectivity even at low success probabilities, unlike bipartite networks, which require near-perfect success to percolate.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Optimized Distribution of Entanglement Graph States in Quantum Networks

Xiaojie Fan, Caitao Zhan, Himanshu Gupta +1 more

Building large-scale quantum computers, essential to demonstrating quantum advantage, is a key challenge. Quantum networks can help address this challenge by enabling the construction of large, robust, and more capable quantum computing platforms by connecting smaller quantum computers. Moreover, unlike classical systems, quantum networks can enable fully secured long-distance communication. Thus, quantum networks lie at the heart of the success of future quantum information technologies. In quantum networks, multipartite entangled states distributed over the network help implement and support many quantum network applications for communications, sensing, and computing. Our work focuses on developing optimal techniques to generate and distribute multipartite entanglement states efficiently. Prior works on generating general multipartite entanglement states have focused on the objective of minimizing the number of maximally entangled pairs while ignoring the heterogeneity of the network nodes and links as well as the stochastic nature of underlying processes. In this work, we develop a hypergraph-based linear programming framework that delivers optimal (under certain assumptions) generation schemes for general multipartite entanglement represented by graph states, under the network resources, decoherence, and fidelity constraints, while considering the stochasticity of the underlying processes. We illustrate our technique by developing generation schemes for the special cases of path and tree graph states and discuss optimized generation schemes for more general classes of graph states. Using extensive simulations over a quantum network simulator, we demonstrate the effectiveness of our developed techniques and show that they outperform prior known schemes by up to orders of magnitude.

arXiv:2405.00222•IEEE Transactions on Quantum Engineering•Jan 1, 2025•14 citations

Entanglement Routing Based on Fidelity Curves

Bruno Coelho Coutinho, Monteiro, Raul, Luís Bugalho +1 more

How to efficiently distribute entanglement over large-scale quantum networks is still an open problem that greatly depends on the technology considered. In this work, we consider quantum networks where each link is characterized by a trade-off between the entanglement generation rate and fidelity. For such networks, we look at the two following problems: the one of finding the best path to connect any two given nodes, and the problem of finding the best starting node in order to connect three nodes in the network multipartite entanglement routing. Two entanglement distribution models are considered: one where entangled qubits are distributed one at a time, and a flow model where a large number of entangled qubits are distributed simultaneously. The paper proposes of a quite general methodology that uses continuous fidelity curves (i.e., entanglement generation fidelity vs. rate) as the main routing metric. Combined with multi-objective path-finding algorithms, the fidelity curves describing each link allow finding a set of paths that maximize both the end-to-end fidelity and the entanglement generation rate. For the link models and networks considered, it is proven that the algorithm always converges to the optimal solution. It is also shown through simulation that the execution time grows polynomially with the number of network nodes (growing with a power between $1$ and $1.4$, depending on the network)

arXiv:2303.12864•Mar 22, 2023•1 citation

Quantum Routing Beyond Pathfinding: Multipartite Entanglement Complementation

Si-Yi Chen, Angela Sara Cacciapuoti, Marcello Caleffi

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.

quant-pharXiv:2604.13834•Apr 16, 2026•0 citations
Multipartite entanglement, linking multiple nodes simultaneously, is a higher-order correlation that offers advantages over pairwise connections in quantum networks (QNs). Creating reliable, large-scale multipartite entanglement requires entanglement routing, a process that combines local, short-distance connections into a long-distance connection, which can be considered as a transformation of network topology. Here, we address the question of whether a QN can be topologically transformed into another via entanglement routing. Our key result is an exact mapping from multipartite entanglement routing to Nash-Williams's graph immersion problem, extended to hypergraphs. This generalized hypergraph immersion problem introduces a partial order between QN topologies, permitting certain topological transformations while precluding others, offering discerning insights into the design and manipulation of higher-order network topologies in QNs.
The effective routing of entanglement over a quantum network is a fundamental problem in quantum communication. The distribution and reshaping of multipartite entanglement over a quantum network requires scalable protocols that adapt to the underlying topology. Graph states provide a convenient framework for this challenging task, as they encode global entanglement in a structured way that can be locally manipulated to produce a variety of target states, without requiring additional long-distance quantum operations. In this article, we propose graph-state-based routing protocols for sharing GHZ states, achieving larger sizes than those achieved in the existing works for given network topologies. For this improvement, we consider tree structures connecting the users participating in the final GHZ states, as opposed to the linear configurations used in the earlier works. In particular, for grid networks, we show special constructions of such trees that achieve larger GHZ states than the prior works. Moreover, if the user nodes along which the entanglement is to be routed are pre-specified, a strategy is proposed to accomplish this routing.
A quantum network promises to enable long distance quantum communication, and assemble small quantum devices into a large quantum computing cluster. Each network node can thereby be seen as a small few qubit quantum computer. Qubits can be sent over direct physical links connecting nearby quantum nodes, or by means of teleportation over pre-established entanglement amongst distant network nodes. Such pre-shared entanglement effectively forms a shortcut - a virtual quantum link - which can be used exactly once. Here, we present an abstraction of a quantum network that allows ideas from computer science to be applied to the problem of routing qubits, and manage entanglement in the network. Specifically, we consider a scenario in which each quantum network node can create EPR pairs with its immediate neighbours over a physical connection, and perform entanglement swapping operations in order to create long distance virtual quantum links. We proceed to discuss the features unique to quantum networks, which call for the development of new routing techniques. As an example, we present two simple hierarchical routing schemes for a quantum network of N nodes for a ring and sphere topology. For these topologies we present efficient routing algorithms requiring O(log N) qubits to be stored at each network node, O(polylog N) time and space to perform routing decisions, and O(log N) timesteps to replenish the virtual quantum links in a model of entanglement generation.
Percolation theory is widely used to analyze the robustness of quantum networks. However, most studies focus on site-bond percolation in quantum network graphs based on bipartite entanglement and entanglement swapping, overlooking the higher-order interactions necessary to model dynamic quantum networks that include propagating multipartite entangled states. Integrating these elements into a hypergraph percolation framework represents a current gap in the scholarly literature. In hypergraphs, while hyperedge percolation generally results in larger giant components than node percolation, we hypothesize that multipartite (hyperedge) percolation can achieve greater connectivity than bipartite (edge) percolation under suitable conditions. Our results show that when the probability of multipartite entanglement remaining intact is low, distributing only bipartite entanglement provides better connectivity due to lower memory overhead. Conversely, when hyperedge generation is reliable and measurements at repeaters are probabilistic, multipartite entanglement enables networks to achieve full connectivity even at low success probabilities, unlike bipartite networks, which require near-perfect success to percolate.
Building large-scale quantum computers, essential to demonstrating quantum advantage, is a key challenge. Quantum networks can help address this challenge by enabling the construction of large, robust, and more capable quantum computing platforms by connecting smaller quantum computers. Moreover, unlike classical systems, quantum networks can enable fully secured long-distance communication. Thus, quantum networks lie at the heart of the success of future quantum information technologies. In quantum networks, multipartite entangled states distributed over the network help implement and support many quantum network applications for communications, sensing, and computing. Our work focuses on developing optimal techniques to generate and distribute multipartite entanglement states efficiently. Prior works on generating general multipartite entanglement states have focused on the objective of minimizing the number of maximally entangled pairs while ignoring the heterogeneity of the network nodes and links as well as the stochastic nature of underlying processes. In this work, we develop a hypergraph-based linear programming framework that delivers optimal (under certain assumptions) generation schemes for general multipartite entanglement represented by graph states, under the network resources, decoherence, and fidelity constraints, while considering the stochasticity of the underlying processes. We illustrate our technique by developing generation schemes for the special cases of path and tree graph states and discuss optimized generation schemes for more general classes of graph states. Using extensive simulations over a quantum network simulator, we demonstrate the effectiveness of our developed techniques and show that they outperform prior known schemes by up to orders of magnitude.
How to efficiently distribute entanglement over large-scale quantum networks is still an open problem that greatly depends on the technology considered. In this work, we consider quantum networks where each link is characterized by a trade-off between the entanglement generation rate and fidelity. For such networks, we look at the two following problems: the one of finding the best path to connect any two given nodes, and the problem of finding the best starting node in order to connect three nodes in the network multipartite entanglement routing. Two entanglement distribution models are considered: one where entangled qubits are distributed one at a time, and a flow model where a large number of entangled qubits are distributed simultaneously. The paper proposes of a quite general methodology that uses continuous fidelity curves (i.e., entanglement generation fidelity vs. rate) as the main routing metric. Combined with multi-objective path-finding algorithms, the fidelity curves describing each link allow finding a set of paths that maximize both the end-to-end fidelity and the entanglement generation rate. For the link models and networks considered, it is proven that the algorithm always converges to the optimal solution. It is also shown through simulation that the execution time grows polynomially with the number of network nodes (growing with a power between 111 and 1.41.41.4, depending on the network)
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%60\%60% hop reduction, with the algorithm enabling efficient parallelism and strong scalability in inter-domain quantum networks.