acceptodds
Under review as a conference paper at ICLR 2027

Measurement as Training: Exploring BP-Free Learning Method of Neural Networks via Quantum Sampling

Abstract

The training of neural networks, especially large language models, is dominated by iterative optimization driven by backpropagation (BP), whose compute cost grows rapidly with the model and data size, and whose training process suffers from slow convergence, loss spikes, and even sudden collapse. Quantum computing (QC) has been proposed as a promising direction for breaking this bottleneck, yet existing studies merely insert quantum components into the classical pipeline, so the BP outer loop and its cost remain untouched. In this paper, we propose measurement as training (MaT), a fundamentally different QC-based training scheme that does not require BP at all. MaT loads a coherent prior over discretized network parameters as a quantum superposition, marks the parameters whose full-batch training loss is at most through a coherent loss indicator, and applies amplitude amplification to return a certified -good parameter. Theoretically, we prove that under aligned split priors the prior mass of the -good set is a constant bounded away from zero, which yields oracle queries up to preparation cost together with a full-batch -certificate and a quadratic query advantage over classical accept/reject from the same prior. We then extend the analysis from a single linear layer to deep linear models, ReLU networks, and softmax attention, and the guarantees become progressively more conditional as the architecture grows, with negative results and a certificate gap against mini-batch SGD delimiting the scope of the framework. We hope MaT can inspire more training paradigms beyond classical BP for neural networks.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Quantum Computation, Neural Networks, Large Language Models, Machine Learning, Learning Theory

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_9F7COpenReview ↗
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
  1. 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.

  2. 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.

  3. 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 f(θ)f(\theta) 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 f(θ)f(\theta) and encode the result into the quantum register?

4 comments
AuthorsOpenReview ↗

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(θ)f(\theta) 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(θ)f(\theta) is expensive, and that this cost can shrink or remove a query advantage. Section 2 encodes each of the PP parameters as a bb-bit string, so θ\theta occupies K=PbK=Pb qubits, and one call to ULU_{\mathcal{L}} is one reversible full-batch evaluation of f(θ)f(\theta) and of L≤ε\mathcal{L}\le\varepsilon on the superposition. Amplitude amplification then repeats that circuit O(TQ)O(T_Q) 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×bb\times b product at O(b2)O(b^{2}) Toffoli gates, so one oracle call costs N⋅P⋅O(b2)N\cdot P\cdot O(b^{2}) Toffoli gates. With b2/2b^{2}/2 Toffoli gates per product and at most 77 TT gates per Toffoli, the logical counts at b=16b=16 are:

modelNNPPregister K=PbK=PbToffoli gates per callTT gates per call
least squares642564.1×1034.1\times10^{3}2×1062\times10^{6}∼107\sim10^{7}
tiny attention2410241.6×1041.6\times10^{4}3×1063\times10^{6}∼107\sim10^{7}
deep linear4830724.9×1044.9\times10^{4}2×1072\times10^{7}∼108\sim10^{8}
ReLU MLP9625604.1×1044.1\times10^{4}3×1073\times10^{7}∼108\sim10^{8}
GPT-3, full corpus3×10113\times10^{11} tokens1.75×10111.75\times10^{11}2.8×10122.8\times10^{12}7×10247\times10^{24}∼1025\sim10^{25}

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×10233.14\times 10^{23} FLOPs. The table is the reversible, superposition version of one full-corpus forward pass of that same model, about 102510^{25} TT gates and 3×10123\times 10^{12} 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 κ\kappa per call, and Theorem 1 compares MaT with same-prior rejection rather than with a free coherent circuit. Let GG be the classical full-batch cost of the same predicate, and let κ\kappa be the factor by which the coherent circuit exceeds GG. Rejection pays G/pG/p. MaT pays κG/p\kappa G/\sqrt{p}. MaT does not need a cheaper oracle. It needs fewer calls, and the quadratic factor beats the overhead exactly when p<κ−2p<\kappa^{-2}. At κ=102\kappa=10^{2} this is p<10−4p<10^{-4}. Under schoolbook arithmetic κ\kappa scales as b2b^{2} and does not grow with NN or PP at fixed precision. At constant mass both methods use O(1)O(1) calls, so κ\kappa dominates and the constant-mass theorems are feasibility and certificate results. In the small-pp regime the gap between 1/p1/\sqrt{p} and 1/p1/p outgrows a κ\kappa of that form. We will fold the table and p<κ−2p<\kappa^{-2} into the resource appendix.

