Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2103.03264 · Quantum

Quantum routing with fast reversals

Aniruddha Bapat, Andrew M. Childs, Alexey Vyacheslavovich Gorshkov, Samuel King, Eddie Schoute, Hrishee Shastri

Published Aug 31, 2021• 18 citations
arXivHTMLPDF

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 ϵ≈0.034 such that the quantum routing time is at most (1−ϵ)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≤n qubits and give algorithms with quantum routing time at most n/3+O(k2) on paths and at most 2r/3+O(k2) on general graphs with radius r .

DOI
10.22331/q-2021-08-31-533

Related papers

Advantages and Limitations of Quantum Routing

Aniruddha Bapat, Andrew M. Childs, Alexey Vyacheslavovich Gorshkov +1 more

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 $n$-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 $Ω(n)$ speedup if we also allow fast local interactions.

arXiv:2206.01766•PRX Quantum•Feb 1, 2023•26 citations

Quantum routing with teleportation

Dhruv Devulapalli, Eddie Schoute, Aniruddha Bapat +2 more

We study the problem of implementing arbitrary permutations of qubits under interaction constraints in quantum systems that allow for arbitrarily fast local operations and classical communication (LOCC). In particular, we show examples of speedups over swap-based and more general unitary routing methods by distributing entanglement and using LOCC to perform quantum teleportation. We further describe an example of an interaction graph for which teleportation gives a logarithmic speedup in the worst-case routing time over swap-based routing. We also study limits on the speedup afforded by quantum teleportation—showing an O ( N log N ) upper bound on the separation in routing time for any interaction graph—and give tighter bounds for some common classes of graphs. Published by the American Physical Society 2024

arXiv:2204.04185•Physical Review Research•Sep 18, 2024•26 citations

Locality-aware Qubit Routing for the Grid Architecture

Avah Banerjee, Xin Liang, R. Tohid

Due to the short decohorence time of qubits available in the NISQ-era, it is essential to pack (minimize the size and or the depth of) a logical quantum circuit as efficiently as possible given a sparsely coupled physical architecture. In this work we introduce a locality-aware qubit routing algorithm based on a graph theoretic framework. Our algorithm is designed for the grid and certain “grid-like” architectures. We experimentally show the competitiveness of algorithm by comparing it against the approximate token swapping algorithm, which is used as a primitive in many state-of-the-art quantum transpilers. Our algorithm produces circuits of comparable depth (better on random permutations) while being an order of magnitude faster than a typical implementation of the approximate token swapping algorithm.

arXiv:2203.11333•IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2022•7 citations

Algorithmic Theory of Qubit Routing in the Linear Nearest Neighbor Architectures

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama +2 more

The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We show that the qubit routing problem on a path can be solved in a fixed-parameter time where the number of two-qubit gates is a parameter. (3) We show that the qubit routing problem on a path can be solved in polynomial time if each qubit is involved in at most one two-qubit gate.

ACM Transactions on Quantum Computing•Mar 8, 2025•2 citations

Nearly optimal time-independent reversal of a spin chain

Aniruddha Bapat, Eddie Schoute, Alexey Vyacheslavovich Gorshkov +1 more

We propose a time-independent Hamiltonian protocol for the reversal of qubit ordering in a chain of N spins.Our protocol has an easily implementable nearest-neighbor, transverse-field Ising model Hamiltonian with timeindependent, nonuniform couplings.Under appropriate normalization, we implement this state reversal three times faster than a naive approach using SWAP gates, in time comparable to a protocol of Raussendorf [Phys. Rev. A 72, 052301 (2005)] that requires dynamical control. We also prove lower bounds on state reversal by using results on the entanglement capacity of Hamiltonians and show that we are within a factor 1.502(1 + 1/N ) of the shortest time possible.Our lower bound holds for all nearest-neighbor qubit protocols with arbitrary finite ancilla spaces and local operations and classical communication.We give numerical evidence that the fast reversal protocols are more robust to noise than a SWAP-based reversal.Finally, we extend our protocol to an infinite family of nearest-neighbor, time-independent Hamiltonian protocols for state reversal.This includes chains with nearly uniform coupling that may be especially feasible for experimental implementation.

arXiv:2003.02843•Physical Review Research•Feb 22, 2022•8 citations

Circuit Transformations for Quantum Architectures

Andrew M. Childs, Eddie Schoute, Cem M. Unsal

