The optimization landscape of peaked-circuit generation

Abstract

Peaked circuits are random quantum circuits whose measurement returns one bitstring far more often than chance. The probability of that string is the peakedness, and a verifier who knows the string checks the device in a few shots. Peaked circuits are a candidate route to verifiable quantum advantage, and classical generation is the bottleneck. Aaronson and Zhang train a variational circuit by gradient descent, and the peakedness they reach decays exponentially with the number of qubits. They state that either their optimizer stalls or no efficient generation method exists. Here we show that no bare fixed base fits the decay we measure and that neither the barren plateau nor fragmentation of the solution set explains it. We measure the optimization landscape on eighteen instances per size, from eight to sixteen qubits, under a protocol whose falsifiers were fixed in advance. The decay steepens as the qubit number grows, leaving extrapolations to larger devices unsupported. A better optimizer exists, but it gains a few percent and the peakedness it reaches decays at nearly the same rate. Aaronson and Zhang attribute the difficulty to a barren plateau. The plateau is present, but the second-order amplitude data are depth-independent while the attained peakedness is not. Independent runs land on uncorrelated solutions, yet paths connecting them stay well above the scale of a random state, so fragmentation fails at that scale. In the deep limit we take the scrambled state Haar-random. There we prove that no search over a polynomial-parameter Lipschitz family, exhaustive search included, beats the scale of a random state by more than a poly(n) factor on average. Both branches of the Aaronson-Zhang alternative therefore stay open. A generation method must beat a preregistered baseline, and a hardness argument must accommodate a solution set connected at the scale of a random state.