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, which can introduce polynomial depth overheads. Compiling quantum algorithms to work on scalable architectures therefore requires optimizing arrangements of gates and qubits to minimize these overheads. In this talk, I will discuss the problem of implementing arbitrary permutations of qubits under interaction constraints in quantum systems that allow for fast local operations and classical communication (LOCC). I will show examples of speedups over SWAP-based methods by using fast measurement and classical feedback to perform quantum teleportation. Further, I will describe an example of an interaction graph for which fast LOCC gives a logarithmic speedup in the worst-case routing time over SWAP-based routing. I will also discuss limits on the speedup afforded by quantum teleportation.
Pizza and drinks served after the talk.
