Models of quantum complexity growth

Motivation

• For chaotic Hamiltonians, complexity is expected to grow linearly for exponentially long times, but proving lower bounds for specific states is difficult because efficient shortcuts cannot be ruled out.The paper therefore studies ensembles of circuits and derives high-probability complexity statements rather than analyzing one specified Hamiltonian.Source: §1 · p. 4

Limitations of prior work

• Prior results established only complexity Ω(T 1/11) for typical local random circuits and left ancilla-assisted measurements, collisions, and linear scaling unresolved.The earlier argument used a restricted distinguishability notion and did not exclude highly nonuniform distributions of sampled unitaries.Source: §1 · p. 6

Strong complexity

• The paper defines strong complexity through the smallest ancilla-assisted measurement circuit that distinguishes a unitary channel from the completely depolarizing channel.This strong notion implies weaker notions such as the minimal circuit size needed to approximate the unitary.Source: §1 · pp. 6–7

Complexity–design connection

• An approximate unitary k-design typically contains a sampled unitary with strong circuit complexity ≈k, establishing a linear connection between design order and complexity.The result extends prior evidence by allowing ancilla-assisted measurement procedures.Source: §1 · p. 7

Distribution and multiplicity

• The k-design weight distribution cannot be too spiky, so every approximate k-design contains exponentially many unitaries with circuit complexity Ω(k).The stronger result gives exponentially many high-complexity unitaries whose pairwise diamond-norm distance is almost maximal, ruling out concentration in a few tight clusters.Source: §1 · pp. 7–8

Local random circuits

• For sufficiently large local dimension, local circuits of size T contain at least exp(Ω(T)) elements with strong complexity Ω(T), proving linear growth.This follows from linear design growth for circuits with T = O(n2k) and establishes an analogue of the Brown–Susskind conjecture [7].Source: §1 · pp. 5, 8

2.1.1 State complexity

• Strong state complexity measures how many elementary gates are needed for resource-bounded measurements to distinguish a pure state from the maximally mixed state.The distinguishing measurements use at most r 2-local gates, and the definition is operationalized by Figure 2.Source: §2.1.1 · pp. 9–10, Figure 2 · p. 10

2.1.2 Unitary complexity

• Strong unitary complexity similarly limits pre-processing, quantum memory, and post-processing circuits when distinguishing a unitary channel from the depolarizing channel.The optimal unrestricted strategy uses a Bell state and Bell measurement, while the strong definition restricts the total circuit resources; it is more stringent than norm-based approximation definitions.Source: §2.1.2 · pp. 11–12

2.2 Approximate unitary designs

• Approximate unitary k-designs reproduce Haar moments up to order k within diamond distance and include explicit constructions such as local random circuits.They interpolate between structured unitary families and Haar-random unitaries, while 2-designs capture scrambling.Source: §2.2 · p. 13

2.3.1 State complexity growth

• Theorem 2 guarantees at least qualitatively (d/k)^k distinct states of strong complexity at least r + 1 from an ϵ-approximate 2k-design, subject to its stated condition on r.The result applies to states obtained by acting on a fixed starting state and explicitly counts distinct outputs despite possible collisions.Source: §2.3.1 · pp. 13–14

2.3.2 Unitary complexity growth

• Theorem 3 guarantees at least qualitatively (d^2/k)^k distinct unitaries of strong complexity at least r + 1 in a discrete approximate 2k-design, under its stated condition on r.This gives a quantitative count of high-complexity design elements rather than only an average-case probability statement.Source: §2.3.2 · p. 14

2.4 Moment bounds

• The main technical contribution is a general moment bound for channel distinguishability, obtained using Schur-Weyl duality, Weingarten calculus, tensor networks, and convex optimization.The bound addresses sophisticated measurements needed for strong unitary complexity; its dimensional scaling is believed tight, while k-dependent constants may improve.Source: §2.4 · pp. 14–15

2.5 Relation to previous work

