Abstract Distributing entangled states among users is a fundamental problem in quantum networks. Existing protocols like protocol introduced in [npj Quantum Inf. 2019, 5, 76] use graph theoretic tools like local complementation to optimize the number of measurements required to extract any Bell pair among the network users. Such a protocol relies on finding the shortest path between the users. Here, it is established that, in general, the most optimal path to perform the protocol is not along the shortest path. Specific examples of this advantage are provided on networks of size as small as 12 qubits. Bottlenecks in establishing simultaneous Bell pairs in nearest‐neighbor architectures are also explored. Recent results suggesting the unsuitability of the line and ring networks for the implementation of quantum networks due to the bottlenecks are revisited, and using local equivalency relations from graph theory, it's hinted that even grid graphs are not exempted from bottleneck issues. Finally, bottlenecks are simulated in grid graphs of sizes up to . Analysis reveals relative positions within a grid graph that are more susceptible to bottlenecks. It demonstrates the superiority of the protocol along paths that are not shortest paths while avoiding bottlenecks for simultaneous communication requests.
Abstract Distributing entangled states among users is a fundamental problem in quantum networks. Existing protocols like protocol introduced in [npj Quantum Inf. 2019, 5, 76] use graph theoretic tools like local complementation to optimize the number of measurements required to extract any Bell pair among the network users. Such a protocol relies on finding the shortest path between the users. Here, it is established that, in general, the most optimal path to perform the protocol is not along the shortest path. Specific examples of this advantage are provided on networks of size as small as 12 qubits. Bottlenecks in establishing simultaneous Bell pairs in nearest‐neighbor architectures are also explored. Recent results suggesting the unsuitability of the line and ring networks for the implementation of quantum networks due to the bottlenecks are revisited, and using local equivalency relations from graph theory, it's hinted that even grid graphs are not exempted from bottleneck issues. Finally, bottlenecks are simulated in grid graphs of sizes up to . Analysis reveals relative positions within a grid graph that are more susceptible to bottlenecks. It demonstrates the superiority of the protocol along paths that are not shortest paths while avoiding bottlenecks for simultaneous communication requests.
Abstract Quantum communication between distant parties is based on suitable instances of shared entanglement. For efficiency reasons, in an anticipated quantum network beyond point-to-point communication, it is preferable that many parties can communicate simultaneously over the underlying infrastructure; however, bottlenecks in the network may cause delays. Sharing of multi-partite entangled states between parties offers a solution, allowing for parallel quantum communication. Specifically for the two-pair problem, the butterfly network provides the first instance of such an advantage in a bottleneck scenario. In this paper, we propose a more general method for establishing EPR pairs in arbitrary networks. The main difference from standard repeater network approaches is that we use a graph state instead of maximally entangled pairs to achieve long-distance simultaneous communication. We demonstrate how graph-theoretic tools, and specifically local complementation, help decrease the number of required measurements compared to usual methods applied in repeater schemes. We examine other examples of network architectures, where deploying local complementation techniques provides an advantage. We finally consider the problem of extracting graph states for quantum communication via local Clifford operations and Pauli measurements, and discuss that while the general problem is known to be NP-complete, interestingly, for specific classes of structured resources, polynomial time algorithms can be identified.
Quantum communication between distant parties is based on suitable instances of shared entanglement. For efficiency reasons, in an anticipated quantum network beyond point-to-point communication, it is preferable that many parties can communicate simultaneously over the underlying infrastructure; however, bottlenecks in the network may cause delays. Sharing of multi-partite entangled states between parties offers a solution, allowing for parallel quantum communication. Specifically for the two-pair problem, the butterfly network provides the first instance of such an advantage in a bottleneck scenario. In this paper, we propose a more general method for establishing EPR pairs in arbitrary networks. The main difference from standard repeater network approaches is that we use a graph state instead of maximally entangled pairs to achieve long-distance simultaneous communication. We demonstrate how graph-theoretic tools, and specifically local complementation, help decrease the number of required measurements compared to usual methods applied in repeater schemes. We examine other examples of network architectures, where deploying local complementation techniques provides an advantage. We finally consider the problem of extracting graph states for quantum communication via local Clifford operations and Pauli measurements, and discuss that while the general problem is known to be NP-complete, interestingly, for specific classes of structured resources, polynomial time algorithms can be identified.
Quantum communication research has in recent years shifted to include multipartite networks for which questions of quantum network routing naturally emerge. To understand the potential for multipartite routing, we focus on the most promising architectures for future quantum networks---those connecting nodes close to each other. Nearest-neighbor networks, such as rings, lines, and grids, have been studied under different communication scenarios to facilitate the sharing of quantum resources especially in the presence of bottlenecks. We analyze the potential of nearest-neighbor entangling gate quantum networks and identify some serious limitations by demonstrating that rings and lines cannot overcome common bottleneck communication problems.
Distributing entanglement among multiple users is a fundamental problem in quantum networks, requiring an efficient solution. In this work, a protocol is proposed for extracting maximally entangled ($|{\text{GHZ}}_{n}\ensuremath{\rangle}$) states for any number of parties in a quantum network. It is based on the graph-state formalism and requires minimal assumptions on the network state. The protocol only requires local measurements at the network nodes and just a single-qubit memory per user. Existing protocols on bipartite entanglement routing are also improved for specific nearest-neighbor network architectures. To this end, the concept of majorization is utilized to establish a hierarchy among different paths in a network based on their efficacy. This approach utilizes the symmetry of the underlying graph state to obtain better-performing algorithms.
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.
Quantum networks will rely on entanglement distribution to enable multi-user applications such as distributed quantum computing and cryptography. While multipartite entanglement distribution routing protocols have been extensively studied on idealised grid topologies, less is understood about how real network structure shapes their performance and resource requirements. We present a systematic study of four routing protocols for multipartite entanglement distribution, each characterised by the number of paths (single-path and multi-path) and routing strategy (star-based and tree-based), over 81 real network topologies. We identified four distinct topology-dependent performance regimes, where: (i) all protocols perform poorly, (ii) tree-based protocols dominate, (iii) multi-path protocols dominate, or (iv) all protocols perform well. By correlating clusters with graph metrics, we also provide structural explanations for the varied performance of specific protocols. Additionally, motivated by the anticipated high cost of repeaters, we investigated the impact of repeater trimming on the performance of multi-path protocols. Topology strongly governs how far repeater nodes can be removed from the network while maintaining a given performance (distribution rate). For instance, in networks where only 80% of nodes operate as repeaters, well-performing topologies are able to retain over 90% of the distribution rate; whereas sparse, weakly connected graphs exhibit rapid performance degradation, retaining less than half of the distribution rate. Our results provide a topology-aware framework for protocol selection and infrastructure optimisation in future quantum networks, bridging routing design with cost-aware deployment strategies.