Extending linear quantum complexity growth to qubit local circuits and fixed time-independent Hamiltonians

The paper 'Models of Quantum Complexity Growth' rigorously connected the growth of quantum circuit complexity to the formation of approximate unitary $k$-designs, proving that local random circuits with Haar-random two-site gates have linearly growing complexity in the limit of large local dimension $q$. Three source-faithful questions from that work remain open: (1) prove design growth linear in the design order $k$ (Conjecture 2 of the paper: $\mathsf{G}$-local circuits of size $T=O(nk)$ form approximate $k$-designs) for qubit circuits with $q=2$, ideally for $k$ exponentially large in $n$, so that linear strong complexity growth extends to times exponential in system size; (2) prove nontrivial lower bounds on the complexity $C_\delta(e^{-iHt})$ of evolution under specific, fixed, time-independent local Hamiltonians, where design-based techniques fail because they rely on randomness in time; (3) determine whether the $k$-dependent Catalan-number prefactor in the high-order Haar moment bound is necessary or an artifact of the proof. Later work has substantially advanced but not closed these cores: exact and nearly-linear ($\Omega(T/\log T)$) constant-error complexity growth now holds for qubit random circuits up to exponentially many gates, $k$-independent and constant spectral gaps yield designs of size $O(n^2k)$, near-optimal $1$D designs of size $O(nk\log k)$ exist for magic-augmented ensembles, and sustained complexity growth has been proven for generic local time-independent Hamiltonians — yet exactly linear design growth for plain Haar-local qubit circuits, linear strong complexity for qubits, lower bounds for specific named Hamiltonians, and the Catalan-constant question all survive.

Background