• Compared with prior work, the results strengthen approximate-design complexity arguments by using strong unitary complexity and proving exponentially many distinct high-complexity elements, not merely probabilistic typicality.Approximate-design weight bounds prevent extremely spiky distributions, converting average-case statements into quantitative counts; late-time Hamiltonian arguments do not address early-time growth.Source: §2.5 · pp. 15–16

3.1 Local random circuits

• For finite universal gate sets, local random circuits form approximate k-designs as depth increases, and design constraints limit collisions while yielding polynomial complexity growth.The resulting bound gives at least ˜C2log(n)r unitaries with Cδ(U) > r, with circuit size polynomially related to r.Source: §3.1 · pp. 17–18

3.2 Relating two conjectures

• Linear complexity growth in local circuits would follow from linear design growth, linking Conjecture 1 to the design-growth conjecture that G-local circuits of size O(nk) form approximate k-designs.This relation is developed under the assumption that the lower bound on design depth is approximately sufficient.Source: §3.2 · pp. 18–19

3.3 Linear growth in design for local random circuits at large local dimension

• Most local Haar-random circuits at large q have strong complexity Ω(T), growing linearly with circuit size for a long time.Theorem 6 establishes T = O(n^2k) design growth for sufficiently large local dimension, enabling this conclusion through Corollary 3.Source: §3.3 · p. 19

3.4 Brownian circuits/Stochastic quantum Hamiltonians

• Brownian circuits form approximate k-designs in polynomial time and therefore have complexity growing as Ω(t^1/11).The design-time prefactor decreases as interaction strength J increases, since C ∼ 1/J.Source: §3.4 · pp. 20–21

3.5 Nearly time-independent Hamiltonian dynamics

• Nearly time-independent Hamiltonian dynamics achieves almost linear design growth only up to timescales ∼√n, implying linear complexity growth at very early times.The construction reaches moments k = o(n^1/2), but does not provide exponentially long linear growth.Source: §3.5 · p. 21

3.6 Comment on time-independence

• Polynomial design growth makes random-circuit and Brownian models explicit examples of long-time polynomial complexity growth, but randomness in time appears essential for late-time design formation.Time-independent Hamiltonian ensembles retain rigid eigenvalue structure, preventing late-time Haar-randomness and requiring methods beyond design properties.Source: §3.6 · pp. 21–22

4 Complexity in holographic systems

• The authors prove linear complexity growth for local random circuits at large local dimension, but note that unitary-design methods do not directly inform holographic evolution by time-independent Hamiltonians.Holographic complexity is associated with the long-time linear growth of black-hole interiors, with proposals including complexity equals volume and complexity equals action [5] [6] [52].Source: §4 · p. 22

Strong complexity in the bulk

• Strong measurement-based complexity exhibits the holographically expected switchback effect: growth begins only after a chaotic local operator spreads across the system at the scrambling time.Before scrambling, a simple measurement outside the operator lightcone distinguishes the evolving state; afterward, the distinguishing measurement’s complexity begins growing.Source: Strong complexity in the bulk · p. 23
• Adding one clean qubit leaves standard circuit complexity unchanged but resets distinguishing-measurement complexity to order one, directly encoding potential useful computation.This strong definition therefore captures the uncomplexity resource proposed in Ref. [7].Source: Strong complexity in the bulk · p. 23

Entanglement growth by design

• For fast-scrambling systems forming unitary designs linearly in time, all entropies saturate at time order n, whereas the paper’s arguments ensure complexity growth well beyond that threshold.States drawn from designs with k > log d have nearly maximal half-system min-entropy, making all entropies nearly maximal by k ≈ n.Source: Entanglement growth by design · pp. 23–24

5.1.1 Most states have high complexity

• A Haar-random pure state has exponentially large strong δ-state complexity, with low-complexity states remaining exponentially rare until r ≃ q^n/log(n).The Haar measure converts the probability bound into the fraction of low-complexity states.Source: §5.1.1 · p. 25

5.1.2 Most high-complexity states are far apart