AuthorsOpenReview ↗

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 XX, 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 pp to establish an O(1/p)O(1/\sqrt{p}) query upper bound, a full-batch ε\varepsilon-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.

Reviewer_9F7COpenReview ↗

Reply to authors

Thank you for the response. After carefully rereading the manuscript, I still have the following concerns:

  1. 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.

  2. Quantum advantage in the constant-mass regime. I appreciate the clarification that the main contribution lies in establishing lower bounds on the prior mass pp of the marked set. However, when pp is bounded below by a positive constant, both quantum amplitude amplification, with query complexity O(p−1/2)O(p^{-1/2}), and classical rejection sampling from the same prior, with expected query complexity Θ(p−1)\Theta(p^{-1}), require only O(1)O(1) 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 O(1)O(1) 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 κ\kappa 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 Trej=Θ(1/p)T_{\mathrm{rej}}=\Theta(1/p) against TQ=O(1/p)T_{Q}=O(1/\sqrt{p}) for general pp, and at the constant masses of Theorems 2 through 5, p≥1/4p\ge1/4 for the linear theorems and p≥1/8p\ge1/8 for ReLU, both sides are O(1)O(1). Second, the matched baseline returns the same certificate and output law by construction. Third, at p=1/4p=1/4 the quantum total beats rejection only if κ<2\kappa<2, far below schoolbook κ=Θ(b2)\kappa=\Theta(b^{2}). 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, O(1/p)O(1/\sqrt{p}) against Θ(1/p)\Theta(1/p), holds for every p>0p>0, and with the overhead κ\kappa counted the claim is exact: MaT wins the total cost exactly when p<κ−2p<\kappa^{-2}, and below that point the ratio grows without bound:

prior mass ppMaT queries 1/p1/\sqrt{p}rejection queries 1/p1/pratiototal at κ=256\kappa=256
1/41/4, constant mass224422rejection
κ−2≈1.5×10−5\kappa^{-2}\approx1.5\times10^{-5}2562566.6×1046.6\times10^{4}256256tie
10−810^{-8}10410^{4}10810^{8}10410^{4}MaT

Here κ=b2\kappa=b^{2} 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 00-centered prior at q=0.01q=0.01 has p^≈0.012\hat p\approx0.012 and ratio 11.511.5, on the rejection side for schoolbook κ\kappa, and lowering qq 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 Θ(1/pε)\Theta(1/p_{\varepsilon}) not necessarily constant, though the bound can be small enough that the post-Grover cost remains large. State preparation, lastly, is invoked O(TQ)O(T_{Q}) times and enters the same accounting.

We will state this in Appendix E.

Reviewer_2nFuOpenReview ↗
Rating
2
Confidence
4
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a new training method (MaT) for neural networks using quantum computers. The idea is to discretize a NN parameters onto a grid, prepare a coherent prior state over the grid, mark grid points whose full-batch loss is ≤ϵ\le \epsilon with a coherent indicator oracle, and run amplitude amplification. The query cost is O(1/p)O(1/\sqrt p), where pp is the prior mass of the ϵ\epsilon-good set.

Critical strengths

The problem is well motivated and and the approach to encode classical parameters into quantum state is very interesting. And the paper sufficiently discusses the major concerns with QCs such as no-cloning and no free lunch.

Critical weaknesses

My main issue is that the proposed approach already assumes that the starting point is already a good solution (ϵ\epsilon-good set). This highly limits the use case of the proposed method, as acknowledged by the authors in Sec. 5.

