The optimization landscape of peaked-circuit generation

Technical Summary: The Optimization Landscape of Peaked-Circuit Generation

Problem Statement
The paper addresses the generation bottleneck in "peaked circuits," a proposed route to verifiable quantum advantage. Peaked circuits are random quantum circuits that, despite their random appearance, concentrate a constant fraction of their output probability mass on a single computational-basis string. While verifying such an output is efficient for a classical verifier who knows the target string, generating the circuit classically is difficult. Aaronson and Zhang (AZ) proposed a variational approach: appending a trainable brickwall of depth $n/2$ to a random Haar brickwall of depth $n$, then optimizing parameters to maximize the probability of the all-zero string. AZ observed that their gradient descent optimizer plateaued at a size-dependent ceiling, which they attributed to a barren plateau. They left open a dichotomy: either the optimizer stalled in local optima (implying a better algorithm could reach higher), or no efficient generation method exists. This paper maps the optimization landscape to resolve this dichotomy and characterize the scaling of the reachable peakedness.

Methodology
The study employs a rigorous, pre-registered experimental protocol using noiseless statevector simulations of one-dimensional open-boundary brickwall circuits.

• Circuit Architecture: The system consists of a random section $U_r$ (depth $\tau_r = n$) followed by a trainable section $V(\theta)$ (depth $\tau_p = n/2$). The trainable gates are products of 15 Pauli rotations per two-qubit block, yielding $P = \Theta(n^2)$ parameters.
• Optimization Protocol: The primary protocol uses the Adam optimizer with a specific learning rate schedule and 400 steps. The study defines a "stable-local class" of optimizers (gradient-flow-like dynamics with polynomial step sizes and independent restarts).
• Experimental Design: The author tested 18 instances per size for $n=8$ to $14$, with a registered "catch-up" to 18 instances at $n=16$. They utilized large restart ensembles (up to 800 restarts) to distinguish between landscape properties and optimizer budget limitations.
• Landscape Analysis: The paper analyzes the statics of the objective field $\delta(\theta)$, including exact moments (up to the fourth) via Weingarten calculus, gradient statistics, and connectivity using string methods to measure path minima between near-optimal solutions.
• Optimizer Comparison: A pre-registered block compared Adam against L-BFGS-B and plain SGD across different initializations to test for optimizer-specific advantages.

Key Contributions and Results

1. Rejection of the Fixed-Base Scaling Law:
   The paper rejects the fixed exponential decay law ($1.189^{-n}$) proposed by AZ. The author demonstrates that the local decay rate of the reachable peakedness is not constant but steepens monotonically with system size.

   • The decay rate increases from $\approx 1.16$ per qubit at $n=8$ to $\approx 1.295$ at $n=16$ (for converged runs).
   • Consequently, the extrapolation to $n=50$ provided by AZ is unsupported by the data at accessible sizes. The reachable peakedness shrinks faster than previously estimated.

2. Characterization of the Optimization Landscape:

   • No Barren Plateau: The mean gradient and Hessian vanish identically (as expected for Haar-random states), but the variance of the gradient at initialization is only $O(1)$ larger than the Haar limit. The "barren plateau" does not explain the steepening reach; the optimizer exploits structure acquired during optimization, not present at initialization.
   • Connected Shelf, No Overlap Gap: Direct measurement of connectivity via string methods shows that near-optimal solutions form a single connected component at the "trap scale" (the Haar floor $2^{-n}$). Paths between decorrelated solutions stay $10^2$–$10^3$ times above the trap scale. This refutes the overlap-gap mechanism (clustering with forbidden intermediate overlaps) as the source of hardness at the trap scale.
   • Deepening Corrugation: While connected, the "shelf" becomes increasingly corrugated. The median path minimum relative to endpoint values decays as $\approx 0.871^n$, faster than any fixed power law. This deepening corrugation, rather than fragmentation, characterizes the difficulty.

3. Optimizer Robustness and Hardness Conjecture:

   • Downward Failure: Plain SGD, within the registered stable-local class, fails to reach the same peakedness as Adam at the fixed budget, but this is attributed to "pacing" (step size) rather than the landscape itself.
   • Upward Exceedance: In a pre-registered comparison, L-BFGS-B (a quasi-Newton method) achieved a reach $3.9 \pm 1.6\%$ higher than converged Adam at $n=16$ on three instances.
   • Withdrawal of Hardness Conjecture: This exceedance triggers a pre-registered falsifier, leading the author to withdraw their conjecture that "no in-class statistic beats the shrinking reach." However, the scaling law remains: even L-BFGS-B's reach shrinks by a factor of $\approx 1.3$ per qubit.

4. Theoretical Bounds:

   • Deep Limit Ceiling: The author proves that in the deep limit (where the scrambled state is Haar), no family of probes with $poly(n)$ parameters can achieve expected peakedness beyond $poly(n) 2^{-n}$.
   • Finite Depth: At finite depth, the reachable peakedness exceeds this deep limit by a factor that grows with $n$, indicating the optimizer exploits finite-depth structure invisible to second-order amplitude statistics.

Significance and Claims
The paper claims to resolve the dichotomy posed by AZ by characterizing the landscape rather than simply finding a better optimizer.

• The Obstruction: The primary barrier to generating peaked circuits is not a barren plateau or an overlap gap (clustering), but a "shrinking reach" on a connected landscape. The reachable peakedness decays exponentially with a rate that steepens with system size.
• Implications for Quantum Advantage: The $n=50$ estimate for experimental feasibility derived by AZ is unsupported. The steepening decay rate suggests that generating peaked circuits for large $n$ will be significantly harder than previously thought, even if a better optimizer is found.
• Modesty of Claims: The author explicitly states that while they have withdrawn the conjecture that no in-class optimizer can beat the shrinking reach, the measured obstruction (the shrinking rate itself) stands for all optimizers tested so far. The paper does not claim to have found a method that scales efficiently to $n=50$; rather, it provides a precise, negative characterization of the landscape that rules out simple extrapolations and identifies the specific geometric features (steepening decay, deepening corrugation) that define the generation bottleneck.

In summary, the paper establishes that the generation of peaked circuits is hindered by a landscape where the reachable peak probability shrinks faster than any fixed exponential as qubit count increases, a phenomenon driven by deepening corrugation on a connected shelf, rather than by barren plateaus or solution clustering.