Advantages and limitations of quantum routing
arXiv:2206.01766 · doi:10.1103/PRXQuantum.4.010313
Abstract
The Swap gate is a ubiquitous tool for moving information on quantum hardware, yet it can be considered a classical operation because it does not entangle product states. Genuinely quantum operations could outperform Swap for the task of permuting qubits within an architecture, which we call routing. We consider quantum routing in two models: (1) allowing arbitrary two-qubit unitaries, or (2) allowing Hamiltonians with norm-bounded interactions. We lower bound the circuit depth or time of quantum routing in terms of spectral properties of graphs representing the architecture interaction constraints, and give a generalized upper bound for all simple connected -vertex graphs. In particular, we give conditions for a superpolynomial classical-quantum routing separation, which exclude graphs with a small spectral gap and graphs of bounded degree. Finally, we provide examples of a quadratic separation between gate-based and Hamiltonian routing models with a constant number of local ancillas per qubit and of an speedup if we also allow fast local interactions.
arXiv comment45 pages, 7 figures
References in corpus (40)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum Communication Through an Unmodulated Spin Chain
- Large Scale Modular Quantum Computer Architecture with Atomic Memory and Photonic Interconnects
- Lieb-Robinson bounds and the generation of correlations and topological quantum order
- Demonstration of the trapped-ion quantum-CCD computer architecture
- Perfect Transfer of Arbitrary States in Quantum Spin Networks
- Quantum Communication through Spin Chain Dynamics: an Introductory Overview
- Optimal Quantum Circuits for General Two-Qubit Gates
- Lieb-Robinson Bounds and the Exponential Clustering Theorem
- Mirror Inversion of Quantum States in Linear Registers
- Robust Quantum State Transfer in Random Unpolarized Spin Chains
- Spin Chains as Perfect Quantum State Mirrors
- Efficient Distributed Quantum Computing
- Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
- Layered architecture for quantum computing
- Entanglement capabilities of non-local Hamiltonians
- Quantum state transfer via the ferromagnetic chain in a spatially modulated field
- Perfect state transfer on a spin-chain without state initialization
- On the capacities of bipartite Hamiltonians and unitary gates
- Qubit Teleportation and Transfer across Antiferromagnetic Spin Chains
- Quantum Circuits assisted by LOCC: Transformations and Phases of Matter
- Non-Perturbative Entangling Gates between Distant Qubits using Uniform Cold Atom Chains
- Globally controlled quantum wires for perfect qubit transport, mirroring and computing
- Quantum Circuit Placement
- Optimal simulation of two-qubit Hamiltonians using general local operations
- Entanglement rates and area laws
- Interaction cost of non-local gates
- Entanglement area laws for long-range interacting systems
- Upper bounds on entangling rates of bipartite Hamiltonians
- Quantum Skew Divergence
- Quantum computation via translation-invariant operations on a chain of qubits
- Signaling and Scrambling with Strongly Long-Range Interactions
- A quantum primality test with order finding
- Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
- Robustness of QMA against witness noise
- Reversible simulation of bipartite product Hamiltonians
- Quantum routing with fast reversals
- Entanglement bounds on the performance of quantum computing architectures
- Nearly optimal time-independent reversal of a spin chain
- Asymptotic entanglement capacity of the Ising and anisotropic Heisenberg interactions