Quantum routing with fast reversals

Abstract

We present methods for implementing arbitrary permutations of qubits under interaction constraints. Our protocols make use of previous methods for rapidly reversing the order of qubits along a path. Given nearest-neighbor interactions on a path of length $n$, we show that there exists a constant $\epsilon \approx 0.034$ such that the quantum routing time is at most $(1-\epsilon )n$, whereas any swap-based protocol needs at least time $n-1$. This represents the first known quantum advantage over swap-based routing methods and also gives improved quantum routing times for realistic architectures such as grids. Furthermore, we show that our algorithm approaches a quantum routing time of $2n/3$ in expectation for uniformly random permutations, whereas swap-based protocols require time $n$ asymptotically. Additionally, we consider sparse permutations that route $k\le n$ qubits and give algorithms with quantum routing time at most $n/3+O(k^2)$ on paths and at most $2r/3+O(k^2)$ on general graphs with radius $r$.

arXiv comment26 pages, 10 figures. Updated version forthcoming in Quantum

References in corpus (8)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Superconducting Qubits: Current State of Play
• Large Scale Modular Quantum Computer Architecture with Atomic Memory and Photonic Interconnects
• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Optimal simulation of two-qubit Hamiltonians using general local operations
• Interaction cost of non-local gates
• Quantum computation via translation-invariant operations on a chain of qubits
• Circuit Transformations for Quantum Architectures

Cited by in corpus (9)

• Native two-qubit gates in fixed-coupling, fixed-frequency transmons beyond cross-resonance interaction
• Advantages and limitations of quantum routing
• Quantum Routing with Teleportation
• Lift-Connected Surface Codes
• Computing n-time correlation functions without ancilla qubits
• Recursive Methods for Synthesizing Permutations on Limited-Connectivity Quantum Computers
• A Quantum Simulator Based on Locally Controlled Logical Systems
• Transfer and routing of Gaussian states through quantum complex networks with and without community structure
• Quantum Routing and Entanglement Dynamics Through Bottlenecks