PaperlayerView exact revision on arXiv

Source-linked AI summary

Models of quantum complexity growth

Fernando G. S. L. Brandão, Wissam Chemissany, Nicholas Hunter-Jones, Richard Kueng, John Preskill

arXiv:1912.04297v1hep-thcond-mat.str-elquant-ph

TL;DR

Lower bounds on the complexity of particular quantum states and unitaries are difficult because efficient shortcuts are hard to rule out. The paper instead connects unitary k-design growth to strong complexity and proves that local random circuits exhibit linear complexity growth for sufficiently large local dimension. These results provide rigorous support for the expected behavior of chaotic quantum systems under an ancilla-assisted distinguishing definition.

  • Problem

    Useful lower bounds for the complexity of states generated by particular many-body Hamiltonians are difficult to prove, despite the expectation of linear growth for exponentially long times.

  • Method

    The paper rigorously connects approximate unitary k-designs to strong complexity defined through ancilla-assisted distinguishing measurements.

  • Results

    Local random circuits contain at least exp(Ω(T)) elements with strong complexity Ω(T) when the local dimension is sufficiently large.

  • Takeaways & Limitations

    Design-growth results can establish linear complexity growth for local random circuits, supporting the expected chaotic-system scaling.

  • Takeaways & Limitations

    The design-based argument does not extend directly to late-time evolution by time-independent Hamiltonians, whose ensembles are not expected to remain k-designs.

Abstract

from arXiv · show

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 short-cut 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 which 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.

1 Motivation and overview

Quantum complexity is difficult to lower-bound for particular states or evolutions, so the paper studies generic ensembles and connects complexity growth rigorously to unitary k-design growth. This framework supports linear complexity growth for local random circuits under a strong, ancilla-assisted distinguishing definition, especially at sufficiently large local dimension.

  • 1 Motivation and overview: The motivation is that chaotic Hamiltonian evolution is expected to produce linear complexity growth for exponentially long times, but useful lower bounds for particular Hamiltonians remain difficult.The paper therefore studies ensembles of circuits rather than relying only on complexity-theoretic assumptions.
  • 1 Motivation and overview: Earlier counting arguments suggest linear complexity growth until exponential saturation, while rigorous prior results provided weaker polynomial growth and restricted operational access.The paper’s framework addresses these shortcomings through k-designs and a stronger distinguishing formulation.
  • 1 Motivation and overview: The paper defines strong complexity through the minimum circuit size of an ancilla-assisted measurement that distinguishes a circuit from the completely depolarizing channel.This strong notion implies weaker complexity notions such as the minimum circuit size needed to approximate the unitary.
  • 1 Motivation and overview: A linear growth in unitary design order implies linear growth in strong quantum circuit complexity.Approximate k-designs typically contain elements with strong complexity approximately k, and their weight distributions cannot be too concentrated.
  • 1 Motivation and overview: Approximate k-designs contain exponentially many high-complexity unitaries that are nearly maximally separated in diamond norm.The geometric statement rules out concentrating most high-complexity unitaries into a few tightly packed clusters.
  • 1 Motivation and overview: Local circuits of size T contain at least exp(Ω(T)) elements with strong complexity Ω(T) when the local dimension is sufficiently large.This follows from linear design growth for local random circuits and applies when q ≥ q0(T).

2 Quantum complexity and unitary designs

The paper defines strong state and unitary complexity operationally through the difficulty of distinguishing useful quantum objects from maximally mixed or depolarizing alternatives using limited circuits. It then connects approximate unitary designs to large numbers of high-complexity states and unitaries, strengthening probabilistic results about complexity growth.

  • 2.1.1 State complexity: Strong state complexity measures how large a circuit is needed for a restricted measurement to distinguish a pure state from the maximally mixed state.The measurement circuit uses at most r 2-local gates, and complexity is defined by achieving near-optimal distinguishing bias.
  • 2.1.1 State complexity: The strong state-complexity definition is more stringent than traditional preparation complexity: high traditional complexity does not generally imply high strong state complexity.A state containing a generic component can have high traditional complexity while a simple measurement on one qudit distinguishes it effectively.
  • 2.1.2 Unitary complexity: Strong unitary complexity analogously measures the resources needed to distinguish a unitary channel from the completely depolarizing channel.The operational strategy permits limited pre-processing, post-processing, state preparation, and quantum memory, with total size r = r′ + r′′.
  • 2.3 State complexity from designs: An approximate 2k-design contains at least order (d/k)^k distinct states with strong complexity at least r + 1, subject to the stated bound on r.Theorem 2 applies to states generated from a fixed starting state by the unitaries in the design.
  • 2.4 Moment bounds: A discrete approximate 2k-design contains at least order (d^2/k)^k distinct unitaries with strong complexity at least r + 1, under the stated condition on r.Theorem 3 concerns strong unitary complexity and therefore supports a stronger conclusion than traditional approximation-based definitions.
  • 2.5 Relation to previous work: The paper converts average-case design-growth statements into quantitative counting results by proving that approximate-design weights cannot be excessively concentrated.This rules out ensembles whose high complexity is carried by only a tiny number of heavily weighted elements.

