Yuxuan Zhang (Oct 02 2025).
Abstract: Near-term feasibility, classical hardness, and verifiability are the three requirements for demonstrating quantum advantage; most existing quantum advantage proposals achieve at most two. A promising candidate recently proposed is through randomly generated peaked circuits. In this work, we study an explicit construction for random peaked circuits: first selecting a random circuit
C of polynomial size, which forms a
k-design. Subsequently, a second random circuit
C′ is chosen from the same architecture, subject to a postselection criterion:
C′ must exhibit a high overlap with
C in one of their rows. Utilizing unitary design properties, we demonstrate that the circuits generated by this method are non-trivial; specifically,
C′ is provably far from
C†. Indeed, with overwhelmingly high probability, a random peaked circuit generated this way is non-compressible and is of circuit complexity
Ω~(nk). This resolves an open problem posed by Aaronson in 2022. Secondly, we analytically establish that estimating the peakedness of a random peaked circuit to within a
2−poly(n) additive error, is average-case #P-hard. When the additive error is relaxed to
1/poly(n), we note that the worst-case scenario for this problem is BQP-complete. Under widely accepted assumptions on random quantum circuits, we identify a regime where no classical polynomial-time sequential simulator attains inverse-polynomial additive accuracy on the peak on a non-negligible fraction of instances. Thirdly, we study using peaked circuits as a practical attempt for a verifiable quantum advantage protocol. While the postselection method for generating peaked circuits could be costly, we demonstrate that numerical search for
C′ with randomized initialization successfully returns a random peaked circuit, achieving the properties as theoretically predicted.