Classical Verification of Quantum Learning Advantages with Noises

Dong-Ling Deng; Jiaxi Su; Yinghao Ma

REVIEW 2 major objections 5 minor 72 references

Classical Verification of Quantum Learning Advantages with Noises

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that noisy quantum Fourier sampling still supports efficient agnostic parity learning and its classical verification, because a classical error-rectification algorithm recovers heavy Fourier coefficients from…

desk verdict The bit-flip error-rectification algorithm is a genuine new technique and the proof of Theorem 1 holds up, but the depolarizing-noise extension is miscalculated and Theorem 3's noise condition is mismatched with its proof; the core result is sound and the paper deserves refereeing after fixes. read the letter →

arxiv 2411.09210 v1 pith:T7EW6QRN submitted 2024-11-14 quant-ph cs.LG

Yinghao Ma , Jiaxi Su , Dong-Ling Deng This is my paper · ORCID

classification quant-phcs.LG MSC 68Q1268Q3281P68 PACS 03.67.-a03.67.Lx

keywords classicalverificationofquantumlearningFouriersamplingerrorrectificationagnosticparityheavycoefficientsnoisyintermediate-scale(NISQ)devicesinteractiveproofsystemsexampleoracle

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Classical verification of quantum learning has been studied in idealized noiseless settings, and this paper asks whether the advantage survives on the noisy machines available now. It claims that for quantum Fourier sampling under independent bit-flip noise at rate $\eta$, a classical error-rectification algorithm can recover every heavy Fourier coefficient of the target function — every frequency component contributing probability mass at least $\theta$ — using only $k = O(\log(n/\delta)/\theta^2)$ noisy samples, provided $\eta \le \theta/10$. Once those heavy coefficients are restored, the agnostic parity learning task of finding the parity function that best matches the target becomes efficient, and a classical verifier with access to a random example oracle can certify the noisy quantum prover's answer in one round of communication whenever the target function has a gap in its Fourier spectrum. The practical payoff is that delegation of learning to untrusted, noisy quantum cloud servers could be made reliable without full quantum error correction.

What carries the argument

The load-bearing object is the noisy quantum Fourier sampling distribution $p_\eta(s)$, the convolution of the ideal squared Fourier spectrum $p_0(s)=|\hat{g}(s)|^2$ with a bit-flip channel. The mechanism that carries the argument is the nearest-neighbor matching step in the recursive error-rectification algorithm: at each prefix length $m$, every noisy sample is assigned to the closest candidate prefix in Hamming distance, and the algorithm keeps the $2/\theta$ prefixes with the largest empirical frequency. Lemma S3 bounds the probability of a mismatch by the noise rate $\eta$, so a genuinely heavy coefficient is matched correctly with probability at least $3/5$; this is what converts a deconvolution problem into a heavy-hitter search with logarithmic sample complexity. In the verification protocol, the equivalent load-bearing test is the sum-of-squares check $\sum_{s\in L}\tilde{g}(s)^2 \ge 1-\tau^2/2$, which separates the case where $L$ contains the full support of $\hat{g}$ from the case where it misses at least one nonzero coefficient.

What would settle it