• There are N = 1/6 exp(∆^2d/(9π^3)) high-complexity states whose pairwise trace distance is at least 1 −∆.An inductive probabilistic construction combines high-complexity probability with concentration away from each fixed state.Source: §5.1.2 · p. 26

5.2 Proof of Theorem 2

• Approximate 2k-designs yield quantitative high state-complexity bounds because their moment concentration and approximately flat state weights support union and counting arguments.The deviation bound scales qualitatively as d^-k and becomes tighter as the design order 2k increases.Source: §5.2 · pp. 26–27

5.3 Proof of Theorem 3

• Theorem 3 extends the argument to unitary complexity using tight Haar-moment bounds, circuit-measurement counting, and approximate design weight flatness.The resulting probabilistic statement is converted into a quantitative count of distinct high-complexity unitaries.Source: §5.3 · p. 28

5.4 Distant and distinct design elements

• Unitary and state designs contain an exponential number, Ω(d^k), of distinct high-complexity elements, while the proof further establishes pairwise separation.The latter property is needed to capture the ergodic character of chaotic evolution over the unitary group.Source: §5.4 · p. 28

Distant and distinct state design elements

• For approximate spherical k-designs, low state complexity has probability O(d^-k) when r ≲ kn, enabling exponentially many pairwise-separated high-complexity states.A union bound and probabilistic iteration construct the separated set while the relevant failure probability remains below one.Source: Distant and distinct state design… · pp. 29–30

Distant and distinct unitary design elements

• For approximate unitary k-designs, low unitary complexity has probability O(d^-2k) when r ≲ nk, enabling exponentially many pairwise-separated high-complexity unitaries.The construction uses a union bound over nearby reference unitaries and iteratively adds distant design elements.Source: Distant and distinct unitary design… · p. 30

6.1 Distinguishing states and channels

• The section begins with the general single-shot question of distinguishing two known biased coins, motivating the classical and quantum discrimination settings.Quantum states use POVMs and Born’s rule as matrix generalizations of classical probability vectors and events.Source: §6.1 · p. 31, §6.1.2 · p. 32

6.1.1 Distinguishing classical probability distributions

• Classical single-shot discrimination is a tractable linear program whose maximum-likelihood rule chooses the distribution more likely to produce the observed outcome.The resulting bias is the total variational distance between the two probability distributions.Source: §6.1.1 · pp. 31–32

6.1.2 Distinguishing quantum states

• The Holevo-Helstrom theorem identifies the optimal quantum measurement for distinguishing two states and equates its bias with their trace distance [28, 29].The optimal two-outcome measurement projects onto the positive range of ρ − σ.Source: §6.1.2 · pp. 32–33

6.1.3 Distinguishing quantum channels

• Quantum channel distinguishability permits entangled inputs and is quantified by the diamond distance, which has a computationally tractable semidefinite-program formulation [64, 65–67].Optimizing measurements yields trace distance between output states, while convexity restricts input optimization to pure states; entanglement with quantum memory can improve distinguishability.Source: §6.1.3 · p. 33

6.2.1 Cornering “easy” unitary transformations

• The framework defines easy unitaries as transformations generated by at most r local gates from a universal gate set, with universality ensuring density as r grows [30].Circuit size counts total elementary gates, and Solovay-Kitaev compilation gives only constant overhead between universal gate sets.Source: §6.2.1 · pp. 34–35

6.2.2 Cornering “easy” measurements

• Easy measurements are modeled as two-outcome measurements implemented through a simple ancilla, an at-most-r-gate basis change, and a computational-basis projective measurement.Naimark’s theorem connects arbitrary two-outcome measurements to projective measurements on a system extended by a qubit ancilla.Source: §6.2.2 · p. 35

7.1 Notation and basic facts from matrix analysis

• The matrix-analysis background defines quantum states, traces, Schatten norms, partial traces, and positive semidefinite operators used throughout the technical development.Pure states are normalized vectors, and positive semidefiniteness is preserved under partial traces; for psd matrices, the trace norm equals the trace.Source: §7.1 · pp. 36–37

