PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Complexity of Time Evolution with Chaotic Hamiltonians

Vijay Balasubramanian, Matthew DeCross, Arjun Kar, Onkar Parrikar

arXiv:1905.05765v3hep-thcs.CCquant-ph

TL;DR

The paper asks how linear complexity growth and its time scales arise in chaotic systems. Using geodesic methods and the Eigenstate Complexity Hypothesis, it finds evidence for exponential-time linear growth in large-N SYK, while N = 2 complexity oscillates after initial linear growth.

  • Problem

    The paper seeks to understand the origin and time scales of conjectured linear complexity growth in chaotic systems, which is expected to persist until exponential times.

    Source: §1 · p. 5

  • Method

    The authors study time-evolution complexity as geodesic length on the unitary group using the Euler-Arnold equation and propose ECH as a condition for exponential-time linear growth, modulo global obstructions.

    Source: §1 · p. 6, §4 · pp. 32–33

  • Results

    Large-N SYK numerically satisfies ECH, providing evidence for exponential-time linear complexity growth; for integrable N = 2, complexity grows linearly initially and then oscillates.

    Source: §1 · p. 7, §4 · p. 33

  • Takeaways & Limitations

    The approach relates complexity growth to spectral properties and energy eigenstates, connecting it to chaos and integrability.

    Source: §4 · p. 32

    Showing that nontrivial geodesic loops remain longer than the linear solution at polynomial times requires resumming perturbation theory to account for changes in the geodesic trajectory.

    Source: §4.2 · p. 36

Abstract

from arXiv · show

We study the quantum complexity of time evolution in large-$N$ chaotic systems, with the SYK model as our main example. This complexity is expected to increase linearly for exponential time prior to saturating at its maximum value, and is related to the length of minimal geodesics on the manifold of unitary operators that act on Hilbert space. Using the Euler-Arnold formalism, we demonstrate that there is always a geodesic between the identity and the time evolution operator $e^{-iHt}$ whose length grows linearly with time. This geodesic is minimal until there is an obstruction to its minimality, after which it can fail to be a minimum either locally or globally. We identify a criterion - the Eigenstate Complexity Hypothesis (ECH) - which bounds the overlap between off-diagonal energy eigenstate projectors and the $k$-local operators of the theory, and use it to show that the linear geodesic will at least be a local minimum for exponential time. We show numerically that the large-$N$ SYK model (which is chaotic) satisfies ECH and thus has no local obstructions to linear growth of complexity for exponential time, as expected from holographic duality. In contrast, we also study the case with $N=2$ fermions (which is integrable) and find short-time linear complexity growth followed by oscillations. Our analysis relates complexity to familiar properties of physical theories like their spectra and the structure of energy eigenstates and has implications for the hypothesized computational complexity class separations PSPACE $\nsubseteq$ BQP/poly and PSPACE $\nsubseteq$ BQSUBEXP/subexp, and the "fast-forwarding" of quantum Hamiltonians.

1 Introduction

The paper asks how circuit complexity grows in chaotic systems at late times, where gravity-inspired expectations predict linear growth followed by saturation. It studies this question through geodesics on the full unitary group and analyzes when a linearly growing geodesic remains locally minimizing.

1 Introduction

  • Nielsen’s framework defines circuit complexity through a minimal geodesic on the unitary group, with a right-invariant metric that penalizes motion along nonlocal directions.The geodesic smoothly approximates a sequence of elementary gates.Source: §1 · p. 3, Figure 1 · p. 4
  • Prior work often studied geodesics in restricted state or circuit subspaces; this paper instead studies the complete SU(2^(N/2)) group manifold using SYK as a chaotic example.The authors aim to study complexity growth in chaotic systems rather than free field theories.Source: §1 · pp. 3–4
  • Chaotic-system complexity is conjectured to grow linearly until times of order e^N, then fluctuate around Cmax ∼ poly(N)e^N; the paper seeks a field-theoretic account of this behavior.Here N is the number of SYK fermions, or more generally the log dimension of the Hilbert space.Source: §1 · p. 5, Figure 2 · p. 5
  • A linearly growing geodesic to e^(-iHt) exists under locality and uniform easy-direction costs, but may cease to minimize after a conjugate point.No conjugate points at sub-exponential times is necessary, though not sufficient, for the expected exponential-time behavior.Source: §1 · p. 6
  • ECH requires off-diagonal energy-eigenstate projectors to have e^(-S)-suppressed overlap with easy directions; the authors argue it bounds conjugate points exponentially and numerically find SYK satisfies ECH.The hypothesis concerns the Hamiltonian and gate set; S is the log Hilbert-space dimension.Source: §1 · pp. 6–7

