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:2510.18832

Sharp Transitions for Subsystem Complexity

Yale Fan, Nicholas Hunter-Jones, Andreas Karch, Shivan Mittal

Published Oct 21, 2025• 0 citations
arXivHTMLPDF

Abstract

The circuit complexity of time-evolved pure quantum states grows linearly in time for an exponentially long time. This behavior has been proven in certain models, is conjectured to hold for generic quantum many-body systems, and is believed to be dual to the long-time growth of black hole interiors in AdS/CFT. Achieving a similar understanding for mixed states remains an important problem. In this work, we study the circuit complexity of time-evolved subsystems of pure quantum states. We find that for greater-than-half subsystem sizes, the complexity grows linearly in time for an exponentially long time, similarly to that of the full state. However, for less-than-half subsystem sizes, the complexity rises and then falls, returning to low complexity as the subsystem equilibrates. Notably, the transition between these two regimes occurs sharply at half system size. We use holographic duality to map out this picture of subsystem complexity dynamics and rigorously prove the existence of the sharp transition in random quantum circuits. Furthermore, we use holography to predict features of complexity growth at finite temperature that lie beyond the reach of techniques based on random quantum circuits. In particular, at finite temperature, we argue for an additional sharp transition at a critical less-than-half subsystem size. Below this critical value, the subsystem complexity saturates nearly instantaneously rather than exhibiting a rise and fall. This novel phenomenon, as well as an analogous transition above half system size, provides a target for future studies based on rigorous methods.

DOI
10.48550/arxiv.2510.18832

Related papers

Quantum Complexity Dynamics for Disjoint Subsystems

Yale Fan, Nicholas Hunter-Jones, Andreas Karch +2 more

Quantum complexity has emerged as a natural probe of chaos, thermalization, and the black hole interior on timescales long after local observables have equilibrated. However, its time evolution has been studied almost exclusively in subsystems confined to a single connected region. We show, using complementary tools from holography and random quantum circuits, that noncontiguous subsystems composed of multiple disjoint regions give rise to qualitatively new physics compared to the contiguous case. First, at finite temperature, a subsystem occupying less than half of the total system can carry high complexity at late times, even as the complexity of its larger complement remains low. This inversion of the usual hierarchy is intrinsically thermal: it vanishes in the infinite-temperature limit, which is the regime modeled by random quantum circuits. Second, if a subsystem's complexity equilibrates at an early time, then fragmenting it into $m$ disjoint components can further reduce this timescale by a factor of $m$, a phenomenon we exhibit in both holography and random quantum circuits. These results not only sharpen the correspondence between geometric and computational notions of complexity, but also motivate the search for novel complexity phenomena in quantum dynamics.

hep-thCross-listedarXiv:2609.00126•Sep 2, 2026•0 citations

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

Growth and collapse of subsystem complexity under random unitary circuits

Jeongwan Haah, Douglas Stanford

For chaotic quantum dynamics modeled by random unitary circuits, we study the complexity of reduced density matrices of subsystems as a function of evolution time where the initial global state is a product pure state. The state complexity is defined as the minimum number of local quantum channels to generate a given state from a product state to a good approximation. In 1+1 1 + 1 d, we prove that the complexity of subsystems of length \ell ℓ smaller than half grows linearly in time T T at least up to T = \ell / 4 T = ℓ / 4 but becomes zero after time T = \ell /2 T = ℓ / 2 in the limit of a large local dimension, while the complexity of the complementary subsystem of length larger than half grows linearly in time up to exponentially late times. Using holographic correspondence, we give some evidence that the state complexity of the smaller subsystem should actually grow linearly up to time T = \ell/2 T = ℓ / 2 and then abruptly decay to zero.

arXiv:2510.18805•SciPost Physics•Jul 22, 2026•0 citations

Quantum complexity phase transitions in monitored random circuits

Ryotaro Suzuki, Jonas Haferkamp, Jens Eisert +1 more

