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.
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.
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.
Quantum communications promises major changes in today’s communication networks by sending qubits over long distances. These qubits enable large-scale quantum computing or information-theoretically secure distribution of symmetrical keys. One of the main enablers is quantum teleportation, which makes sending quantum information between two nodes possible even when they are far apart. From these nodes, one can build a larger quantum network, but due to the nature of quantum physics, certain tasks that are well understood in classical networks, such as routing, cannot be handled in a similar way. Our work focuses on modifying a previously created model for a ring-like quantum network and assessing the effect of introducing a new node type. Our results show that this node can alter properties of the underlying network. We also look at the possibilities of modeling the capacity of the network as well as the availability of the newly introduced edges, which open interesting questions for future research.
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.
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.
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.
Over the past 50 years, conventional network routing design has undergone substantial growth, evolving from small networks with static nodes to large systems connecting billions of devices. This progress has been achieved through the separation of concerns principle, which entails integrating network functionalities into a graph or random network design and employing specific network protocols to facilitate diverse communication capabilities. This paper aims to highlight the potential of designing routing techniques for quantum networks, which exhibit unique properties due to quantum mechanics. Quantum routing design requires a substantial deviation from conventional network design protocols since it must account for the unique features of quantum entanglement and information. However, implementing these techniques poses significant challenges, such as decoherence and noise in quantum systems, restricted communication ranges, and highly specialized hardware prerequisites. The paper commences by examining essential research on quantum routing design methods and proceeds to cover fundamental aspects of quantum routing, associated quantum operations, and the steps necessary for building efficient and robust quantum networks. This paper summarizes the present state of quantum routing techniques, including their principles, protocols, and challenges, highlighting potential applications and future directions.