On Random Routing and its Application to Quantum Interconnection Networks

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.