Fast Quantum Algorithms for Learning Linear Threshold Functions

Aleksandrs Krivcenko; Ronald de Wolf; Tuyen Nguyen

REVIEW

Fast Quantum Algorithms for Learning Linear Threshold Functions

Aleksandrs Krivcenko, Tuyen Nguyen, Ronald de Wolf

Quantum Physics · Submitted 30 Sep 2026

Pith's verdict: Strong paper with a real gap: the tightness proof of the headline Θ(log k) Majority-junta result fails as printed — a numerator/denominator slip in the adversary matrix that the stress test caught and the structured review missed.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on October 1, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.40331 (version 3)

Pith IDC3LLXNBL, Pith's permanent record of this paper and its review

CitationAleksandrs Krivcenko, Ronald de Wolf, Tuyen Nguyen. "Fast Quantum Algorithms for Learning Linear Threshold Functions." arXiv:2609.40331 (2026). https://pith.science/paper/C3LLXNBL

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Two things you should know. First, the paper is genuinely substantial: three new query-complexity results, with careful parameter discipline in Section 3 and unusually honest self-assessment of its own caveats. Second, the tightness half of the headline Θ(log k) Majority-junta theorem (Theorems 4.1, 4.6, B.1) is not proved as printed, and the stress-test note is correct on this. I checked Eq (144) directly: Γ[A,B] = (1/|A\B|)·binom(m,|A\B|)², yet Lemma 4.6 claims every row sum is Σ_{s=1}^m 1/s. For fixed A there are binom(m,s)² sets B at distance s, each contributing (1/s)·binom(m,s)², so the row sum is Σ_s (1/s)·binom(m,s)⁴ — 16.5 for m=2, not 1.5, and Θ(m⁴) generally, not Θ(log m). Lemma 4.7's identity cuts the same way; it only goes through with the binom in the denominator. The intended matrix is plainly (1/s)·binom(m,s)^{-2}, a one-line fix, but as written both lemmas are mutually inconsistent and the Ω(log k) lower bound fails. The O(log k) upper bound (Theorem 4.5) does not depend on this and stands.

What the paper does well beyond that: Result 1 gives an exponential quantum–classical separation in membership-query complexity (O(log(n/ε)) vs Ω(n log(1/ε))), and the parameter choices — η = ρε_g/(48π(3n+1)), ρ = Θ(n^{-1/2}), the K, M budgets — do multiply out to the claimed bounds. The exactly-affine height-function argument is clean: no Taylor remainder, errors confined to finite precision. The authors flag the boundary-discontinuity subtlety in Section 5 themselves ([b564]–[b565], [b171]–[b172]), which is to their credit; the stacked discretization/QHT error budget there is the other soft spot, since it rests on the quoted [JIS+26, Theorem 19] plus several layers of approximation, none machine-checked and no code shipped. The AI-use disclosure confirms substantial AI involvement in proof development, which raises the verification burden for reviewers without itself being evidence of error.

For a reader: the upper bounds and Result 1 are solid; the Ω(log k) claim needs the Γ fix before you believe it. Send to referees — this deserves serious review, and the referee should be pointed at Section 4.4 first. If the fix is what it looks like, the paper is high-value.

Referee report

Significance

If correct, the results are substantial: an exponential quantum–classical separation for membership-query LTF learning, the first tight Θ(log k) characterization of Majority-junta learning (closing an open problem of [Bel15]), and a quartic quantum advantage in dimension for Gaussian example queries. The paper is careful about boundary conventions (sign(0)=1, Remark 2.3) and explicitly handles the halfspace-boundary discretization error in Proposition 5.1, which is a genuine technical subtlety. The benchmarks are external published results ([KMT93], [BL13], [Bel15]), so there is no circularity, and the AI-use disclosure is transparent. The principal defect is in the lower-bound (tightness) half of the Majority-junta result: the adversary matrix defined in Eq. (144) is inconsistent with the analyses of both Lemmas 4.6 and 4.7. The O(log k) upper bound (Theorem 4.5) and the results of Sections 3 and 5 are not affected by this defect.

Major objections (3)