Recently, the dynamics of quantum systems that involve both unitary evolution and quantum measurements have attracted attention due to the exotic phenomenon of measurement-induced phase transitions. The latter refers to a sudden change in a property of a state of n qubits, such as its entanglement entropy, depending on the rate at which individual qubits are measured. At the same time, quantum complexity emerged as a key quantity for the identification of complex behaviour in quantum many-body dynamics. In this work, we investigate the dynamics of the quantum state complexity in monitored random circuits, where n qubits evolve according to a random unitary circuit and are individually measured with a fixed probability at each time step. We find that the evolution of the exact quantum state complexity undergoes a phase transition when changing the measurement rate. Below a critical measurement rate, the complexity grows at least linearly in time until {saturating to a value e Ω ( n ) .} Above, the complexity does not exceed poly ⁡ ( n ) . In our proof, we make use of percolation theory to find paths along which an exponentially long quantum computation can be run below the critical rate, and to identify events where the state complexity is reset to zero above the critical rate. We lower bound the exact state complexity in the former regime using recently developed techniques from algebraic geometry. Our results combine quantum complexity growth, phase transitions, and computation with measurements to help understand the behavior of monitored random circuits and to make progress towards determining the computational power of measurements in many-body systems.

arXiv:2305.15475•Quantum•Feb 10, 2025•9 citations

Models of Quantum Complexity Growth

Fernando G. S. L. Brandão, Wissam A Chemissany, Nicholas Hunter-Jones +2 more

The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics.The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state.It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions.To go further, one may study more generic models of complexity growth.We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group.This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity.We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind.Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.

arXiv:1912.04297•PRX Quantum•Jul 29, 2021•121 citations

COMPLEXITY AND ENTANGLEMENT OF QUANTUM SYSTEMS ACROSS SCALES

Li, Yue

This thesis studies the complexity, thermalization, and entanglement properties of quantum mechanical systems and the implications of their behavior in high energy and condensed matter models. In Chapter 2, we use the geometry of Lie groups to study the circuit complexity of quantum mechanical systems and develop the technology to analytically predict the appearance of the obstruction to the complexity growth of integrable systems. We simulate the spin and fermionic systems, in which the amount of chaos can be controlled, and conjecture the close relation between quantum complexity and thermalization. In Chapter 3, we apply quantum information theory to an evaporating black hole in Jackiw-Teitelboim gravity in the context of AdS/CFT as a quantum error correction protocol. By calculating the entropy measures using gravitational path integrals, we establish the criterion for an error in the Hawking radiation to be correctable and identify the transition in the reversibility of the error channel as the Page transition. In Chapter 4, we study a 1+1 dimensional random circuit with measurement and dissipation. We map this type of quantum system to a classical Ising model analytically and show that the entanglement dynamics can be understood as the thermodynamics of the domain wall formed in the spin model, as one of the spatial dimensions stretches. We then confirm the calculated time scales in the classical theory qualitatively with simulations of realistic qubit circuits. Overall, we present a holistic picture of quantum systems, from those evolving with pure unitary, to those evolving also with influence from the environment. The complexity of the theory and entanglement of the states exhibit universal behavior at early times (∼ O(N)) and distinct long-time behavior, determined by their thermalization properties in spin chains, toy models of black holes in AdS/CFT, and monitored random circuits with dissipation.

