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

Linear Growth of Circuit Complexity from Brownian Dynamics

Shao-Kai Jian, Gregory S. Bentsen, Brian G. Swingle

Published Jun 28, 2022• 2 citations
arXivHTMLPDF

Abstract

We calculate the frame potential for Brownian clusters of $N$ spins or fermions with time-dependent all-to-all interactions. In both cases the problem can be mapped to an effective statistical mechanics problem which we study using a path integral approach. We argue that the $k$th frame potential comes within $ε$ of the Haar value after a time of order $t \sim k N + k \log k + \log ε^{-1}$. Using a bound on the diamond norm, this implies that such circuits are capable of coming very close to a unitary $k$-design after a time of order $t \sim k N$. We also consider the same question for systems with a time-independent Hamiltonian and argue that a small amount of time-dependent randomness is sufficient to generate a $k$-design in linear time provided the underlying Hamiltonian is quantum chaotic. These models provide explicit examples of linear complexity growth that are also analytically tractable.

DOI
10.48550/arxiv.2206.14205

Related papers

Linear growth of circuit complexity from Brownian dynamics

Shao-Kai Jian, Gregory S. Bentsen, Brian G. Swingle

A bstract How rapidly can a many-body quantum system generate randomness? Using path integral methods, we demonstrate that Brownian quantum systems have circuit complexity that grows linearly with time. In particular, we study Brownian clusters of N spins or fermions with time-dependent all-to-all interactions, and calculate the Frame Potential to characterize complexity growth in these models. In both cases the problem can be mapped to an effective statistical mechanics problem which we study using path integral methods. Within this framework it is straightforward to show that the k th Frame Potential comes within ϵ of the Haar value after a time of order t ~ kN + k log k + log ϵ − 1 . Using a bound on the diamond norm, this implies that such circuits are capable of coming very close to a unitary k -design after a time of order t ~ kN . We also consider the same question for systems with a time-independent Hamiltonian and argue that a small amount of time-dependent randomness is sufficient to generate a k -design in linear time provided the underlying Hamiltonian is quantum chaotic. These models provide explicit examples of linear complexity growth that are analytically tractable and are directly applicable to practical applications calling for unitary k -designs.

Journal of High Energy Physics•Aug 28, 2023•21 citations

Complexity is not enough for randomness

Shiyong Guo, Martin Sasieta, Brian G. Swingle

We study the dynamical generation of randomness in Brownian systems as a function of the degree of locality of the Hamiltonian. We first express the trace distance to a unitary design for these systems in terms of an effective equilibrium thermal partition function, and provide a set of conditions that guarantee a linear time to design. We relate the trace distance to design to spectral properties of the time-evolution operator. We apply these considerations to the Brownian p p -SYK model as a function of the degree of locality p p . We show that the time to design is linear, with a slope proportional to 1/p 1 / p . We corroborate that when p p is of order the system size this reproduces the behavior of a completely non-local Brownian model of random matrices. For the random matrix model, we reinterpret these results from the point of view of classical Brownian motion in the unitary manifold. Therefore, we find that the generation of randomness typically persists for exponentially long times in the system size, even for systems governed by highly non-local time-dependent Hamiltonians. We conjecture this to be a general property: there is no efficient way to generate approximate Haar random unitaries dynamically, unless a large degree of fine-tuning is present in the ensemble of time-dependent Hamiltonians. We contrast the slow generation of randomness to the growth of quantum complexity of the time-evolution operator. Using known bounds on circuit complexity for unitary designs, we obtain a lower bound determining that complexity grows at least linearly in time for Brownian systems. We argue that these bounds on circuit complexity are far from tight and that complexity grows at a much faster rate, at least for non-local systems.

arXiv:2405.17546•SciPost Physics•Dec 4, 2024•9 citations

Chaos and complexity by design

Daniel A. Roberts, Beni Yoshida

We study the relationship between quantum chaos and pseudorandomness by developing probes of unitary design. A natural probe of randomness is the “frame poten-tial,” which is minimized by unitary k-designs and measures the 2-norm distance between the Haar random unitary ensemble and another ensemble. A natural probe of quantum chaos is out-of-time-order (OTO) four-point correlation functions. We show that the norm squared of a generalization of out-of-time-order 2k-point correlators is proportional to the kth frame potential, providing a quantitative connection between chaos and pseudorandomness. Additionally, we prove that these 2k-point correlators for Pauli operators completely determine the k-fold channel of an ensemble of unitary operators. Finally, we use a counting argument to obtain a lower bound on the quantum circuit complexity in terms of the frame potential. This provides a direct link between chaos, complexity, and randomness.

arXiv:1610.04903•Journal of High Energy Physics•Apr 1, 2017•456 citations

Projected state ensemble of a generic model of many-body quantum chaos

Amos Chan, Andrea De Luca

Abstract The projected ensemble is based on the study of the quantum state of a subsystem A conditioned on projective measurements in its complement. Recent studies have observed that a more refined measure of the thermalization of a chaotic quantum system can be defined on the basis of convergence of the projected ensemble to a quantum state design, i.e. a system thermalizes when it becomes indistinguishable, up to the k th moment, from a Haar ensemble of uniformly distributed pure states. Here we consider a random unitary circuit with the brick-wall geometry and analyze its convergence to the Haar ensemble through the frame potential and its mapping to a statistical mechanical problem. This approach allows us to highlight a geometric interpretation of the frame potential based on the existence of a fluctuating membrane, similar to those appearing in the study of entanglement entropies. At large local Hilbert space dimension q , we find that all moments converge simultaneously with a time scaling linearly in the size of region A , a feature previously observed in dual unitary models. However, based on the geometric interpretation, we argue that the scaling at finite q on the basis of rare membrane fluctuations, finding the logarithmic scaling of design times t k = O ( log ⁡ k ) . Our results are supported with numerical simulations performed at q = 2.