[§4.4, Eq. (144), Lemma 4.6] The matrix Γ[A,B] = (1/|A\B|)·binom(m,|A\B|)² defined in Eq. (144) does not have row sum Σ_{s=1}^m 1/s as Lemma 4.6 claims. For fixed A there are exactly binom(m,s)² sets B with |A\B| = s, and each contributes (1/s)·binom(m,s)², so the row sum is Σ_s (1/s)·binom(m,s)⁴ = Ω(m⁴) (for m = 2 this is 16.5, not 1.5). The proof of Lemma 4.6 multiplies the number of sets B by 1/s and omits the binom(m,s)² factor that is already present in the entry. Consequently ∥Γ∥ = Θ(log k) does not follow from the matrix as written, and the adversary ratio in Theorem 4.6 is not established.
[§4.4, Appendix B.3 (Eq. 276), Theorem B.1] The proof of Lemma 4.7 uses the identity Σ_{B∈L_b} Γ[A,B] = Σ_s (1/s)·Pr(X_s = b) at Eq. (276), which is valid only if Γ[A,B] = 1/(s·binom(m,s)²), i.e., with the binomial in the denominator. This is mutually inconsistent with the definition in Eq. (144): the two lemmas are each consistent with different versions of Γ. The intended matrix is evidently Γ[A,B] = 1/(|A\B|·binom(m,|A\B|)²), under which the row sum becomes Σ_s 1/s = Θ(log k) and the cycle-lemma derivation in Section B.3 goes through (including the weighted Schur test giving ∥Γ∘Δ_S∥ = O(1)). The identical matrix is reused in Theorem B.1 (restricted to U of size 2m), so the same correction is needed there. The authors must adopt one definition and re-verify Lemmas 4.6, 4.7, and the bound of Section B.3 end-to-end; as printed, the Ω(log k) half of Theorem 4.1 is unsupported, while the O(log k) upper bound of Theorem 4.5 is unaffected.
[Theorem 4.1, Table 1] Because the tightness half of Theorem 4.1 rests entirely on the adversary matrix above, the Θ(log k) statement is not currently proven; the paper should state clearly, after the correction, that the regime conditions (n ≥ 2k for the promise |A| = k; every n ≥ k for the promise 1 ≤ |A| ≤ k) are preserved, since these footnotes in Table 1 are accurate and independent of the Γ defect.

Minor objections (4)

[Throughout] Much of the inline mathematics is typeset without spacing (e.g., 'Pr[|⟨w,x⟩|≤∆√n]≤√(2/π)∆√n' and the gate-complexity display in Theorem 3.2); the manuscript needs a careful copy-edit so that formulas are readable in the published version.
[§4.4, Lemma 4.6 (after the fix)] Once the matrix is corrected to Γ[A,B] = 1/(s·binom(m,s)²), the norm argument should be restated explicitly: Γ·1 = H_m·1, hence ∥Γ∥ = H_m = Θ(log k), and the weighted Schur test in Section B.3 should be re-verified with the stated constant 4, since the proof text there cites Equation (275) whose current derivation depends on the uncorrected entry.
[Theorem 3.1] The symbol L_ε is used as a real length (L_ε = 2⌈log₂(20T_ε)⌉) inside a logarithm; a one-sentence clarification that this is a grid half-length, not a bit count, would prevent a misreading of the query bound O(log(1 + L_ε/ζ)).
[§5.5, Eq. (174)] The choice of constants c1, c2 in Theorem 5.7 is order-of-magnitude only; a short remark listing which term of Eq. (174) enforces which hypothesis of Theorem 5.2 (degree cutoff, discretization, QHT error, tail) would improve auditability, since Section 5's claim stacks Proposition 5.1, Lemma 5.1, and the quoted Lemma 5.2.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Quantum membership queries learn linear threshold functions with O(log(n/ε)) queries, against a classical Ω(n log(1/ε)) barrier, and reduce Majority-junta learning to Θ(log k).

The reading

