- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The authors combine the standard Grover search (amplitude amplification) algorithm with classical neural networks (NNs) and propose a quantum algorithm for training NNs without the backpropagation step. The paper is well written and easy to follow. The authors also provide a rigorous theoretical analysis of the proposed quantum algorithm for NN training. However, from my perspective, the main idea is somewhat straightforward, as it essentially amounts to a direct application of Grover search to the NN training problem. Furthermore, computing NN functions coherently on a quantum register may require a very large number of quantum gates, which could substantially diminish, or even eliminate, any potential quantum advantage. In summary, I do not believe that the current manuscript provides sufficiently significant contributions or sufficiently surprising results to meet the standards of ICLR.
Critical strengths
From a high-level perspective, the paper investigates how quantum computers can help accelerate the training of classical AI models, particularly in the current era of large language models (LLMs), which is a highly active topic in the quantum computing community. The paper is well written and easy to follow. All parameters and problem statements are clearly defined.
Critical weaknesses
-
Some of the cited references do not seem particularly relevant. For example, in the Introduction, the authors state that “Quantum machine learning (QML) has accordingly been proposed as a vehicle for importing such speedups into learning.” However, the cited references mainly focus on variational quantum algorithms rather than Grover search or amplitude amplification, and therefore do not directly support the statement in the present context.
-
The proposed quantum algorithm is somewhat straightforward. From my perspective, the overall construction is not particularly surprising, as it essentially applies Grover search to the training of classical neural networks.
-
My main concern is the scalability of the proposed method. In fact, the quantum algorithm requires all NN functions to be encoded and evaluated coherently within a quantum register. However, even relatively simple arithmetic operations, such as modular inversion, may require a large number of T gates in a fault-tolerant quantum implementation. Practical NN functions are considerably more complex and would therefore be much more costly to implement on a quantum computer. This potentially large circuit overhead may significantly diminish, or even eliminate, the claimed quantum advantage.
Questions for authors
My main concern is the quantum-gate implementation required to evaluate a complex NN function in superposition. In particular, how is the function coherently encoded and evaluated in a quantum register? Furthermore, since the resulting quantum state must subsequently be used within the amplitude amplification (AA) subroutine, the total number of elementary quantum gates could become extremely large and may be difficult to implement even on fault-tolerant quantum computers. For example, for a practical NN model such as GPT-3, what would be the estimated quantum gate count required to coherently evaluate and encode the result into the quantum register?
4 comments
On the novelty of the construction
On the novelty of the construction
The search component of MaT relies on amplitude amplification, which is indeed a standard quantum primitive. A construction limited to applying Grover search directly to neural network weights would offer limited novelty.
However, the standard Grover algorithm does not determine whether the target set of a given network architecture possesses non-negligible probability mass, which constitutes the central theoretical question analyzed in this paper. Under uniform ambient priors, this probability mass is exponentially small, rendering the quadratic quantum speedup ineffective. Conversely, under geometric split priors derived from the input data matrix , we prove that the target mass remains constant for linear models, deep linear models, and ReLU networks, while establishing an explicit decaying packing bound for softmax attention architectures. Theorem 1 then leverages this prior mass to establish an query upper bound, a full-batch -certificate, and exact sampling from the conditional prior distribution over the marked set, improving upon same-prior classical rejection sampling. In this respect, our work follows a similar theoretical structure to Montanaro (2015) as well as Kapoor, Wiebe, and Svore (2016), where the core scientific contribution lies in formalizing the quantum oracle and characterizing the marked space for specific function classes. In our framework, the primary focus is analyzing the prior mass landscape of deep classical architectures subject to full-batch loss predicates.
On QML citations in the Introduction
The Introduction currently motivates Grover search via its square-root speedup while citing quantum machine learning literature that largely focuses on variational algorithms. As a result, using the phrase "such speedups" inadvertently creates a disconnect between the amplitude amplification technique and the cited variational references. We will revise this section to clearly distinguish between these two topics. Citations to Grover (1996) and Brassard, Høyer, Mosca, and Tapp (2002) will be retained specifically to ground the quantum search primitive. References to the variational QML literature, including work by Biamonte, Cerezo, and Benedetti, as well as subsequent hybrid language modeling papers, will be reframed to contextualize quantum learning methods more broadly. In Section 4, these works will continue to serve as examples of frameworks relying on classical iterative optimization outer loops and subject to barren plateaus, while no longer being cited as evidence for Grover-style speedups.
Reply to authors
Thank you for the response. After carefully rereading the manuscript, I still have the following concerns:
-
Resource estimates and error-correction overhead. I appreciate the additional resource estimates for implementing neural-network computations on quantum circuits. Do these estimates include the overhead of quantum error correction, or do they account only for logical resources? Even at the logical level, the reported resource requirements appear substantial, with very deep circuits.
-
Quantum advantage in the constant-mass regime. I appreciate the clarification that the main contribution lies in establishing lower bounds on the prior mass of the marked set. However, when is bounded below by a positive constant, both quantum amplitude amplification, with query complexity , and classical rejection sampling from the same prior, with expected query complexity , require only queries. Classical rejection sampling also provides the same full-batch loss guarantee and conditional output distribution. Consequently, the constant-mass examples do not establish an asymptotic quantum advantage and leave open whether any constant-factor benefit survives the costs of coherent state preparation and oracle implementation. From this perspective, the proposed protocol may not provide many quantum speed-up, if my understanding is correct.
We sincerely thank the reviewer for the careful rereading. Both answers are direct. The reported estimates are logical resources, and error correction is not included. And the understanding of the reviewer about the constant-mass regime is correct: at constant mass both sides are queries, and we claim no separation. What remains is one distinction, which one table below makes precise.
On error correction. The counts are logical qubits and logical Toffoli and T gates under schoolbook arithmetic. We have not done a fault-tolerant compilation and will not quote converted numbers of our own. A surface-code implementation multiplies them by a distance-squared factor per logical qubit plus distillation hardware, and by the threshold theorem the required distance grows only logarithmically in the gate count, so the converted circuits are orders of magnitude deeper while the per-call overhead inflates only polylogarithmically. The surface-code logical error analysis is Fowler et al. (2012), and a concrete end-to-end accounting on 20 million noisy qubits is Gidney and Ekera (2021). We will label the resource table as logical and add these citations.
On the constant-mass regime. We concede all three points. First, Proposition 9 states against for general , and at the constant masses of Theorems 2 through 5, for the linear theorems and for ReLU, both sides are . Second, the matched baseline returns the same certificate and output law by construction. Third, at the quantum total beats rejection only if , far below schoolbook . At constant mass rejection is therefore the cheaper computation, and Theorems 2 through 5 are feasibility results rather than separations: they guarantee searchable mass where the uniform prior has exponentially little. We will say so in Section 5.
What we respectfully maintain is only that "may not provide many quantum speed-up" extrapolates from that regime to the whole protocol. The query bound of Theorem 1, against , holds for every , and with the overhead counted the claim is exact: MaT wins the total cost exactly when , and below that point the ratio grows without bound:
| prior mass | MaT queries | rejection queries | ratio | total at |
|---|---|---|---|---|
| , constant mass | rejection | |||
| tie | ||||
| MaT |
Here is an idealized schoolbook value, and error correction moves the crossover row down by polylogarithmic factors only. Two caveats keep this table honest. The first is that our measured point sits above the crossover: the -centered prior at has and ratio , on the rejection side for schoolbook , and lowering moves below the crossover by the scaling of Proposition 9 rather than by a new experiment. The second is where the small masses come from: Theorem 6 proves a softmax packing bound that decays with the box radius, with the matched cost not necessarily constant, though the bound can be small enough that the post-Grover cost remains large. State preparation, lastly, is invoked times and enters the same accounting.
We will state this in Appendix E.
On coherent evaluation and gate cost
We thank the reviewer for the thoughtful feedback. The main concern raised is the number of quantum gates required to evaluate f(θ) coherently, particularly at the scale of GPT-3. Additionally, the reviewer notes that the construction resembles a direct application of Grover search and points out that the Introduction cites variational QML literature when discussing Grover speedups. We address each of these points in detail below.
On coherent evaluation and gate cost
We share the concern that a coherent circuit for f(θ) is expensive, and that this cost can shrink or remove a query advantage. Section 2 encodes each of the P parameters as a b-bit string, so θ occupies K=Pb qubits, and one call to UL is one reversible full-batch evaluation of f(θ) and of L≤ε on the superposition. Amplitude amplification then repeats that circuit O(TQ) times. The cost model does not treat the call as free.
The circuit is the reversible counterpart of a classical forward pass. Schoolbook arithmetic prices a b×b product at O(b2) Toffoli gates, so one oracle call costs N⋅P⋅O(b2) Toffoli gates. With b2/2 Toffoli gates per product and at most 7 T gates per Toffoli, the logical counts at b=16 are:
As shown in the table, the GPT-3 row is large because GPT-3 is large. The Introduction records that classical pretraining consumed 3.14×1023 FLOPs. The table is the reversible, superposition version of one full-corpus forward pass of that same model, about 1025 T gates and 3×1012 logical qubits under schoolbook arithmetic. Present devices cannot hold that register. However, we respectfully claim that it is a date on the hardware curve, not a limit of Theorem 1, as classical transistor counts grew exponentially. We do not freeze logical qubits and T-gate throughput at present scales, and we do not treat a later expansion of quantum hardware as implausible. Such an expansion would decide whether a GPT-3-sized register fits. It would not change the query comparison below. The resource appendix therefore reads its table as a diagnostic of present and near-term devices, and the theorems are proved on structured low-dimensional charts, including the LoRA-scale register that the appendix names as the realistic present direction.
However, even after the hardware curve moves, the coherent circuit still costs a factor κ per call, and Theorem 1 compares MaT with same-prior rejection rather than with a free coherent circuit. Let G be the classical full-batch cost of the same predicate, and let κ be the factor by which the coherent circuit exceeds G. Rejection pays G/p. MaT pays κG/p. MaT does not need a cheaper oracle. It needs fewer calls, and the quadratic factor beats the overhead exactly when p<κ−2. At κ=102 this is p<10−4. Under schoolbook arithmetic κ scales as b2 and does not grow with N or P at fixed precision. At constant mass both methods use O(1) calls, so κ dominates and the constant-mass theorems are feasibility and certificate results. In the small-p regime the gap between 1/p and 1/p outgrows a κ of that form. We will fold the table and p<κ−2 into the resource appendix.