Random quantum circuits anti-concentrate in log depth

Motivation

• Anti-concentration measures whether computational-basis output probabilities are sufficiently spread out, using collision probability as the quantitative criterion.The collision probability is the probability that two independently sampled measurement outcomes agree.Source: §I · p. 1
• Anti-concentration matters because it is used in formal hardness arguments for random-circuit simulation and required by some classical simulation algorithms.The cited examples include noisy-circuit simulation and algorithms that spoof linear cross-entropy benchmarking.Source: §I · p. 1

Prior work

• Earlier work often inferred anti-concentration from the stronger 2-design property, although one-dimensional circuits were shown to anti-concentrate in O(log(n)) depth.The paper contrasts this with 2-design depths that can scale as O(n) for fully connected circuits and geometrically local circuits in 1D.Source: §I · p. 1

Contributions

• For one-dimensional circuits, the paper adds a matching lower bound to the known O(log(n)) upper bound and proves an Ω(log(n)) depth lower bound for every architecture.This refutes the conjecture that two-dimensional circuits anti-concentrate in O(√log(n)) depth.Source: §I · pp. 1–2
• For fully connected qubit circuits, 5n log(n)/6 gates are necessary and sufficient up to subleading corrections, settling a conjecture from Ref. [16].The fully connected architecture chooses each gate’s qudit pair uniformly among all possible pairs.Source: §I · p. 2

Method

• The analysis maps collision probability to an Ising-like partition function and interprets the resulting bit assignments through a Markov chain.This yields sharp bounds and qualitative intuition about convergence in architectures not explicitly analyzed.Source: §I · p. 2

Definition

• For an n-qudit circuit, the collision probability is the expected probability that two independent measurement outcomes agree, with uniform output giving the minimum q^-n.It is also proportional to the output-probability second moment and is averaged over random circuit instances.Source: §II · p. 2
• An architecture is anti-concentrated when its averaged collision probability satisfies Z ≤ α^-1q^-n for a constant α independent of n.The paper uses α = 1/4 for theorem statements, while other fixed α values change only lower-order terms.Source: §II · p. 2

Intuition

• Globally Haar-random circuits have collision probability approximately 2q^-n, whereas low-depth circuits can have much larger collision probability because mass remains concentrated on few outcomes.The intermediate anti-concentrated regime has Z ≈ cq^-n for n-independent c.Source: §II · pp. 2–3

Significance

• This collision-probability criterion is relevant because anti-concentration supports both hardness arguments and the efficiency of certain classical simulation algorithms.The definition can also yield constant-probability lower bounds on output probabilities through the Paley-Zygmund inequality.Source: §II · p. 3

Scope

• The exponential output-probability law associated with Eq. (3) is weaker than the paper’s definition because it can hold even when Z exceeds every constant multiple of q^-n.The cited hardness arguments also require additional unproven conjectures, so Eq. (3) alone does not establish simulation hardness.Source: §II · p. 3

Method

• Collision probability is represented as a discrete sum that can be interpreted as an expectation value of a stochastic process.The correspondence is developed in the main analysis and derived fully in Appendix B.Source: §III · p. 3

Bounds

• The paper derives general and architecture-specific upper and lower bounds on collision probability.These bounds are then converted into bounds on the anti-concentration size s_AC.Source: §III · p. 3

Threshold

• The anti-concentration size s_AC is the minimum circuit size satisfying Z ≤ 2Z_H, where Z_H is the Haar collision probability.Because Z approaches Z_H as Z_H(1 + e^-Ω(s/n)), changing the constant 2 changes s_AC only by linear-in-n subleading terms.Source: §III · p. 3

Main result

• s_AC = Θ(n log(n)) for both one-dimensional and complete-graph architectures, with matching constant prefactors for the n log(n) term.The table summarizes the corresponding upper and lower bounds across architectures.Source: Table I · p. 4

1D architecture

• For one-dimensional ring circuits, the anti-concentration depth satisfies d_AC ≤ d* = O(log(n)).The depth is related to circuit size by d = 2s/n.Source: §1 · p. 4

Complete-graph architecture