My second issue is that as Proposition 9 notes, when pp is constant, both MaT and classical rejection sampling from the same prior take Θ(1)\Theta(1) queries. The only speedup is the generic Grover quadratic factor in the small-pp regime, where the paper proves no mass bounds. So the constant-mass theorems contribute no advantage.

Some missing references:

  • Ricks & Ventura (NeurIPS 2003, “Training a quantum neural network”),

  • Kapoor, Wiebe & Svore (NeurIPS 2016, “Quantum perceptron models”) give Grover-based training with quadratic speedups.

Questions for authors

Q1. Is there any regime with both a proven mass lower bound and p=o(1)p = o(1) so that the quadratic speedup is realized?

Q2. The proposed encoding scheme might lead to high number of qubits as the parameters are directly discretized and encoded onto qubits. How about encoding the parameters into the superposition coefficients (amplitude encoding) as opposed to the proposed encoding?

3 comments
AuthorsOpenReview ↗

Page 1: On the claim that the start is already -good

We sincerely thank the reviewer.

On the claim that the start is already ε\varepsilon-good

We agree with the reviewer that the strongest constant-mass theorems use a prior aligned with the good set, and that Section 5 treats this alignment as given rather than as a cheap construction. However, MaT does not start from a parameter that is already ε\varepsilon-good, and Section 5 does not say that it does.

Section 5 says that alignment between the prior and the loss geometry is a hypothesis of the sampler, and that obtaining such a prior, for example from a warm start, is a separate problem. That is a statement about a distribution, not about a starting weight. The prior is specified by geometry and by a center. Geometry names the loss-sensitive subspace and the flat subspace. For a linear layer these are the row space of XX and ker⁡(X)\ker(X), and both can be read from XX with no trained θ\theta. A center names a point near one particular solution. A constant mass of 1/41/4 still leaves three quarters of the prior unmarked, so even a fully aligned prior is a search problem: most draws fail the predicate. What MaT then does is turn that mass pp into a certified full-batch parameter with O(1/p)O(1/\sqrt{p}) queries rather than Θ(1/p)\Theta(1/p) rejection draws, with the output law of the prior conditioned on the marked set, as in Theorem 1.

That residual search is not cosmetic. We ran least squares with only the geometric split: the prior is taken from XX, centered at 00, and never sees a trained θ\theta or X+yX^{+}y (N=64N=64, d=256d=256, 20 seeds, 2048 calibration draws, 2048 evaluation draws). Trej=1/p^T_{\mathrm{rej}}=1/\hat p per seed and TQT_Q is the Theorem 1 schedule for success probability 2/32/3. All columns are seed means, and the ratio column is averaged per seed. When ε\varepsilon is a calibration quantile qq of this prior, evaluated on held-out draws, MaT is several times cheaper than random sampling from the same distribution, and the gap widens as the marked set gets rarer:

qqmass p^\hat pTrejT_{\mathrm{rej}}TQT_QTrej/TQT_{\mathrm{rej}}/T_Q
0.010.010.0120.01296.196.18.058.0511.511.5
0.050.050.0510.05120.120.14.054.054.954.95
0.100.100.1010.1019.989.983.003.003.333.33
0.250.250.2500.2504.004.002.002.002.002.00

No known good solution is used in this table. At q=0.01q=0.01 random sampling needs about 9696 full-batch tests. MaT needs about 88. The start is a 00-centered geometric prior, not an ε\varepsilon-good parameter.

AuthorsOpenReview ↗

Page 2: On Proposition 9 and constant mass

On Proposition 9 and constant mass

We agree with the reviewer that Proposition 9 is a comparison with same-prior rejection, and that a constant prior mass makes both costs of constant order. Proposition 9 together with the constant mass p≥1/4p\ge 1/4 of the linear theorems writes TQ=O(1)T_Q=O(1) and Trej=Θ(1)T_{\mathrm{rej}}=\Theta(1). The Grover factor, as a growing function of 1/p1/p, is visible when pp is small.