7.2 Convex geometry and optimization

• Convex optimization supplies the key principle that convex functions attain maxima at extreme points, which are pure states for the set of quantum states.This reduces the relevant diamond-distance optimization to pure-state inputs.Source: §7.2 · pp. 37–38
• For psd A, the function h(X) = Tr(XAXA) is nonnegative and convex, providing a technical bound for general Haar moments.Convexity follows by applying nonnegativity to h(X − Y) in the expansion of h(τX + (1 − τ)Y).Source: §7.2 · p. 38

7.3 Wiring calculus

• Wiring calculus represents tensors as boxes and contracted indices as connected lines, enabling graphical manipulations of traces, measurements, flips, and vectorization.Born’s rule becomes Tr(Mρ) = ⟨ψ|M|ψ⟩, while vectorization maps matrices linearly into tensor-product vectors and preserves inner products.Source: §7.3 · pp. 38–39

7.4 Random unitaries and k-designs

• The Haar measure is the unique left/right-invariant measure on U(d), and k-fold twirls average operators over Haar-random unitaries or specified unitary ensembles.These channels formalize the moments used to compare random-unitary ensembles with the full unitary group.Source: §7.4 · p. 40
• A unitary k-design exactly matches the Haar k-fold twirl and therefore captures the first k Haar moments; Pauli operators form an exact 1-design, while higher-k constructions are limited.The n-qubit Clifford group is noted as a notable exact-design construction for k = 3 [15] [16] [17].Source: §7.4 · p. 40
• Schur-Weyl duality states that operators on (C^d)^⊗k commuting with every U^⊗k are exactly linear combinations of permutation operators.This duality underlies the exact Haar-moment and random-unitary-average formulas used later.Source: §7.4 · p. 40

7.5 Haar-integration over the unitary group

• Weingarten calculus expresses arbitrary Haar moments through permutations, contraction operators, and Weingarten functions on S_k.The Weingarten function depends on permutation cycle type and has a character expansion over integer partitions of k.Source: §7.5 · pp. 41–42
• For k ≥ d, the representation-theoretic expression remains valid by restricting to partitions with length ℓ(λ) ≤ d.This restriction keeps the denominator polynomial c_λ(d) free of zeroes.Source: §7.5 · p. 41
• The k-fold Haar twirl is characterized by permutation operators, with Weingarten functions forming the pseudoinverse of their Gram matrix.The Gram entries are Tr(P_σP_τ) = d^ℓ(σ^-1τ), and direct matrix inversion becomes intractable as k! grows.Source: §7.5 · p. 42
• Haar integration yields explicit averages for traces, pure-state moments, and conjugated-observable expectation values.The pure-state k-fold average is expressed through the projector onto the symmetric subspace.Source: §7.5 · pp. 43–44

7.6 Approximate k-designs and bounds on weight distributions

• Approximate k-designs interpolate between Haar-random ensembles and structured ensembles while relaxing exact moment matching.The definition compares an ensemble’s k-fold twirling channel with the Haar twirl using an additive error ϵ scaled with d.Source: §7.6 · pp. 44–45
• Approximate k-designs impose max 1≤j≤N p_j ≤ (1 + ϵ) k! d^2k and N ≥ d^2k.Thus the design condition strongly constrains both the largest ensemble weight and the ensemble size.Source: §7.6 · pp. 45–46
• For fixed input states, approximate unitary k-designs induce weighted approximate complex-projective k-designs on their orbit states.The analysis emphasizes distinct orbit states because different unitaries can produce the same state, and derives corresponding weight and cardinality bounds.Source: §7.6 · pp. 45–46

7.7 A general moment bound for Haar random unitaries

• Haar-random unitaries satisfy centered-moment bounds for every order k = 1, . . . , d2/3.The setting takes U ∈U(d) uniformly from Haar measure, with d I denoting the depolarizing channel.Source: §7.7 · p. 47
• The Haar moment bound is expressed using the k-th Catalan number.Source: §7.7 · p. 47