• For complete-graph circuits, a randomly chosen size-s circuit typically has depth at most O(s log(n)/n), making O(log(n)^2) depth sufficient for anti-concentration.Each gate acts on a random pair of qudits without regard to spatial proximity.Source: §1 · p. 4

General architectures

• Regularly connected architectures satisfy a general bound with a = Θ(1) and s* = Θ(n^2), corresponding to Θ(n) gates per qudit.This result applies to many natural architectures, including standard geometrically local architectures in any spatial dimension.Source: §1 · p. 4

Open direction

• The paper conjectures that the general regularly connected bound can be improved from s* = Θ(n^2) to Θ(n log(n)).The authors explicitly describe the current general result as weaker than the specific one-dimensional and complete-graph results.Source: §1 · p. 4

General lower bound

• The general lower bound shows that sublogarithmic depth cannot achieve anti-concentration for any random quantum circuit architecture.When s grows below the n log(n) threshold, the collision probability remains arbitrarily larger than the Haar value as n increases.Source: §2 · p. 4

1D architecture

• For the 1D architecture, the improved lower bound matches the upper bound up to subleading corrections.The bound uses the same architecture-dependent constant a as the corresponding upper bound.Source: §2 · p. 5

Complete-graph architecture

• For the complete-graph architecture, the lower bound is likewise tight with the upper bound up to subleading corrections.For qubits, the resulting n log(n) prefactor is 5/6, settling a conjecture from Ref. [16].Source: §2 · p. 5

Combined result

• Together, the bounds establish sAC = Θ(n log(n)) for both architectures and determine the matching leading constant prefactor.Thus the required circuit size has the same asymptotic scaling in the two geometries despite their different connectivity.Source: §2 · p. 5

Architecture comparison

• For q ≥ 5, the 1D architecture anti-concentrates faster than the complete-graph architecture under these model definitions.The 1D coefficient decreases like 1/log(q), whereas the complete graph requires roughly n log(n)/2 gates to involve all qudits with high probability.Source: §2 · p. 5

Unitary designs

• For 1D circuits, the paper improves the prior O(log(n)) anti-concentration depth implication from approximate designs to a matching Θ(log(n)) result.For D ≥ 2, the paper conjectures the same scaling but does not prove it, so O(n1/D) remains the best known bound.Source: §IV · p. 5

Prior complete-graph bounds

• For complete-graph circuits with qubits, the paper obtains a leading anti-concentration size of 5n log(n)/6, correcting the factor-of-two discrepancy in Ref. [16]'s heuristic conjecture.The earlier conjecture was 5n log(n)/3 up to leading order.Source: §IV · p. 5

Classical simulation implications

• The general lower bound contradicts Barak, Chou, and Gao [32]'s conjecture that 2D circuits anti-concentrate at O(log(n)) depth.For sublogarithmic depth, the paper shows 2^nZ ≥ exp(n1−o(1)), preventing the conjectured behavior.Source: §IV · p. 5

Methodological relation

• The analysis uses Haar integration to produce an Ising-like partition function and then applies a Markov-chain analysis with transition rules distinct from Pauli-string random walks.This connects the method to prior statistical-mechanical treatments while retaining a different dynamical structure.Source: §IV · pp. 5–6

Approximate-design requirements

• Approximate 2-design arguments can certify anti-concentration only when their approximation error is exponentially small in the number of qudits.This applies to diamond-norm bounds and tensor-product-expander conditions, which otherwise control collision probability only up to additive error.Source: A. Connection to 2-design · p. 6

1D depth comparison

• For 1D random circuits, achieving the exponentially small error needed for anti-concentration through approximate designs requires linear depth.Although TPEs arise at constant depth for weaker error scales, anti-concentration still requires ε = 1/q2n.Source: A. Connection to 2-design · p. 6

Conceptual distinction

• Anti-concentration targets certain second-moment matrix elements, while the approximate 2-design condition requires small moments for all states, including states entangled across tensor copies.Some such states necessarily require linear depth to equilibrate on the 1D architecture.Source: A. Connection to 2-design · p. 6

Role in hardness arguments