2 Geometry of SU(2N/2)

This section develops a locality-weighted right-invariant geometry on the unitary group and applies it to complexity in the N = 2 model and for arbitrary N. It describes linear growth along a simple geodesic, with oscillations and a disorder-averaged plateau in the N = 2 case.

2 Geometry of SU(2N/2)

  • For polynomial-complexity target unitaries, suppressing motion in non-k-local directions requires a cost factor μ proportional to e^S, up to a polynomial factor in S.The geometry uses gamma-matrix products as generators, assigns cost 1 to k-local directions and 1 + μ to harder directions, and defines a right-invariant metric; this makes minimal geodesic length the complexity measure.Source: §2 · pp. 7–10

2.1 Analytics for N = 2

  • For N = 2, the Euler-Arnold solution makes path length depend only on the tangent-vector magnitude at the identity, while a nonperturbative matrix method avoids path ordering to impose the endpoint condition.The method solves for initial velocities that reach the target unitary, after which the minimal-complexity geodesic must be selected among possible solutions.Source: §2.1 · pp. 11–13

2.2 Numerics for N = 2

  • For N = 2 with J3 = 0, complexity grows linearly at early times, reaches π, then oscillates linearly with slopes ±J.At the maximum distance π, the minimal path switches direction on SU(2) ≃ S3, rather than forming the late-time plateau expected for higher groups.Source: Figure 3 · p. 13, §2.2 · pp. 13–14
  • The disorder-averaged complexity grows linearly at early times with slope sqrt(π/2)σ, then approaches the late-time asymptotic value π/2.Source: Figure 5 · p. 15, §2.2 · p. 15
  • Under the stated scaling assumptions, the disorder-averaged N = 2 plateau begins at t ∼ poly(N)e^N, consistent with the expected exponential timescale.This estimate assumes Cmax ∼ poly(N)e^N and that 1/σ scales polynomially in N.Source: §2.2 · p. 16

2.3 Linear geodesic for arbitrary N

  • For arbitrary N, gamma-product generators have fully antisymmetric structure constants, and the Euler-Arnold equation distinguishes easy directions with at most k fermions from harder directions with more than k.The respective cost factors are c and c̄.Source: §2.3 · p. 17
  • The local/nonlocal velocity equations have an antisymmetric coupling structure, yet admit a simple solution within the local subspace with no nonlocal contribution.The solution uses an ansatz confined to local directions.Source: §2.3 · p. 18
  • For a k-local Hamiltonian target, the authors call the resulting path the linear geodesic; assuming it is minimal, its complexity grows linearly with time.The linear growth matches expectations from holographic calculations and earlier observations in the geodesic formalism [4] [18]; the authors then investigate whether this geodesic is the correct minimum.Source: §2.3 · pp. 18–19

3 Conjugate points and the eigenstate complexity hypothesis

This section examines when the linear geodesic ceases to minimize complexity by analyzing conjugate points and the role of cost factors. It argues that ECH keeps the geodesic locally minimizing to exponential times at large N, while allowing a small number of accidental conjugate points.

3 Conjugate points and the eigenstate complexity hypothesis

  • Conjugate points obstruct local minimality, while geodesic loops can obstruct global minimality even when no conjugate points are present.The section addresses conjugate points but does not prove the absence of geodesic loops.Source: §3 · pp. 19–20

3.1 Solving the Jacobi equation

  • The Jacobi equation is obtained by linearizing the Euler-Arnold equation around V = Ht, with easy costs c = 1 and hard costs c̄ = 1 + µ.The analysis focuses on these uniform easy and hard costs; varying hard costs with operator non-locality is left as a possible generalization.Source: §3.1 · p. 21