•Jan 1, 2023•0 citations
The circuit complexity of time-evolved pure quantum states grows linearly in time for an exponentially long time. This behavior has been proven in certain models, is conjectured to hold for generic quantum many-body systems, and is believed to be dual to the long-time growth of black hole interiors in AdS/CFT. Achieving a similar understanding for mixed states remains an important problem. In this work, we study the circuit complexity of time-evolved subsystems of pure quantum states. We find that for greater-than-half subsystem sizes, the complexity grows linearly in time for an exponentially long time, similarly to that of the full state. However, for less-than-half subsystem sizes, the complexity rises and then falls, returning to low complexity as the subsystem equilibrates. Notably, the transition between these two regimes occurs sharply at half system size. We use holographic duality to map out this picture of subsystem complexity dynamics and rigorously prove the existence of the sharp transition in random quantum circuits. Furthermore, we use holography to predict features of complexity growth at finite temperature that lie beyond the reach of techniques based on random quantum circuits. In particular, at finite temperature, we argue for an additional sharp transition at a critical less-than-half subsystem size. Below this critical value, the subsystem complexity saturates nearly instantaneously rather than exhibiting a rise and fall. This novel phenomenon, as well as an analogous transition above half system size, provides a target for future studies based on rigorous methods.
Quantum complexity has emerged as a natural probe of chaos, thermalization, and the black hole interior on timescales long after local observables have equilibrated. However, its time evolution has been studied almost exclusively in subsystems confined to a single connected region. We show, using complementary tools from holography and random quantum circuits, that noncontiguous subsystems composed of multiple disjoint regions give rise to qualitatively new physics compared to the contiguous case. First, at finite temperature, a subsystem occupying less than half of the total system can carry high complexity at late times, even as the complexity of its larger complement remains low. This inversion of the usual hierarchy is intrinsically thermal: it vanishes in the infinite-temperature limit, which is the regime modeled by random quantum circuits. Second, if a subsystem's complexity equilibrates at an early time, then fragmenting it into mmm disjoint components can further reduce this timescale by a factor of mmm, a phenomenon we exhibit in both holography and random quantum circuits. These results not only sharpen the correspondence between geometric and computational notions of complexity, but also motivate the search for novel complexity phenomena in quantum dynamics.
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.
For chaotic quantum dynamics modeled by random unitary circuits, we study the complexity of reduced density matrices of subsystems as a function of evolution time where the initial global state is a product pure state. The state complexity is defined as the minimum number of local quantum channels to generate a given state from a product state to a good approximation. In 1+1 1 + 1 d, we prove that the complexity of subsystems of length \ell ℓ smaller than half grows linearly in time T T at least up to T = \ell / 4 T = ℓ / 4 but becomes zero after time T = \ell /2 T = ℓ / 2 in the limit of a large local dimension, while the complexity of the complementary subsystem of length larger than half grows linearly in time up to exponentially late times. Using holographic correspondence, we give some evidence that the state complexity of the smaller subsystem should actually grow linearly up to time T = \ell/2 T = ℓ / 2 and then abruptly decay to zero.
Recently, the dynamics of quantum systems that involve both unitary evolution and quantum measurements have attracted attention due to the exotic phenomenon of measurement-induced phase transitions. The latter refers to a sudden change in a property of a state of n qubits, such as its entanglement entropy, depending on the rate at which individual qubits are measured. At the same time, quantum complexity emerged as a key quantity for the identification of complex behaviour in quantum many-body dynamics. In this work, we investigate the dynamics of the quantum state complexity in monitored random circuits, where n qubits evolve according to a random unitary circuit and are individually measured with a fixed probability at each time step. We find that the evolution of the exact quantum state complexity undergoes a phase transition when changing the measurement rate. Below a critical measurement rate, the complexity grows at least linearly in time until {saturating to a value e Ω ( n ) .} Above, the complexity does not exceed poly ⁡ ( n ) . In our proof, we make use of percolation theory to find paths along which an exponentially long quantum computation can be run below the critical rate, and to identify events where the state complexity is reset to zero above the critical rate. We lower bound the exact state complexity in the former regime using recently developed techniques from algebraic geometry. Our results combine quantum complexity growth, phase transitions, and computation with measurements to help understand the behavior of monitored random circuits and to make progress towards determining the computational power of measurements in many-body systems.
The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high-energy physics.The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state.It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a shortcut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions.To go further, one may study more generic models of complexity growth.We provide a rigorous connection between complexity growth and unitary k-designs, ensembles that capture the randomness of the unitary group.This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity.We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind.Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.
This thesis studies the complexity, thermalization, and entanglement properties of quantum mechanical systems and the implications of their behavior in high energy and condensed matter models. In Chapter 2, we use the geometry of Lie groups to study the circuit complexity of quantum mechanical systems and develop the technology to analytically predict the appearance of the obstruction to the complexity growth of integrable systems. We simulate the spin and fermionic systems, in which the amount of chaos can be controlled, and conjecture the close relation between quantum complexity and thermalization. In Chapter 3, we apply quantum information theory to an evaporating black hole in Jackiw-Teitelboim gravity in the context of AdS/CFT as a quantum error correction protocol. By calculating the entropy measures using gravitational path integrals, we establish the criterion for an error in the Hawking radiation to be correctable and identify the transition in the reversibility of the error channel as the Page transition. In Chapter 4, we study a 1+1 dimensional random circuit with measurement and dissipation. We map this type of quantum system to a classical Ising model analytically and show that the entanglement dynamics can be understood as the thermodynamics of the domain wall formed in the spin model, as one of the spatial dimensions stretches. We then confirm the calculated time scales in the classical theory qualitatively with simulations of realistic qubit circuits. Overall, we present a holistic picture of quantum systems, from those evolving with pure unitary, to those evolving also with influence from the environment. The complexity of the theory and entanglement of the states exhibit universal behavior at early times (∼ O(N)) and distinct long-time behavior, determined by their thermalization properties in spin chains, toy models of black holes in AdS/CFT, and monitored random circuits with dissipation.