This paper tries to establish that coherent quantum access collapses the query cost of learning linear threshold functions (halfspaces) in three settings where classical learners are far weaker. In the real-domain membership-query model, a quantum learner recovers the unknown weight vector and threshold with O(log(n/ε)) queries and Õ(n) gates, versus the classical Ω(n log(1/ε)) query bound. In the Boolean membership-query model, the special case of learning an equal-weight Majority-junta is shown to need Θ(log k) queries, closing a gap left open by prior work that only achieved O($k^{{1/4}}$). In the weaker quantum-example model under the Gaussian distribution, homogeneous halfspaces are learned with O($n^{{1/4}}$/√ε) queries via a quantum Hermite transform, a quartic improvement over the classical dimension dependence. If these proofs hold, they are exact, closed-form query-complexity statements rather than empirical or asymptotic guesses.

What carries the argument

The paper rests on three mechanisms. (1) For membership queries: the height function h_p(x) = θ/⟨w,p⟩ − ⟨w,x⟩/⟨w,p⟩ along a fixed direction p is exactly affine, so its gradient equals −w/⟨w,p⟩; a coherent binary search approximates h_p and Jordan's grid-based gradient-estimation algorithm recovers all coordinates in parallel with O(1) oracle calls. (2) For Boolean Majority-junta learning: the dual adversary SDP whose optimal value characterizes quantum query complexity, restricted to low-rank 'intersection-free' solutions parametrized by a single (k+1)×(k+1) matrix; feasibility reduces to a polynomial condition solved by Krawtchouk polynomials whose roots partition {1,...,k−1} by residue mod 4, giving objective O(log k). (3) For quantum examples: the Hermite ridge identity h_k(⟨w,x⟩) = Σ_{|α|=k} √(k!/α!) w^α h_α(x), which shows that the degree-k Hermite component of a halfspace encodes k identical copies of |w⟩; the discrete quantum Hermite transform (QHT) exposes this structured high-degree component, amplitude amplification over the degree band accesses it with O($K^{{1/4}}$) queries, a second-to-first-quantization isometry converts it to |w⟩^{⊗K}, and gate-efficient tomography extracts the classical direction.

Extended reading notes

Core claim

The central claim is a trio of query-complexity results for learning LTFs. First, using a geometric reduction from halfspace membership to an affine height function whose gradient is collinear with the unknown normal, a quantum learner estimates both the boundary offset and the gradient in parallel, achieving O(log(n/ε)) membership queries and Õ(n) gates (Theorem 3.4), with a matching Ω(log(1/ε)) lower bound from ordered search (Theorem 3.5). Second, a homogeneous LTF whose weights are equal on an unknown support A is the Majority function on A; the paper constructs feasible solutions to the dual adversary semidefinite program—using Krawtchouk polynomials and a novel mod-4 root-partition construction—showing Θ(log k) bounded-error quantum query complexity for identifying A (Theorem 4.1). Third, from a discretized quantum-example oracle under the Gaussian measure, the paper applies the efficient quantum Hermite transform, projects onto a degree band K..2K whose Hermite mass is Θ($K^{{-1/2}}$), converts the band state via an isometry into K copies of the direction state |w⟩, and recovers w by pure-state tomography, using O($n^{{1/4}}$/√ε) oracle applications (Theorem 5.7).

Load-bearing premise

The example-query result of Section 5 rests on the finite-dimensional quantum Hermite transform of [JIS+26] together with the paper's own discretization and boundary-cell error bounds all holding simultaneously at the chosen grid size M = poly(n, 1/ε), so that the compounded approximation error—discretization, QHT synthesis, band projection, and isometry—stays below the stated η.

Editorial extensions

If this is right

Exponential quantum–classical separation: learning general halfspaces from membership queries drops from classical Ω(n log(1/ε)) to quantum O(log(n/ε)), and the paper proves a matching Ω(log(1/ε)) quantum lower bound.
The Majority-junta open problem from the earlier O(k^{1/4}) algorithm is fully resolved: Θ(log k) queries for both the exact-support and bounded-support promises, valid for all n ≥ k.
This is the first application of the efficient quantum Hermite transform to a natural machine-learning problem, giving a quartic improvement in dimension for learning homogeneous halfspaces from quantum examples under the Gaussian distribution.
The Hermite-ridge structure (degree-k component = k copies of |w⟩) offers a template for learning other ridge-structured or low-complexity function classes from quantum examples.

Reading between the lines

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