Run Algorithm S1 on a known function with a controlled Fourier spectrum, for example one parity with $\hat{g}(s^*)=0.6$ and several coefficients just below the threshold, under bit-flip noise at rate $\eta=0.01$ with $\theta=0.1$, and check whether the true heavy set is contained in $L$ using $k=O(\log(n/\delta)/\theta^2)$ samples; observing a miss at constant probability, or requiring $k$ to grow with $n$ beyond logarithmic, would contradict Theorem 1.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that measurement noise in quantum Fourier sampling is not a quantum obstacle to be corrected by quantum error correction, but a classical deconvolution problem. The noisy distribution is the ideal distribution convolved with an independent bit-flip channel, $p_\eta(s) = \sum_{s'} \eta^{d_H(s,s')}(1-\eta)^{n-d_H(s,s')}p_0(s')$, and Theorem 1 gives a recursive list-maintenance algorithm that, for $\eta \le \theta/10$, returns a set $L$ of size at most $\lfloor 2/\theta\rfloor$ containing every $s$ with $p_0(s)\ge\theta$, using $k=O(\log(n/\delta)/\theta^2)$ noisy samples with probability at least $1-\delta$. The same algorithm feeds Corollary 1, which produces an $\ell^\infty$-accurate estimate of the Fourier coefficients of the target function, and Theorem 2, which solves 1-agnostic parity learning with error $\varepsilon$ under noise rate $\eta\le\varepsilon^2/10$. Theorem 3 then provides a one-round interactive proof in which a classical verifier checks the prover's returned Fourier set and accepts only if the sum of squared estimated coefficients is close to $1$, a test that is complete and sound under the promise $F_\tau$ that no nonzero Fourier coefficient is smaller than $\tau$.

Load-bearing premise

The load-bearing premise is the promise that the target function's frequency content is gapped: every nonzero Fourier coefficient has magnitude at least $\tau$, and the device noise stays below $\tau^2/10$; without that gap, a returned list that misses some small Fourier mass can still pass the verifier's check and lead to a suboptimal parity.

Editorial extensions

If this is right

Noisy quantum Fourier sampling remains useful for learning: heavy Fourier coefficients of the target function can be restored from logarithmically many noisy samples, with no additional qubits or gates and no quantum error correction.
The error-rectification step plus classical random examples yields an $\ell^\infty$ approximation to the full Fourier spectrum, which directly gives a near-optimal parity hypothesis for agnostic parity learning.
A classical verifier can interact once with an untrusted noisy quantum prover and either accept a near-optimal parity or reject, with soundness error at most $\delta$, whenever the target function has no nonzero Fourier coefficient below $\tau$ and the noise rate is below $\tau^2/10$.
The same rectification argument extends to depolarizing noise and, more generally, to any single-qubit error that acts as an effective measurement-outcome flip, so the result is not tied to the specific bit-flip model.
Theorem 1's algorithm is stated as a general classical routine for distributions corrupted by bounded per-bit flip noise, so it can be reused outside QFS whenever the same convolution structure appears.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Editorial inference: the recursive matching routine is really a classical heavy-hitter algorithm for distributions under bit-flip noise, so it should apply to any learning problem whose oracles produce Fourier-sparse samples corrupted by bounded noise; label-noise robust sparse Fourier recovery is a natural neighbour.
Editorial inference: the spectral-gap promise $F_\tau$ is the practical bottleneck: if real target functions have many tiny nonzero Fourier coefficients, the verifier's sum-of-squares test either rejects or forces $\tau$ small, which in turn forces the device noise $\eta$ below $\tau^2/10$; this is a testable restriction on which real datasets the protocol can certify.
Editorial inference: one direct experimental check would be to run QFS on a known Fourier-sparse function, inject controlled bit flips at various rates, and compare the recovered heavy set with the prediction of Theorem 1; current cloud quantum platforms should be able to do this with a handful of qubits.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the short version. The bit-flip error-rectification algorithm (Algorithm S1) is the real contribution, and I believe the proof of Theorem 1 is sound: the recursive matching argument, Lemma S3's bound, and the union bound over n steps all line up. That is new relative to Caro et al., which assumed noiseless quantum examples. The Corollary 1 and Theorem 2 consequences follow cleanly. The verification protocol is a fairly direct adaptation of Caro et al. with this added rectification step; the completeness/soundness argument is standard and acceptable.

The soft spots are all in the noise modeling and the theorem statements. First, the depolarizing noise extension in Eqs. (5)-(6) is wrong. For Λ_dep(ρ) = (1-η)ρ + η I/2, a measurement outcome in the computational basis flips with probability η/2, not η - η^2/2. So the claimed equivalence to the bit-flip model with η_eff = η - η^2/2 is not what the circuit produces. The correct mapping is η_eff = η/2 (up to the conditioning on the y-qubit). This means the paper's advertised result for depolarizing channels is unsupported as written. It is patchable, but it is a real error, not a cosmetic one, because depolarizing noise is one of the headline models in the abstract and in Fig. 1(c).

Second, Theorem 3's completeness condition says 'noise strength below O(ε^2)' but the proof requires η ≤ τ^2/10, where τ is the spectral gap. That's a different parameter. The statement should be O(τ^2), or the relationship between ε and τ should be made explicit. As written, the mismatch would confuse readers.

Third, the abstract oversells the practicality. The real condition is η ≤ O(θ) for finding heavy coefficients and η ≤ O(ε^2) for the parity learning guarantee. That means the tolerated noise shrinks quadratically as the target accuracy improves. For ε = 0.01 you need η ≤ 10^-5, which is not 'practical constant-level noise' in the NISQ sense. The constant is there, but small.

Finally, the verification protocol relies on the spectral gap promise F_τ: no nonzero Fourier coefficient below τ. It is explicitly stated in Theorem 3, so I don't call it a hidden flaw, but the abstract's 'sparse Fourier coefficients' is weaker and understates the assumption.

Overall: the core bit-flip result is solid and worth publishing after these fixes. The paper deserves a serious referee, not a desk reject. I'd send it to review with a note to check the depolarizing mapping and align Theorem 3's noise condition with its proof. If the authors fix those, the paper is a reasonable contribution to the delegated quantum learning literature.

Referee Report

2 major / 5 minor

Summary. The paper studies whether classical verification of quantum learning can be made robust to noise in the quantum prover's hardware. It focuses on quantum Fourier sampling (QFS) and agnostic parity learning. The authors propose a classical error-rectification algorithm that, from O(log(n/δ)/θ^2) samples of a bit-flip-noisy QFS distribution, outputs a small set L containing all heavy Fourier coefficients (Theorem 1). They use this to estimate the Fourier coefficients (Corollary 1), to solve 1-agnostic parity learning with a noisy quantum prover and classical random examples (Theorem 2), and to give a one-round interactive proof system with a classical verifier and a noisy quantum prover under a spectral-gap promise on the target function (Theorem 3). The technical core is a recursive nearest-neighbor matching argument in SM Sec. II.

Significance. The bit-flip part of the paper is a solid and self-contained contribution: the matching lemma (Lemma S3) is correct, the recursion maintains the invariant H_m ⊆ L_m, and the sample complexity is explicit and logarithmic in n. If the advertised depolarizing-noise extension is repaired, the results would be a meaningful step toward practical delegation of quantum learning to NISQ-era servers, and the verification protocol naturally extends the noise-free framework of Caro et al. [20]. The soundness of the verification step is information-theoretic and does not depend on computational assumptions. However, the paper currently overstates its generality: the depolarizing-noise calculation contains a mathematical error, and the completeness statement of Theorem 3 does not match its proof.

major comments (2)

[QFS with noises, Eqs. (5)-(6)] The claimed reduction of depolarizing noise to bit-flip noise is not correct. For a single qubit, Λ_dep(ρ) = (1−η_dep)ρ + η_dep I/2 maps a computational-basis outcome b to b with probability 1−η_dep/2 and to 1−b with probability η_dep/2. Conditioning on the y-qubit outcome being 1 gives p_dep(s) = Σ_{s'} q^{d_H(s,s')}(1−q)^{n−d_H(s,s')}[(1−q)p0(s') + q δ_{s',0}] with q = η_dep/2. This is of the same form as Eq. (5), but with q, not with η_eff = η_dep − η_dep^2/2 as defined in Eq. (6). The factor (1−η_dep)^2 used for the 'original result' is therefore unjustified. Since the abstract and Fig. 1(c) advertise depolarizing noise as a main model, this error is load-bearing; the bit-flip Theorem 1 is unaffected, and the depolarizing claim appears patchable by replacing η_eff with q, but as written the extension is not established.
[Theorem 3, Completeness bullet] The completeness condition as stated in the main text, 'If the noise strength of P is below O(ε^2)', does not match the proof. The proof in SM Theorem S5 requires η ≤ τ^2/10, where τ is the spectral-gap parameter from Definition S3; Step 1 applies Theorem S1 with θ = τ^2. Since τ can be much smaller than ε, the stated O(ε^2) condition is neither the one used nor sufficient for the protocol as proved. The theorem should state the noise condition in terms of τ (e.g., η ≤ τ^2/10) or impose an explicit relation such as τ ≥ cε.

minor comments (5)

[SM Sec. V, Eq. (S26)] The two bad events in the soundness proof, H⊆L with Step 3 failure and H⊄L with L passing validation, are disjoint, so their probabilities add; the soundness error is at most 2δ/3, not δ/3. The final soundness bound δ still holds because 2δ/3 < δ, so this does not affect the theorem.
[Theorem 3, Step 1] Step 1 should explicitly state that the verifier runs Algorithm S1 on the samples received from the prover; this is what enforces the size bound |L| ≤ 2/τ^2 and keeps the verifier efficient against arbitrary provers. If instead the prover is expected to supply L, a verifier-side size check is needed.
[Fig. 1(c) caption] The caption describing the depolarizing channel has the probabilities reversed; it should say that the channel applies ρ with probability 1−η_dep and I/2 with probability η_dep.
[Abstract and Discussion] There are several typos: 'whether existed' should be 'whether existing' in the abstract; 'the the quantum Fourier sampling' should be 'the quantum Fourier sampling'; and 'Ryderger atoms' should be 'Rydberg atoms' in the Discussion.
[SM Theorem S3, proof] The sentence 'with probability at least 1−δ/2×2 = 1−δ' is not a correct composition of the two success probabilities; the intended bound is (1−δ/2)^2 ≥ 1−δ, which is what the argument needs.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main results are derived from explicit concentration bounds, Höffding estimates, and a parameter-free sum-of-squares test; the depolarizing-noise extension contains a non-circular calculation error.

full rationale

I walked the claimed derivation chain and found no load-bearing circular step. Theorem 1's error-rectification algorithm is proved directly from the noisy distribution pη(s) defined in Eq. (S4), the matching-error bound in Lemma S3, and an ℓ∞ concentration bound (Lemma S1, cited to Caro et al. but external and standard; not an author self-citation). The returned set L is not defined to be the heavy set; the induction Hm ⊆ Lm is established by showing that every heavy sm has empirical frequency at least θ/2, so the output is derived rather than assumed. Corollary 1 and Theorem 2 combine this with Höffding estimates of Fourier coefficients from independent noiseless classical random examples; the loss-to-Fourier identity is a standard equality, not a redefinition. Theorem 3's verification protocol is sound under the explicit promise Fτ defined in Definition S3, and its Step-2 sum-of-squares test uses Parseval's identity and the spectral-gap promise to certify H ⊆ L; the protocol is adapted from Ref. [20], which is not a self-citation. No fitted parameter is renamed as a prediction, and no uniqueness theorem from the authors' prior work is imported. Two non-circular concerns should be flagged, as the reviewing rule requires, though they do not affect the circularity score: (i) the depolarizing-noise reduction in Eqs. (5)-(6) states an effective flip rate ηeff = ηdep − ηdep²/2, but the circuit in Fig. 1(c) gives per-qubit effective flip rate q = ηdep/2, with p0,eff = (1−q)p0 + qδ0 (up to total probability), because the I/2 component produces a random bit; the claimed factor (1−ηdep)² is unexplained. This affects the depolarizing extension but not the bit-flip Theorem 1. (ii) In Theorem 3 the completeness statement says noise strength below O(ε²), whereas the proof and supplementary theorem use η ≤ τ²/10; these thresholds are not matched. Both are correctness gaps, not circular reductions, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard concentration bounds, Parseval's identity, the QFS sampling model, and a specific bit-flip noise model. The only questionable axiom is the depolarizing-noise equivalence, whose derivation appears wrong. No free parameters are fitted; all quantities are proven inputs. No new entities are invented.

assumptions (5)

standard math Hoeffding's inequality and standard concentration bounds suffice to estimate empirical distributions and Fourier coefficients within the claimed sample counts.
Used in Lemma S1 and Lemma S2 to convert raw samples into ℓ∞-accurate estimates with high probability.
standard math Parseval's identity Σ_s ĝ(s)^2 = 1 for g(x) = 1-2f(x), a boolean function with values ±1.
Used in the validation step of Theorem 3 to detect missing Fourier coefficients by testing whether Σ_{s∈L} ĝ(s)^2 is close to 1.
domain assumption The noise-free QFS circuit with the quantum example oracle samples the first n qubits from p_0(s) = |ĝ(s)|^2 conditioned on the last qubit being 1.
This is the standard Bernstein-Vazirani/QFS result, cited as Ref. [26]; the whole paper builds on this sampling model.
domain assumption Independent bit-flip measurement noise on each of the first n qubits, with the last qubit unaffected, produces the distribution p_η(s) = Σ_{s'} η^{dH}(1-η)^{n-dH} p_0(s').
This defines the noise model in Fig. 1(b) and Eq. (3); Theorem 1's algorithm is tailored to this convolution form.
ad hoc to paper Depolarizing noise on each qubit is equivalent to a measurement-outcome flip error with a single effective probability η_eff.
This is claimed after Eq. (5)-(6) but the stated derivation is incorrect: after one depolarizing channel the original outcome survives with probability 1-η_dep/2, not (1-η_dep)^2. The equivalence is used to extend Theorems 1 and 2 to the depolarizing model.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Classical Verification of Quantum Learning Advantages with Noises." pith.science (2026). https://pith.science/paper/T7EW6QRN

@misc{pith2026241109210,
  author       = {Pith},
  title        = {Pith review of: Classical Verification of Quantum Learning Advantages with Noises},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T7EW6QRN}},
  note         = {Machine review of arXiv:2411.09210}
}

