Quantum routing with fast reversals
summary
A time‑independent XX+local field Hamiltonian implements state reversal on an n‑spin chain in time π/4·(n+1), versus swap‑based routing (swap time 3π/4) giving a normalized 3× speedup; a lower bound from entanglement capacity gives time ≥ n/α with α≈1.912. Sparse k‑swap permutations route in time ≤ n/3 + k^2 on a path. A recursive tripartite binary sort sorts bits in time (1/2 − ε)n with ε≈0.017, yielding worst‑case routing ≤ (1 − 2ε)n and empirical performance ≈ 2n/3.
AI-written summary · about
chapters (14)
- 0:00Start
- 0:33Connectivity Constrains Gate Operations
- 1:23What Is Routing
- 3:33State Reversal
- 3:43What Exactly Is State Reversal
- 5:38The Entanglement Capacity Theorem
- 6:44Entanglement Capacity Theorem
- 8:01Sparse Permutation
- 8:14Six Sparse Permutation
- 9:20Routing Algorithm for K-Sparse Permutations on Chains
- 10:43Binary Sorting Algorithm
- 12:02Divide and Conquer Strategy
- 12:38Tripartite Binary Sort
- 18:02Gate-Based Quantum Routing
related talks
01h 05mVerifiable quantum advantage: old and new ideas
46mSymmetries, Graph Properties, and Quantum Speedups
30mHow to fault-tolerantly realize any quantum circuit with local operations
45mQuantum Pseudo-Randomness From Domain Walls and Spectral Gaps
51mOn constant T-depth circuits
37m(Sub)Exponential Advantage of Adiabatic Quantum Computation With No Sign Problem
01h 06mQuantum Algorithms for Approximating Partition Functions
46mOn Scrambling Times of Quantum Systems, Including Black Holes