3 Complexity growth in random circuits

The paper connects complexity growth to approximate unitary designs, then applies known design-growth results to random-circuit models. This yields polynomial complexity growth generally and linear growth for local Haar-random circuits at large local dimension.

  • 3.1 Local random circuits: G-local random circuits are generated by repeatedly applying random neighboring two-qubit gates from a universal gate set, with each gate defining one time step.The construction uses a finite gate set containing inverses.
  • 3.1 Local random circuits: Theorem 5 shows that G-local random circuits form approximate k-designs once their size satisfies the stated polynomial design-growth condition.The bound depends on the local dimension, approximation error, design order, and gate set.
  • 3 Complexity growth in random circuits: Approximate k-designs contain exponentially many high-complexity unitaries that are nearly maximally separated, limiting the effect of circuit collisions.This provides the rigorous bridge from design properties to complexity lower bounds.
  • 3.1 Local random circuits: The resulting complexity bound is polynomial: circuits of size T contain unitaries with strong δ-unitary complexity r related by T ≃ r^11.The construction guarantees at least ˜C2log(n)r such unitaries under the stated conditions.
  • 3.3 Linear growth in design for local random circuits at large local dimension: At large local dimension q, most local random circuits have strong complexity Ω(T), establishing linear complexity growth for a long time.This verifies the linear-growth conjecture for the large-q Haar-random two-site model, though not for an exponentially long time.
  • 3.6 Comment on time-independence: Brownian circuits have complexity growing polynomially in time as Ω(t^1/11), while time-independent Hamiltonian evolutions generally do not form late-time k-designs.The latter limitation follows from the rigid spectral structure of time-independent evolution.

4 Complexity in holographic systems

The paper relates its complexity framework to holographic expectations, including long-time growth and the switchback effect. It also argues that the strong distinguishing-measurement definition captures useful-computation potential in ways the standard circuit definition may not.

  • 4 Complexity in holographic systems: The paper proves linear complexity growth for large-q local random circuits, but notes that this design-based connection is unlikely to directly describe time-independent Hamiltonian evolution in holography.The stated result is linear growth, though not for an exponentially long time.
  • Strong complexity in the bulk: The strong complexity definition is motivated as potentially more compatible with holographic expectations than standard circuit complexity.The paper frames this as a motivation rather than a proved holographic equivalence.
  • Strong complexity in the bulk: For evolved local operators, both definitions exhibit a switchback delay before linear growth begins after the operator spreads across the system.The delay is associated with cancellations outside the operator’s lightcone and ends near the scrambling time.
  • Strong complexity in the bulk: Adding one clean qubit leaves minimal circuit complexity unchanged but resets distinguishing-measurement complexity to order one.This difference motivates interpreting strong complexity as encoding potential for useful quantum computation.
  • 4 Complexity in holographic systems: Design order can grow long-term even though entanglement entropies saturate after relatively short growth in design order.The section uses this contrast to connect complexity growth with holographic geometric growth.

5 Proof of the main results