7.8 Moment bounds for approximate designs

• For an ϵ-approximate unitary k-design, the same assumptions yield a corresponding moment bound through Corollary 5.The corollary compares the approximate-design quantity with its Haar expectation while controlling the mismatch using the approximate k-design property.Source: §7.8 · p. 47
• The approximate-design proof decomposes the centered moment into a Haar contribution and a controlled remainder.The first contribution is bounded by the Haar theorem, while the design property keeps the mismatch Δ controlled.Source: §7.8 · p. 47
• The proof uses that the relevant operator is a traceless difference of two positive semidefinite matrices.This structural fact is applied again to complete the bound, together with Eq. (7.5).Source: §7.8 · pp. 47–48
• Corollary 6 extends the moment analysis to k-design orbits generated from a state |x⟩∈Cd and a measurement M satisfying I ⪰M ⪰0.The measurement is replaced by its traceless part without increasing the operator norm, enabling the remaining Haar expectation to be bounded by trace inequalities.Source: §7.8 · p. 48

7.9 Proof of the general moment bound

• Theorem 8’s random variable is reformulated via |φ⟩ = vec(Φ), with M_Φ = (I ⊗ Φ†)M(I ⊗ Φ) and ||Φ||_2 = 1.This reduces the analysis to bounding M_Φ and its partial contractions under ||M||_∞ ≤ 1.Source: §7.9 · p. 48
• Convexity over quantum states and matrix Hölder inequalities provide the required 2-norm bounds for M_Φ and its partial contractions.The argument uses ρ = Φ†Φ as a quantum state and maximizes convex functions at pure-state extreme points.Source: §7.9 · pp. 49–50
• Haar averaging a unitary channel and its adjoint decouples the acted-on register and produces the depolarizing channel.The resulting expectation equals the corresponding expression with D(ρ) = Tr(ρ)I/d.Source: §7.9 · p. 50
• Centering replaces M_Φ by its traceless component M̄_Φ = M_Φ − Tr(M_Φ)I/d, yielding a reformulation of the centered random variable.The tracelessness condition Tr(M̄_Φ) = 0 is central to eliminating self-contractions later.Source: §7.9 · p. 50

Bounds on centered moments

• For k ≤ d^2/3, higher centered moments are expanded by Weingarten calculus into tensor-network contractions built from M̄_Φ, Tr_2(M̄_Φ), and Tr_1(M̄_Φ).Self-contractions vanish because M̄_Φ is traceless, while tensor-network values are bounded by products of constituent 2-norms.Source: Bounds on centered moments · pp. 51–52
• The potentially dangerous Tr_1(M̄_Φ) factors occur only at subleading order, because differing permutation cycle structures incur dimension suppression through the Weingarten function.Leading terms have σ = τ, whereas dangerous contractions require a cycle-type difference.Source: Bounds on centered moments · pp. 52–53
• The proof controls dangerous factors by ν_3(σ,τ) ≤ 2d(σ,τ), combines this with Weingarten bounds involving the k-th Catalan number, and establishes the general moment bound.The permutation distance is measured by the minimum number of transpositions, each changing cycle count by one.Source: Bounds on centered moments · p. 53

Motivation

• ε-coverings make complexity-growth statements meaningful for continuous ensembles of local random circuits.The circuits act on n qudits of local dimension q, with gates chosen Haar-randomly from U(q^2).Source: §7.10 · p. 54

Construction

• An ε-covering requires every unitary in one set to be diamond-norm approximated within ε by a unitary in the covering set.The covering is constructed by approximating each of the nT circuit gates to accuracy ε/T, following Lemma 27 from [12].Source: §7.10 · p. 54

Design connection

• If the original ensemble is an ϵ-approximate unitary k-design, its ε-covering is an ϵ′-approximate design with ϵ′ = ϵ + 2d^2kε.This uses Proposition 8 from [12], together with cardinality bounds for approximate designs and local-random-circuit coverings.Source: §7.10 · p. 54

Result

