We present a framework for analyzing random routing on multistage interconnection networks and show its relation to routing on quantum interconnects proposed earlier by the authors. Quantum interconnects operate on quantum bits (qubits) and have the potential to form non-blocking networks with simple routing schemes by exploiting properties like superposition. Broadly speaking, quantum circuits operate probabilistically, and our random routing model on classical networks is a step in the direction of characterizing the design of such quantum networks. Specifically, we use the probability settings for individual switches to obtain the rate matrix for the network and show how this information is automatically encoded by the quantum network in its output state. Also, the inverse problem of finding the switch probability parameters given a rate matrix is shown to have direct relation to quantum interconnect design.
We present a framework for analyzing random routing on multistage interconnection networks and show its relation to routing on quantum interconnects proposed earlier by the authors. Quantum interconnects operate on quantum bits (qubits) and have the potential to form non-blocking networks with simple routing schemes by exploiting properties like superposition. Broadly speaking, quantum circuits operate probabilistically, and our random routing model on classical networks is a step in the direction of characterizing the design of such quantum networks. Specifically, we use the probability settings for individual switches to obtain the rate matrix for the network and show how this information is automatically encoded by the quantum network in its output state. Also, the inverse problem of finding the switch probability parameters given a rate matrix is shown to have direct relation to quantum interconnect design.
Flexible distribution of data in the form of quantum bits or qubits among spatially separated entities is an essential component of envisioned scalable quantum computing architectures. Accordingly, we consider the problem of dynamically permuting groups of quantum bits, i.e., qubit packets, using networks of reconfigurable quantum switches. We demonstrate and then explore the equivalence between the quantum process of creation of packet superpositions and the process of randomly routing packets in the corresponding classical network. In particular, we consider an n × n Baseline network for which we explicitly relate the pairwise input-output routing probabilities in the classical random routing scenario to the probability amplitudes of the individual packet patterns superposed in the quantum output state. We then analyze the effect of using quantum random routing on a classically non-blocking configuration like the Benes network. We prove that for an n × n quantum Benes network, any input packet assignment with no output contention is probabilistically self-routable. In particular, we prove that with random routing on the first (log n-1) stages and bit controlled self-routing on the last log n stages of a quantum Benes network, the output packet pattern corresponding to routing with no blocking is always present in the output quantum state with a non-zero probability. We give a lower bound on the probability of observing such patterns on measurement at the output and identify a class of 2 n-1 permutation patterns for which this bound is equal to 1, i.e., for all the permutation patterns in this class the following is true: in every pattern in the quantum output assignment all the valid input packets are present at their correct output addresses. In the second part of this thesis we give the complete design of quantum sparse crossbar concentrators. Sparse crossbar concentrators are rectangular grids of simple 2 × 2 switches or crosspoints, with the switches arranged such that any k inputs can be connected to some k outputs. We give the design of the quantum crosspoints for such concentrators and devise a self-routing method to concentrate quantum packets. Our main result is a rigorous proof that certain crossbar structures, namely, the fat-slim and banded quantum crossbars allow, without blocking, the realization of all concentration patterns with self-routing. In the last part we consider the scenario in which quantum packets are queued at the inputs to an n × n quantum non-blocking switch. We assume that each packet is a superposition of m classical packets. Under the assumption of uniform traffic, i.e., any output is equally likely to be accessed by a packet at an input we find the minimum value of m such that the output quantum state contains at least one packet pattern in which no two packets contend for the same output. Our calculations show that for m=9 the probability of a non-contending output pattern occurring in the quantum output is greater than 0.99 for all n up to 64.
This paper investigates the application of quantum walks to the design of routing protocols for computer networks. Traditional routing algorithms, reliant on classical probability and exhaustive search, often suffer from inefficiencies and vulnerabilities, particularly in large and complex network topologies. Quantum walks, leveraging the principles of superposition and interference, offer a fundamentally different approach. This research proposes a framework for encoding network topologies within a quantum walk environment and utilizing the walk's inherent properties to explore the network and identify optimal paths. The core of the approach lies in mapping network nodes to quantum bits (Qubits) and utilizing the walk's probabilistic nature to simulate path exploration. We explore key aspects of this approach, including walk initialization, boundary conditions, and measurement strategies. The potential benefits of this method, such as reduced latency, improved bandwidth utilization, and enhanced resilience to network disruptions, are discussed. We present a theoretical model for the routing protocol and analyze its performance characteristics, focusing on metrics like path length, traversal time, and success rate. While this work is primarily a theoretical exploration, it lays a foundation for future research and development of practical quantum routing solutions.
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.
Over the course of the last five decades, there has been substantial growth in conventional network routing design, transitioning from small static node networks to vast systems connecting billions of devices. This evolution has been facilitated by the separation of concerns principle, which involves integrating network functionalities into graph or random network designs and utilizing specific protocols to enable diverse communication capabilities. The landscape of quantum networks is rapidly evolving, presenting new paradigms in information transmission and processing. Routing protocols play a pivotal role in establishing efficient communication pathways within quantum networks, enabling the transmission of quantum states and entanglement across interconnected nodes. The objective of this paper is to shed light on existing entanglement routing design techniques within quantum networks. The design of quantum entanglement routing necessitates a departure from conventional network protocols due to its unique considerations of quantum entanglement and entanglement swapping. However, the implementation of these techniques is fraught with significant challenges, including quantum system decoherence and noise, limitations on communication ranges, and the need for specialized hardware. The paper initiates by surveying critical research in quantum routing design techniques, then delves into essential aspects of the routing concept, associated quantum operations, and the step-wise process for establishing efficient and resilient quantum networks. In summary, this paper provides an overview of the current landscape of quantum entanglement routing techniques. It outlines their core principles, protocols, and challenges, while also highlighting potential applications and charting future directions for research and development.
Entanglement routing in near-term quantum networks consists of choosing the optimal sequence of short-range entanglements to combine through swapping operations to establish end-to-end entanglement between two distant nodes. Similar to traditional routing technologies, a quantum routing protocol uses network information to choose the best paths to satisfy a set of end-to-end entanglement requests. However, in addition to network state information, a quantum routing protocol must also take into account the requested entanglement fidelity, the probabilistic nature of swapping operations, and the short lifetime of entangled states. In this work, we formulate a practical entanglement routing problem and analyze and categorize the main approaches to address it, drawing comparisons to, and inspiration from, classical network routing strategies where applicable. We classify and discuss the studied quantum routing schemes into reactive, proactive, and hybrid routing.
Flexible distribution of data in the form of quantum bits (qubits) amongst spatially separated entities is an essential component of envisioned scalable quantum computing architectures. Since qubits cannot be copied, this operation of moving qubits can be relatively costly in terms of resources. Moreover, implementation of quantum gates requires precise and extensive classical control and computation too. Accordingly, we consider the problem of dynamically permuting groups of qubits, i.e., qubit packets using reconfigurable quantum switches in which routing information is calculated classically as a possible way to reduce this cost. We design a 2 x 2 switch based on the controlled-swap quantum gate and show that if switch settings are determined using efficient classical algorithms, then quantum switches can be mapped onto classical non-blocking interconnection switch topologies with low cost by using this switch. Specific quantum switch designs for the optimal Benes network and the planar Spanke-Bcnes network are given.