The proof establishes that random states and design elements are typically highly complex, and that high-complexity elements cannot be confined to a few clusters. Probabilistic counting and concentration arguments provide the core mechanism.

  • 5.1.1 Most states have high complexity: A random pure state is exceedingly likely to have exponentially large strong δ-state complexity.The fraction of low-complexity states remains exponentially tiny until r ≃ q^n/log(n).
  • 5.1.2 Most high-complexity states are far apart: Concentration of measure and a union bound generate distant high-complexity states iteratively until exponential suppression is balanced by the list size.The argument first chooses a high-complexity state and then excludes states too close to previously chosen elements.
  • 5.1.2 Most high-complexity states are far apart: The probabilistic method shows that exponentially many high-complexity states have pairwise trace distance at least 1 − ∆.The construction obtains N = 1/6 exp(∆^2d^9π^3) such states.
  • 5 Proof of the main results: The proof’s technical contribution is a tight bound on the Haar moments needed to extend these concentration arguments to approximate 2k-design ensembles.The bound identifies the highest design moment that still approximates Haar-random behavior.
  • 5.2 Designs contain distant high-complexity states: For approximate spherical k-designs, low-complexity states occur with probability O(d^-k) when r is below the stated k-dependent threshold.A second probability bound controls closeness to any fixed reference state.
  • 5.2 Designs contain distant high-complexity states: For approximate unitary k-designs, low-complexity unitaries occur with probability O(d^-2k) when r is roughly below the stated nk threshold.The same union-bound construction then yields many high-complexity unitaries far from one another.

6 Conceptual background and contributions

The section develops optimal single-shot strategies for distinguishing classical distributions, quantum states, and quantum channels, then uses these operational ideas to define circuit-based quantum complexity. It introduces local gate decompositions as the basis for measuring circuit size and simplicity.

  • 6.1.1 Distinguishing classical probability distributions: Maximum-likelihood events optimize single-shot discrimination of classical distributions under nonnegativity and normalization constraints.The optimal event selects outcomes where p_i ≥ q_i.
  • 6.1.2 Distinguishing quantum states: The optimal measurement for distinguishing quantum states projects onto the positive range of ρ − σ, yielding the trace distance as the optimal bias.This is identified as the Holevo-Helstrom theorem.
  • 6.1.3 Distinguishing quantum channels: Channel discrimination permits entangled inputs with quantum memory, and optimizing over inputs and measurements defines the diamond distance.Convexity allows the input optimization to be restricted to pure states, while the resulting optimization has a semidefinite-program formulation.
  • 6.2 Quantum complexity: A universal two-qudit gate set decomposes arbitrary unitaries into finite local circuits, with circuit size counting total elementary gates rather than depth.The set G_r contains unitaries generated by G-local circuits of size at most r.
  • 6.2 Quantum complexity: The section frames quantum complexity operationally as distinguishing a pure state or unitary channel from a maximally mixed or depolarizing counterpart.This motivates two-outcome measurements as the relevant conceptual test.

7 Technical background and contributions

The section supplies mathematical tools for quantum-information calculations, including matrix norms, convex optimization, wiring diagrams, vectorization, Haar moments, and unitary designs. These tools support the paper’s analysis of random-unitary ensembles and complexity.

  • 7.1 Convexity and optimization: Convexity lets the diamond-distance optimization over quantum states be reduced to pure states, since pure states are extreme points of the state set.The relevant norm expression is convex, so a maximum occurs at an extreme point.
  • 7.1 Convexity and optimization: Lemma 4 establishes that h(X) = Tr(XAXA) is nonnegative and convex when A is positive semidefinite.The proof expands h on convex combinations and uses h(X − Y) ≥ 0.
  • 7.3 Wiring calculus: Wiring calculus represents tensors as boxes with indexed lines, allowing contractions and Born-rule expressions to be manipulated graphically.The formalism tracks contracted indices and supports identities involving traces and vectorization.
  • 7.3 Wiring calculus: Vectorization maps matrices to tensor-product vectors, and the construction is an isometry.The map is defined on computational-basis elements and extended linearly.
  • 7.4 Unitary designs: A unitary k-design matches the first k Haar moments through equality of its k-fold twirl with the Haar twirl.The framework interpolates between structured gate ensembles and Haar-random unitaries requiring exponentially large approximating circuits.
  • 7.4 Unitary designs: Schur-Weyl duality identifies operators commuting with all k-fold unitaries as linear combinations of permutation operators, enabling exact Haar-moment calculations.Permutation operators act by rearranging the k tensor copies.

7.5 Haar-integration over the unitary group

