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

Locality and Complexity in Quantum Information Dynamics

Dhruv Devulapalli

Published Jan 1, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.13016/sj0x-d8ce

Related papers

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

Quantum Entanglement and the Emergence of Thermalization in Isolated Many-Body Systems Exploring Information Analytics and Emergent Dynamics in Complex Quantum Systems

Jagbir Ahlawat

Quantum many-body systems exhibit highly complex interactions that give rise to emergent collective phenomena beyond the behavior of individual particles. One of the most intriguing challenges in modern quantum physics is understanding how isolated quantum systems evolve toward thermal equilibrium despite following fundamentally reversible quantum dynamics. Quantum entanglement has emerged as a central mechanism governing information propagation, thermalization, and the development of statistical equilibrium in isolated many-body systems. Simultaneously, recent advances in quantum information science have enabled researchers to investigate the relationship between entanglement dynamics, information scrambling, and emergent quantum behavior using computational and analytical approaches. This study proposes a Quantum Information Analytics Framework for investigating thermalization processes in isolated many-body quantum systems through the integration of entanglement dynamics, quantum information measures, statistical mechanics, and computational modeling. The proposed framework evaluates system evolution using multiple performance indicators, including entanglement entropy, information propagation, thermal equilibrium, quantum coherence, and computational stability. The findings indicate that quantum entanglement plays a fundamental role in driving thermalization while preserving the underlying unitary evolution of isolated quantum systems. The proposed analytical framework contributes to a deeper understanding of emergent quantum dynamics and provides valuable insights for quantum computing, quantum simulation, condensed matter physics, and next-generation quantum information technologies.

Dandao Xuebao/Journal of Ballistics•Jun 30, 2026•0 citations

Entanglement dynamics and chaos in long-range quantum systems

Silvia Pappalardi

Over the past twenty years, experimental and technological progresses have motivated a renewed attention to the study of non-equilibrium isolated many-body systems, leading to a relatively well-established paradigm in the case of local Hamiltonians. In the present thesis, I have used quantum information theoretical tools to study out-of-equilibrium dynamics, with particular attention on long-range interacting many-body systems. I have explored the dynamics of bipartite and multipartite entanglement in connection to chaos and scrambling in various long-range (clean and disordered) models. The results contained in this thesis contribute to establishing semi-classical tools as powerful techniques for the description of the quantum information spreading in long-range systems. I have further considered a different, yet connected question, concerning the multipartite entanglement structure of chaotic eigenstates and its generic evolution.

•Sep 29, 2020•2 citations

Quantum Stochastic Processes and Quantum Many-Body Physics

Johannes Bausch

This dissertation investigates the theory of quantum stochastic processes and its applications in quantum many-body physics. The main goal is to analyse complexity-theoretic aspects of both static and dynamic properties of physical systems modelled by quantum stochastic processes. The thesis consists of two parts: the first one addresses the computational complexity of certain quantum and classical divisibility questions, whereas the second one addresses the topic of Hamiltonian complexity theory. In the divisibility part, we discuss the question whether one can efficiently sub-divide a map describing the evolution of a system in a noisy environment, i.e. a CPTP- or stochastic map for quantum and classical processes, respectively, and we prove that taking the nth root of a CPTP or stochastic map is an NP-complete problem. Furthermore, we show that answering the question whether one can divide up a random variable $X$ into a sum of $n$ iid random variables $Y_i$, i.e. $X=\sum_{i=1}^n Y_i$, is poly-time computable; relaxing the iid condition renders the problem NP-hard. In the local Hamiltonian part, we study computation embedded into the ground state of a many-body quantum system, going beyond "history state" constructions with a linear clock. We first develop a series of mathematical techniques which allow us to study the energy spectrum of the resulting Hamiltonian, and extend classical string rewriting to the quantum setting. This allows us to construct the most physically-realistic QMAEXP-complete instances for the LOCAL HAMILTONIAN problem (i.e. the question of estimating the ground state energy of a quantum many-body system) known to date, both in one- and three dimensions. Furthermore, we study weighted versions of linear history state constructions, allowing us to obtain tight lower and upper bounds on the promise gap of the LOCAL HAMILTONIAN problem in various cases. We finally study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.

•Oct 4, 2017•1 citation

Sustained growth of quantum circuit complexity in many-body Hamiltonian dynamics

Wonjun Lee, Saúl Pilatowsky-Cameo, Soonwon Choi

The quantum circuit complexity of an evolving many-body quantum system is believed to exhibit a sustained growth, maintained for timescales much longer than the onset of thermalization. Most previous works have focused on models which violate energy conservation, such as random unitary circuits. Here we study generic, local time-independent Hamiltonian dynamics. We unconditionally prove that for generic local Hamiltonians and typical initial product states at high effective temperature, the robust quantum circuit complexity must grow over a very long period of time, attaining an exponentially large value at late times. Our approach relies on two structural properties that we prove rigorously: (i) generic local Hamiltonians satisfy generalized spectral no-resonance conditions of arbitrary order, and (ii) typical high-temperature product states are effectively supported in exponentially many energy eigenstates. These properties have been widely assumed without proof in prior works. As corollaries of this result, we show the late-time state displays robust volume-law entanglement that is irremovable by polynomial-size circuits, and we establish a no fast-forwarding result for generic local Hamiltonians. We also lower bound the complexity of preparing sufficiently large subsystems with local quantum channels, in contrast with sufficiently small thermalizing regions which we show retain low complexity at late times.

