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:2505.16948 · PRX Quantum

Quantum Routing and Entanglement Dynamics Through Bottlenecks

Dhruv Devulapalli, Chao Yin, Andrew Y. Guo, Eddie Schoute, Andrew M. Childs, Alexey Vyacheslavovich Gorshkov, Andrew Lucas

Published Dec 2, 2025• 0 citations
arXivHTMLPDF

Abstract

To implement arbitrary quantum circuits in architectures with restricted interactions, one may effectively simulate all-to-all connectivity by routing quantum information. We consider the entanglement dynamics and routing between two regions only connected through an intermediate “bottleneck” region with few qubits. In such systems, where the entanglement rate is restricted by a vertex boundary rather than an edge boundary of the underlying interaction graph, existing results such as the small incremental entangling theorem give only a trivial constant lower bound on the routing time (the minimum time to perform an arbitrary permutation). We significantly improve the lower bound on the routing time in systems with a vertex bottleneck. Specifically, for any system with two regions L , R with N L , N R qubits, respectively, coupled only through an intermediate region C with N C qubits, for any δ > 0 we show a lower bound of Ω ( N R 1 − δ / N L N C ) on the Hamiltonian quantum routing time when using piecewise time-independent Hamiltonians, or time-dependent Hamiltonians subject to a smoothness condition. We also prove an upper bound on the average amount of bipartite entanglement between L and C , R that can be generated in time t by such architecture-respecting Hamiltonians in systems constrained by vertex bottlenecks, improving the scaling in the system size from O ( N L t ) to O ( N L t ) . As a special case, when applied to the star graph (i.e., one vertex connected to N leaves), we obtain an Ω ( N 1 − δ ) lower bound on the routing time and on the time to prepare N / 2 Bell pairs between the vertices. We also show that, in systems of free particles, we can route optimally on the star graph in time Θ ( N ) using Hamiltonian quantum routing, obtaining a speedup over gate-based routing, which takes time Θ ( N ) .

DOI
10.1103/7b1x-hjcy

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•21 citations

Locality and Complexity in Quantum Information Dynamics

Dhruv Devulapalli

Locality constrains the flow of information between different parts of many-body quantum systems. In quantum computers, this affects the ability to perform arbitrary interactions for quantum information processing tasks. A crucial challenge for scalable quantum architectures is thus to minimize the overheads due to locality constraints. Locality constraints also affect the way information and entanglement can be spread in many body quantum systems, and our ability to make predictions about such systems. One way to implement arbitrary interactions in locality-constrained architectures is by permuting qubits, also known as performing quantum routing. In the first part of this thesis, we investigate quantum routing strategies using emerging architectural capabilities beyond swap gates. We first investigate the use of mid-circuit measurements and classical feedback, which enable quantum teleportation. We prove upper bounds on the speedup afforded by the use of quantum teleportation for routing. We also design architectural connectivities which can exploit teleportation-based speedups. We then consider quantum routing by continuous-time Hamiltonian evolution, designing a routing algorithm that achieves a polynomial speedup in routing time over gate-based routing methods in architectures with a bottleneck, which is an intermediate region that constrains interactions between the rest of the device. We improve the lower bound on the time taken for routing in such systems, and develop a matching upper bound on the closely related task of generating and distributing entanglement. In the second part of this thesis, we investigate the behavior of finite-sized systems evolving by local Hamiltonians for a long duration. A major direction of research in condensed matter physics is the investigation of whether isolated systems thermalize (i.e., reach a state of thermal equilibrium). Various theoretical proposals such as information scrambling, entanglement between subsystems, and the eigenstate thermalization hypothesis have attempted to explain the conditions under which systems equilibrate. At the same time, notable counter-examples to thermalization have been found, such as systems that are integrable, exhibit many-body localization, or quantum many-body scars. We approach this question from a complexity-theoretic perspective. We show that the problem of deciding whether or not observables equilibrate to a givenvalue is PSPACE-complete. We also show that deciding whether observables relax to the thermal equilibrium value is contained in PSPACE, and is PSPACE-hard under quantum polynomial time reductions. These problems are thus intractable even for a quantum computer. Our results indicate that the proposed conditions leading to thermalization are either difficult to decide, or are not generic indicators of thermalization.

•Jan 1, 2025•0 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•12 citations

Entanglement Routing and Bottlenecks in Grid Networks

Vaisakh Mannalath, Anirban Pathak