• Anti-concentration converts small additive simulation errors into small relative errors for most outcomes, preserving the hardness relevance of encoded probabilities.Without anti-concentration, probabilities are much smaller than the mean for most outcomes, making relative error extremely large and undermining existing hardness arguments.Source: B. Implications for arguments on… · p. 7

Limits of the argument

• Anti-concentration is only one step toward hardness: proving approximate-sampling hardness and extending hardness from arbitrary circuits to random circuits still requires an additional conjecture.Current techniques handle these steps separately but do not combine them simultaneously.Source: B. Implications for arguments on… · pp. 6–7

Implications for circuit depth

• The paper’s sharp gate-count bounds constrain when hardness-of-simulation arguments have the potential to work and suggest shallower candidate supremacy circuits.The authors report Θ(log(n)) anti-concentration depth for 1D circuits and argue that comparable 2D depth may be defensible instead of Ω(√n), while noting that larger depth can make tensor-network simulation harder.Source: B. Implications for arguments on… · p. 7

Limits of the argument

• The breakdown of hardness arguments without anti-concentration does not generally imply easy simulation, because 2D circuits may enter a hard-to-simulate regime before anti-concentration.An algorithm for certain constant-depth 2D circuits is efficient below a threshold and conjectured inefficient above a larger threshold, leaving an intermediate regime that is not anti-concentrated but may remain hard to simulate.Source: B. Implications for arguments on… · p. 7

Trajectory representation

• The collision probability becomes a discrete weighted sum over length-(s + 1) trajectories of I/S configurations, obtained by averaging each local Haar gate.Each configuration assigns I or S to every qudit, and each trajectory receives a nonnegative weight.Source: §V · pp. 7–8
• A trajectory has positive weight only when disagreeing gate inputs trigger a bit flip, with each flip reducing the weight by q/(q^2 + 1), or 2/5 for qubits.The dominant contributions therefore come from trajectories with few bit flips.Source: §V · p. 8

Statistical-mechanical interpretation

• The same weighted sum can be interpreted as an Ising-like partition function or as the expectation of a Markov chain evolving the configurations.These interpretations support the subsequent stochastic and combinatorial bounds.Source: §V · p. 8

Fixed points and collision probability

• In the infinite-size limit, positive-weight trajectories reach one of two fixed points, I^n or S^n, and their total contribution reproduces the global-Haar collision probability Z_H.At finite size, unreached trajectories remain overweighted, so Z > Z_H and decreases toward Z_H as the circuit grows.Source: §V · p. 8

Convergence and scaling

• Typical trajectories begin Θ(n) bit flips from a fixed point and move a constant fraction closer per Θ(n)-gate layer, yielding Θ(n log(n)) gates for anti-concentration.For complete-graph circuits, random pairing creates Θ(x) disagreeing pairs when x S assignments remain, while analogous behavior is proved for 1D circuits.Source: §V · pp. 8–9
• The complete-graph trajectories approach fixed points exponentially with characteristic time Θ(n), and anti-concentration occurs when Z falls below 2Z_H, illustrated at s = 214 for n = 60.The 1D proof instead uses domain-wall configurations, while the complete-graph proof uses reduced trajectories and Chernoff bounds.Source: §V · pp. 9–10, Figure 3 · p. 10

Implications

• For shallow circuits, a small set of measurement outcomes can remain exponentially heavier than average, while deeper circuits gradually spread probability mass across outcomes.The framework relates this process to stochastic equilibration and supplies quantitative upper and lower bounds.Source: §VI · p. 10
• The proven Θ(n log(n)) size for both 1D and complete-graph architectures suggests that anti-concentration is relatively insensitive to connectivity and typically corresponds to O(log(n)) depth.The authors characterize this broader statement as evidence or a conjecture for natural architectures, not as a general theorem.Source: §VI · pp. 10–11

Practical significance

• The bounds provide explicit gate counts when anti-concentration is desirable, which is useful when gates are noisy or costly to implement.Source: §VI · p. 10

Implications

• Anti-concentration requires Ω(n log(n)) gates, so heavy measurement outcomes persist for every constant-depth architecture and also for the cited 2D depth regime.The paper states that 2D circuits of depth O(log(n)) considered in Ref. [32] cannot yet be anti-concentrated.Source: §VI · pp. 10–11

