Capital Area Theory Seminar
Theoretical models of quantum computation usually assume that 2-qubit gates can be performed between arbitrary pairs of qubits. However, in practice, scalable quantum architectures have qubit connectivity constraints. These are usually specified by a graph, with vertices corresponding to qubits, and edges corresponding to pairs of qubits between which gates can be performed. Performing quantum algorithms on such architectures requires modifying quantum circuits to respect these connectivity constraints, while minimizing the circuit depth overhead. A natural way to do this is by rearranging qubits on the connectivity graph, which is analogous to the classical problem of routing with swaps. In this talk, I will discuss how using quantum teleportation can provide speedups over swap-based methods. Further, I will describe an example of an interaction graph for which teleportation gives a logarithmic speedup in the worst-case routing time over SWAP-based routing. I will also present a new swap-based algorithm for sparse routing, and use it to show bounds on the speedup afforded by quantum teleportation.