read the original abstract

Classical verification of quantum learning allows classical clients to reliably leverage quantum computing advantages by interacting with untrusted quantum servers. Yet, current quantum devices available in practice suffers from a variety of noises and whether existed classical verification protocols carry over to noisy scenarios remains unclear. Here, we propose an efficient classical error rectification algorithm to reconstruct the noise-free results given by the quantum Fourier sampling circuit with practical constant-level noises. In particular, we prove that the error rectification algorithm can restore the heavy Fourier coefficients by using a small number of noisy samples that scales logarithmically with the problem size. We apply this algorithm to the agnostic parity learning task with uniform input marginal and prove that this task can be accomplished in an efficient way on noisy quantum devices with our algorithm. In addition, we prove that a classical client with access to the random example oracle can verify the agnostic parity learning results from the noisy quantum prover in an efficient way, under the condition that the Fourier coefficients are sparse. Our results demonstrate the feasibility of classical verification of quantum learning advantages with noises, which provide a valuable guide for both theoretical studies and practical applications with current noisy intermediate scale quantum devices.

Figures

Figures reproduced from arXiv: 2411.09210 by the authors.

**Figure 1.** FIG. 1: (a) A sketch of classical verification of quantum learning with noises. We focus our discussion on the scenario where a [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

72 extracted references · 55 canonical work pages

[1]

Biamonte, P

J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature 549, 195 (2017)

2017
[2]

Therefore by using QFS, we can sample from probability distribution p0 with constant probability

Conditioned on y = 1 , the probability distri- bution of the first n qubit is p0(s) = |ˆg(s)|2, whereas when y = 0 all the first n qubits collapse to state |0⟩. Therefore by using QFS, we can sample from probability distribution p0 with constant probability. Each execution of the QFS cir- cuit requires one copy of the quantum example|ψf⟩ andO(n) single-qu...

work page
[3]

Dunjko and H

V . Dunjko and H. J. Briegel, Machine learning & artificial in- telligence in the quantum domain: a review of recent progress, Rep. Prog. Phys. 81, 074001 (2018)

work page 2018
[4]

(4) By definition||˜g||0≤| L′|≤ 2 ε2

Let T′ be the list of classical random examples, define: ˜g(s) =    1 k′ ∑ x∈T ′ g(x)χs(x), s∈L 0, s / ∈L. (4) By definition||˜g||0≤| L′|≤ 2 ε2 . For s /∈ L,|ˆg(s)−˜g(s)| = |ˆg(s)| ≤ ε. For s ∈ L, by the Hoeffding inequality: 4 Pr(|ˆg(s)−˜g(s)| > ε) ≤ 2e− 1 2k′ε2 . Let 2e− 1 2k′ε2 ≤ ε2δ 4 , so k′ = O ( log(1/εδ) ε2 ) , then the success probability obey...

work page
[5]

This leads to the conclusion that H ⊆ L

As a result, for sm ∈ Hm with pm(sm)≥ θ, with high probability its empirical distribution will be no less than 1 2θ, and sm will be contained in Lm. This leads to the conclusion that H ⊆ L. After some tech- nique calculations as shown in the Supplementary Materials Sec. II, we arrive at the conclusion that the success probabil- ity Pr(H ⊆ L)≥ 1−2ne−kθ2/20...

work page
[6]

Das Sarma, D.-L

S. Das Sarma, D.-L. Deng, and L.-M. Duan, Machine learning meets quantum physics, Phys. Today 72, 48 (2019)

work page 2019
[7]

Gao, Z.-Y

X. Gao, Z.-Y . Zhang, and L.-M. Duan, A quantum machine learning algorithm based on generative models, Sci. Adv. 4, eaat9004 (2018)

work page 2018
[8]

Cerezo, G

M. Cerezo, G. Verdon, H.-Y . Huang, L. Cincio, and P. J. Coles, Challenges and opportunities in quantum machine learning, Nat. Comput. Sci. 2, 567 (2022)

2022

Show all 72 references

[9]

Lloyd, M

S. Lloyd, M. Mohseni, and P. Rebentrost, Quantum principal component analysis, Nat. Phys. 10, 631 (2014)

2014
[10]

Rebentrost, M

P. Rebentrost, M. Mohseni, and S. Lloyd, Quantum support vec- tor machine for big data classification, Phys. Rev. Lett. 113, 130503 (2014)

2014
[11]

A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Phys. Rev. Lett. 103, 150502 (2009)

2009
[12]

Y . Liu, S. Arunachalam, and K. Temme, A rigorous and robust quantum speed-up in supervised machine learning, Nat. Phys. 17, 1013 (2021)

2021
[13]

L. K. Grover, A fast quantum mechanical algorithm for database search, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing(1996) pp. 212–219

1996
[14]

Brassard, P

G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum am- 6 plitude amplification and estimation, Contemp. Math. 305, 53 (2002)

2002
[15]

N. H. Bshouty and J. C. Jackson, Learning DNF over the Uni- form Distribution Using a Quantum Example Oracle, SIAM J. Comput. 28, 1136 (1998)

1998
[16]

L. G. Valiant, A theory of the learnable, Commun. ACM 27, 1134 (1984)

1984
[17]

Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Inf

D. Haussler, Decision theoretic generalizations of the PAC model for neural net and other learning applications, Inf. Com- put. 100, 78 (1992)

1992
[18]

M. J. Kearns, R. E. Schapire, and L. M. Sellie, Toward efficient agnostic learning, Mach. Learn. 17, 115 (1994)

1994
[19]

Arunachalam, S

S. Arunachalam, S. Chakraborty, T. Lee, M. Paraashar, and R. de Wolf, Two new results about quantum exact learning, Quantum 5, 587 (2021)

2021
[21]

Atıcı and R

A. Atıcı and R. A. Servedio, Quantum algorithms for learning and testing juntas, Quantum Inf. Process. 6, 323 (2007)

2007
[22]

R. A. Servedio and S. J. Gortler, Equivalences and Separations Between Quantum and Classical Learnability, SIAM J. Com- put. 33, 1067 (2004)

2004
[23]

Montanaro, The quantum query complexity of learning mul- tilinear polynomials, Inf

A. Montanaro, The quantum query complexity of learning mul- tilinear polynomials, Inf. Process. Lett. 112, 438 (2012)

2012
[24]

M. C. Caro, M. Hinsche, M. Ioannou, A. Nietner, and R. Sweke, Classical Verification of Quantum Learning, in 15th Innovations in Theoretical Computer Science Conference (ITCS 2024), Leibniz International Proceedings in Informatics (LIPIcs), V ol. 287 (Schloss Dagstuhl – Leibni...

2024
[25]

Arunachalam and R

S. Arunachalam and R. De Wolf, Optimal quantum sample complexity of learning algorithms, J. Mach. Learn. Res. 19, 1 (2018)

2018
[26]

Atici and R

A. Atici and R. A. Servedio, Improved Bounds on Quantum Learning Algorithms, Quantum Inf. Process. 4, 355 (2005)

2005
[27]

Zhang, An improved lower bound on query complexity for quantum PAC learning, Inf

C. Zhang, An improved lower bound on query complexity for quantum PAC learning, Inf. Process. Lett.111, 40 (2010)

2010
[28]

A. W. Cross, G. Smith, and J. A. Smolin, Quantum learning robust against noise, Phys. Rev. A 92, 012327 (2015)

2015
[29]

A. B. Grilo, I. Kerenidis, and T. Zijlstra, Learning-with-errors problem is easy with quantum samples, Phys. Rev. A 99, 032314 (2019)

2019
[30]

Bernstein and U

E. Bernstein and U. Vazirani, Quantum complexity theory, in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing - STOC ’93 , STOC ’93 (ACM Press,
[31]

P. W. Shor, Scheme for reducing decoherence in quantum com- puter memory, Phys. Rev. A52, R2493 (1995)

1995
[32]

A. M. Steane, Simple quantum error-correcting codes, Phys. Rev. A 54, 4741 (1996)

1996
[33]

Knill, R

E. Knill, R. Laflamme, and W. H. Zurek, Resilient quantum computation, Science 279, 342 (1998)

1998
[34]

B. M. Terhal, Quantum error correction for quantum memories, Rev. Mod. Phys. 87, 307 (2015)

2015
[35]

Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018)

J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018)

2018
[36]

https://www.ibm.com/quantum/technology (2024)

2024
[37]

Wurtz, A

J. Wurtz, A. Bylinskii, B. Braverman, J. Amato-Grill, S. H. Cantu, F. Huber, A. Lukin, F. Liu, P. Weinberg, J. Long, S.-T. Wang, N. Gemelke, and A. Keesling, Aquila: Quera’s 256-qubit neutral-atom quantum computer (2023), arXiv:2306.11727 [quant-ph]

2023 arXiv
[38]

https://www.qm-ware.com/product/qmware-cloud-platform/ (2024)

2024
[39]

https://quafu.baqis.ac.cn/ (2024)

2024
[40]

Gheorghiu, T

A. Gheorghiu, T. Kapourniotis, and E. Kashefi, Verification of Quantum Computation: An Overview of Existing Approaches, Theory Comput. Syst. 63, 715 (2018)

2018
[41]

Mahadev, Classical Verification of Quantum Computations, in 2018 IEEE 59th Annual Symposium on Foundations of Com- puter Science (FOCS) (IEEE, 2018) pp

U. Mahadev, Classical Verification of Quantum Computations, in 2018 IEEE 59th Annual Symposium on Foundations of Com- puter Science (FOCS) (IEEE, 2018) pp. 259–267

2018
[42]

J. F. Fitzsimons, Private quantum computation: an introduction to blind quantum computing and related protocols, npj Quan- tum Inf. 3, 23 (2017)

2017
[43]

Broadbent, J

A. Broadbent, J. Fitzsimons, and E. Kashefi, Universal Blind Quantum Computation, in 2009 50th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2009) pp. 517– 526