Open problems

• The paper leaves open whether the general lower bound can be sharpened and whether a random-pairing architecture is the fastest anti-concentrator.It also identifies sharp analyses for 2D and higher-dimensional local architectures as valuable open problems.Source: §VI · p. 11

1. Random quantum circuits (RQCs)

• A random quantum circuit consists of a fixed two-qudit gate diagram together with independently sampled unitary gates, drawn here from Haar measure or any 2-design.The circuit starts from |1^n⟩, and computational-basis measurements are performed on all n qudits.Source: §1 · pp. 11–12

2. Random quantum circuit architectures

• An architecture is the procedure that chooses the circuit diagram, with the paper studying complete-graph random pairings and alternating nearest-neighbor layers on a 1D ring.Source: §2 · p. 12

3. Collision probability and anti-concentration

• Collision probability is the probability that two independent samples from a distribution agree; it equals the mean squared outcome probability and is minimized by the uniform distribution.For a uniform distribution over M outcomes, the minimum is |M|^-1.Source: §3 · pp. 12–13
• A distribution is α-anti-concentrated when its collision probability is at most α^-1 times the uniform minimum, with α = 1 corresponding exactly to uniformity.The paper applies this definition to circuit measurement outcomes and averages over circuit instances to define anti-concentrated architectures.Source: §3 · p. 13
• For an anti-concentrated architecture, Markov’s inequality bounds the fraction of atypical circuit instances, while Paley–Zygmund implies that a constant fraction of outcomes retain mass within a constant factor of the mean.Sharper concentration of individual instances would require higher moments beyond the second.Source: §3 · p. 13
• The expected collision probability also admits equivalent circuit, Ising-like partition-function, and stochastic-process interpretations.Source: Figure 4 · p. 14

1. Averaging individual unitaries over the Haar measure

• Haar averaging converts the collision-probability calculation into a weighted discrete sum over identity/swap configurations for each circuit location.The construction applies independently to local Haar unitaries and exact two-designs, with two-qudit gates inducing a linear transformation on configurations.Source: Appendix B · p. 14, §1 · pp. 14–16

2. Collision probability as statistical mechanical partition function

• The resulting configuration trajectories have products of nonnegative transition weights, yielding a partition function for an Ising-like model with local interactions.Each configuration maps {I, S} to Ising spin values, and the energy decomposes into local terms determined by the gate locations and local dimension.Source: §1 · p. 16, §2 · p. 16
• Higher moments would require k! symmetric-group configurations and can introduce negative weights, complicating the bounding strategies used for the collision-probability analysis.The second moment is tractable because its two possible values produce an Ising-like model with nonnegative weights.Source: §2 · p. 17

3. Unbiased random walk

• The unbiased random walk starts uniformly over {I, S}^n, leaves agreeing gate bits unchanged, and flips one disagreeing bit with equal probability while penalizing flips.Accounting for trajectory probabilities makes this walk exactly equivalent to the weighted trajectory sum defining the collision probability.Source: §3 · p. 17

4. Biased random walk

• The biased walk changes the initial distribution and favors flipping S to I, while an exponential endpoint weight cancels the transition bias and preserves the same partition-function value.Its dynamics use probabilities q^2/(q^2 + 1) for S-to-I and 1/(q^2 + 1) for I-to-S when the gate bits disagree.Source: §4 · p. 17

5. Computing sums over trajectories

• Trajectory sums can be reduced to Hamming-weight processes: in the infinite-size limit, contributions depend on the initial configuration only through its Hamming weight and satisfy a recursion with boundary conditions.The biased walk’s hitting probabilities then determine termination at the all-I or all-S fixed points.Source: §5 · pp. 17–19

6. Sanity check: Infinite circuit size convergence to Haar value

• In the infinite circuit-size limit, the biased walk converges to a mixture of the all-I and all-S configurations, reproducing the Haar collision-probability value.This agrees with the expected convergence of products of Haar-random local gates toward an n-qudit Haar-random unitary.Source: §6 · p. 19

1. Upper bound on collision probability

