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 ) .
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
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 .
Limited connectivity makes nonlocal quantum gates expensive on near-neighbor hardware, where compilation typically relies on SWAP transport, inheriting both depth overhead and path congestion. We present a swap-free routing framework in which higher levels of a qudit act as orthogonal spectral buses that transport control information without moving the computational state. We show that exact congestion relief in nearest-neighbor architectures requires local Hilbert-space expansion. In this model, a nonlocal operation over a path of length
L requires
2L+1 logical routing primitives, compared to the
3L baseline. Overlapping routes remain distinguishable through bus labels encoded in the same physical qudits. This routing algebra extends to Boolean fan-in at a common target: multiple controls arriving on distinct buses trigger a local unitary based on an arbitrary Boolean function of bus digits, yielding multi-control operations of depth
2L+Dg+O(1) for fan-in size
K and target-synthesis cost
Dg. We prove decodability, reversibility, and correctness for CNOT and Boolean fan-in, along with a state-count lower bound
d≥2K+1 for exact overlap routing. Cirq simulations confirm single-control correctness and zero crosstalk. Compiler-level benchmarks on QFT, QAOA, and mirror-interaction circuits verify the predicted congestion law and transport reduction. Noisy QuTiP simulations show that the architectural advantage depends on higher-level coherence and speed. These results identify spectral qudit routing as a congestion-relief architecture that separates nonlocal control delivery from local target-side aggregation, providing a minimal mechanism for overcoming qubit routing limitations.
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.
Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. These connectivity constraints are commonly viewed as a significant disadvantage. For example, compiling an unrestricted
n-qubit quantum circuit to one with poor qubit connectivity, such as a 1-D chain, usually results in a blowup of depth by
O(n2)and size by
O(n). It is appealing to conjecture that this overhead is unavoidable—a random circuit on
nqubits has
Θ(n)two-qubit gates in each layer and a constant fraction of them act on qubits separated by distance
Θ(n). While it is known that almost all
n-qubit unitary operations need quantum circuits of
Ω(4n/n)depth and
Ω(4n)size to realize with all-to-all qubit connectivity, in this article, we show that all
n-qubit unitary operations can be implemented by quantum circuits of
O(4n/n)depth and
O(4n)size even under 1-D chain qubit connectivity constraint. We extend this result and investigate qubit connectivity in three directions. First, we consider more general connectivity graphs and show that the circuit size can always be made
O(4n)as long as the graph is connected. For circuit depth, we study
d-dimensional grids, complete
d-ary trees and expander graphs, and show results similar to the 1-D chain. Second, we consider the case when ancillary qubits are available. We show that, with ancilla, the circuit depth can be made polynomial, and the space-depth trade-off is not impaired by connectivity constraints unless we have exponentially many ancillary qubits. Third, we obtain nearly optimal results on special families of unitaries, including diagonal unitaries, 2-by-2 block diagonal unitaries, and quantum state preparation (QSP) unitaries, the last being a fundamental task used in many quantum algorithms for machine learning and linear algebra.