Heuristic Quantum Advantage with Peaked Circuits

We design and demonstrate heuristic quantum advantage with peaked circuits (HQAP circuits) on Quantinuum's System Model H2 quantum processor. Through extensive experimentation with state-of-the-art classical simulation strategies, we identify a clear gap between classical and quantum runtimes. By studying peaked circuits designed with our protocol of varying sizes and all-to-all connectivity, we experimentally implemented them on H2, observed the target peak with high statistical confidence, and showed that the 2000 two-qubit-gate instance is solved directly in under 2 hours. Through classical-simulation extrapolation using state-of-the-art methods, we estimate the same instance would take years on exascale systems (Frontier, Summit), suggesting a potentially exponential separation. This work marks an important milestone toward verifiable quantum advantage, as well as providing a useful benchmarking protocol for current utility-scale quantum hardware. We sketch our protocol for designing these circuits, provide extensive numerical results leading to our extrapolation estimates, and we make these circuits publicly available. We invite the community to try additional methods to solve these circuits to see if this gap persists even with novel classical techniques. We further outline how peaked circuits can underpin new cryptographic protocols, where messages are encoded into HQAP circuits that can only be efficiently decrypted by NISQ quantum devices with sufficient scale and fidelity, while remaining intractable for classical computers.