However, constant-mass theorems are not empty, and they do not claim an unbounded query gap against rejection. They buy a marked set that is large enough to search, against an unaligned uniform prior whose mass is exponentially small. That is the content of Section 5 and of the uniform-prior negative results. Feasibility of the search, and a growing Grover ratio, are two different claims, and we have kept them separate. For a general mass pp, Theorem 1 still gives TQ=O(1/p)T_Q=O(1/\sqrt{p}) against Trej=Θ(1/p)T_{\mathrm{rej}}=\Theta(1/p), together with the full-batch certificate and the conditional output law. Those last two guarantees do not disappear when pp is constant.

The statement that the paper proves no mass bounds in the small-pp regime is not accurate. The softmax theorem gives an explicit decaying packing lower bound on the uniform fraction of the box, and then TQ=O(1/pε)T_Q=O(1/\sqrt{p_{\varepsilon}}) against Θ(1/pε)\Theta(1/p_{\varepsilon}). That bound is small, so Grover still leaves an exponential cost. It is nevertheless a proven mass. Empirically, the 00-centered geometric prior above has p^≈0.012\hat p\approx 0.012 at q=0.01q=0.01, where Trej/TQ≈11.5T_{\mathrm{rej}}/T_Q\approx 11.5. That is a measured mass, small enough that the quadratic factor is visible, and obtained without a trained center.

AuthorsOpenReview ↗

Page 3: Other concerns

On the missing Grover-training references

We agree that Ricks and Ventura (NeurIPS 2003) and Kapoor, Wiebe, and Svore (NeurIPS 2016) use Grover search for training, and we will cite them.

However, those papers and MaT are not the same training problem. Ricks and Ventura Grover-search a uniform superposition of weight bitstrings in a threshold quantum network, marking a chosen classification fraction. Kapoor, Wiebe, and Svore Grover-search a classical perceptron, either for a misclassified example inside the update loop or over version space. MaT searches classical parameters of linear, deep linear, ReLU, and softmax models from a geometric prior, with a full-batch predicate L(θ)≤ε\mathcal{L}(\theta)\le\varepsilon. Theorem 1 then converts the prior mass pp into O(1/p)O(1/\sqrt{p}) queries, a full-batch certificate, and the law of the prior conditioned on the marked set, against same-prior rejection.

Questions

Is there any regime with both a proven mass lower bound and pp small so that the quadratic speedup is realized?

Yes. The softmax packing bound is a proven, decaying pεp_{\varepsilon}, and Theorem 1 then gives TQ=O(1/pε)T_Q=O(1/\sqrt{p_{\varepsilon}}) against Θ(1/pε)\Theta(1/p_{\varepsilon}). The same shape holds for a uniform tube around a linear solution. Those bounds are small, so the remaining cost can still be exponential. The table in the first section is the measured analogue: at q=0.01q=0.01, p^≈0.012\hat p\approx 0.012 and Trej/TQ≈11.5T_{\mathrm{rej}}/T_Q\approx 11.5. Constant mass 1/41/4 is not that regime. There the ratio is a constant, as Proposition 9 states.

How about encoding the parameters into the superposition coefficients (amplitude encoding) as opposed to the proposed encoding?

Section 2 encodes each grid point as a computational-basis label of K=⌈log⁡2M⌉K=\lceil\log_2 M\rceil qubits, so a measurement returns one classical θ\theta after a search over that grid. Amplitude encoding of θ\theta into superposition coefficients can shrink the parameter register, which grows with PP and the bit precision, and we view it as a promising direction for that qubit count, to be taken up as future work. However, a measurement then no longer yields the weight vector, so the procedure is no longer a search over a grid of candidate parameters, which is the encoding Theorem 1 uses.

Reviewer_Xa5COpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes training neural networks using quantum search instead of backpropagation. A quantum computer searches through possible model parameters and increases the chance of finding ones with sufficiently low training loss. The main theoretical result is that this quantum search can require fewer attempts than randomly sampling parameters from the same distribution. Much of the paper studies how to choose distributions where good parameters are reasonably likely to occur.

Critical strengths

