Demonstration of Exponential Quantum Speedup with Constant-Depth Compiled Circuits for Simon's Problem

Referee: §4 (Experimental Results) and the associated figures on queries-to-solution: the exponential speedup claim rests on the observed scaling of the number-of-queries-to-solution metric, yet the manuscript provides no error bars, no description of the exact classical baseline algorithm (including whether it exploits the known Hamming-weight restriction), no statistical tests for the exponential fit, and no data-exclusion criteria. These omissions prevent verification that the reported gap arises from quantum interference rather than noise or baseline mis-specification.

Authors: We agree that these elements are necessary for rigorous verification of the results. In the revised manuscript we will add error bars derived from repeated experimental runs on both devices, provide an explicit description of the classical baseline (the standard Ω(2^{n/2}) query lower bound for Simon’s problem), include statistical tests (regression analysis and goodness-of-fit metrics) supporting the reported scaling, and state the data-exclusion criteria (runs with measured fidelity below a documented threshold). These additions will allow readers to confirm that the observed gap is consistent with quantum interference. revision: yes

Referee: Introduction and §2 (Problem Definition and Classical Complexity): the headline claim of exponential quantum speedup requires that the classical query complexity remains exponential even when the secret string s is restricted to Hamming weight k. Standard Simon lower bounds apply to unrestricted s; for bounded k the manuscript neither supplies an explicit lower-bound proof nor exhaustive classical simulations of the concrete oracles used. If classical complexity reduces to poly(n,2^k) for the realized k values, the reported exponential gap is not evidence of algorithmic speedup.

Authors: We thank the referee for this important observation. The manuscript compares against the standard unrestricted Simon lower bound. For the restricted-Hamming-weight promise, a classical algorithm that enumerates weight-k candidates and verifies collisions can achieve O(binomial(n,k)) queries. In the revision we will (i) add an explicit discussion of this restricted classical complexity, (ii) report exhaustive classical simulations of the concrete oracles for the small-n instances studied, and (iii) qualify the speedup claims by Hamming-weight regime, noting polynomial classical scaling for the smallest k and exponential scaling once binomial(n,k) becomes super-polynomial. Where the data support only polynomial speedup we will adjust the text and figure captions accordingly. revision: partial

Referee: §3 (Compilation Strategy): while the constant-depth compilation is a technical contribution, the manuscript does not quantify how the restriction to low-Hamming-weight instances interacts with the oracle implementation or whether the compiled circuits remain hard to simulate classically for the k range studied. This information is load-bearing for interpreting the speedup as quantum rather than an artifact of the restricted problem class.

Authors: We agree that further quantification is required. The low-Hamming-weight restriction permits a simplified oracle construction whose two-qubit gate count and depth scale linearly with k rather than n, enabling the constant-depth compiled circuits. In the revised §3 we will (i) tabulate gate counts and depth versus k, (ii) provide classical simulation cost estimates (state-vector or tensor-network) showing that the compiled circuits remain exponentially hard to simulate for the studied k range because the quantum algorithm still requires maintaining a superposition over 2^n amplitudes, and (iii) argue that the observed query advantage cannot be reproduced by any classical algorithm that merely exploits the promise without performing an equivalent number of oracle calls. Where feasible we will also include small-scale classical circuit simulations as supporting data. revision: yes