Weingarten calculus expresses Haar averages of arbitrary unitary moments through permutation operators and Weingarten functions. This framework supports moment calculations, design definitions, and bounds on ensemble weights and cardinality.

  • Moment calculations: Mixed moments containing unequal numbers of U and U† vanish identically, simplifying Haar averages of unitary expressions.
  • Weingarten calculus: Weingarten calculus computes arbitrary Haar moments by summing permutation-index contractions weighted by functions determined by permutation cycle types.The associated Weingarten matrix is the pseudoinverse of the permutation-operator Gram matrix, while a representation-theoretic form enables high-moment calculations.
  • Haar twirls: The k-fold Haar twirl is invariant under k-fold unitary conjugation and can be represented using permutation operators.This invariance underlies the twirling formalism used throughout the moment calculations.
  • Approximate k-designs: Approximate k-designs reproduce Haar twirling up to an additive error whose scaling is chosen to mimic relative error.The definition uses the Haar twirl as its reference and extends to infinite ensembles.
  • Approximate k-designs: Approximate k-designs impose strong restrictions on ensemble weights and size, including max_j p_j ≤ (1 + ϵ) k! / d^(2k) and N ≥ d^(2k).The results also establish cardinality bounds for weighted state orbits and distinguish between distinct states and distinct unitaries.

7.7 A general moment bound for Haar random unitaries

This section establishes moment bounds for Haar-random unitaries and transfers them to approximate unitary k-designs. The resulting estimates apply to centered moments over a specified range of orders.

  • Moment bounds: Centered moments of Haar-random unitary observables admit bounds for orders k = 1, . . . , d^(2/3).The bound is expressed using the depolarizing channel and dimension-dependent moment estimates.
  • Approximate designs: The same centered-moment control extends from Haar-random unitaries to ϵ-approximate unitary k-designs.The approximation error remains controlled through the approximate-design property.
  • Design orbits: The results also yield moment bounds for observables evaluated on orbits of approximate k-designs.The orbit formulation covers pure states and measurements with the stated operator constraints.

7.9 Proof of the general moment bound

The proof derives the general moment bound by centering the observable, expanding Haar moments with Weingarten calculus, and controlling the resulting tensor networks. Dimension suppression offsets potentially dangerous contractions.

  • Reformulation and centering: The proof rewrites the centered random variable using a traceless transformed observable and the vectorization of the input state.The transformed operator is constructed by conjugating with the state’s matrix representation and subtracting its trace component.
  • Expectation value and centering: Averaging a unitary channel produces the depolarizing channel, providing the reference expectation used to center the random variable.The corresponding reformulation expresses the deviation between the random channel value and its depolarized expectation.
  • Tensor-network expansion: Weingarten expansion converts each higher-moment contribution into tensor networks whose constituents are bounded by 2-norm estimates.Self-contractions vanish because the centered observable is traceless, while the remaining network factors are bounded separately.
  • Bounding dangerous terms: Potentially dangerous partial-trace terms are suppressed by Weingarten dimension factors and occur only when permutation cycle structures differ.The number of such terms is bounded by the permutation distance, which controls the final summation.
  • Conclusion: The resulting estimates establish the advertised general moment bound for Haar-random unitaries.

7.10 ε-coverings of local random circuits

Because local random-circuit ensembles are continuous, the analysis replaces them with finite ε-coverings. Combining covering-size bounds with approximate-design cardinality bounds yields a circuit-size lower bound for forming k-designs.

  • ε-coverings: An ε-covering discretizes local random circuits by approximating each circuit unitary in diamond norm.The covering is constructed by approximating each of the nT local gates to accuracy ε/T.
  • Design transfer: The covering inherits an approximate-design property with error ϵ′ = ϵ + 2d^(2k)ε when the original ensemble is an ϵ-approximate unitary k-design.
  • Circuit-size lower bound: Local random circuits require essentially linear scaling in both n and k to implement a unitary design optimally.This conclusion follows from combining the lower bound on approximate-design cardinality with the upper bound on covering cardinality.

A Concentration of measure for Haar-uniform vectors

