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

Random routing and concentration in quantum switching networks

Rahul Ratan

Published Jan 1, 2008• 0 citations
OpenAlex

Abstract

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.

Related papers

Self-Routing Quantum Sparse Crossbar Packet Concentrators

Rahul Ratan, A. Yavuz Oruç

Quantum switching networks are derived from conventional switching networks by replacing the classical switches by quantum switches. We give the quantum circuit design and routing of an n \times m network, called a quantum concentrator that can direct quantum bit packets in arbitrary quantum states from any of its k inputs to some of its k outputs, where 1 \le k \le m \le n. Our designs are based on sparse crossbars which are rectangular grids of 2 \times 2 crosspoints. Sparse crossbar concentrator structures with theoretically minimum crosspoint complexities for any values of n and m are well known but no self-routing algorithms have been reported for such concentrators. We transform two such families of optimal concentrators, called fat-slim and banded sparse crossbars into quantum networks and provide self-routing algorithms for these families of concentrators. In this process, we extend the notion of packet concentration to a quantum network and design self-routing quantum crosspoints from quantum gates. We address issues critical to quantum operation like reversibility and localized self-routing and give a rigorous proof that quantum fat-slim and banded sparse crossbar concentrators are self-routable. The self-routing algorithms described in the paper can be used for both quantum and classical sparse crossbar concentrators by the linearity property of all quantum systems.

IEEE Transactions on Computers•Jun 23, 2010•7 citations

Quantum Switching Networks with Classical Routing

Rahul Ratan, Manish Kumar Shukla, A. Yavuz Oruç

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.

Conference on Information Sciences and Systems•Mar 1, 2007•10 citations

On Random Routing and its Application to Quantum Interconnection Networks

Rahul Ratan, Manish Shukla, A. Yavuz Oruç

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.

Conference on Information Sciences and Systems•Mar 1, 2006•2 citations

Quantum Switching Networks: Unicast and Multicast

Manish Shukla

Quantum switching networks are analogs of classical switching networks in which classical switches are replaced by quantum switches. These networks are used to switch quantum data among a set of quantum sources and receivers. They can also be used to efficiently switch classical data, and help overcome some limitations of classical switching networks by utilizing the unique properties of quantum information systems, such as superposition and parallelism. In this thesis, we design several such networks which can be broadly put in the following three categories: 1. Quantum unicast networks: We give the design of quantum Baseline network (QBN) which is a self-routing and unicast quantum packet switch that uses the Baseline topology. The classical version of the network blocks packets internally even when there are no output contentions and each input packet is addressed to a different output. The QBN uses the principles of quantum superposition and parallelism to overcome such blocking. Also, for assignments that have multiple input packets addressed to an output, this network creates a quantum superposition of all these packets on that output, ensuring that all packets have non-zero probabilities of being observed on that output. 2. Quantum concentrators: We introduce a new network called quantum concentrator, which is a key component of our quantum multicasting network design. This concentrator is also an n × n quantum switching network, to be denoted by n-QC, and which, for any m, 1 ≤ m ≤ n, routes arbitrary quantum states on any m of its inputs to its top m outputs. This network uses O(n log n) quantum gates, and has a gate level depth of O(log 2 n). We also give several variations of this network, the main ones being order-preserving and priority quantum concentrators. 3. Quantum multicast networks: We first design a quantum multicasting network, called a generalized quantum connector (GQC) which can be used to multicast quantum information from n input sources to n outputs. Since general quantum states cannot be copied due to the no-cloning theorem, this network actually multicasts superposed classical information packets, contained in a finite number of qubits at each input. Copying needed for such multicasting is obtained by Wootters and Zurek's quantum copying machines or controlled-not gates. This n-input and n-output (n × n) network, to be denoted by n-GQC, is recursively constructed using n/2-GQCs and uses O(n log 2 n) quantum gates. The time complexity of this network in terms of gate level depth is O(log 3 n). We also give two variations of this network which improve its behavior when routing multicast assignments that have multiple input packets contending for same outputs.

•Jan 1, 2010•0 citations

The Quantum Baseline Network

Manish Shukla, Rahul Ratan, A. Yavuz Oruç

We present the design of a self-routing quantum packet switch which improves on a previous design given by the authors [1]. Like the earlier design, this switch too routes packets represented by quantum bits (qubits) but it reduces the routing overhead per packet from O(log N) qubits to O(1) qubits by eliminating the need for an extra "dummy" inputoutput pair and their associated "dummy" packets at each 2 2 internal switch. The quantum self-routing switch creates a superposition of all the maximum size non-blocking subsets of input packets at its outputs, which cannot be achieved by any classical self-routing switching network that is internally blocking. In addition to the network design, we give a method to characterize the output quantum state of the switch using the concepts of frames and balanced matrices.

