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:2409.03656 · Physical review. B./Physical review. B

Quantum complexity and localization in random and time-periodic unitary circuits

Himanshu Sahu, Aranya Bhattacharya, Pingal Pratyush Nath

Published May 19, 2026• 0 citations
arXivHTMLPDF

Abstract

We study the growth and saturation of complexity in Krylov basis in random quantum circuits. In Haar-random unitary evolution, we show that, for large system sizes, this notion of complexity grows linearly before saturating at a late-time value of $d/2$, where $d$ is the Hilbert space dimension, at timescales $\sim d$. Our numerical analysis encompasses two classes of random circuits: brick-wall random unitary circuits and Floquet random circuits. In brick-wall case, complexity in Krylov basis exhibits dynamics consistent with Haar-random unitary evolution, while the inclusion of measurements significantly slows its growth down. For Floquet random circuits, we show that localized phases lead to reduced late-time saturation values of the complexity enabling us to probe the transition between thermal and many-body localized phases.

DOI
10.1103/mf2z-mrpd

Related papers

Saturation and Recurrence of Quantum Complexity in Random Local Quantum Dynamics

Michał Oszmaniec, Marcin Kotowski, Michał Horodecki +1 more

Quantum complexity is a measure of the minimal number of elementary operations required to approximately prepare a given state or unitary channel. Recently, this concept has found applications beyond quantum computing—in studying the dynamics of quantum many-body systems and the long-time properties of anti–de Sitter black holes. In this context, Brown and Susskind [] conjectured that the complexity of a chaotic quantum system grows linearly in time up to times exponential in the system size, saturating at a maximal value, and remaining maximally complex until undergoing recurrences at doubly exponential times. In this work, we prove the saturation and recurrence of complexity in two models of chaotic time evolutions based on (i) random local quantum circuits and (ii) stochastic local Hamiltonian evolution. Our results advance an understanding of the long-time behavior of chaotic quantum systems and could shed light on the physics of black-hole interiors. From a technical perspective, our results are based on establishing new quantitative connections between the Haar measure and high-degree approximate designs, as well as the fact that random quantum circuits of sufficiently high depth converge to approximate designs. Published by the American Physical Society 2024

arXiv:2205.09734•Physical Review X•Dec 24, 2024•13 citations

Mixing and localisation in random time-periodic quantum circuits.

Tom Farshi, Daniele Toniolo, Carlos E. González-Guillén +2 more

How much does local and time-periodic dynamics resemble a random unitary? In the present work we address this question by using the Clifford formalism from quantum computation. We analyse a Floquet model with disorder, characterised by a family of local, time-periodic, random quantum circuits in one spatial dimension. We observe that the evolution operator enjoys an extra symmetry at times that are a half-integer multiple of the period. With this we prove that after the scrambling time, namely when any initial perturbation has propagated throughout the system, the evolution operator cannot be distinguished from a (Haar) random unitary when all qubits are measured with Pauli operators. This indistinguishability decreases as time goes on, which is in high contrast to the more studied case of (time-dependent) random circuits. We also prove that the evolution of Pauli operators displays a form of mixing. These results require the dimension of the local subsystem to be large. In the opposite regime our system displays a novel form of localisation, produced by the appearance of effective one-sided walls, which prevent perturbations from crossing the wall in one direction but not the other

•Jul 7, 2020•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

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

Mixing and localization in random time-periodic quantum circuits of Clifford unitaries

Tom Farshi, Daniele Toniolo, Carlos E. González-Guillén +2 more

How much do local and time-periodic dynamics resemble a random unitary? In the present work, we address this question by using the Clifford formalism from quantum computation. We analyze a Floquet model with disorder, characterized by a family of local, time-periodic, and random quantum circuits in one spatial dimension. We observe that the evolution operator enjoys an extra symmetry at times that are a half-integer multiple of the period. With this, we prove that after the scrambling time, namely, when any initial perturbation has propagated throughout the system, the evolution operator cannot be distinguished from a (Haar) random unitary when all qubits are measured with Pauli operators. This indistinguishability decreases as time goes on, which is in high contrast to the more studied case of (time-dependent) random circuits. We also prove that the evolution of Pauli operators displays a form of mixing. These results require the dimension of the local subsystem to be large. In the opposite regime, our system displays a novel form of localization, produced by the appearance of effective one-sided walls, which prevent perturbations from crossing the wall in one direction but not the other.

