Posted

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 CC of polynomial size, which forms a kk-design. Subsequently, a second random circuit CC' is chosen from the same architecture, subject to a postselection criterion: CC' must exhibit a high overlap with CC in one of their rows. Utilizing unitary design properties, we demonstrate that the circuits generated by this method are non-trivial; specifically, CC' is provably far from CC^\dagger. Indeed, with overwhelmingly high probability, a random peaked circuit generated this way is non-compressible and is of circuit complexity Ω~(nk)\tilde \Omega(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 2poly(n)2^{-\text{poly}(n)} additive error, is average-case #P-hard. When the additive error is relaxed to 1/poly(n)1/\text{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 CC' with randomized initialization successfully returns a random peaked circuit, achieving the properties as theoretically predicted.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!