Over a decade after its proposal, the idea of using quantum computers to sample hard distributions has remained a key path to demonstrating quantum advantage. Yet a severe drawback remains: the anti-concentrated distributions believed to be hard to classically simulate are typically hard to verify without exponential classical effort. In this series of work, we propose peaked circuit sampling, addressing this challenge by using circuits that are otherwise random but engineered to produce a pronounced “peak” on a specific computational-basis string, providing a direct verification handle while retaining complexity-theoretic hardness.
To this end, I will summarize three complementary results. First, we analyze explicit “random + peaking” architectures and quantify when nontrivial peakedness can (and cannot) be generated efficiently, motivating peaked circuits as a plausible route to verifiable advantage. ([arXiv][1]) Second, I present average hardness results for generic random peaked circuits, including circuit-complexity lower bounds and average-case #P-hardness of estimating peakedness to high precision, along with connections to BQP/QCMA regimes relevant for efficient verification. ([arXiv][2]) Third, I discuss heuristic ways of constructing large peaked circuits, which have been experimentally demonstrated on Quantinuum’s H2 processor. We show results with an empirical gap between quantum runtimes and leading classical simulation strategies, positioning peaked circuits as both a benchmarking tool and a concrete step toward verifiable quantum advantage. ([arXiv][3])
arXiv: [1] 2404.14493, [2] 2510.00132, [3] 2510.25838