arXiv:2007.03339•Journal of Mathematical Physics•Mar 1, 2022•10 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
We study the growth and saturation of complexity in Krylov basis in random quantum circuits. In Haar-random unitary evolution, we show that, for large system sizes, this notion of complexity grows linearly before saturating at a late-time value of d/2d/2d/2, where ddd is the Hilbert space dimension, at timescales ∼d\sim d∼d. Our numerical analysis encompasses two classes of random circuits: brick-wall random unitary circuits and Floquet random circuits. In brick-wall case, complexity in Krylov basis exhibits dynamics consistent with Haar-random unitary evolution, while the inclusion of measurements significantly slows its growth down. For Floquet random circuits, we show that localized phases lead to reduced late-time saturation values of the complexity enabling us to probe the transition between thermal and many-body localized phases.
Quantum complexity is a measure of the minimal number of elementary operations required to approximately prepare a given state or unitary channel. Recently, this concept has found applications beyond quantum computing—in studying the dynamics of quantum many-body systems and the long-time properties of anti–de Sitter black holes. In this context, Brown and Susskind [] conjectured that the complexity of a chaotic quantum system grows linearly in time up to times exponential in the system size, saturating at a maximal value, and remaining maximally complex until undergoing recurrences at doubly exponential times. In this work, we prove the saturation and recurrence of complexity in two models of chaotic time evolutions based on (i) random local quantum circuits and (ii) stochastic local Hamiltonian evolution. Our results advance an understanding of the long-time behavior of chaotic quantum systems and could shed light on the physics of black-hole interiors. From a technical perspective, our results are based on establishing new quantitative connections between the Haar measure and high-degree approximate designs, as well as the fact that random quantum circuits of sufficiently high depth converge to approximate designs. Published by the American Physical Society 2024
How much does local and time-periodic dynamics resemble a random unitary? In the present work we address this question by using the Clifford formalism from quantum computation. We analyse a Floquet model with disorder, characterised by a family of local, time-periodic, random quantum circuits in one spatial dimension. We observe that the evolution operator enjoys an extra symmetry at times that are a half-integer multiple of the period. With this we prove that after the scrambling time, namely when any initial perturbation has propagated throughout the system, the evolution operator cannot be distinguished from a (Haar) random unitary when all qubits are measured with Pauli operators. This indistinguishability decreases as time goes on, which is in high contrast to the more studied case of (time-dependent) random circuits. We also prove that the evolution of Pauli operators displays a form of mixing. These results require the dimension of the local subsystem to be large. In the opposite regime our system displays a novel form of localisation, produced by the appearance of effective one-sided walls, which prevent perturbations from crossing the wall in one direction but not the other
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.
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.
How much do local and time-periodic dynamics resemble a random unitary? In the present work, we address this question by using the Clifford formalism from quantum computation. We analyze a Floquet model with disorder, characterized by a family of local, time-periodic, and random quantum circuits in one spatial dimension. We observe that the evolution operator enjoys an extra symmetry at times that are a half-integer multiple of the period. With this, we prove that after the scrambling time, namely, when any initial perturbation has propagated throughout the system, the evolution operator cannot be distinguished from a (Haar) random unitary when all qubits are measured with Pauli operators. This indistinguishability decreases as time goes on, which is in high contrast to the more studied case of (time-dependent) random circuits. We also prove that the evolution of Pauli operators displays a form of mixing. These results require the dimension of the local subsystem to be large. In the opposite regime, our system displays a novel form of localization, produced by the appearance of effective one-sided walls, which prevent perturbations from crossing the wall in one direction but not the other.
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.