•Jan 1, 2005•6 citations

The design of a quantum Benes switch

Jung-Shian Li, Ching‐Fang Yang

In this paper, we propose a novel framework for building a NtimesN quantum Benes switch that can route quantum packets without blocking. Previous studies about quantum systems have discussed many switching algorithms including merge sorting (Cheng and Wang, 2006) or self-routing Banyan switch (Shukla et al., 2005) etc. We build a newly quantum parallel routing scheme that achieves internally conflict free and real-time path permutations by using the quantum logic circuit modules.

IEEE International Conference on Electron Devices and Solid-State Circuits (EDSSC)•Jan 1, 2007•0 citations
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.
Quantum switching networks are derived from conventional switching networks by replacing the classical switches by quantum switches. We give the quantum circuit design and routing of an n \times m network, called a quantum concentrator that can direct quantum bit packets in arbitrary quantum states from any of its k inputs to some of its k outputs, where 1 \le k \le m \le n. Our designs are based on sparse crossbars which are rectangular grids of 2 \times 2 crosspoints. Sparse crossbar concentrator structures with theoretically minimum crosspoint complexities for any values of n and m are well known but no self-routing algorithms have been reported for such concentrators. We transform two such families of optimal concentrators, called fat-slim and banded sparse crossbars into quantum networks and provide self-routing algorithms for these families of concentrators. In this process, we extend the notion of packet concentration to a quantum network and design self-routing quantum crosspoints from quantum gates. We address issues critical to quantum operation like reversibility and localized self-routing and give a rigorous proof that quantum fat-slim and banded sparse crossbar concentrators are self-routable. The self-routing algorithms described in the paper can be used for both quantum and classical sparse crossbar concentrators by the linearity property of all quantum systems.
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.
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.
Quantum switching networks are analogs of classical switching networks in which classical switches are replaced by quantum switches. These networks are used to switch quantum data among a set of quantum sources and receivers. They can also be used to efficiently switch classical data, and help overcome some limitations of classical switching networks by utilizing the unique properties of quantum information systems, such as superposition and parallelism. In this thesis, we design several such networks which can be broadly put in the following three categories: 1. Quantum unicast networks: We give the design of quantum Baseline network (QBN) which is a self-routing and unicast quantum packet switch that uses the Baseline topology. The classical version of the network blocks packets internally even when there are no output contentions and each input packet is addressed to a different output. The QBN uses the principles of quantum superposition and parallelism to overcome such blocking. Also, for assignments that have multiple input packets addressed to an output, this network creates a quantum superposition of all these packets on that output, ensuring that all packets have non-zero probabilities of being observed on that output. 2. Quantum concentrators: We introduce a new network called quantum concentrator, which is a key component of our quantum multicasting network design. This concentrator is also an n × n quantum switching network, to be denoted by n-QC, and which, for any m, 1 ≤ m ≤ n, routes arbitrary quantum states on any m of its inputs to its top m outputs. This network uses O(n log n) quantum gates, and has a gate level depth of O(log 2 n). We also give several variations of this network, the main ones being order-preserving and priority quantum concentrators. 3. Quantum multicast networks: We first design a quantum multicasting network, called a generalized quantum connector (GQC) which can be used to multicast quantum information from n input sources to n outputs. Since general quantum states cannot be copied due to the no-cloning theorem, this network actually multicasts superposed classical information packets, contained in a finite number of qubits at each input. Copying needed for such multicasting is obtained by Wootters and Zurek's quantum copying machines or controlled-not gates. This n-input and n-output (n × n) network, to be denoted by n-GQC, is recursively constructed using n/2-GQCs and uses O(n log 2 n) quantum gates. The time complexity of this network in terms of gate level depth is O(log 3 n). We also give two variations of this network which improve its behavior when routing multicast assignments that have multiple input packets contending for same outputs.
We present the design of a self-routing quantum packet switch which improves on a previous design given by the authors [1]. Like the earlier design, this switch too routes packets represented by quantum bits (qubits) but it reduces the routing overhead per packet from O(log N) qubits to O(1) qubits by eliminating the need for an extra "dummy" inputoutput pair and their associated "dummy" packets at each 2 2 internal switch. The quantum self-routing switch creates a superposition of all the maximum size non-blocking subsets of input packets at its outputs, which cannot be achieved by any classical self-routing switching network that is internally blocking. In addition to the network design, we give a method to characterize the output quantum state of the switch using the concepts of frames and balanced matrices.