3.2 Conjugate points as zero modes

  • A conjugate point occurs when the first-order change in the target unitary vanishes, making the associated super-operator Y(µ) have a zero mode.A zero mode must be Hermitian and traceless to represent a valid conjugate point in su(2^(N/2)).Source: §3.2 · p. 23

3.3 Conjugate points in the bi-invariant case

  • With the bi-invariant metric, the first conjugate point occurs at t_c = 2π/(E_max−E_min), which in SYK scales as 1/N and makes the geodesic cease to be minimal early.The bi-invariant metric treats arbitrary operators as easy, unlike the physically motivated complexity metric with locality-based costs.Source: §3.3 · p. 24

3.4 Turning on cost factors

  • Numerical results show that interacting SYK satisfies ECH, whereas q = 2 SYK-like Hamiltonians have only e^−S suppression, rather than the e^−2S suppression found in chaotic systems.For the SYK samples, the reported distribution of r_mn has sample mean 1 and standard deviation 0.14; the q = 2 overlap evidence is discussed in Appendix C.Source: §3.4 · pp. 26–27
  • The ECH requires off-diagonal energy-eigenstate projectors to have exponentially suppressed overlap with local generators, a condition logically independent of ETH.The paper relates ECH to ETH for k-local generators but emphasizes that ECH specifically constrains the projectors’ overlap with the easy directions.Source: §3.4 · pp. 25, 27
  • At large N, ECH and a cost factor µ = e^(1−ϵ)S keep the linear geodesic free of conjugate points at sub-exponential times, so it remains locally minimizing for exponential times.This conclusion assumes ∆max does not scale exponentially with N; the argument moves the low-lying conjugate points of the bi-invariant case to exponential times.Source: §3.4 · p. 29
  • If an off-diagonal projector nearly lies in the easy directions, conjugate points may instead appear at O(1) times and end linear minimality early.The paper expects this behavior at small N when the energy gap is not exponentially small.Source: §3.4 · pp. 29–30
  • For chaotic systems, the cost factor can reach e^(1−ϵ)S, whereas weaker suppression in integrable systems makes the argument break down around e^(S/2).For polynomial times, the analysis permits µ ∼ e^(1−ϵ)S; beyond that value, its argument breaks down.Source: §3.4 · p. 30
  • The functions φ_mn remain close to one, so no zero modes develop before a φ_mn drops away from one, which does not occur until exponential times.The conclusion applies in the parameter regimes analyzed, where other contributions are suppressed.Source: §3.4 · p. 31
  • Almost all eigenvalues of Y remain bounded away from zero, lifting almost all conjugate points, though large corrections to a small number may leave accidental ones.The row norms of the off-diagonal correction δY are exponentially small, but the argument does not rule out significant corrections to a small number of eigenvalues.Source: §3.4 · pp. 31–32
  • The remaining accidental conjugate points are not expected to occur generically in Hamiltonian families and are expected to be destroyed by small perturbations.They require fine-tuning of δY, unlike the generic conjugate-point families in the bi-invariant metric.Source: §3.4 · p. 32

4 Discussion

The discussion connects complexity growth to spectral and eigenstate structure, and examines its late-time saturation, computational implications, and relation to quantum chaos. It identifies open questions about global minimality and extending the analysis beyond finite-dimensional systems.

4.1 Late-time saturation

  • A plateau can arise from competing geodesics and large-N self-averaging even when all operators are simple; its onset depends on the choice of simple operations.With a bi-invariant metric, the plateau starts at polynomial rather than exponential time; disorder averaging can reproduce some large-N features at small N, but washes out doubly exponential recurrences.Source: §4 · p. 33
  • In ten N = 8 SYK realizations, complexity grows linearly before saturating near t ∼ 2π/∆max, as other geodesics take over.The authors caution that numerical minimization may not find the true global minimum, so the plotted values are upper bounds.Source: §4.1 · p. 34, Figure 10 · p. 35

4.2 Quantum computation

  • The proposed global-geodesic-loop argument remains incomplete: nontrivial loops may cease to be geodesics with nonlocal costs, but their lengths require further analysis.The authors identify a precise version of this argument as a possible route to conditional separations PSPACE ⊈ BQP/poly and PSPACE ⊈ BQSUBEXP/subexp.Source: §4.2 · pp. 35–36