quant-pharXiv:2609.26885•Sep 24, 2026•1 citation

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
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
Quantum many-body systems exhibit highly complex interactions that give rise to emergent collective phenomena beyond the behavior of individual particles. One of the most intriguing challenges in modern quantum physics is understanding how isolated quantum systems evolve toward thermal equilibrium despite following fundamentally reversible quantum dynamics. Quantum entanglement has emerged as a central mechanism governing information propagation, thermalization, and the development of statistical equilibrium in isolated many-body systems. Simultaneously, recent advances in quantum information science have enabled researchers to investigate the relationship between entanglement dynamics, information scrambling, and emergent quantum behavior using computational and analytical approaches. This study proposes a Quantum Information Analytics Framework for investigating thermalization processes in isolated many-body quantum systems through the integration of entanglement dynamics, quantum information measures, statistical mechanics, and computational modeling. The proposed framework evaluates system evolution using multiple performance indicators, including entanglement entropy, information propagation, thermal equilibrium, quantum coherence, and computational stability. The findings indicate that quantum entanglement plays a fundamental role in driving thermalization while preserving the underlying unitary evolution of isolated quantum systems. The proposed analytical framework contributes to a deeper understanding of emergent quantum dynamics and provides valuable insights for quantum computing, quantum simulation, condensed matter physics, and next-generation quantum information technologies.
Over the past twenty years, experimental and technological progresses have motivated a renewed attention to the study of non-equilibrium isolated many-body systems, leading to a relatively well-established paradigm in the case of local Hamiltonians. In the present thesis, I have used quantum information theoretical tools to study out-of-equilibrium dynamics, with particular attention on long-range interacting many-body systems. I have explored the dynamics of bipartite and multipartite entanglement in connection to chaos and scrambling in various long-range (clean and disordered) models. The results contained in this thesis contribute to establishing semi-classical tools as powerful techniques for the description of the quantum information spreading in long-range systems. I have further considered a different, yet connected question, concerning the multipartite entanglement structure of chaotic eigenstates and its generic evolution.
This dissertation investigates the theory of quantum stochastic processes and its applications in quantum many-body physics. The main goal is to analyse complexity-theoretic aspects of both static and dynamic properties of physical systems modelled by quantum stochastic processes. The thesis consists of two parts: the first one addresses the computational complexity of certain quantum and classical divisibility questions, whereas the second one addresses the topic of Hamiltonian complexity theory. In the divisibility part, we discuss the question whether one can efficiently sub-divide a map describing the evolution of a system in a noisy environment, i.e. a CPTP- or stochastic map for quantum and classical processes, respectively, and we prove that taking the nth root of a CPTP or stochastic map is an NP-complete problem. Furthermore, we show that answering the question whether one can divide up a random variable XXX into a sum of nnn iid random variables YiY_iYi​, i.e. X=∑i=1nYiX=\sum_{i=1}^n Y_iX=∑i=1n​Yi​, is poly-time computable; relaxing the iid condition renders the problem NP-hard. In the local Hamiltonian part, we study computation embedded into the ground state of a many-body quantum system, going beyond "history state" constructions with a linear clock. We first develop a series of mathematical techniques which allow us to study the energy spectrum of the resulting Hamiltonian, and extend classical string rewriting to the quantum setting. This allows us to construct the most physically-realistic QMAEXP-complete instances for the LOCAL HAMILTONIAN problem (i.e. the question of estimating the ground state energy of a quantum many-body system) known to date, both in one- and three dimensions. Furthermore, we study weighted versions of linear history state constructions, allowing us to obtain tight lower and upper bounds on the promise gap of the LOCAL HAMILTONIAN problem in various cases. We finally study a classical embedding of a Busy Beaver Turing Machine into a low-dimensional lattice spin model, which allows us to dictate a transition from a purely classical phase to a Toric Code phase at arbitrarily large and potentially even uncomputable system sizes.
The quantum circuit complexity of an evolving many-body quantum system is believed to exhibit a sustained growth, maintained for timescales much longer than the onset of thermalization. Most previous works have focused on models which violate energy conservation, such as random unitary circuits. Here we study generic, local time-independent Hamiltonian dynamics. We unconditionally prove that for generic local Hamiltonians and typical initial product states at high effective temperature, the robust quantum circuit complexity must grow over a very long period of time, attaining an exponentially large value at late times. Our approach relies on two structural properties that we prove rigorously: (i) generic local Hamiltonians satisfy generalized spectral no-resonance conditions of arbitrary order, and (ii) typical high-temperature product states are effectively supported in exponentially many energy eigenstates. These properties have been widely assumed without proof in prior works. As corollaries of this result, we show the late-time state displays robust volume-law entanglement that is irremovable by polynomial-size circuits, and we establish a no fast-forwarding result for generic local Hamiltonians. We also lower bound the complexity of preparing sufficiently large subsystems with local quantum channels, in contrast with sufficiently small thermalizing regions which we show retain low complexity at late times.
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.