Quantum computer architectures impose restrictions on qubit interactions. We propose efficient circuit transformations that modify a given quantum circuit to fit an architecture, allowing for any initial and final mapping of circuit qubits to architecture qubits. To achieve this, we first consider the qubit movement subproblem and use the ROUTING VIA MATCHINGS framework to prove tighter bounds on parallel routing. In practice, we only need to perform partial permutations, so we generalize ROUTING VIA MATCHINGS to that setting. We give new routing procedures for common architecture graphs and for the generalized hierarchical product of graphs, which produces subgraphs of the Cartesian product. Secondly, for serial routing, we consider the TOKEN SWAPPING framework and extend a 4-approximation algorithm for general graphs to support partial permutations. We apply these routing procedures to give several circuit transformations, using various heuristic qubit placement subroutines. We implement these transformations in software and compare their performance for large quantum circuits on grid and modular architectures, identifying strategies that work well in practice.

arXiv:1902.09102•Leibniz international proceedings in informatics•Jan 1, 2019•124 citations
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 ϵ≈0.034 such that the quantum routing time is at most (1−ϵ)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≤n qubits and give algorithms with quantum routing time at most n/3+O(k2) on paths and at most 2r/3+O(k2) on general graphs with radius r .
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 nnn-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 Ω(n)Ω(n)Ω(n) speedup if we also allow fast local interactions.
We study the problem of implementing arbitrary permutations of qubits under interaction constraints in quantum systems that allow for arbitrarily fast local operations and classical communication (LOCC). In particular, we show examples of speedups over swap-based and more general unitary routing methods by distributing entanglement and using LOCC to perform quantum teleportation. We further describe an example of an interaction graph for which teleportation gives a logarithmic speedup in the worst-case routing time over swap-based routing. We also study limits on the speedup afforded by quantum teleportation—showing an O ( N log N ) upper bound on the separation in routing time for any interaction graph—and give tighter bounds for some common classes of graphs. Published by the American Physical Society 2024
Due to the short decohorence time of qubits available in the NISQ-era, it is essential to pack (minimize the size and or the depth of) a logical quantum circuit as efficiently as possible given a sparsely coupled physical architecture. In this work we introduce a locality-aware qubit routing algorithm based on a graph theoretic framework. Our algorithm is designed for the grid and certain “grid-like” architectures. We experimentally show the competitiveness of algorithm by comparing it against the approximate token swapping algorithm, which is used as a primitive in many state-of-the-art quantum transpilers. Our algorithm produces circuits of comparable depth (better on random permutations) while being an order of magnitude faster than a typical implementation of the approximate token swapping algorithm.
The qubit routing problem, also known as the swap minimization problem, is a (classical) combinatorial optimization problem that arises in the design of compilers of quantum programs. We study the qubit routing problem from the viewpoint of theoretical computer science, while most of the existing studies investigated the practical aspects. We concentrate on the linear nearest neighbor (LNN) architectures of quantum computers, in which the graph topology is a path. Our results are three-fold. (1) We prove that the qubit routing problem is NP-hard. (2) We show that the qubit routing problem on a path can be solved in a fixed-parameter time where the number of two-qubit gates is a parameter. (3) We show that the qubit routing problem on a path can be solved in polynomial time if each qubit is involved in at most one two-qubit gate.
We propose a time-independent Hamiltonian protocol for the reversal of qubit ordering in a chain of N spins.Our protocol has an easily implementable nearest-neighbor, transverse-field Ising model Hamiltonian with timeindependent, nonuniform couplings.Under appropriate normalization, we implement this state reversal three times faster than a naive approach using SWAP gates, in time comparable to a protocol of Raussendorf [Phys. Rev. A 72, 052301 (2005)] that requires dynamical control. We also prove lower bounds on state reversal by using results on the entanglement capacity of Hamiltonians and show that we are within a factor 1.502(1 + 1/N ) of the shortest time possible.Our lower bound holds for all nearest-neighbor qubit protocols with arbitrary finite ancilla spaces and local operations and classical communication.We give numerical evidence that the fast reversal protocols are more robust to noise than a SWAP-based reversal.Finally, we extend our protocol to an infinite family of nearest-neighbor, time-independent Hamiltonian protocols for state reversal.This includes chains with nearly uniform coupling that may be especially feasible for experimental implementation.
Quantum computer architectures impose restrictions on qubit interactions. We propose efficient circuit transformations that modify a given quantum circuit to fit an architecture, allowing for any initial and final mapping of circuit qubits to architecture qubits. To achieve this, we first consider the qubit movement subproblem and use the ROUTING VIA MATCHINGS framework to prove tighter bounds on parallel routing. In practice, we only need to perform partial permutations, so we generalize ROUTING VIA MATCHINGS to that setting. We give new routing procedures for common architecture graphs and for the generalized hierarchical product of graphs, which produces subgraphs of the Cartesian product. Secondly, for serial routing, we consider the TOKEN SWAPPING framework and extend a 4-approximation algorithm for general graphs to support partial permutations. We apply these routing procedures to give several circuit transformations, using various heuristic qubit placement subroutines. We implement these transformations in software and compare their performance for large quantum circuits on grid and modular architectures, identifying strategies that work well in practice.