Abstract Distributing entangled states among users is a fundamental problem in quantum networks. Existing protocols like protocol introduced in [npj Quantum Inf. 2019, 5, 76] use graph theoretic tools like local complementation to optimize the number of measurements required to extract any Bell pair among the network users. Such a protocol relies on finding the shortest path between the users. Here, it is established that, in general, the most optimal path to perform the protocol is not along the shortest path. Specific examples of this advantage are provided on networks of size as small as 12 qubits. Bottlenecks in establishing simultaneous Bell pairs in nearest‐neighbor architectures are also explored. Recent results suggesting the unsuitability of the line and ring networks for the implementation of quantum networks due to the bottlenecks are revisited, and using local equivalency relations from graph theory, it's hinted that even grid graphs are not exempted from bottleneck issues. Finally, bottlenecks are simulated in grid graphs of sizes up to . Analysis reveals relative positions within a grid graph that are more susceptible to bottlenecks. It demonstrates the superiority of the protocol along paths that are not shortest paths while avoiding bottlenecks for simultaneous communication requests.

arXiv:2211.12535•Annalen der Physik•Jan 17, 2025•0 citations

Learning Many-Body Hamiltonians Using a Local Probe

Suying Liu, Zitai Xu, Alexey V. Gorshkov +3 more

Hamiltonian learning provides a systematic framework for reconstructing unknown quantum dynamics. However, existing protocols typically assume direct measurement access to the entire system. With fast single-qubit control and a connected reference backbone, we show that a single measurable qubit suffices to learn all $O(N)$ independent parameters of a bounded-degree two-body Hamiltonian on $N$ qubits at the Heisenberg limit. Crucially, our protocol uses robust SWAP gates synthesized by quantum signal processing, enabling coherent transfer of states evolving under distant Hamiltonian parameters to the measurable qubit. This transfer requires no prior calibration of the Hamiltonian parameters of the intermediate links. A parallel learning architecture achieves total query time $\widetilde{O}(N)$ for an $N$-qubit chain, while retaining Heisenberg-limited precision scaling. On the chain, these scalings match the fundamental precision and information-propagation lower bounds up to logarithmic factors. The framework further extends to arbitrary bounded-degree interaction graphs. Our results establish a scalable route to learning an extensive number of many-body Hamiltonian parameters through only a local measurement interface.

quant-pharXiv:2610.02157•Oct 2, 2026•0 citations

Improved Qubit Routing for QAOA Circuits

Ayse Kotil, Fedor Šimkovic, Martin Leib

We develop a qubit routing algorithm with polynomial classical run time for the Quantum Approximate Optimization Algorithm (QAOA). The algorithm follows a two step process. First, it obtains a near-optimal solution, based on Vizing's theorem for the edge coloring problem, consisting of subsets of the interaction gates that can be executed in parallel on a fully parallelized all-to-all connected QPU. Second, it proceeds with greedy application of SWAP gates based on their net effect on the distance of remaining interaction gates on a specific hardware connectivity graph. Our algorithm strikes a balance between optimizing for both the circuit depth and total SWAP gate count. We show that it improves upon existing state-of-the-art routing algorithms for QAOA circuits defined on $k$-regular as well as Erdös-Renyi problem graphs of sizes up to $N \leq 400$.