2009
[44]

Goldwasser, S

S. Goldwasser, S. Micali, and C. Rackoff, The knowledge com- plexity of interactive proof-systems, Providing Sound Founda- tions for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali , 203 (2019)

2019
[45]

Shamir, IP = PSPACE, J

A. Shamir, IP = PSPACE, J. ACM 39, 869 (1992)

1992
[46]

Goldwasser, G

S. Goldwasser, G. N. Rothblum, J. Shafer, and A. Yehudayoff, Interactive Proofs for Verifying Machine Learning, in 12th In- novations in Theoretical Computer Science Conference (ITCS
[47]

V . Lyubashevsky, The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem, in International Workshop on Approximation Algorithms for Com- binatorial Optimization (Springer, 2005) pp. 378–389

2005
[48]

M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge university press, 2010)

2010
[49]

Angluin, Queries and concept learning, Mach

D. Angluin, Queries and concept learning, Mach. Learn. 2, 319 (1988)

1988
[50]

Goldreich and L

O. Goldreich and L. A. Levin, A hard-core predicate for all one- way functions, in Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing , STOC ’89 (Association for Computing Machinery, New York, NY , USA, 1989) pp. 25– 32

1989
[51]

Kushilevitz and Y

E. Kushilevitz and Y . Mansour, Learning decision trees using the Fourier spectrum, in Proceedings of the Twenty-Third An- nual ACM Symposium on Theory of Computing , STOC ’91 (Association for Computing Machinery, New York, NY , USA,
[52]

S. Barz, E. Kashefi, A. Broadbent, J. F. Fitzsimons, A. Zeilinger, and P. Walther, Demonstration of blind quantum computing, Science 335, 303 (2012)

2012
[53]

Regev, On lattices, learning with errors, random linear codes, and cryptography, J

O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM 56, 1 (2009)

2009
[54]

Bengio, I

Y . Bengio, I. Goodfellow, and A. Courville, Deep learning , V ol. 1 (MIT press Cambridge, MA, USA, 2017)

2017
[55]

Huang, R

H.-Y . Huang, R. Kueng, and J. Preskill, Information-theoretic bounds on quantum advantage in machine learning, Phys. Rev. Lett. 126, 190505 (2021)

2021
[56]

S. Chen, J. Cotler, H.-Y . Huang, and J. Li, Exponential separa- tions between learning with and without quantum memory, in 2021 IEEE 62nd Annual Symposium on Foundations of Com- puter Science (FOCS) (IEEE, 2022) pp. 574–585

2021
[57]

Arute, K

F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al. , Quantum supremacy using a programmable supercon- ducting processor, Nature 574, 505 (2019)

2019
[58]

C. D. Bruzewicz, J. Chiaverini, R. McConnell, and J. M. Sage, Trapped-ion quantum computing: Progress and challenges, Appl. Phys. Rev. 6 (2019)

2019
[59]

Monroe, W

C. Monroe, W. C. Campbell, L.-M. Duan, Z.-X. Gong, A. V . Gorshkov, P. W. Hess, R. Islam, K. Kim, N. M. Linke, G. Pagano, P. Richerme, C. Senko, and N. Y . Yao, Pro- grammable quantum simulations of spin systems with trapped 7 ions, Rev. Mod. Phys. 93, 025001 (2021)

2021
[60]

Georgescu, Trapped ion quantum computing turns 25, Nat

I. Georgescu, Trapped ion quantum computing turns 25, Nat. Rev. Phys. 2, 278 (2020)

2020
[61]

Kjaergaard, M

M. Kjaergaard, M. E. Schwartz, J. Braum ¨uller, P. Krantz, J. I.- J. Wang, S. Gustavsson, and W. D. Oliver, Superconducting qubits: Current state of play, Annu. Rev. Condens. Matter Phys. 11, 369 (2020)

2020
[63]

W. Ren, W. Li, S. Xu, K. Wang, W. Jiang, F. Jin, X. Zhu, J. Chen, Z. Song, P. Zhang, et al., Experimental quantum ad- versarial learning with programmable superconducting qubits, Nat. Comput. Sci. 2, 711 (2022)

2022
[64]

Saffman, T

M. Saffman, T. G. Walker, and K. Mølmer, Quantum informa- tion with rydberg atoms, Rev. Mod. Phys. 82, 2313 (2010)

2010
[65]

Bluvstein, S

D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, et al., Logical quantum processor based on reconfigurable atom arrays, Nature 626, 58 (2024). Supplementary Materials for: Classical Verification of Quantum...

2024 arXiv
[66]

(S6) 3 Denotepmatch m (sm) to be the probability distribution of the matching result of a noisy sample, then for sm∈ Hm, we have pmatch m (sm)≥ Pr(sm→sm)pm(sm)≥ 3 5θ. Consider the empirical distribution pemp m (sm) we get in line 11 of the algorithm, by lemma S1, with probabil...
[67]

Thus, we can obtain the same result as in Theorem S1

(S16) The remainder of the proof follows the same steps as in Theorem S1. Thus, we can obtain the same result as in Theorem S1. III. PROOF OF COROLLARY 1 With the resultL from Algorithm S1, we can use the method in Lemma S2 to estimate the Fourier coefficients of the elements ...
[68]

Then use the algorithm in Lemma S2 to produce an estimation ˜g(s) of ˆg(s) for s∈ L such that∀s∈ S,|ˆg(s)− ˜g(s)|≤ ε with success probability at least 1− δ
[69]

We define ˜g(s) = 0 for s /∈ L, thus||˜g||0≤| L|≤ 2 ε2

By Theorem S1 and Lemma S2, these require k = O ( log(n/δ) ε4 ) samples from a noisy QFS circuit and k′ = O ( log(1/εδ) ε2 ) classical random examples respectively. We define ˜g(s) = 0 for s /∈ L, thus||˜g||0≤| L|≤ 2 ε2 . To show ||ˆg− ˜g||∞≤ ε, notice that for s /∈ L,|ˆg(s)− ...
[70]

Based on the algorithm in Theorem S1, the verifier V asks the proverP to providek =O ( log(n/δ) τ 4 ) samples from noisy QFS circuit, and produce a set L containingH ={s∈X n :|ˆg(s)|≥ τ} ={s∈X n :|ˆg(s)|̸ = 0} with probability at least 1− δ 3, using samples fromP andk′ 1 =O ( ...
[71]

If the sum ˜S = ∑ s∈L(˜g(s))2≥ 1− 1 2τ 2, the verifier chooses to trustH⊆L, otherwise it rejects the interaction

The verifier V checks the reliability ofL by using the algorithm in Lemma S2 to obtain a 1 8τ 3-approximation ˜g(s) of ˆg(s) fors∈ L with probability 1− δ 3, which requires k′ 2 = O ( log(1/τδ ) τ 6 ) samples from random example oracle. If the sum ˜S = ∑ s∈L(˜g(s))2≥ 1− 1 2τ 2...
[72]

ThenV choosess0∈ arg maxs∈L ˜g(s) and outputs h(x) = s0·x as learning result

The verifierV again uses the algorithm in Lemma S2 to obtain anε-approximation ˜g′(s) of ˆg(s) fors∈L with probability 1−δ 3 usingk′ 3 =O ( log(1/τδ ) ε2 ) samples from random example oracle. ThenV choosess0∈ arg maxs∈L ˜g(s) and outputs h(x) = s0·x as learning result. For Ste...
[73]

M. C. Caro, M. Hinsche, M. Ioannou, A. Nietner, and R. Sweke, Classical Verification of Quantum Learning (2023)

2023
[2021]

(Schloss Dagstuhl – Leibniz-Zentrum f ¨ur Informatik, 2021)

2021

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Biamonte, P

J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, Quantum machine learning, Nature 549, 195 (2017)

2017

[2] [2]

Therefore by using QFS, we can sample from probability distribution p0 with constant probability

Conditioned on y = 1 , the probability distri- bution of the first n qubit is p0(s) = |ˆg(s)|2, whereas when y = 0 all the first n qubits collapse to state |0⟩. Therefore by using QFS, we can sample from probability distribution p0 with constant probability. Each execution of the QFS cir- cuit requires one copy of the quantum example|ψf⟩ andO(n) single-qu...

work page

[3] [3]

Dunjko and H

V . Dunjko and H. J. Briegel, Machine learning & artificial in- telligence in the quantum domain: a review of recent progress, Rep. Prog. Phys. 81, 074001 (2018)

work page 2018

[4] [4]

(4) By definition||˜g||0≤| L′|≤ 2 ε2

Let T′ be the list of classical random examples, define: ˜g(s) =    1 k′ ∑ x∈T ′ g(x)χs(x), s∈L 0, s / ∈L. (4) By definition||˜g||0≤| L′|≤ 2 ε2 . For s /∈ L,|ˆg(s)−˜g(s)| = |ˆg(s)| ≤ ε. For s ∈ L, by the Hoeffding inequality: 4 Pr(|ˆg(s)−˜g(s)| > ε) ≤ 2e− 1 2k′ε2 . Let 2e− 1 2k′ε2 ≤ ε2δ 4 , so k′ = O ( log(1/εδ) ε2 ) , then the success probability obey...

work page

[5] [5]

This leads to the conclusion that H ⊆ L

As a result, for sm ∈ Hm with pm(sm)≥ θ, with high probability its empirical distribution will be no less than 1 2θ, and sm will be contained in Lm. This leads to the conclusion that H ⊆ L. After some tech- nique calculations as shown in the Supplementary Materials Sec. II, we arrive at the conclusion that the success probabil- ity Pr(H ⊆ L)≥ 1−2ne−kθ2/20...

work page

[6] [6]

Das Sarma, D.-L

S. Das Sarma, D.-L. Deng, and L.-M. Duan, Machine learning meets quantum physics, Phys. Today 72, 48 (2019)

work page 2019

[7] [7]

Gao, Z.-Y

X. Gao, Z.-Y . Zhang, and L.-M. Duan, A quantum machine learning algorithm based on generative models, Sci. Adv. 4, eaat9004 (2018)

work page 2018

[8] [8]

Cerezo, G

M. Cerezo, G. Verdon, H.-Y . Huang, L. Cincio, and P. J. Coles, Challenges and opportunities in quantum machine learning, Nat. Comput. Sci. 2, 567 (2022)

2022