The idea is novel and interesting, and the paper contains a substantial amount of theoretical work. I appreciate that the authors discuss important limitations rather than presenting the method as a general replacement for existing training methods. The paper studies several types of neural networks and shows clearly that choosing a good distribution of parameters is important. It also discusses cases where simple or poorly chosen distributions do not work.

Critical weaknesses

My main concern is that the method seems to require substantial knowledge about where good parameters are located before the quantum search begins. Some of the strongest results use distributions constructed close to known good solutions, making it unclear how much of the training problem has actually been avoided. The language-model experiment strengthens this concern because SGD is first used to obtain the solution around which the search distribution is constructed. I am also concerned about the cost of performing the loss evaluation on an actual quantum computer. The clearest speedup is against random sampling from the same distribution, rather than against practical training methods such as SGD, so it is unclear whether the theoretical advantage translates into an advantage for realistic neural-network training.

Questions for authors
  • The paper carefully notes that the loss oracle and prior preparation are not free. Could the authors provide one concrete end-to-end resource estimate for a small example, including data access, forward evaluation, loss calculation, and prior preparation? This would help readers understand where the proposed query advantage is likely to remain meaningful in practice.

  • The paper acknowledges that obtaining an aligned prior is a separate problem and suggests that it might come from a cheap warm start. Could the authors describe the most promising concrete way of producing such a prior without first solving most of the training problem? Even a limited example would make the intended workflow much clearer.

  • The language-model experiment suggests that classical training creates the prior mass later used by MaT. Do the authors therefore see MaT mainly as a replacement for training, as a method for improving or sampling around an existing solution, or as part of a hybrid training pipeline? Clarifying the intended use would help position the contribution.

  • The paper gives a conditional comparison with SGD rather than claiming an unconditional advantage. Could the authors provide a worked example of a realistic regime in which their condition for outperforming SGD is expected to hold, including the cost of constructing the prior and implementing the loss oracle?

  • The strongest constant-mass results rely on substantial alignment with the geometry of good solutions. Which parts of this alignment could realistically be estimated from data or architecture alone, and which parts would require information obtained during training?

  • Could the authors identify the smallest experiment that could demonstrate MaT as an actual training procedure rather than as sampling around a solution found by SGD? This could provide a useful path toward stronger empirical validation, even if the model and dataset are very small.

  • Among the paper’s results, which do the authors consider the strongest evidence that MaT could eventually become useful beyond the query-complexity setting? It would be helpful to hear which theoretical or empirical direction they believe is most promising for closing the gap to practical training.

5 comments
AuthorsOpenReview ↗

Page 1: On the knowledge required before search

We sincerely thank the reviewer.

On the knowledge required before search

We agree with the reviewer that the strongest constant-mass theorems use priors aligned with the good set, and that the language-model probe places the prior at an SGD solution. However, an aligned prior is not a solved training problem, and MaT does not start from a parameter that is already ε\varepsilon-good.

The prior is specified by geometry and by a center. Geometry names the loss-sensitive subspace and the flat subspace. For a linear layer these are the row space of XX and ker⁡(X)\ker(X), and both can be read from XX with no trained θ\theta. A center names a point near one particular solution. The language-model probe uses that center. We have treated it as given in Section 5. A constant mass of 1/41/4 still leaves three quarters of the prior unmarked, so even a fully aligned prior is a search problem: most draws fail the predicate. What MaT then does, and what unstructured random search does not, is turn that mass pp into a certified full-batch parameter with O(1/p)O(1/\sqrt{p}) queries rather than Θ(1/p)\Theta(1/p) rejection draws, and with the output law of the prior conditioned on the marked set rather than a single descent path, as in Theorem 1.

That residual search is the part of training we actually remove, and it is not cosmetic. We ran least squares with only the geometric split: the prior is taken from XX, centered at 00, and never sees a trained θ\theta or X+yX^{+}y (N=64N=64, d=256d=256, 20 seeds, 2048 calibration draws, 2048 evaluation draws). Trej=1/p^T_{\mathrm{rej}}=1/\hat p per seed and TQT_Q is the Theorem 1 schedule for success probability 2/32/3. All columns are seed means, and the ratio column is averaged per seed. When ε\varepsilon is a calibration quantile qq of this prior, evaluated on held-out draws, MaT is several times cheaper than random sampling from the same distribution, and the gap widens as the marked set gets rarer:

qqmass p^\hat pTrejT_{\mathrm{rej}}TQT_QTrej/TQT_{\mathrm{rej}}/T_Q
0.010.010.0120.01296.196.18.058.0511.511.5
0.050.050.0510.05120.120.14.054.054.954.95
0.100.100.1010.1019.989.983.003.003.333.33
0.250.250.2500.2504.004.002.002.002.002.00

No known good solution is used in this table. At q=0.01q=0.01 random sampling needs about 9696 full-batch tests. MaT needs about 88. The same pattern holds at every listed quantile, so the query advantage is not an artefact of a prior parked on an SGD point.

AuthorsOpenReview ↗

Page 2: On the cost of the loss oracle

On the cost of the loss oracle

We agree with the reviewer that evaluating the loss on a quantum computer is a genuine cost, and that this cost is not a single running time. One call to ULU_{\mathcal{L}} occupies a parameter register, reads the training data, evaluates the network, and marks L≤ε\mathcal{L}\le\varepsilon. A coherent circuit for a very large model can be expensive. However, Section 3 fixes the cost accounting, one oracle call as one landscape access with TprepT_{\mathrm{prep}} separate, and the resource appendix prices the register. We split this cost into four parts, so that the part MaT reduces can be seen separately from the part it does not.

The first part is the register. With PP trainable scalars at bb-bit precision the parameter register uses K=PbK=Pb qubits, plus ancillae for the indicator. We have given this count in the resource discussion. MaT does not shrink KK. Amplitude amplification never claims to. The register is the price of holding a superposition over parameters, and we treat it as such.

The second part is data access. The hard oracle of Section 3 is a full-batch predicate, so one call reads the NN training points once. That is heavier than a mini-batch step. It is also the source of the full-batch certificate: the mark L≤ε\mathcal{L}\le\varepsilon is a statement about the whole training set, not about a subsample. We view this as an acceptable trade, because the certificate is one of the guarantees of Theorem 1 rather than an extra afterthought.

The third part is arithmetic: the reversible evaluation of f(θ)f(\theta) and of the indicator. An order-of-magnitude gate estimate for this arithmetic is given in our response to Reviewer 4. Any such circuit must implement the same full-batch map, so the cost is paid per oracle call. Reducing the number of calls therefore reduces how often that circuit is used. Prior preparation is not the oracle, but Theorem 1 invokes the preparation unitary O(TQ)O(T_Q) times, which is why we have kept TprepT_{\mathrm{prep}} separate in Section 3.

The fourth part is how often the oracle is queried. This is the part MaT improves. Theorem 1 uses O(1/p)O(1/\sqrt{p}) calls against Θ(1/p)\Theta(1/p) rejection draws from the same prior and the same predicate. On the geometric 00-centered models of the previous section, at q=0.10q=0.10, this factor is about three:

architectureNNPPTQT_QTrejT_{\mathrm{rej}}
least squares64642562563.03.010.610.6
least squares1281285125123.03.09.719.71
least squares256256102410243.03.010.110.1
deep linear4848307230723.03.010.510.5
ReLU MLP9696256025603.03.010.210.2
tiny attention2424102410243.03.09.839.83

The oracle is therefore costly, and we do not hide that. What we have argued in Section 3, and what the table illustrates, is that MaT does not need a cheaper oracle than classical rejection. It needs fewer calls to the same full-batch oracle, and each accepted call carries the certificate. If a future circuit for ULU_{\mathcal{L}} is so heavy that even three calls are impractical, that limitation applies to any method that uses the same coherent predicate. It does not remove the query reduction relative to rejection, nor the full-batch meaning of the mark.

AuthorsOpenReview ↗

Page 3: On the comparison with SGD

On the comparison with SGD