arXiv:2312.15982•Dec 26, 2023•1 citation
To implement arbitrary quantum circuits in architectures with restricted interactions, one may effectively simulate all-to-all connectivity by routing quantum information. We consider the entanglement dynamics and routing between two regions only connected through an intermediate “bottleneck” region with few qubits. In such systems, where the entanglement rate is restricted by a vertex boundary rather than an edge boundary of the underlying interaction graph, existing results such as the small incremental entangling theorem give only a trivial constant lower bound on the routing time (the minimum time to perform an arbitrary permutation). We significantly improve the lower bound on the routing time in systems with a vertex bottleneck. Specifically, for any system with two regions L , R with N L , N R qubits, respectively, coupled only through an intermediate region C with N C qubits, for any δ > 0 we show a lower bound of Ω ( N R 1 − δ / N L N C ) on the Hamiltonian quantum routing time when using piecewise time-independent Hamiltonians, or time-dependent Hamiltonians subject to a smoothness condition. We also prove an upper bound on the average amount of bipartite entanglement between L and C , R that can be generated in time t by such architecture-respecting Hamiltonians in systems constrained by vertex bottlenecks, improving the scaling in the system size from O ( N L t ) to O ( N L t ) . As a special case, when applied to the star graph (i.e., one vertex connected to N leaves), we obtain an Ω ( N 1 − δ ) lower bound on the routing time and on the time to prepare N / 2 Bell pairs between the vertices. We also show that, in systems of free particles, we can route optimally on the star graph in time Θ ( N ) using Hamiltonian quantum routing, obtaining a speedup over gate-based routing, which takes time Θ ( N ) .
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.
Locality constrains the flow of information between different parts of many-body quantum systems. In quantum computers, this affects the ability to perform arbitrary interactions for quantum information processing tasks. A crucial challenge for scalable quantum architectures is thus to minimize the overheads due to locality constraints. Locality constraints also affect the way information and entanglement can be spread in many body quantum systems, and our ability to make predictions about such systems. One way to implement arbitrary interactions in locality-constrained architectures is by permuting qubits, also known as performing quantum routing. In the first part of this thesis, we investigate quantum routing strategies using emerging architectural capabilities beyond swap gates. We first investigate the use of mid-circuit measurements and classical feedback, which enable quantum teleportation. We prove upper bounds on the speedup afforded by the use of quantum teleportation for routing. We also design architectural connectivities which can exploit teleportation-based speedups. We then consider quantum routing by continuous-time Hamiltonian evolution, designing a routing algorithm that achieves a polynomial speedup in routing time over gate-based routing methods in architectures with a bottleneck, which is an intermediate region that constrains interactions between the rest of the device. We improve the lower bound on the time taken for routing in such systems, and develop a matching upper bound on the closely related task of generating and distributing entanglement. In the second part of this thesis, we investigate the behavior of finite-sized systems evolving by local Hamiltonians for a long duration. A major direction of research in condensed matter physics is the investigation of whether isolated systems thermalize (i.e., reach a state of thermal equilibrium). Various theoretical proposals such as information scrambling, entanglement between subsystems, and the eigenstate thermalization hypothesis have attempted to explain the conditions under which systems equilibrate. At the same time, notable counter-examples to thermalization have been found, such as systems that are integrable, exhibit many-body localization, or quantum many-body scars. We approach this question from a complexity-theoretic perspective. We show that the problem of deciding whether or not observables equilibrate to a givenvalue is PSPACE-complete. We also show that deciding whether observables relax to the thermal equilibrium value is contained in PSPACE, and is PSPACE-hard under quantum polynomial time reductions. These problems are thus intractable even for a quantum computer. Our results indicate that the proposed conditions leading to thermalization are either difficult to decide, or are not generic indicators of thermalization.
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
Abstract Distributing entangled states among users is a fundamental problem in quantum networks. Existing protocols like protocol introduced in [npj Quantum Inf. 2019, 5, 76] use graph theoretic tools like local complementation to optimize the number of measurements required to extract any Bell pair among the network users. Such a protocol relies on finding the shortest path between the users. Here, it is established that, in general, the most optimal path to perform the protocol is not along the shortest path. Specific examples of this advantage are provided on networks of size as small as 12 qubits. Bottlenecks in establishing simultaneous Bell pairs in nearest‐neighbor architectures are also explored. Recent results suggesting the unsuitability of the line and ring networks for the implementation of quantum networks due to the bottlenecks are revisited, and using local equivalency relations from graph theory, it's hinted that even grid graphs are not exempted from bottleneck issues. Finally, bottlenecks are simulated in grid graphs of sizes up to . Analysis reveals relative positions within a grid graph that are more susceptible to bottlenecks. It demonstrates the superiority of the protocol along paths that are not shortest paths while avoiding bottlenecks for simultaneous communication requests.
Hamiltonian learning provides a systematic framework for reconstructing unknown quantum dynamics. However, existing protocols typically assume direct measurement access to the entire system. With fast single-qubit control and a connected reference backbone, we show that a single measurable qubit suffices to learn all O(N)O(N)O(N) independent parameters of a bounded-degree two-body Hamiltonian on NNN qubits at the Heisenberg limit. Crucially, our protocol uses robust SWAP gates synthesized by quantum signal processing, enabling coherent transfer of states evolving under distant Hamiltonian parameters to the measurable qubit. This transfer requires no prior calibration of the Hamiltonian parameters of the intermediate links. A parallel learning architecture achieves total query time O~(N)\widetilde{O}(N)O(N) for an NNN-qubit chain, while retaining Heisenberg-limited precision scaling. On the chain, these scalings match the fundamental precision and information-propagation lower bounds up to logarithmic factors. The framework further extends to arbitrary bounded-degree interaction graphs. Our results establish a scalable route to learning an extensive number of many-body Hamiltonian parameters through only a local measurement interface.
We develop a qubit routing algorithm with polynomial classical run time for the Quantum Approximate Optimization Algorithm (QAOA). The algorithm follows a two step process. First, it obtains a near-optimal solution, based on Vizing's theorem for the edge coloring problem, consisting of subsets of the interaction gates that can be executed in parallel on a fully parallelized all-to-all connected QPU. Second, it proceeds with greedy application of SWAP gates based on their net effect on the distance of remaining interaction gates on a specific hardware connectivity graph. Our algorithm strikes a balance between optimizing for both the circuit depth and total SWAP gate count. We show that it improves upon existing state-of-the-art routing algorithms for QAOA circuits defined on kkk-regular as well as Erdös-Renyi problem graphs of sizes up to N≤400N \leq 400N≤400.