The proposition is proved by embedding complex unit vectors into a real sphere and applying concentration of measure to a Lipschitz quadratic form. The proof uses Levy’s Lemma after bounding the function’s Lipschitz constant.

  • Statement: The proposition assumes ∥M∥∞≤1 and a uniformly chosen vector |ψ⟩ from the complex unit sphere.These assumptions are the starting conditions for the concentration result.
  • Concentration tool: Levy’s Lemma supplies concentration for Lipschitz functions on the real unit sphere.The appendix identifies Levy’s Lemma as concentration of measure on S^(2d−1).
  • Proof strategy: The proof embeds the complex unit sphere in C^d isometrically into the real sphere S^(2d−1) in R^(2d), preserving uniform distributions.Under this embedding, the quadratic form ⟨ψ|M|ψ⟩ becomes a real-valued function.
  • Lipschitz bound: For Hermitian M, the embedded quadratic form has expectation preserved and Lipschitz constant 2∥M∥∞≤2.The Lipschitz bound is established using the operator norm and the trace norm of a difference of pure states.

B Designs and the traditional definition of complexity

This section connects k-design structure to traditional circuit-based complexity for states and unitaries. The resulting theorems state that exponentially many design elements have high weak complexity.

  • Weak state complexity: Weak state complexity is defined by the minimum size of a circuit that prepares a state within δ accuracy.The definition uses circuits V∈G_r built from a universal 2-local gate set.
  • Design connection: Complex projective and unitary k-designs are sufficiently restrictive to yield quantitative lower bounds on constituent-state and constituent-unitary complexity.The section frames design structure as a way to turn expected complexity statements into quantitative ones.
  • State designs: Theorem 10 states that an ϵ-approximate complex projective k-design contains exponentially many states with high weak complexity.The supplied theorem statement and follow-up passage identify the exponential-in-k counting conclusion.
  • Weak unitary complexity: Weak unitary complexity is the minimum circuit size needed to approximate a unitary transformation.This is the traditional circuit-based definition used for the unitary-design result.
  • Unitary designs: Theorem 11 similarly states that an ϵ-approximate unitary k-design contains exponentially many unitaries with high complexity.The result is presented as the unitary analogue of the state-design theorem.
  • Proof scope: The appendix develops the counting arguments for these weak-complexity results, distinct from the stronger operational complexity definitions used in the main paper.The distinction separates circuit-approximation complexity from the operational definition based on distinguishing measurements.

B.1 Weak state complexity for spherical designs

The state-design proof bounds the probability that a design-drawn state has low weak complexity by combining circuit counting with concentration and moment bounds. Negating this probability yields many high-complexity states.

  • State-distance bound: The approximation condition is controlled using the rank-two difference between the target state and the circuit-prepared pure state.The trace norm is obtained from the two nonzero eigenvalues of this difference.
  • Low-complexity event: The proof characterizes low weak state complexity through the existence of a circuit V∈G_r whose output approximates the sampled state.A union bound then ranges over the possible circuits of size r.
  • Probability bound: Markov’s inequality bounds the probability that a spherical-design sample satisfies the approximation condition for a fixed circuit.The argument then uses design moment bounds to control the averaged event.
  • Counting conclusion: A union bound over G_r, together with bounds on the circuit count and design weights, bounds the fraction of states with complexity at most r.The proof converts this probability estimate into a lower bound on the number of high-complexity design states.
  • Conclusion: The resulting counting argument completes the proof that sufficiently many states in an approximate spherical k-design have weak complexity greater than r.The final step combines the preceding probability inequalities.

B.2 Weak unitary complexity for unitary designs

The unitary-design proof parallels the state-design argument while using channel approximation and unitary-design trace moments. Circuit counting then yields a lower bound on the number of high-complexity unitaries.

  • Reformulation: The proof first replaces weak unitary complexity with an equivalent formulation and uses a necessary condition for circuit approximation.This reformulation supplies the event to which the probability bounds are applied.
  • Low-complexity event: Low weak unitary complexity requires some circuit V∈G_r whose channel is close to the sampled unitary in diamond distance.A union bound reduces the event to approximation by one of the size-r circuits.
  • Probability bound: Markov’s inequality bounds the probability that a unitary-design sample satisfies the fixed-circuit approximation condition.The bound uses moments of traces evaluated over an approximate unitary k-design.
  • Counting conclusion: Circuit-count bounds and unitary-design weight bounds convert the low-complexity probability into a lower bound on high-complexity unitaries.The proof represents the relevant probability as an expectation involving the indicator of high-complexity design elements.
  • Conclusion: Combining the preceding inequalities completes the proof of the unitary-design complexity theorem.The argument is the unitary analogue of the spherical-design counting proof.
Loading 1912.04297v1…