Models of Quantum Complexity Growth

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.

Popular Summary

Quantum complexity is central to quantum information theory and arises in many recent developments in both quantum many-body physics and high-energy theory. Intuitively speaking, quantum complexity measures how far away a state (or unitary) is from a simple initial configuration, e.g., a product state (the identity map). This notion is closely related to the minimum time—or more precisely, the circuit size—required to prepare a certain state (unitary) of interest. While upper bounds on quantum complexity are comparatively easy, lower bounds are notoriously challenging, as these are contingent on the nonexistence of a more efficient state and unitary preparation procedure.

In this work, we rigorously derive lower bounds on the complexity growth for a variety of random time evolutions. Our arguments involve three steps: We first relate the traditional definition of circuit complexity to a strictly stronger one that comes with an operational interpretation in terms of an optimal distinguishing measurement. We then leverage techniques from representation theory, tensor networks, and convex geometry to prove that most elements of a unitary $k$-design must have strong circuit complexity proportional to $k$. Finally, we use powerful existing results on the convergence of various models to unitary designs in order to relate design growth to the evolution time, or, more precisely, circuit size. Combining these steps then implies that local random quantum circuits generate unitary transformations whose complexity grows linearly in time. In a broader context, our work aims to bridge exciting ideas in different fields: Quantum many-body physics and holography on the one hand, and quantum information on the other.

Figure 1

Expected complexity growth in random circuits. Conjecture 1 states that, for random quantum circuits acting on $n$ qubits, the circuit complexity grows linearly with circuit size (time) until it saturates at a value exponentially large in $n$. Our work provides rigorous evidence supporting this picture for quantum systems with sufficiently large local dimension; see Corollary 5.

Figure 2

Pictographic illustration of strong state complexity (Definition 2). A blackbox either outputs a (known) pure state $\rho =|\psi ⟩⟨\psi |$, or the maximally mixed state ${\rho }_0=(1/d)\mathbb{I}$. The task is to correctly guess which one it produced by applying a preprocessing circuit $V$ (blue line pattern) of limited size $r$ and performing a simple measurement (right). We say that $|\psi ⟩$ has strong state complexity less than $r$ if the probability of correctly distinguishing both possibilities is close to optimal.

Figure 3

Pictographic illustration of strong unitary complexity (Definition 3). A blackbox (center) takes quantum states as inputs and applies either a unitary channel $\mathcal{U}(\rho )=U\rho U^{†}$, or the depolarizing channel $\mathcal{D}(\rho )={\rho }_0=\mathbb{I}/d$. The task is to correctly guess which evolution occurred. The rules of the game allow short pre- and postprocessing circuits (blue line patterns) that may involve a quantum memory. The final guess must be based on a simple measurement (right). We say that $U$ has complexity less than $r=r^{\prime }+r^{″}$ if the probability of correctly distinguishing both options is close to optimal.

Figure 4

Illustration of elementary gate decompositions. A unitary $V$ on $n=10$ qudits is comprised of $12$ geometrically local 2-qudit gates at random positions, i.e., $\mathrm{size}(V)=12$.