• For r-regularly connected architectures, the collision probability can be upper-bounded because every nonfixed configuration is likely to encounter a gate crossing its S/I partition within O(n) gates.The bound relies on each such crossing forcing a bit flip that reduces the trajectory weight.Source: §1 · pp. 19–20
• Regular connectivity holds for the 1D and complete-graph architectures, but not for the hypercube, where crossing every partition can require Θ(n log(n)) gates.The appendix notes that repeated gates on one pair would prevent collision-probability decrease and must be excluded.Source: §1 · pp. 19–20
• The general upper-bound theorem does not optimize the Θ(n^2) prefactor and conjectures that stronger analysis could reduce the scaling to Θ(n log(n)) for regularly connected architectures.This is presented as an unoptimized bound and a conjectured improvement, not as an established result.Source: §1 · p. 21

2. Lower bound on collision probability

• Any RQC architecture requires Ω(n log(n)) gates for anti-concentration, implying an Ω(log(n)) lower bound on circuit depth.The lower bound follows from the persistence probability of S-valued bits in the biased walk, regardless of the architecture’s gate pattern.Source: §2 · p. 21
• The lower-bound argument tracks each qudit’s number of incident gates and uses convexity to show that distributing those gates cannot eliminate the residual collision probability too quickly.Each gate acts on two indices, so the incidence counts sum to 2s; the resulting bound yields the circuit-size and depth consequences.Source: §2 · pp. 21–22

1. Domain walls and notation

• The 1D analysis maps configurations to domain walls whose trajectories move between alternating positions, can annihilate, but cannot create new pairs.Periodic boundary conditions require an even number of domain walls, and each domain-wall set corresponds to exactly two configurations.Source: §1 · p. 22, Appendix D · p. 22

G G0 GU

• Every trajectory decomposes uniquely into a conserved-domain-wall part GU and a part G0 in which all domain walls annihilate by the circuit’s end.The decomposition supports the upper-bound analysis; under periodic boundary conditions, the conserved part has an even number of domain walls.Source: G G0 GU · p. 23

2. Collision probability upper bound

• For depth at least d*, the upper-bound analysis yields Z ≤ ZH (1 + exp(log(n) − da + log(e − 1) + a)).The bound follows by weighting domain-wall trajectories according to their motion and annihilation structure.Source: §2 · pp. 23–24

3. Collision probability lower bound

• The lower bound applies when s*−s ≥ A′n, with explicit A on the order of e−10 and A′ ≈ −log(A).The proof lower-bounds Z using trajectories with many unannihilated domain walls and imposes spacing conditions between them.Source: §3 · p. 25, Figure 6 · p. 26
• |sAC − (2a)−1n log(n)| = O(n), so the 1D anti-concentration threshold is determined to within an additive linear term.The result combines the upper and lower bounds for the smallest circuit size satisfying Z ≤ 2ZH.Source: §3 · p. 25
• Trajectories in B_H,j decompose into domain-wall pairs that coincide with the jth domain wall of H and later annihilate.For a fixed coincidence point, the combined weight of pairs annihilating at time t′ is bounded by (2q/(q2 + 1))2t′, and summing over t′ ≥ t gives a bound for pairs coinciding at time t.Source: §3 · p. 29
• At each time t, intersections with the jth domain wall are either absent or contribute at most the derived bound, yielding a product over possible domain-wall inclusions.This accounts for potentially many intersecting pairs while restricting each time step to zero or one intersection contribution.Source: §3 · p. 29
• For q ≥ 2, monotonic decrease of the exponent’s q-dependent function enables the resulting bound to be combined with Eq. (D50).The passage states that the final inequality follows from q ≥ 2 and monotonicity in q before combining the preceding estimate with Eq. (D50).Source: §3 · p. 29

1. Proof intuition and guide