We agree with the reviewer that the sharpest query bound is against random sampling from the same prior, and that this is not the same as beating SGD. Theorem 1 and the matched baseline in Section 3 are written against rejection sampling with an identical predicate. We have a comparison with SGD in the appendix, and it is conditional: MaT uses fewer landscape accesses only when pp is large relative to the SGD horizon, with the oracle and preparation costs priced separately. The appendix states this as a boundary condition.

However, this is an asymmetric comparison rather than a missing SGD win. SGD and MaT do not optimize the same object, do not read the data in the same way, and do not return the same kind of output. We list four differences that follow from the definitions in Section 2 and Section 3, and that we view as the training-relevant content of the method.

  1. Global ε\varepsilon-optimality, not a mini-batch mark. Mini-batch SGD is driven by a batch loss. Stopping on that batch loss need not mean L≤ε\mathcal{L}\le\varepsilon on the full training set. MaT reports a parameter only when the full-batch predicate accepts. On the same 00-centered priors, at q=0.10q=0.10, we stop mini-batch SGD when a scaled batch loss meets ε\varepsilon (8 starts per seed, 200 steps), and then check the full-batch mark:
architecturemini-batch stop ratemini-batch full-batch certificateMaT full-batch certificate
least squares0.670.670.0440.0441.001.00
deep linear1.001.000.700.701.001.00
ReLU MLP1.001.000.680.681.001.00
tiny attention1.001.000.380.381.001.00

MaT never reports an uncertified point. The mini-batch rule fires on one batch loss, often early, and the stopped run is then measured on the full training set for the first time, so the mark fails on a substantial fraction of stops. This is the certificate gap of uncertified mini-batch stopping (Appendix D.1).

  1. No dependence on data order. A mini-batch trajectory depends on the sequence of batches. The hard oracle of Section 3 is a symmetric function of the NN training points. Permuting the dataset does not change ULU_{\mathcal{L}}, the marked set, or the output law. Order-dependent artefacts of SGD (the path, the spikes along a particular shuffle) are not part of the MaT procedure.

  2. Forward evaluation only. MaT never forms a gradient and never runs a backward pass. One landscape access is one coherent evaluation of the full-batch predicate. Hardware, or a classical simulator, that can support inference of f(θ)f(\theta) and of L\mathcal{L} is enough for the search loop. The extra memory and arithmetic of backpropagation are not required. We have taken this as part of the definition of MaT in Section 3, not as an implementation footnote.

  3. A distribution, not a single trajectory. SGD returns one path and one endpoint. On success, Theorem 1 returns a sample from the prior conditioned on the marked set. At the same q=0.10q=0.10, each seed yields about 200200 distinct accepted draws, and the pairwise RMS distance among them stays next to that of the full prior. Repeated runs of MaT therefore probe the ε\varepsilon-good set rather than repeating one descent.

These four points do not say that MaT uses fewer steps than SGD. They say that the two methods are not competing on the same scoreboard: MaT spends queries to obtain a certified, order-invariant, forward-only sample from a marked distribution. That is the advantage we ask the reviewer to weigh against the fact that the quadratic query bound is leveled at same-prior rejection.

Reviewer_qbwnOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposed measurement as training (MaT), a quantum-sampling-inspired training scheme that does not require backpropagation (BP).

Critical strengths

A new way to do BP-free learning via quantum sampling.

Critical weaknesses

There is no result showing the effectiveness of the proposed method.

Questions for authors

Do you have any results to show the effectiveness of the SOTA BP-based learning?

1 comment

We thank the reviewer for reading the paper and for highlighting the need to make the empirical evidence easier to find. We agree that this evidence should have been more visible in the main text, and the experiments are already in the submission. They are collected in Appendix I (finite-instance audits) and Appendix J (language-model probe). The corresponding figures are Figure 2 (empirical ladder) and Figure 3 (language-model probe). Figure 1 is the appendix map. On the question about standard backpropagation-based training, the probe of Appendix J places draws from the prior alongside SGD, AdamW, RMSProp, Lion, and Muon on the same loss (Figure 3). The source code is linked in the Reproducibility Statement. We will point to it more explicitly. Thanks.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.