4.3 Quantum chaos

  • ECH links exponential-time linear complexity growth to small overlaps between off-diagonal eigenstate projectors and k-local operators, and is satisfied numerically in chaotic SYK.For N = 2, the integrable theory instead shows initial linear growth followed by oscillations.Source: §4 · p. 33, §4.3 · p. 37
  • The authors leave recovery of the continuum limit as IR and UV cutoffs are removed as an open problem.Their results were developed for finite-dimensional systems interpreted as discretized continuum theories.Source: §4.3 · p. 38

A Majorana Fermion Basis for su(2N/2)

The appendix constructs a Majorana-based generator basis for su(2N/2), then establishes its algebraic properties and derives selection rules for its structure constants.

A Majorana Fermion Basis for su(2N/2)

  • Products of Majorana operators, with factors of i chosen to ensure Hermiticity, form the proposed generator basis indexed by binary strings.The number of nonzero bits gives the number of fermions in a generator.Source: A Majorana Fermion Basis for su(2N/2) · p. 38
  • The generators are traceless and linearly independent, as shown using gamma-matrix trace properties and a contradiction based on taking traces.The appendix uses the tensor-product Pauli-matrix construction for the odd-product trace argument.Source: A Majorana Fermion Basis for su(2N/2) · p. 39
  • A structure constant is nonzero only when a ⊕ b = c and q_a q_b + q_a∧b is odd; every nonzero constant has magnitude 2.For k = 2, these rules restrict which local velocities can couple to nonlocal ones in the Euler-Arnold equation.Source: A Majorana Fermion Basis for su(2N/2) · pp. 40–41

B Conjugate points in perturbation theory

The appendix perturbs the Jacobi-field equation around the bi-invariant geodesic to track how its conjugate points move when a cost is added to heavy directions. The perturbative result finds a first-order splitting of their degeneracy and agrees with the main-text scaling under ECH.

B Conjugate points in perturbation theory

  • Turning on an infinitesimal cost ϵ for heavy directions shifts the bi-invariant conjugate-point locations at linear order.The calculation expands the Jacobi field, the Euler-Arnold equation linearized around the linear geodesic.Source: B Conjugate points in perturbation… · pp. 41–42
  • At first order in ϵ, the two-fold degeneracy of the bi-invariant conjugate points splits, but both points persist.The two possible phase choices for the initial perturbation yield the two locations.Source: B Conjugate points in perturbation… · p. 43
  • Under ECH, the perturbative analysis agrees with the main-text result that conjugate points move to t ∼ t(0)(1 + µ).The appendix obtains this agreement when the δV_L term is dropped from its perturbative expression.Source: B Conjugate points in perturbation… · p. 43

C Some more details on ECH

In SYK, coefficients of a typical off-diagonal eigenstate projector are spread across generator directions, implying the ECH scaling for its weight in easy directions. For q = 4, fermion-number symmetry splits the projector weights into two distributions without changing their overall exponential suppression.

C Some more details on ECH

  • In SYK, coefficients are more or less uniformly distributed over e^2S generators, making R_mn proportional to the easy-direction fraction as ECH requires.Figure 11 shows the coefficients for a typical projector; pooling them across projectors gives an exponential-tail distribution.Source: C Some more details on ECH · p. 44, Figure 11 · p. 44
  • Pooling SYK coefficients yields an exponential tail, so normalized sums over easy coefficients are expected to give Gaussian R_mn distributions at large N, consistent with Fig. 8.This expectation follows from the central limit theorem.Source: C Some more details on ECH · p. 44
  • For the integrable Hamiltonian H = ψ1ψ2, projector coefficients overlap with about e^S generators rather than SYK's e^2S, suggesting milder R_mn suppression.Figure 12 shows coefficients for a typical projector of this Hamiltonian.Source: C Some more details on ECH · p. 44, Figure 12 · p. 44
  • For q = 4, fermion-number-preserving projectors have enhanced R_mn and fermion-number-reversing projectors have suppressed R_mn, with only polynomial shifts that preserve overall exponential suppression.Figure 13 shows the two distributions for k = 4, q = 4, and N = 12.Source: C Some more details on ECH · p. 45, Figure 13 · p. 45
Loading 1905.05765v3…