Random Routing and Concentration in Quantum Switching Networks

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 <italic>n &times; n</italic> 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 <italic>n &times; n</italic> 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 <italic>n</italic>-1) stages and bit controlled self-routing on the last

log <italic>n</italic> 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<super><italic>n</italic>-1</super> 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 <italic>every</italic> 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 &times; 2 switches or crosspoints,

with the switches arranged such that any <italic>k</italic> inputs can be connected

to some <italic>k</italic> 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 <italic>n &times; n </italic> quantum non-blocking

switch. We assume that each packet is a superposition of <italic>m</italic> 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 <italic>m</italic> 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 <italic>m</italic>=9 the probability of a

non-contending output pattern occurring in the quantum output is

greater than 0.99 for all <italic>n</italic> up to 64.