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.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.

arXiv:2409.03656Physical review. B./Physical review. BMay 19, 20260 citations

The power of noisy random quantum circuits

Bill Fefferman

Bulletin of the American Physical SocietyMar 16, 20210 citations

Random unitaries in extremely low depth

Thomas Schuster, Jonas Haferkamp, Hsin-Yuan Huang

Random unitaries are central to quantum technologies and the study of complex quantum many-body physics. However, existing protocols for generating random unitaries require long evolution times and deep circuits. In this work, we prove that local quantum circuits can form random unitaries in extremely low depth on any geometry. These shallow circuits have low complexity and create only short-range correlations, yet are indistinguishable from random unitaries with exponential complexity. This finding contrasts sharply with classical systems, in which a long evolution time is required to appear random. Our results have widespread applications across quantum science, from device benchmarking to quantum advantages. Moreover, they reveal that fundamental physical properties-including evolution time, causal structure, and phases of matter-are provably hard to learn.Random unitaries are central to quantum technologies and the study of complex quantum many-body physics. However, existing protocols for generating random unitaries require long evolution times and deep circuits. In this work, we prove that local quantum circuits can form random unitaries in extremely low depth on any geometry. These shallow circuits have low complexity and create only short-range correlations, yet are indistinguishable from random unitaries with exponential complexity. This finding contrasts sharply with classical systems, in which a long evolution time is required to appear random. Our results have widespread applications across quantum science, from device benchmarking to quantum advantages. Moreover, they reveal that fundamental physical properties-including evolution time, causal structure, and phases of matter-are provably hard to learn.

arXiv:2407.07754ScienceJul 3, 202571 citations

Notes on Interrogating Random Quantum Circuits

Luís T. A. N. Brandão, René Peralta

Jan 1, 20203 citations

On the moments of random quantum circuits and robust quantum complexity

Jonas Haferkamp

We prove new lower bounds on the growth of robust quantum circuit complexity -- the minimal number of gates $C_δ(U)$ to approximate a unitary $U$ up to an error of $δ$ in operator norm distance. More precisely we show two bounds for random quantum circuits with local gates drawn from a subgroup of $SU(4)$ . First, for $δ=Θ(2^{-n})$ , we prove a linear growth rate: $C_δ\geq d/\mathrm{poly}(n)$ for random quantum circuits on $n$ qubits with $d\leq 2^{n/2}$ gates. Second, for $ δ=Ω(1)$, we prove a square-root growth of complexity: $C_δ\geq \sqrt{d}/\mathrm{poly}(n)$ for all $d\leq 2^{n/2}$ . Finally, we provide a simple conjecture regarding the Fourier support of randomly drawn Boolean functions that would imply linear growth for constant $δ$ . While these results follow from bounds on the moments of random quantum circuits, we do not make use of existing results on the generation of unitary $t$ -designs. Instead, we bound the moments of an auxiliary random walk on the diagonal unitaries acting on phase states. In particular, our proof is comparably short and self-contained.We prove new lower bounds on the growth of robust quantum circuit complexity -- the minimal number of gates $C_δ(U)$ to approximate a unitary $U$ up to an error of $δ$ in operator norm distance. More precisely we show two bounds for random quantum circuits with local gates drawn from a subgroup of $SU(4)$. First, for $δ=Θ(2^{-n})$, we prove a linear growth rate: $C_δ\geq d/\mathrm{poly}(n)$ for random quantum circuits on $n$ qubits with $d\leq 2^{n/2}$ gates. Second, for $ δ=Ω(1)$, we prove a square-root growth of complexity: $C_δ\geq \sqrt{d}/\mathrm{poly}(n)$ for all $d\leq 2^{n/2}$. Finally, we provide a simple conjecture regarding the Fourier support of randomly drawn Boolean functions that would imply linear growth for constant $δ$. While these results follow from bounds on the moments of random quantum circuits, we do not make use of existing results on the generation of unitary $t$-designs. Instead, we bound the moments of an auxiliary random walk on the diagonal unitaries acting on phase states. In particular, our proof is comparably short and self-contained.

arXiv:2303.16944Mar 29, 20231 citation

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.

We prove new lower bounds on the growth of robust quantum circuit complexity -- the minimal number of gates

C_δ(U)

to approximate a unitary

U

up to an error of

δ

in operator norm distance. More precisely we show two bounds for random quantum circuits with local gates drawn from a subgroup of

SU(4)

. First, for

δ=Θ(2^{-n})

, we prove a linear growth rate:

C_δ\geq d/\mathrm{poly}(n)

for random quantum circuits on

n

qubits with

d\leq 2^{n/2}

gates. Second, for $ δ=Ω(1)$, we prove a square-root growth of complexity:

C_δ\geq \sqrt{d}/\mathrm{poly}(n)

for all

d\leq 2^{n/2}

. Finally, we provide a simple conjecture regarding the Fourier support of randomly drawn Boolean functions that would imply linear growth for constant

δ

. While these results follow from bounds on the moments of random quantum circuits, we do not make use of existing results on the generation of unitary

t

-designs. Instead, we bound the moments of an auxiliary random walk on the diagonal unitaries acting on phase states. In particular, our proof is comparably short and self-contained.