Heuristic Quantum Advantage with Peaked Circuits
Hrant Gharibyan, Mohammed Zuhair Mullath, Nicholas E. Sherman, Vincent P. Su, Hayk Tepanyan, Yuxuan Zhang · 2025
Read Heuristic Quantum Advantage with Peaked Circuits by Hrant Gharibyan, Mohammed Zuhair Mullath, Nicholas E. Sherman, Vincent P. Su, Hayk Tepanyan, Yuxuan Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-25838.txt.
Introduction
Hrant Gharibyan and five co-authors report a test of quantum advantage using circuits designed to peak on one target output. A peaked circuit is built so that one bit string, a string of zeros and ones, should appear far more often than others. They run their circuits on Quantinuum System Model H2, a commercial quantum processor.
Their largest run used two thousand two qubit gates and produced the target in under two hours. By extending results from leading classical methods, they argue the same task would take years on top supercomputers, which hints at a large gap. They also prove a related decision problem is hard for quantum verification in a formal sense.
Catalog record
| CREATOR | Hrant Gharibyan, Mohammed Zuhair Mullath, Nicholas E. Sherman, Vincent P. Su, Hayk Tepanyan, Yuxuan Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 67 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-25838
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Heuristic Quantum Advantage with Peaked Circuits Hrant Gharibyan, Mohammed Zuhair Mullath, Nicholas E. Sherman, Vincent P. Su, Hayk Tepanyan, Yuxuan Zhang Abstract 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. Our largest instance involves all-to-all connectivity with 2000 two-qubit gates, which H2 can produce the target peaked bitstring directly in under 2 hours. Our extrapolations from leading classical simulation techniques such as tensor networks with belief propagation and Pauli path simulators indicate 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 and provide extensive numerical results leading to our extrapolation estimates. Separate from our constructed HQAP circuits, we prove hardness on a decision problem involving generic peaked circuits. When both the input and output bitstrings of a peaked circuit are unknown, determining whether the circuit is peaked constitutes a QCMA-complete problem, meaning the problem remains hard even for a quantum polynomial-time machine under commonly accepted complexity assumptions. Inspired by this observation, we propose an application of the peaked circuits as a potentially quantum-safe encryption scheme [ 1 , 2 , 3 , 4 ] . We make our peaked circuits publicly available and invite the community to try additional methods to solve these circuits to see if this gap persists even with novel classical techniques. 1 Introduction Random circuit sampling (RCS) [ 5 , 6 , 7 ] has emerged as a primary benchmark for demonstrating quantum computational advantage, exemplified by Google’s 2019 Sycamore experiment [ 8 ] and later followed by USTC Zuchongzhi works [ 9 , 10 ] . However, recent large-scale demonstrations from Google’s Willow [ 11 ] and Quantinuum’s H-2 [ 12 ] , while likely beyond classical simulation, expose a fundamental limitation of random circuit sampling: verification through cross-entropy benchmarking becomes exponentially expensive at large scales, rendering direct validation impossible. We present a scalable method for demonstrating heuristic quantum advantage using peaked quantum circuits [ 13 ] , circuits engineered to produce specific output bitstrings with anomalously high probability compared to an truly random circuit but otherwise look random. The verification protocol is straightforward: Alice constructs a peaked circuit knowing its peak bitstring, Bob executes the circuit with his quantum computer measuring in the computational basis, and Alice verifies by checking if Bob’s output matches the known peak. No exponential classical computation is required. Our contributions are threefold: (i) We develop scalable construction techniques for peaked circuits at larger qubit counts and depths using methods related to identity obfuscation [ 14 , 15 , 16 ] . (ii) Through extensive benchmarking, we demonstrate that our circuits resist state-of-the-art classical simulation methods including matrix product states [ 17 , 18 , 19 , 20 ] , tensor networks with belief propagation [ 19 , 21 ] , and Pauli path simulators [ 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 ] . (iii) We motivate this construction further with hardness results for a decision problem involving general peaked circuits. In particular, we prove that determining whether an unknown circuit is peaked constitutes a QCMA-complete problem. Note that this is separate from our definition of “solving” our HQAP circuits, where the input string is fixed to the all zeros state. Peaked circuits broadly have mounting evidence for their hardness. Simulating random peaked circuits is hard in the average case, analogous to RCS, particularly for circuits generated via post-selection [ 30 ] and error correction codes [ 31 ] . Our theoretical results in this work further add to the literature on hardness when the quantum circuit is peaked from a specific input bitstring to a particular output bitstring. However, our primary contribution lies in demonstrating the empirical difficulty of classically simulating circuits that not only admit efficient construction, but can also be implemented on existing quantum hardware. The relationship between our practical construction and the broader ensemble of peaked circuits remains an open question. In the absence of this theoretical connection, we refrain from asserting strong classical intractability results, instead characterizing the observed quantum-classical separation as a heuristic quantum advantage. The rest of the paper is organized as follows. In Section 2, we summarize the empirical runtime gap between quantum and classical resources needed to solve our peaked circuits. In Section 3, we describe briefly the techniques used to construct these peaked circuits. In Section 4, we provide additional background and details on the classical methods we implement for comparison. In section 5, we study a potential practical application of peaked circuits as a post-quantum cryptographic primitive. We conclude in Section 6 and invite others to test other ways of finding the peak in Section 7. 2 A Gap in Classical and Quantum Runtime for Solving Peaked Circuits We start with our main result, which is an empirical gap in the time it takes to solve peaked circuits that we have constructed. Though our methods can generalize to even larger circuits, we focus on what is achievable on existing hardware, in particular Quantinuum’s H-2 processor [ 32 ] with 56 qubits and any-to-any connectivity. We create peaked circuits with 56 qubits and two-qubit gate counts ranging from 200 up to 2000. The quantum run time is approximately a few hours, while classical methods fail to extract the correct answer at around 700 RZZ gate circuits with reasonable computational resources. We estimate the largest circuits would require millions of GPU hours. From Ref. [ 13 ] , we take the following definition. Definition 1.1 (Peaked Circuit). Given \delta\in(0,1] , we call the unitary C \delta -peaked if: \max_{s\in\{0,1\}^{N}}\,|\langle s|C|0^{N}\rangle|^{2}\geq\delta with a corresponding peak weight \delta_{\textbf{s}}\equiv|\langle\textbf{s}|C|0^{N}\rangle|^{2} . where s is the peaked bitstring. To “solve” a peaked circuit means given C , e.g. a circuit description in terms of gates, one correctly identifies the peaked bitstring s . For sufficiently small systems, one can compute the full statevector and compute the maximal amplitude squared but this clearly does not scale well with system size. With access to a quantum computer, one can simply run the circuit an O(1/\delta_{\textbf{s}}) times to observe a signal. Of course, in the presence of noise, one may encounter an overhead in the required number of shots. a) b) c) Figure 1 : Gap in Classical and Quantum Runtimes for Solving 56 qubit HQAP Circuits . a) We compare classical techniques (MPS, PPS and TNS+BP) with quantum techniques for solving 56 qubit, 10% peaked circuits with all-to-all connectivity. As number of RZZs increases, classical methods require estimated millions of Nvidia H100 GPU hours, while the quantum device requires less than 2 hours. More details on the classical methods can be found in section 4 b) The performance of the quantum device drops with the growing number of RZZs in the HQAP circuit as expected, with still strong signal of 5/1000 (correct) peak samples for a 2044 RZZ circuit. c) Actual results