Quantum complexity and negative curvature

As time passes, once simple quantum states tend to become more complex. For strongly coupled $k$-local Hamiltonians, this growth of computational complexity has been conjectured to follow a distinctive and universal pattern. In this paper we show that the same pattern is exhibited by a much simpler system—classical geodesics on a compact two-dimensional geometry of uniform negative curvature. This striking parallel persists whether the system is allowed to evolve naturally or is perturbed from the outside.

Figure 1

An example of a random circuit with $K=6$, $k=2$, and depth 4. The six qubits (black lines) are randomly grouped into three ordered pairs, and then a gate (blue box) is applied to each pair. At the next time step, they are randomly regrouped.

Figure 2

The evolution of the computational complexity of the operator $e^{iH\tau }$ for a generic $k$-local Hamiltonian $H$. At $t=0$ the operator $e^{iHt}$ is the identity and so has complexity zero. At early and intermediate times the complexity increases linearly, with coefficient $K/2$. After a time exponential in the number of qubits $K$, the complexity saturates at a value ${\mathcal{C}}_{\max }$ that is exponential in $K$. It then fluctuates near that maximum value. Very very rarely—so rarely that we must wait the double exponentially long quantum recurrence time for it to be likely to have happened even once—the complexity of the system may fluctuate down to near zero, before growing again.

Figure 3

The size of the precursor as a function of $\tau -{\tau }_{*}$ for the epidemic function Eq. (2.11). For $\tau -{\tau }_{*}\ll 1$ the size is growing exponentially as the epidemic spreads throughout the system, but it is growing from such a small baseline as to be visually indistinguishable from zero. When $\tau ={\tau }_{*}$, almost every site is infected, and $s(\tau )$ abruptly saturates at $K$.

Figure 4

The multiple precursor operator $W_{\text{multi}}({\tau }_n,{\tau }_{n-1},\dots ,{\tau }_1)$. When ${\tau }_i-{\tau }_{i-1}$ and ${\tau }_{i+1}-{\tau }_i$ have the same sign, as at ${\tau }_2$ and ${\tau }_6$, $W_i$ is called a “through-going” insertion, and there is generically no cancellation. When ${\tau }_i-{\tau }_{i-1}$ and ${\tau }_{i+1}-{\tau }_i$ have opposite signs, as at the other ${\tau }_i$, this is called a “switchback,” and there is a partial cancellation that reduces the complexity by $K{\tau }_{*}$.

Figure 5

An example of a compactification of the hyperbolic plane. Start with a ginormous equilateral polygon centered at the origin, and then identify sides to make the compact and conical-deficit-free space ${\mathcal{H}}_g$.

Figure 6

Following a geodesic on ${\mathcal{H}}_g$. When the geodesic crosses the red polygon that bounds ${\mathcal{H}}_g$ through side $A$, it re-enters the geometry at the identified point on the polygon through side $\overline{A}$. (For convenience, the identified sides are shown here as being close together, though typically they will be very distant.) In this picture, a geodesic is traced through several such exits, re-entries, and re-exits.

Figure 7

A small perturbation represented as a perpendicular kick to a geodesic.

Figure 8

Perturbing a trajectory of increasing complexity results in a new trajectory on which the complexity is still increasing. Since the conformal factor $y^{-2}$ is blowing up at small $y$, the horizontal deviation is exponentially increasing. However, the rate of change of complexity is almost unaffected by the kick.

Figure 9

On the left side, we show a trajectory of decreasing complexity—$y$ is increasing. On the right side, we show the effect of a perturbation. The kick results in a small change of direction in the trajectory, which is then magnified by the negative curvature. After a scrambling time, the complexity bottoms out and starts to increase ($y$ decreases).

Figure 10

A precursor is represented by three segments of geodesics in ${\mathbb{H}}^2$. This is a schematic picture that represents distances more faithfully than in Poincaré coordinates.

Figure 11

Schematic representation of the product of two precursors on the negatively curved geometry. For large $|{\tau }_1|$, $|{\tau }_2|$, and $|{\tau }_1-{\tau }_2|$, the length of the shortest geodesic connecting the start to the end is shorter than the sum of the five defining geodesic segments by an amount equal to two individual switchback subtractions.

Figure 12

The number of possible circuits grows exponentially with circuit depth. At depth zero, the circuit is the identity. After a single time step (on left), there are $\mathrm{O}(K^{K/2})$ possible unitaries that could have been created. After two time steps (on right), there are $\mathrm{O}(K^K)$. Almost all the possible unitaries reached after two steps are distinct though there are rare coincidences. This forms a tree. A Cayley tree is known to be a discrete model of a hyperbolic space.

Figure 13

We thank the mathematician and artist Daina Taimina for allowing us to use her crocheted model as an illustration of how space-filling the hyperbolic plane becomes when embedded in flat space. The geometry of the surface is a slightly thickened hyperbolic plane. As it grows out from the center, it will become densely packed at some radial distance from the starting point. The larger the dimension of the embedding space, the further the crocheting can proceed before becoming densely packed.