Let $\mathbb{F}_q$ be the finite field of size $q$ and let $\ell: \mathbb{F}_q^n \to \mathbb{F}_q$ be a linear function. We introduce the {\em Learning From Subset} problem LFS$(q,n,d)$ of learning $\ell$, given samples $u \in \mathbb{F}_q^n$ from a special distribution depending on $\ell$: the probability of sampling $u$ is a function of $\ell(u)$ and is non zero for at most $d$ values of $\ell(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 \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: \mathbb{Z}_q^n \to \{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 \cite{CD07, Friedl} 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.
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.
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 consider a natural generalization of an abelian Hidden Subgroup Problem where the subgroups and their cosets correspond to graphs of linear functions over a finite field $\F$ with d elements. The hidden functions of the generalized problem are not restricted to be linear but can also be m-variate polynomial functions of total degree n≥2. The problem of identifying hidden m-variate polynomials of degree less or equal to n for fixed n and m is hard on a classical computer since Ω(d) black-box queries are required to guarantee a constant success probability. In contrast, we present a quantum algorithm that correctly identifies such hidden polynomials for all but a finite number of values of d with constant probability and that has a running time that is only polylogarithmic in d.
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).
We generalize the PAC (probably approximately correct) learning model to the quantum world by generalizing the concepts from classical functions to quantum processes, defining the problem of \emph{PAC learning quantum process}, and study its sample complexity. In the problem of PAC learning quantum process, we want to learn an ϵ-approximate of an unknown quantum process c∗ from a known finite concept class C with probability 1−δ using samples {(x1,c∗(x1)),(x2,c∗(x2)),…}, where {x1,x2,…} are computational basis states sampled from an unknown distribution D and {c∗(x1),c∗(x2),…} are the (possibly mixed) quantum states outputted by c∗. The special case of PAC-learning quantum process under constant input reduces to a natural problem which we named as approximate state discrimination, where we are given copies of an unknown quantum state c∗ from an known finite set C, and we want to learn with probability 1−δ an ϵ-approximate of c∗ with as few copies of c∗ as possible. We show that the problem of PAC learning quantum process can be solved with O(ϵ2log∣C∣+log(1/δ)) samples when the outputs are pure states and O(ϵ2log3∣C∣(log∣C∣+log(1/δ))) samples if the outputs can be mixed. Some implications of our results are that we can PAC-learn a polynomial sized quantum circuit in polynomial samples and approximate state discrimination can be solved in polynomial samples even when concept class size ∣C∣ is exponential in the number of qubits, an exponentially improvement over a full state tomography.