The height-function-plus-gradient recipe is likely transferable beyond halfspaces: any convex body whose boundary queries can be turned into an affine or smoothly varying height function should inherit a similar logarithmic quantum query bound, generalizing the convex-optimization separation-query results the paper cites.
The Θ(log k) Majority-junta result is proven through the dual adversary SDP, which typically yields no gate-complexity guarantee; a concrete span program distilled from the intersection-free solution would be needed before the speedup can be deployed as a circuit-level primitive.
The quantum-example result uses only the two highest-degree Hermite coefficients' mass; the same band-projection trick may extend to non-homogeneous LTFs if the threshold is treated as a separate scalar to be estimated, though the paper leaves this open.
The mod-4 polynomial construction is a specific instance of a general root-partition feasibility scheme; analogous constructions might yield log-k algorithms for learning other symmetric k-juntas such as OR or ExactHalf, where polynomial (√k-type) bounds currently prevail.

Original abstract

Linear threshold functions (LTFs) are $\{-1,1\}$-valued functions $f_{w,\theta}(x)=\text{sgn}(\langle w,x\rangle-\theta)$, where $w\in\mathbb R^n$ has unit norm, $\theta\in\mathbb R$, and $x\in\mathbb R^n$ or $\{-1,1\}^n$. If $\theta=0$, the LTF is homogeneous, denoted $f_w=f_{w,0}$. LTFs are fundamental linear classifiers. We give three results: one for general LTFs and two for homogeneous LTFs. (1) With real-domain membership queries evaluating $f_{w,\theta}(x)$ at any chosen $x\in\mathbb R^n$, we learn an LTF with classification error at most $\varepsilon$ under the standard Gaussian distribution using $O(\log(n/\varepsilon))$ queries and $\widetilde{O}(n)$ other gates. Classically, $\Omega(n\log(1/\varepsilon))$ queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF $f_w$ over $\{-1,1\}^n$ whose $k$ nonzero weights are equal and positive is Majority on the support of $w$. We identify this hidden support exactly using $O(\log k)$ queries, exponentially improving Belovs' $O(k^{1/4})$ upper bound. Our algorithm uses $O(n\log n\log k)$ gates and has $O(\log n\log k)$ non-oracle depth. Classical algorithms require $\Omega(k\log(n/k))$ queries. (3) Suppose a unitary $U$ prepares discretized Gaussian quantum examples, corresponding to $\int_x\sqrt{\gamma_n(x)}|x\rangle|f_w(x)\rangle\,dx$. This is weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most $\varepsilon$ under the Gaussian distribution using $O(n^{1/4}/\sqrt{\varepsilon})$ applications of $U$ and $U^\dagger$ and $\widetilde{O}\!(\frac{n^{5/4}}{\sqrt{\varepsilon}}+\frac{n}{\varepsilon^2})$ other gates. Classically, $\Omega(n/\varepsilon)$ examples are needed, giving a quartic quantum speedup in $n$. We show that the quantum query complexities in all three cases are optimal by proving matching lower bounds.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-10-01: 1 request, 10,654 input tokens.

What the abstract itself states, as probabilities: claims first 0.09 · states limitation 0.62 · human participants 0.01 · controlled comparison 0.24 · randomized assignment 0.02 · states quantitative result 0.99 · compares with prior results 0.97 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

