Demonstration of Exponential Quantum Speedup with Constant-Depth Compiled Circuits for Simon’s Problem
Phattharaporn Singkanipa, Victor Kasatkin, Daniel A. Lidar · 2026
Read Demonstration of Exponential Quantum Speedup with Constant-Depth Compiled Circuits for Simon’s Problem by Phattharaporn Singkanipa, Victor Kasatkin, Daniel A. Lidar (2026) 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-2604-27457.txt.
Introduction
Singkanipa, Kasatkin, and Lidar demonstrate exponential quantum speedup for a restricted Simon's problem, where the hidden string's Hamming weight stays below a cutoff, on superconducting processors. Their hardware-aware compilation reduces Simon query circuits to constant depth, needing only nearest-neighbour connections and no overhead. On IBM's Boston and Miami processors, the circuits reach fidelity to show speedup without error suppression. They observe exponential speedup over the classical bound from cutoff four up on Boston and for low-to-intermediate cutoffs on Miami, with polynomial speedup there.
Catalog record
| CREATOR | Phattharaporn Singkanipa, Victor Kasatkin, Daniel A. Lidar |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39063 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.27457
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Demonstration of Exponential Quantum Speedup with Constant-Depth Compiled Circuits for Simon’s Problem Phattharaporn Singkanipa, Victor Kasatkin, Daniel A. Lidar Abstract We demonstrate exponential quantum speedup for a restricted-Hamming-weight version of Simon’s problem on present-day superconducting quantum processors by introducing a hardware-aware compilation strategy that compiles the quantum part of each Simon query circuit to constant depth. The resulting compiled circuits have O ( 1 ) O(1) depth and linear connectivity, map directly onto common device layouts, and avoid additional routing and SWAP overhead. Implemented on IBM’s 156 156 -qubit Boston and 120 120 -qubit Miami processors, the resulting circuits achieve sufficiently high fidelity to exhibit algorithmic quantum speedup without error suppression. Using the number-of-queries-to-solution metric, we observe exponential speedup over the classical lower bound across the full Hamming-weight range studied on Boston and across low-to-intermediate Hamming weights on Miami; at higher Hamming weights on Miami, we still observe polynomial speedup. The same construction also reaches a regime where the original Simon problem is recovered for the problem sizes studied. These results show that careful hardware-aware compilation can make exponential quantum speedup experimentally accessible for a canonical hidden-subgroup problem in the NISQ regime. I Introduction Demonstrating an algorithmic quantum speedup, one in which a quantum algorithm solves a computational problem more efficiently than any classical algorithm as the problem size grows, is a central goal of quantum computing. While theoretical quantum advantages have been established for decades Deutsch and Jozsa 1992 ; Bernstein and Vazirani 1997 ; Simon 1997 ; Grover 1997 ; Shor 1997 ; Childs et al. 2003 ; Van Dam et al. 2006 ; Harrow et al. 2009 ; Montanaro 2016 ; Bravyi et al. 2018 ; Bravyi et al. 2020 ; Bharti et al. 2022 ; Daley et al. 2022 , realizing them on physical hardware is challenging due to the noise and limited scale of current noisy intermediate-scale quantum (NISQ) Preskill 2018 devices. This goal is distinct from quantum supremacy experiments Aaronson and Chen 2017 ; Arute et al. 2019 ; Wu et al. 2021 ; Zhong et al. 2020 ; Zhong et al. 2021 ; Morvan et al. 2024 , which demonstrate classically intractable sampling tasks without addressing computational utility, and from device benchmarking Figgatt et al. 2017 ; Wright et al. 2019 ; Roy et al. 2020 ; Pelofske et al. 2022 ; Lubinski et al. 2023 ; Tripathi et al. 2025 , which characterizes hardware performance without resolving the question of algorithmic scaling Barak et al. 2021 ; Zlokapa et al. 2023 ; Aharonov et al. 2023 . Experimental progress toward this goal has been made across a range of hardware platforms Albash and Lidar 2018 ; King et al. 2021 ; Saggio et al. 2021 ; Centrone et al. 2021 ; Maslov et al. 2021 ; Xia et al. 2021 ; Huang et al. 2022 ; Ebadi et al. 2022 ; Zhou et al. 2022 ; King et al. 2023 ; Kim et al. 2023 , where better-than-classical success probabilities have been reported for specific problem instances. However, many of these demonstrations compare against a restricted set of classical algorithms or rely on complexity-theoretic assumptions rather than direct empirical evidence of a scaling advantage. A rigorous demonstration of algorithmic quantum speedup requires a performance comparison against the best known classical algorithms over a broad and increasing range of problem sizes, which remains a stringent benchmark that few experiments have met. Conjecture-free quantum scaling advantages have recently been demonstrated on IBM Quantum superconducting processors using hardware-aware error suppression techniques. Ref. Pokharel and Lidar 2023 reported a scaling advantage for the Bernstein-Vazirani algorithm using dynamical decoupling (DD) Viola and Lloyd 1998 ; Viola et al. 1999 ; Zanardi 1999 ; Vitali and Tombesi 1999 ; Duan and Guo 1999 , while Ref. Singkanipa et al. 2025 extended this approach to restricted-Hamming-weight instances of Simon’s problem, which belongs to the class of Abelian hidden subgroup problems Jozsa 2001 . The compiled Simon’s problem circuit in Ref. Singkanipa et al. 2025 had a star-type CNOT structure with depth O(\HW(b)) for a hidden string b . Embedding this structure onto the heavy-hex connectivity architecture of IBM Quantum processors introduced substantial SWAP overhead, making error suppression indispensable for maintaining circuit fidelity. Specifically, DD was combined with measurement error mitigation (MEM) Temme et al. 2017 to demonstrate algorithmic speedup in the resulting deep circuits. In this work, we show that, under the same compiler rules as in Ref. Singkanipa et al. 2025 , Simon query circuits can be compiled so that their quantum part has constant depth, without changing the underlying oracle problem. Our construction requires only linear connectivity and yields compiled query circuits with O(1) quantum depth, independent of \HW(b) . These circuits use only two entangling layers, map natively onto common two-dimensional superconducting-qubit layouts, and avoid additional routing and SWAP overhead. Our results show that careful hardware-aware compilation can significantly enhance quantum-classical scaling separations on NISQ devices, even without error suppression, and underscore the importance of co-designing algorithms with hardware constraints in mind. In the original formulation of Simon’s problem, one is given a function f_{b}\colon\{0,1\}^{n}\to\{0,1\}^{n} promised to be either 1-to-1 or 2-to-1, such that f_{b}(x)=f_{b}(y) if and only if x=y or x=y\oplus b , where b\in\{0,1\}^{n} is a hidden bitstring. The task is to determine which case holds and, in the 2-to-1 case, to identify b . Here we focus on the 2-to-1 case and restrict b to have Hamming weight at most w\leq n , yielding the restricted-HW version of Simon’s problem \mathsf{w}_{{w}}\textnormal{Simon-}{n} . The original Simon’s problem is recovered by setting w=n . We analyze performance using an oracle-query metric, the number-of-queries-to-solution (NTS) Singkanipa et al. 2025 , and show that this setting enables a clear quantum scaling advantage even on contemporary superconducting qubit architectures. The same compiled-circuit construction also allows the original Simon’s problem to be implemented up to a certain problem size, so the demonstrated exponential speedup is not limited to the restricted-Hamming-weight setting in those cases. The speedup is quantified in a guessing game setting introduced in Singkanipa et al. 2025 , whose rules are briefly summarized in Section II . In particular, we restate the game settings, the speedup metric NTS, and the classical and quantum algorithms for solving Simon’s problem, along with the methodology for comparing the performance of each player. In Section III , we present the main contribution of this work: a compilation scheme that yields constant-depth Simon query circuits, together with its experimental implementation. The speedup results are presented in Section IV , followed by the conclusion in Section V . Additional technical details and supplemental results are provided in the appendices. II Quantum speedup in a guessing game II.1 Rules of the game We adopt the single-player guessing game introduced in Ref. Singkanipa et al. 2025 . A function f\colon\{0,1\}^{n}\to\{0,1\}^{n} satisfying the 2-to-1 condition is drawn uniformly at random and is not revealed to the player, who instead has oracle access to evaluate f(x) for any input x\in\{0,1\}^{n} . The player may perform any number of oracle queries, along with arbitrary classical computation, before submitting a guess for the hidden bitstring b . The correctness of the guess is then verified, after which a