Quantum circuit complexity is the minimum number of elementary (say, two-qubit) gates needed to synthesize a given unitary $U$ or quantum state, possibly up to an error tolerance $\delta$; it is written $C_\delta(U)$. Most unitaries on $n$ qubits have complexity exponential in $n$ by a counting argument, but proving lower bounds for any particular unitary is notoriously hard, since one must rule out every possible computational shortcut. Brown and Susskind nevertheless conjectured, motivated by the AdS/CFT correspondence (where the growth of a black-hole interior is dual to the growth of the boundary state's complexity), that in a chaotic quantum many-body system the complexity of the time-evolved state grows linearly in time for a time exponential in the system size, long after entanglement entropies have saturated.

A unitary $k$-design is an ensemble of unitaries whose first $k$ statistical moments match those of the Haar measure (the uniform measure on the unitary group); approximate $k$-designs reproduce those moments up to a small error. Random quantum circuits are the standard physical way to build $k$-designs: a $\mathsf{G}$-local circuit is a sequence of random two-site gates drawn from a fixed gate set, arranged on $n$ qudits of local dimension $q$ ($q=2$ for qubits, total Hilbert-space dimension $d=q^n$). Brandão, Harrow, and Horodecki proved that such circuits of size $O(n^2k^{11})$ form approximate $k$-designs, with improved bounds available only for large $q$ or special geometries. The key idea of the source paper (Brandão, Chemissany, Hunter-Jones, Kueng, and Preskill, PRX Quantum 2, 030316 (2021)) is that an approximate $k$-design must contain exponentially many unitaries of complexity roughly proportional to the circuit size that generated it, so lower bounds on design growth convert into lower bounds on complexity growth. Using this, they proved that local random circuits at sufficiently large local dimension $q$ have 'strong' complexity growing linearly in the circuit size $T$. Their strong complexity is a deliberately more stringent notion: a state has strong complexity less than $r$ if a pre-processing circuit of size $r$ followed by a simple measurement can distinguish the state from the maximally mixed state near-optimally; a lower bound on strong complexity implies the corresponding bound on ordinary circuit complexity.

The paper is explicit about what its methods cannot reach. For qubits ($q=2$) the known design-formation size carried polynomial overheads in both $n$ and $k$, so the paper's Conjecture 2 — that $\mathsf{G}$-local circuits of size $T=O(nk)$ form approximate $k$-designs — was 'currently out of reach', and the authors note they 'have not proved linear complexity growth up to time scales of order $d$' and that 'proving an optimal design growth for local random circuits away from the large $q$ limit would allow us to better probe late-time complexity'. Second, the design route fundamentally uses randomness in time: for an ensemble of time-evolutions generated by time-independent Hamiltonians the rigid spectral structure prohibits late-time Haar randomness, so understanding complexity growth for the deterministic, energy-conserving evolution $e^{-iHt}$ of a fixed local Hamiltonian $H$ — precisely the holographically motivated case — requires techniques beyond designs. Third, the main technical tool is a new high-order Haar moment bound for the outcome statistics of measurements applied to Haar-random unitaries: for a bipartite input state and a measurement $M$, the $k$-th centered moment of $\mathrm{Tr}[M(U\otimes I)\rho(U^\dagger\otimes I)]$ is bounded by $C_k(k!)^2/d^{k/2}$, where $C_k$ is the $k$-th Catalan number. This bound is obtained via Schur–Weyl duality (the standard decomposition of tensor powers of the Hilbert space under the joint action of the unitary group and the permutation group), Weingarten calculus — the calculus for integrating polynomials over the unitary group — and tensor-network and convex-optimization arguments. The authors believe the $d^{-k/2}$ scaling is tight but state they 'do not know if the Catalan number is necessary, or merely an artifact of our proof technique'.

Subsequent work sharpened the scalings: random brickwork qubit circuits (two-qubit gates arranged in alternating, staggered layers) form approximate $k$-designs at depth $O(nk^{5+o(1)})$ (improving the $O(nk^{10.5})$ bound obtained from the spectral-gap method — the spectral gap being the gap between the two largest eigenvalues of the moment operator, the matrix whose mixing rate governs convergence of the circuit's $k$-th moments to the Haar moments), then with a number-of-gates overhead $\tilde O(n^2k)$ and a spectral gap independent of $k$, and most recently with a constant spectral gap; near-optimal $1$D $k$-designs with $O(nk\log k)$ magic (non-Clifford) gates exist for a Clifford+$T$ random ensemble (Clifford gates augmented by non-Clifford gates of the standard fault-tolerant gate set); and the constant-error circuit complexity of random qubit circuits was proven to grow as $\Omega(T/\log T)$ up to $T\le 4^n$. On the Hamiltonian side, sustained (though not linear) complexity growth was proven for generic local time-independent Hamiltonians and typical high-temperature product states. What remains unresolved, in the precise forms the source paper states them, is the content of the problem below.

Problem Statement

Establish the linear growth of quantum complexity — and the unitary-design growth that implies it — for physically relevant quantum many-body dynamics, removing the large-local-dimension and randomness-in-time assumptions under which the source results were proven. Specifically, in the formulations stated by Brandão, Chemissany, Hunter-Jones, Kueng, and Preskill (PRX Quantum 2, 030316 (2021)):

(1) Design growth for qubit circuits. Prove that $\mathsf{G}$-local random circuits on $n$ qubits (local dimension $q=2$) of size $T=O(nk)$ form approximate unitary $k$-designs — the paper's Conjecture 2 — improving on the then-known size $O(n^2k^{11})$ and on the current state of the art ($O(n^2k)$ via constant spectral gaps; $O(nk\log k)$ magic gates for magic-augmented 1D ensembles). Ideally the statement should hold for design orders $k$ exponentially large in $n$, so that the paper's route (an approximate $k$-design contains exponentially many unitaries of complexity proportional to the generating circuit size) extends the linear strong (distinguishing-measurement) complexity growth of local random circuits from the large-$q$ regime to qubits, and to times exponential in the system size.

(2) Complexity growth for time-independent Hamiltonians. Prove lower bounds on the complexity $C_\delta(e^{-iHt})$ of the unitary generated by a specific, fixed, local, time-independent Hamiltonian $H$ — the energy-conserving and holographically motivated case — that increase with the evolution time $t$ (so that a $t$-independent bound does not qualify as nontrivial) and ideally are linear in $t$, i.e. $\Omega(t)$. The statement does not supply $H$: any specific fixed local model that the solver names explicitly and holds fixed is admissible, with a chaotic, holographically motivated local model the intended target. The design-based techniques of the source paper cannot apply directly, since ensembles of time-independent evolutions do not converge to approximate designs at late times (eigenvalue rigidity: the fixed, discrete spectrum of $H$ prevents the evolutions $e^{-iHt}$ from equidistributing over the unitary group as $t$ varies), so new proof techniques are required; existing unconditional results cover only generic (measure-typical) Hamiltonians, random Hamiltonian ensembles, or bounds conditional on complexity-theoretic assumptions.

(3) Constants in the Haar moment bound. Determine whether the $k$-dependent prefactor $C_k(k!)^2$ (with $C_k$ the $k$-th Catalan number) in the source paper's high-order Haar moment bound for measurement outcome statistics is necessary or can be removed/reduced, which would sharpen the quantitative complexity lower bounds obtainable from design growth.

These three deliverables serve one common objective: a rigorous quantitative theory of quantum complexity growth in local many-body dynamics without the large-$q$ or time-randomness crutches — with (1) supplying the design-growth engine, (2) its extension to deterministic energy-conserving dynamics, and (3) the sharp constants that control the resulting complexity counts. Each of (1)–(3) is posed as an independent open problem and may be resolved on its own; a full realization of the common objective requires all three.

References

1. Fernando G. S. L. Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, and John Preskill, 'Models of Quantum Complexity Growth', PRX Quantum 2, 030316 (2021), DOI 10.1103/PRXQuantum.2.030316, https://doi.org/10.1103/PRXQuantum.2.030316, arXiv:1912.04297, https://arxiv.org/abs/1912.04297.
2. Fernando G. S. L. Brandão, Aram W. Harrow, and Michał Horodecki, 'Local Random Quantum Circuits are Approximate Polynomial-Designs', Communications in Mathematical Physics 346, 397–434 (2016), DOI 10.1007/s00220-016-2706-8, https://doi.org/10.1007/s00220-016-2706-8.
3. Adam R. Brown and Leonard Susskind, 'The Second Law of Quantum Complexity', Physical Review D 97, 086015 (2018), DOI 10.1103/PhysRevD.97.086015, https://doi.org/10.1103/PhysRevD.97.086015, arXiv:1701.01107, https://arxiv.org/abs/1701.01107.
4. Nicholas Hunter-Jones, 'Unitary designs from statistical mechanics in random quantum circuits' (2019), arXiv:1905.12053, https://arxiv.org/abs/1905.12053.
5. Jonas Haferkamp, Philippe Faist, Naga B. T. Kothakonda, Jens Eisert, and Nicole Yunger Halpern, 'Linear growth of quantum circuit complexity' (2021), arXiv:2106.05305, https://arxiv.org/abs/2106.05305.
6. Zhi Li, 'Short Proofs of Linear Growth of Quantum Circuit Complexity' (2022), arXiv:2205.05668, https://arxiv.org/abs/2205.05668.
7. Jonas Haferkamp, 'Random quantum circuits are approximate unitary $t$-designs in depth $O(nt^{5+o(1)})$' (2022), arXiv:2203.16571, https://arxiv.org/abs/2203.16571.
8. Jonas Haferkamp, 'On the moments of random quantum circuits and robust quantum complexity' (2023), arXiv:2303.16944, https://arxiv.org/abs/2303.16944.
9. Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan, 'Incompressibility and spectral gaps of random circuits' (2024), arXiv:2406.07478, https://arxiv.org/abs/2406.07478.
10. Tim Baer and Jeongwan Haah, 'Random unitary circuits with constant spectral gap' (2026), arXiv:2607.20919, https://arxiv.org/abs/2607.20919.
11. Zhi Li, 'One Gate at a Time: Complexity Growth in Random Quantum Circuits' (2026), arXiv:2609.17457, https://arxiv.org/abs/2609.17457.
12. Wonjun Lee, Saúl Pilatowsky-Cameo, and Soonwon Choi, 'Sustained growth of quantum circuit complexity in many-body Hamiltonian dynamics' (2026), arXiv:2609.26885, https://arxiv.org/abs/2609.26885.
13. Guoding Liu and Jonas Helsen, '(Almost) quadruply optimal unitary designs in 1D' (2026), arXiv:2608.18650, https://arxiv.org/abs/2608.18650.
14. Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen, 'Simple constructions of linear-depth t-designs and pseudorandom unitaries' (2024), arXiv:2404.12647, https://arxiv.org/abs/2404.12647.
15. Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang, 'Random unitaries in extremely low depth' (2024), arXiv:2407.07754, https://arxiv.org/abs/2407.07754.
16. Shivan Mittal and Nicholas Hunter-Jones, 'Local random quantum circuits form approximate designs on arbitrary architectures' (2023), arXiv:2310.19355, https://arxiv.org/abs/2310.19355.
17. Michał Oszmaniec, Marcin Kotowski, Michał Horodecki, and Nicholas Hunter-Jones, 'Saturation and Recurrence of Quantum Complexity in Random Local Quantum Dynamics', Physical Review X 14, 041068 (2024), DOI 10.1103/PhysRevX.14.041068, https://doi.org/10.1103/PhysRevX.14.041068, arXiv:2205.09734, https://arxiv.org/abs/2205.09734.
18. Marcin Kotowski, Michał Oszmaniec, and Michał Horodecki, 'Extremal jumps of circuit complexity of unitary evolutions generated by random Hamiltonians' (2023), arXiv:2303.17538, https://arxiv.org/abs/2303.17538.
19. Jeongwan Haah and Douglas Stanford, 'Growth and collapse of subsystem complexity under random unitary circuits' (2025), arXiv:2510.18805, https://arxiv.org/abs/2510.18805.