Linear threshold functions are $f_{w,\theta}(x)=\text{sign}(\langle x,w \rangle -\theta)$, where the weight vector $w\in\mathbb{R}^n$ is a unit vector, $\theta\in\mathbb R$ is a threshold, and typically $x\in\mathbb{R}^n$ or $x\in\{-1,1\}^n$. When $\theta=0$, the LTF is called homogeneous, and we write $f_w:=f_{w,0}$. Such functions are among the most important objects in machine learning, since they serve to linearly discriminate positive and negative examples. We give three positive results about learning LTFs: 1. Suppose we can make real-domain queries, meaning we can compute $f_{w,\theta}(x)$ at any $x\in\mathbb{R}^n$ of our choice. We give a quantum algorithm that learns $f_{w,\theta}$ up to Euclidean error~$\epsilon$ using $O(\log(n/\epsilon))$ membership queries and $\widetilde{O}(n)$ other gates. Then we have also learned $f_{w,\theta}$ up to error $O(\epsilon)$ when $x$ is Gaussian. Classical algorithms need $\Omega(n\log(1/\epsilon))$ queries. 2. A homogeneous LTF $f_w$ on domain $\{-1,1\}^n$ where $w$ has only $k$ nonzero entries of the same value, is the Majority function on the support of $w$. Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns $f_w$) using $O(k^{1/4})$ queries. We give an exponential improvement, using $O(\log k)$ queries. 3. Suppose we have a unitary $U$ that can produce (discretized) \emph{quantum examples} under Gaussian measure, corresponding to $\int_x \sqrt{\gamma_n(x)}|x\rangle |f_w(x)\rangle dx$. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient \emph{Hermite transform} of Jain et al.\ to learn homogeneous LTFs~$f_w$ with error~$\epsilon$ under the Gaussian distribution, using $O(n^{1/4}/\sqrt{\epsilon})$ applications of $U$ and $U^\dagger$ and $\widetilde{O}(n^2/\epsilon^4)$ other gates.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Linear threshold functions are $f_{w,\theta}(x)=\text{sign}(\langle x,w \rangle -\theta)$, where the weight vector $w\in\mathbb{R}^n$ is a unit vector, $\theta\in\mathbb R$ is a threshold, and typically $x\in\mathbb{R}^n$ or $x\in\{-1,1\}^n$.	background 1.00	0.05	0.02	asserted 1.00
s1	When $\theta=0$, the LTF is called homogeneous, and we write $f_w:=f_{w,0}$.	background 1.00	0.20	0.02	asserted 0.99
s2	Such functions are among the most important objects in machine learning, since they serve to linearly discriminate positive and negative examples.	background 1.00	0.04	0.02	asserted 1.00
s3	We give three positive results about learning LTFs: 1.	contribution 1.00	0.88	0.27	asserted 0.95
s4	Suppose we can make real-domain queries, meaning we can compute $f_{w,\theta}(x)$ at any $x\in\mathbb{R}^n$ of our choice.	method 0.55	0.18	0.03	asserted 0.59
s5	We give a quantum algorithm that learns $f_{w,\theta}$ up to Euclidean error~$\epsilon$ using $O(\log(n/\epsilon))$ membership queries and $\widetilde{O}(n)$ other gates.	contribution 0.56	0.95	0.30	asserted 1.00
s6	Then we have also learned $f_{w,\theta}$ up to error $O(\epsilon)$ when $x$ is Gaussian.	result 0.77	0.82	0.10	asserted 0.99
s7	Classical algorithms need $\Omega(n\log(1/\epsilon))$ queries. 2.	result 0.51	0.28	0.09	asserted 1.00
s8	A homogeneous LTF $f_w$ on domain $\{-1,1\}^n$ where $w$ has only $k$ nonzero entries of the same value, is the Majority function on the support of $w$.	background 0.95	0.15	0.04	asserted 1.00
s9	Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns $f_w$) using $O(k^{1/4})$ queries.	background 0.98	0.03	0.06	asserted 1.00
s10	We give an exponential improvement, using $O(\log k)$ queries. 3.	result 0.72	0.93	0.17	asserted 1.00
s11	Suppose we have a unitary $U$ that can produce (discretized) \emph{quantum examples} under Gaussian measure, corresponding to $\int_x \sqrt{\gamma_n(x)}\|x\rangle \|f_w(x)\rangle dx$.	method 0.60	0.28	0.04	asserted 0.47
s12	This is a weaker access model than membership queries.	background 0.55	0.35	0.02	asserted 1.00
s13	We give a quantum algorithm based on the efficient \emph{Hermite transform} of Jain et al.\ to learn homogeneous LTFs~$f_w$ with error~$\epsilon$ under the Gaussian distribution, using $O(n^{1/4}/\sqrt{\epsilon})$ applications of $U$ and $U^\dagger$ and $\widetilde{O}(n^2/\epsilon^4)$ other gates.	contribution 0.82	0.93	0.20	asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.67 · evidence from proof or derivation 0.99.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.