arXiv:2402.16939•Journal of Physics A Mathematical and Theoretical•Aug 21, 2024•16 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

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
We calculate the frame potential for Brownian clusters of NNN spins or fermions with time-dependent all-to-all interactions. In both cases the problem can be mapped to an effective statistical mechanics problem which we study using a path integral approach. We argue that the kkkth frame potential comes within εεε of the Haar value after a time of order t∼kN+klog⁡k+log⁡ε−1t \sim k N + k \log k + \log ε^{-1}t∼kN+klogk+logε−1. Using a bound on the diamond norm, this implies that such circuits are capable of coming very close to a unitary kkk-design after a time of order t∼kNt \sim k Nt∼kN. We also consider the same question for systems with a time-independent Hamiltonian and argue that a small amount of time-dependent randomness is sufficient to generate a kkk-design in linear time provided the underlying Hamiltonian is quantum chaotic. These models provide explicit examples of linear complexity growth that are also analytically tractable.
A bstract How rapidly can a many-body quantum system generate randomness? Using path integral methods, we demonstrate that Brownian quantum systems have circuit complexity that grows linearly with time. In particular, we study Brownian clusters of N spins or fermions with time-dependent all-to-all interactions, and calculate the Frame Potential to characterize complexity growth in these models. In both cases the problem can be mapped to an effective statistical mechanics problem which we study using path integral methods. Within this framework it is straightforward to show that the k th Frame Potential comes within ϵ of the Haar value after a time of order t ~ kN + k log k + log ϵ − 1 . Using a bound on the diamond norm, this implies that such circuits are capable of coming very close to a unitary k -design after a time of order t ~ kN . We also consider the same question for systems with a time-independent Hamiltonian and argue that a small amount of time-dependent randomness is sufficient to generate a k -design in linear time provided the underlying Hamiltonian is quantum chaotic. These models provide explicit examples of linear complexity growth that are analytically tractable and are directly applicable to practical applications calling for unitary k -designs.
We study the dynamical generation of randomness in Brownian systems as a function of the degree of locality of the Hamiltonian. We first express the trace distance to a unitary design for these systems in terms of an effective equilibrium thermal partition function, and provide a set of conditions that guarantee a linear time to design. We relate the trace distance to design to spectral properties of the time-evolution operator. We apply these considerations to the Brownian p p -SYK model as a function of the degree of locality p p . We show that the time to design is linear, with a slope proportional to 1/p 1 / p . We corroborate that when p p is of order the system size this reproduces the behavior of a completely non-local Brownian model of random matrices. For the random matrix model, we reinterpret these results from the point of view of classical Brownian motion in the unitary manifold. Therefore, we find that the generation of randomness typically persists for exponentially long times in the system size, even for systems governed by highly non-local time-dependent Hamiltonians. We conjecture this to be a general property: there is no efficient way to generate approximate Haar random unitaries dynamically, unless a large degree of fine-tuning is present in the ensemble of time-dependent Hamiltonians. We contrast the slow generation of randomness to the growth of quantum complexity of the time-evolution operator. Using known bounds on circuit complexity for unitary designs, we obtain a lower bound determining that complexity grows at least linearly in time for Brownian systems. We argue that these bounds on circuit complexity are far from tight and that complexity grows at a much faster rate, at least for non-local systems.
We study the relationship between quantum chaos and pseudorandomness by developing probes of unitary design. A natural probe of randomness is the “frame poten-tial,” which is minimized by unitary k-designs and measures the 2-norm distance between the Haar random unitary ensemble and another ensemble. A natural probe of quantum chaos is out-of-time-order (OTO) four-point correlation functions. We show that the norm squared of a generalization of out-of-time-order 2k-point correlators is proportional to the kth frame potential, providing a quantitative connection between chaos and pseudorandomness. Additionally, we prove that these 2k-point correlators for Pauli operators completely determine the k-fold channel of an ensemble of unitary operators. Finally, we use a counting argument to obtain a lower bound on the quantum circuit complexity in terms of the frame potential. This provides a direct link between chaos, complexity, and randomness.
Abstract The projected ensemble is based on the study of the quantum state of a subsystem A conditioned on projective measurements in its complement. Recent studies have observed that a more refined measure of the thermalization of a chaotic quantum system can be defined on the basis of convergence of the projected ensemble to a quantum state design, i.e. a system thermalizes when it becomes indistinguishable, up to the k th moment, from a Haar ensemble of uniformly distributed pure states. Here we consider a random unitary circuit with the brick-wall geometry and analyze its convergence to the Haar ensemble through the frame potential and its mapping to a statistical mechanical problem. This approach allows us to highlight a geometric interpretation of the frame potential based on the existence of a fluctuating membrane, similar to those appearing in the study of entanglement entropies. At large local Hilbert space dimension q , we find that all moments converge simultaneously with a time scaling linearly in the size of region A , a feature previously observed in dual unitary models. However, based on the geometric interpretation, we argue that the scaling at finite q on the basis of rare membrane fluctuations, finding the logarithmic scaling of design times t k = O ( log ⁡ k ) . Our results are supported with numerical simulations performed at q = 2.
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 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.