Let F_{q} be the finite field of size q and let l: F_{q}^{n} -> F_{q} be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning l, given samples u in F_{q}^{n} from a special distribution depending on l: the probability of sampling u is a function of l(u) and is non zero for at most d values of l(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^{O(d)} and running time polynomial in log q and (n+d)^{O(d)}. Our algorithm generalizes and improves upon previous results [Friedl et al., 2014; Gabor Ivanyos, 2008] that had provided algorithms for LFS(q,n,q-1) with running time (n+q)^{O(q)}. We further present applications of our result to the Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: Z_{q}^{n} -> {0, 1}^{l}, that is we can make queries of the form f_{s}(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=n^{O(1)} is prime and q-r=O(1). The best known algorithms [Andrew M. Childs and Wim van Dam, 2007; Friedl et al., 2014] for HMS(q,n,r) with these parameters require exponential time.
Let F_{q} be the finite field of size q and let l: F_{q}^{n} -> F_{q} be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning l, given samples u in F_{q}^{n} from a special distribution depending on l: the probability of sampling u is a function of l(u) and is non zero for at most d values of l(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^{O(d)} and running time polynomial in log q and (n+d)^{O(d)}. Our algorithm generalizes and improves upon previous results [Friedl et al., 2014; Gabor Ivanyos, 2008] that had provided algorithms for LFS(q,n,q-1) with running time (n+q)^{O(q)}. We further present applications of our result to the Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: Z_{q}^{n} -> {0, 1}^{l}, that is we can make queries of the form f_{s}(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=n^{O(1)} is prime and q-r=O(1). The best known algorithms [Andrew M. Childs and Wim van Dam, 2007; Friedl et al., 2014] for HMS(q,n,r) with these parameters require exponential time.
Let F_{q} be the finite field of size q and let l: F_{q}^{n} -> F_{q} be a linear function. We introduce the Learning From Subset problem LFS(q,n,d) of learning l, given samples u in F_{q}^{n} from a special distribution depending on l: the probability of sampling u is a function of l(u) and is non zero for at most d values of l(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)^{O(d)} and running time polynomial in log q and (n+d)^{O(d)}. Our algorithm generalizes and improves upon previous results [Friedl et al., 2014; Gábor Ivanyos, 2008] that had provided algorithms for LFS(q,n,q-1) with running time (n+q)^{O(q)}. We further present applications of our result to the Hidden Multiple Shift problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f: Z_{q}^{n} -> {0, 1}^{l}, that is we can make queries of the form f_{s}(x,h) = f(x-hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n, q-r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=n^{O(1)} is prime and q-r=O(1). The best known algorithms [Andrew M. Childs and Wim van Dam, 2007; Friedl et al., 2014] for HMS(q,n,r) with these parameters require exponential time.
Let Fq be the finite field of size q and let ℓ:Fqn→Fq be a linear function. We introduce the {\em Learning From Subset} problem LFS(q,n,d) of learning ℓ, given samples u∈Fqn from a special distribution depending on ℓ: the probability of sampling u is a function of ℓ(u) and is non zero for at most d values of ℓ(u). We provide a randomized algorithm for LFS(q,n,d) with sample complexity (n+d)O(d) and running time polynomial in logq and (n+d)O(d). Our algorithm generalizes and improves upon previous results \cite{Friedl, Ivanyos} that had provided algorithms for LFS(q,n,q−1) with running time (n+q)O(q). We further present applications of our result to the {\em Hidden Multiple Shift} problem HMS(q,n,r) in quantum computation where the goal is to determine the hidden shift s given oracle access to r shifted copies of an injective function f:Zqn→{0,1}l, that is we can make queries of the form fs(x,h)=f(x−hs) where h can assume r possible values. We reduce HMS(q,n,r) to LFS(q,n,q−r+1) to obtain a polynomial time algorithm for HMS(q,n,r) when q=nO(1) is prime and q−r=O(1). The best known algorithms \cite{CD07, Friedl} for HMS(q,n,r) with these parameters require exponential time.
An important special case of the hidden subgroup problem is equivalent to the hidden shift problem over abelian groups. An efficient solution to the latter problem could serve as a building block of quantum hidden subgroup algorithms over solvable groups. The main idea of a promising approach to the hidden shift problem is a reduction to solving systems of certain random disequations in finite abelian groups. By a disequation we mean a constraint of the form f(x)=0. In our case, the functions on the left hand side are generalizations of linear functions. The input is a random sample of functions according to a distribution which is up to a constant factor uniform over the "linear" functions f such that f(u)=0 for a fixed, although unknown element u∈A. The goal is to find u, or, more precisely, all the elements u′∈A satisfying the same disequations as u. In this paper we give a classical probabilistic algorithm which solves the problem in an abelian p-group A in time polynomial in the sample size N, where $N=(\log\size{A})^{O(q^2)}$, and q is the exponent of A.
Linear threshold functions (LTFs) are {−1,1}-valued functions fw,θ(x)=sgn(⟨w,x⟩−θ), where w∈Rn has unit norm, θ∈R, and x∈Rn or {−1,1}n. If θ=0, the LTF is homogeneous, denoted fw=fw,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 fw,θ(x) at any chosen x∈Rn, we learn an LTF with classification error at most ε under the standard Gaussian distribution using O(log(n/ε)) queries and O(n) other gates. Classically, Ω(nlog(1/ε)) queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF fw 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(logk) queries, exponentially improving Belovs' O(k1/4) upper bound. Our algorithm uses O(nlognlogk) gates and has O(lognlogk) non-oracle depth. Classical algorithms require Ω(klog(n/k)) queries. (3) Suppose a unitary U prepares discretized Gaussian quantum examples, corresponding to ∫xγn(x)∣x⟩∣fw(x)⟩dx. This is weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most ε under the Gaussian distribution using O(n1/4/ε) applications of U and U† and O(εn5/4+ε2n) other gates. Classically, Ω(n/ε) 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.
We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model ("OR queries"), the oracle returns whether a given subset of the vertices contains any edges. In the second ("parity queries"), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al.\ for a "gapped" version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.
Exponential quantum speedup for F3n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
We study vector subset sum over F3n: given m random vectors from F3n, find a nonempty subset that sums to zero; the smaller m, the more difficult it is to find such a subset. Chen, Liu, and Zhandry (EUROCRYPT'22) introduced an efficient quantum algorithm that solves this problem when m≈n2/2, where a naive classical algorithm would require exponential time. Subsequently, Kothari, O'Donnell, and Wu (STOC'2026) gave an efficient classical algorithm that only requires m≈n2/3 vectors, thus removing the hope for an exponential quantum advantage in this parameter regime.
Using the framework of Chen, Liu, and Zhandry, we give quantum algorithms that require much fewer input vectors, renewing the possibility of an exponential quantum speedup: for any fixed ε>0, our quantum algorithm solves F3-subset sum in polynomial time with m=ε⋅n2 vectors. More generally, we establish a full sample--time tradeoff that interpolates between exponential and polynomial runtime.
The main ingredient is a deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest. For this, we rigorously establish a sample--time tradeoff that was predicted by earlier algebraic heuristics. For vector subset sums over larger fields, we also significantly improve classical algorithms in Kothari, O'Donnell, and Wu (STOC'2026).