• The covering argument gives a lower bound on the size required for local random circuits to form k-designs.The bound follows by combining the approximate-design cardinality lower bound with the covering-size upper bound.Source: §7.10 · p. 54
• An optimal random-circuit implementation of a unitary design must scale essentially linearly in both n and k.This conclusion summarizes the resulting lower bound for local random circuits.Source: §7.10 · p. 54

• Proposition 1 considers ⟨ψ|M|ψ⟩ for Haar-uniform |ψ⟩ ∈ C^d and Hermitian M with ∥M∥∞ ≤ 1.Source: A Concentration of measure for… · p. 55
• Levy’s lemma supplies the concentration conclusion, with the Lipschitz estimate supported by block-matrix norm preservation and a trace-norm calculation for pure-state differences.Source: A Concentration of measure for… · pp. 55–56
• The complex unit sphere embeds isometrically into S2d−1 ⊂ R2d, preserving uniform measure and converting the quadratic expectation into a real-sphere function.Source: A Concentration of measure for… · p. 55
• The converted function is 2∥M∥∞-Lipschitz, hence has Lipschitz constant at most 2 under the proposition’s norm bound.Source: A Concentration of measure for… · p. 55

Definitions

• Weak state complexity is the minimum size of a circuit that prepares a state from an initial state within the specified approximation tolerance.For n qudits, circuits are built from a universal 2-local gate set, with total dimension d = q^n.Source: B Designs and the traditional… · p. 56

State designs

• Approximate complex projective k-designs contain an exponentially large-in-k number of states with high weak complexity.The result follows from quantitative counting arguments for constituent states of the design.Source: B Designs and the traditional… · pp. 56–57

Definitions

• Weak unitary complexity is the minimum size of a gate-set circuit that approximates the target unitary within the specified tolerance.This traditional definition is weaker than the operational complexity based on the distinguishing measurement.Source: B Designs and the traditional… · pp. 56–57

Unitary designs

• Approximate unitary k-designs likewise contain an exponentially large-in-k number of unitaries with high weak complexity.The unitary result converts expected complexity statements for design elements into a quantitative count.Source: B Designs and the traditional… · p. 57

Characterization

• Weak δ-state complexity is rewritten using the trace distance between |ψ⟩⟨ψ| and V|0⟩⟨0|V†.The difference operator has rank at most two, allowing its trace norm to be evaluated through its two eigenvalues and the overlap |⟨ψ|V|0⟩|².Source: §B.1 · pp. 57–58

Probability bound

• The event of complexity at most r occurs when some V ∈ G_r satisfies the defining overlap condition, so a union bound reduces the problem to fixed-V events.This identifies the low-complexity event as a union over the candidate transformations in G_r.Source: §B.1 · p. 58
• For a state sampled from an approximate spherical k-design, Markov’s inequality and design moment estimates bound each fixed-V event.The argument uses the corresponding averaged overlap bound for a fixed state and a state drawn from the design.Source: §B.1 · p. 58

Primary claim

• Combining the expectation bound with the cardinality estimate for G_r yields an upper bound on the probability that a spherical-design state has complexity at most r.The proof then negates this low-complexity assertion and rewrites the complementary probability as an expectation of an indicator, using the design-weight bound to complete the primary claim.Source: §B.1 · pp. 58–59

• The proof reformulates weak δ-unitary complexity and identifies a necessary condition for complexity at most r.The condition is expressed through the existence of a unitary V in G_r whose channel is close in diamond distance.Source: §B.2 · p. 59
• A union bound reduces the low-complexity probability to fixed-unitary estimates, which are bounded using Markov’s inequality and unitary-design trace moments.The moment calculation applies to a fixed V and U averaged over an ε-approximate unitary k-design.Source: §B.2 · p. 59
• Negating the resulting estimate yields a lower bound on the probability that a k-design unitary has complexity greater than r, completed using design-weight bounds and the number M of such unitaries.M denotes the number of unitaries in the k-design with weak δ-complexity greater than r.Source: §B.2 · pp. 59–60