Learning halfspaces with logarithmically many quantum queries

A linear threshold function, or halfspace, labels a point by the sign of an inner product minus a threshold. Krivcenko, Nguyen, and de Wolf (arXiv:2609.40331, version 2, 5 Oct 2026) study how many times a quantum algorithm has to evaluate that label. The note below follows Theorems 3.4 and 3.5, the Boolean bound in Theorem 4.1, and the example-oracle bound in Theorem 5.8. The paper is a preprint. Nothing here promotes it to a journal theorem.

The query model

The target is f(x) = sign of the inner product of a unit vector w with x, minus a real threshold θ. The error that matters in Section 3 is classification error under the standard Gaussian: the probability, over a Gaussian x, that the hypothesis and the target disagree. Coherent membership access means the learner may apply, to a superposition, a unitary that writes the label of any chosen real vector. Each such application counts as one query. Query complexity is that count. It is not the number of gates in the rest of the circuit, and the paper keeps the two ledgers separate.

Classically, one query returns one bit. Theorem A.3 of the paper proves that a randomized classical learner needs on the order of n log(1/ε) membership queries to learn a homogeneous halfspace to Gaussian error ε, for every n at least 2 and every ε below a universal constant, with success probability at least 2/3. Improper hypotheses are allowed. The argument is a packing bound. The authors trace the information-theoretic idea to Kulkarni, Mitter, and Tsitsiklis, and they prove the Gaussian statement in the appendix.

The bound

Theorem 3.4 is the quantum upper bound for a general threshold, not only the homogeneous case. For n at least 2 and every ε in the range from 0 up to 1/2, there is a quantum algorithm that outputs a hypothesis with Gaussian classification error at most ε, with probability at least 2/3. It uses on the order of log(n/ε) membership queries and on the order of n other gates, up to factors polylogarithmic in n. The route is geometric. Along a fixed reference direction the label is a one-dimensional threshold, so binary search estimates where the hyperplane sits. The height of that intersection is an affine function of the query point, and its gradient is proportional to w. A gradient-estimation routine, in the line of Jordan's algorithm, recovers the gradient from a constant number of coherent evaluations of an approximation to that height. The threshold is reconstructed from the gradient and the intercept.

Theorem 3.5 is the matching query lower bound, with a smaller range of ε. There is a universal constant ε₀ such that for n at least 2 and every positive ε at most ε₀, any quantum learner that, for every unit vector w, outputs a hypothesis within Gaussian error ε of the homogeneous halfspace, with probability at least 2/3, needs on the order of log(n/ε) membership queries. The proof allows adaptive superposition queries at arbitrary real points and improper hypotheses. The paper's table puts the upper and lower bounds side by side as on the order of log(n/ε). The lower bound is stated for homogeneous targets and for small ε. A learner for general thresholds would solve the homogeneous case, so the same query lower bound applies there too, inside that range of ε.

Two further access models

The Boolean result is a different oracle and a special halfspace. If the domain is the Boolean cube and every nonzero weight is equal, the function is majority on an unknown support of size at most k. Theorem 4.1 says the bounded-error quantum query complexity of identifying that support is on the order of log k. Under the promise that the support has size exactly k, the bound holds for every n at least 2k. Under the promise that the size is between 1 and k, it holds for every n at least k. The authors say this answers an open question in Section 8 of Belovs, whose preprint states an upper bound on the order of k to the power 1/4 for majority. Section 1.1.2 of the new paper is the caveat on that algorithm: it comes from a feasible solution of the dual adversary bound, and for algorithms obtained that way one typically does not get a good upper bound on the gate complexity. The logarithmic Boolean bound is a query bound.

The third model is weaker than membership queries. A unitary prepares a superposition of Gaussian points labeled by a homogeneous halfspace, and the learner may also apply the inverse. Theorem 5.8 says that for n at least 2 and ε in the range from 0 up to 1/2, on the order of n to the power 1/4 over the square root of ε uses of that unitary and its inverse suffice to output a unit vector within Euclidean distance ε of w, with probability at least 2/3. The other gates are on the order of n to the power 5/4 over the square root of ε, plus n over ε squared, up to polylogarithmic factors, together with classical post-processing polynomial in n and 1/ε. The algorithm uses the quantum Hermite transform of Jain, Iyer, Somma, Bao, and Jordan as a subroutine. This page does not re-derive that transform. Against classical examples, the paper's Theorem A.4, marked as following Balcan and Long, gives a lower bound on the order of n/ε. The improvement is a fourth root in n, not an exponential. Section 1.1.3 states an open problem, not a theorem: the example-oracle algorithm is only for a zero threshold.

Where the claim stops

The proved statements are the query and gate counts above, each in its own access model, each with the success probability 2/3 written in the theorem. The paper does not claim a gate bound for the Boolean majority algorithm. It does not claim the example-oracle result for a nonzero threshold. Version 2 adds the optimal log(n/ε) lower bound in Section 3; a reader of version 1 would not have had Theorem 3.5 in this form. Cite the preprint for these statements. This digest is a secondary source.