• Permutation symmetry makes configurations with equal Hamming weight equivalent, reducing the dynamics from {I, S}^n to walks on {0, 1, …, n}.The complete-graph transition changes x with probability 2x(n−x)/(n(n−1)) and then moves to x−1 or x+1 equally likely.Source: §1 · pp. 29–30
• The biased walk starts near Hamming weight n/(q+1), drifts toward 0, and suggests that roughly log(n) time is necessary because residual weight contributes exponentially to Z.Its effective speed decreases near the fixed points, motivating the lower-bound intuition.Source: §1 · p. 30
• The matching upper-bound intuition requires the distribution tail to decay exponentially, because each additional Hamming-weight unit multiplies its contribution to Z by q.The walk’s slowing near 0 gives farther-out tail mass time to catch up, supporting exponential decay.Source: §1 · p. 30

3. Upper bound proof

• The upper-bound proof rewrites Z−ZH as a sum over reduced paths that remain incomplete after s steps, then applies Chernoff bounds to their completion times.For a fixed reduced path, the completion time is a sum of independent exponentially distributed waiting variables; paths are decomposed into subpaths approaching 0 or n.Source: §1 · pp. 30–31, §3 · pp. 36–37

1. Proof intuition and guide

• q2 + 1 / [2(q2 −1)] n log(n) time steps are required by the proof’s cancellation argument, while a linear-in-n term is also necessary but not tightly analyzed.The log(n) factor arises because waiting times increase near the fixed points.Source: §1 · p. 31

a. Trajectories; b. Conditional probabilities and expectations; c. Trajectory concatenation and other operations; d. Important subsets of Γ; e. Reduced trajectories

• The appendix formalizes valid trajectories, conditional path probabilities, concatenation operations, endpoint subsets, and reduced walks obtained by removing consecutive duplicate configurations.Reduced walks never stand still, while the original walk’s waiting times encode the number of time steps spent at each Hamming weight.Source: a. Trajectories · p. 32, b. Conditional probabilities and… · p. 32, c. Trajectory concatenation and other… · p. 32

3. Upper bound proof

• The upper-bound proof decomposes trajectories by their minimum distance w, uses path-reversal symmetry, and selects parameters to cancel the dominant O(n log(n)) and trajectory-weight factors.A unique trajectory decomposition organizes the sum into classes Λ_v and Ξ_w, while the choice of c and the condition s ≥ s* complete the upper bound.Source: §3 · pp. 37, 40

4. Lower bound proof

• s_AC = (q^2 + 1)/(2(q^2 − 1)) n log(n) + O(n) for complete-graph circuits with local dimension q.The appendix combines the upper and lower bounds to identify the leading asymptotic coefficient for the minimum anti-concentration circuit size.Source: §4 · p. 41

5. Delayed proofs of lemmas

• The delayed lemmas evaluate trajectory sums using a recursion for I(x), solved with boundary conditions, while square-root bounds control the auxiliary quantities under the required parameter condition.The recursion has boundary values I(v − 1) = I(n − v + 1) = 0, and the condition on a ensures that q̄_x is real.Source: §5 · pp. 42–43

• The appendix distinguishes diamond-norm approximate designs from weak approximate designs, which are formulated using moment operators and operator norm.Exact designs correspond to ε = 0; weak designs are also called tensor product expanders.Source: Appendix F · p. 44
• Exact unitary 2-designs anti-concentrate because their collision probability matches the Haar second-moment benchmark.For Haar-random unitaries, Z_H = 2/(q^n + 1) ≤ 2/q^n and α = 1/2.Source: Appendix F · pp. 43–44
• ε-approximate 2-designs with ε = 1/q^2n have collision probability Z ≤ 3/q^n and therefore α = 1/3 anti-concentration.The same quantitative conclusion holds for weak approximate 2-designs defined through the operator-norm moment condition.Source: Appendix F · pp. 44–45
• 1D random circuits anti-concentrate in linear depth as a corollary of known approximate 2-design bounds, while complete-graph circuits have a best-known O(n^2) 2-design bound.If the conjectured O(n log(n)) complete-graph 2-design bound holds, anti-concentration and 2-design formation could occur at the same depth.Source: Appendix F · p. 45
• For 1D circuits, some second-moment states require depth Ω(n) to approach the minimal Haar value, separating 2-design formation from faster anti-concentration.The spectral-gap behavior implies this linear lower bound for approaching the Haar second-moment operator.Source: Appendix F · p. 45