Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1806.09660

On learning linear functions from subset and its applications in quantum computing

Gábor Ivanyos, Anupam Prakash, Miklós Sántha

Published Jun 25, 2018• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1806.09660

Related papers

On Learning Linear Functions from Subset and Its Applications in Quantum Computing

Fernando G. S. L. Brandão, Kalev, Amir, Tongyang Li +3 more

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.

arXiv:1710.02581•Leibniz international proceedings in informatics•Oct 6, 2017•49 citations

On the Sample Complexity of PAC Learning Quantum Process.

Kai-Min Chung, Han-Hsuan Lin

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 $\epsilon$-approximate of an unknown quantum process $c^*$ from a known finite concept class $C$ with probability $1-\delta$ using samples $\{(x_1,c^*(x_1)),(x_2,c^*(x_2)),\dots\}$, where $\{x_1,x_2, \dots\}$ are computational basis states sampled from an unknown distribution $D$ and $\{c^*(x_1),c^*(x_2),\dots\}$ 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-\delta$ an $\epsilon$-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\left(\frac{\log|C| + \log(1/ \delta)} { \epsilon^2}\right)$$ samples when the outputs are pure states and $$O\left(\frac{\log^3 |C|(\log |C|+\log(1/ \delta))} { \epsilon^2}\right)$$ 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.

•Oct 25, 2018•0 citations

Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE

Robin Kothari, Tony Metger, Ryan O'Donnell +2 more

We study vector subset sum over $\mathbb{F}_3^n$: given $m$ random vectors from $\mathbb{F}_3^n$, 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\approx n^2/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 \approx n^2/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 $\mathbb{F}_3$-subset sum in polynomial time with $m=ε\cdot n^2$ 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).

quant-pharXiv:2609.40321•Oct 1, 2026•0 citations

Efficient quantum algorithm for identifying hidden polynomials

Thomas Decker, Jan Draisma, Paweł Wocjan

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\geq 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 $\Omega(\sqrt{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$.

arXiv:0706.1219•Quantum Information and Computation•Mar 1, 2009•13 citations

Quantum algorithms for highly non-linear Boolean functions

Martin Rötteler

Attempts to separate the power of classical and quantum models of computation have a long history. The ultimate goal are exponential separations for computational (promise) problems, however, these do not come a dime a dozen: while there were some early successes in the form of hidden subgroup problems for abelian groups–which generalizes Shor’s factoring algorithm perhaps most faithfully–only for a handful of non-abelian groups efficient quantum algorithms were found. Recently, problems have gotten increased attention that seek to identify hidden sub-structures of other combinatorial and algebraic objects besides groups, notably the quantum algorithms by Childs, Schulman, and Vazirani for shifted subset problems for spheres over a finite field. In this paper we provide new examples for exponential separations by considering hidden shift problems that are defined for several classes of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time with a constant number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms. We also give a quantum algorithm that solves the hidden shift problem for quadratic forms that might be of independent interest. This algorithm can also be used to find approximating polynomials and shifts for functions with large Gowers U3 norm. 1 1

•Jan 1, 2008•24 citations

Fast Quantum Algorithms for Learning Linear Threshold Functions

Aleksandrs Krivcenko, Tuyen Nguyen, Ronald de Wolf

Linear threshold functions are $f_{w,θ}(x)=\text{sign}(\langle x,w \rangle -θ)$, where the weight vector $w\in\mathbb{R}^n$ is a unit vector, $θ\in\mathbb R$ is a threshold, and typically $x\in\mathbb{R}^n$ or $x\in\{-1,1\}^n$. When $θ=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,θ}(x)$ at any $x\in\mathbb{R}^n$ of our choice. We give a quantum algorithm that learns $f_{w,θ}$ up to Euclidean error $ε$ using $O(\log(n/ε))$ membership queries and $\widetilde{O}(n)$ other gates. Then we have also learned $f_{w,θ}$ up to error $O(ε)$ when $x$ is Gaussian. Classical algorithms need $Ω(n\log(1/ε))$ 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) quantum examples under Gaussian measure, corresponding to $\int_x \sqrt{γ_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 Hermite transform of Jain et al. to learn homogeneous LTFs $f_w$ with error $ε$ under the Gaussian distribution, using $O(n^{1/4}/\sqrtε)$ applications of $U$ and $U^\dagger$ and $\widetilde{O}(n^2/ε^4)$ other gates.

quant-pharXiv:2609.40331•Oct 1, 2026•0 citations
Let Fq\mathbb{F}_qFq​ be the finite field of size qqq and let ℓ:Fqn→Fq\ell: \mathbb{F}_q^n \to \mathbb{F}_qℓ:Fqn​→Fq​ be a linear function. We introduce the {\em Learning From Subset} problem LFS(q,n,d)(q,n,d)(q,n,d) of learning ℓ\ellℓ, given samples u∈Fqnu \in \mathbb{F}_q^nu∈Fqn​ from a special distribution depending on ℓ\ellℓ: the probability of sampling uuu is a function of ℓ(u)\ell(u)ℓ(u) and is non zero for at most ddd values of ℓ(u)\ell(u)ℓ(u). We provide a randomized algorithm for LFS(q,n,d)(q,n,d)(q,n,d) with sample complexity (n+d)O(d)(n+d)^{O(d)}(n+d)O(d) and running time polynomial in log⁡q\log qlogq and (n+d)O(d)(n+d)^{O(d)}(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)(q,n,q-1)(q,n,q−1) with running time (n+q)O(q)(n+q)^{O(q)}(n+q)O(q). We further present applications of our result to the {\em Hidden Multiple Shift} problem HMS(q,n,r)(q,n,r)(q,n,r) in quantum computation where the goal is to determine the hidden shift sss given oracle access to rrr shifted copies of an injective function f:Zqn→{0,1}lf: \mathbb{Z}_q^n \to \{0, 1\}^lf:Zqn​→{0,1}l, that is we can make queries of the form fs(x,h)=f(x−hs)f_s(x,h) = f(x-hs)fs​(x,h)=f(x−hs) where hhh can assume rrr possible values. We reduce HMS(q,n,r)(q,n,r)(q,n,r) to LFS(q,n,q−r+1)(q,n, q-r+1)(q,n,q−r+1) to obtain a polynomial time algorithm for HMS(q,n,r)(q,n,r)(q,n,r) when q=nO(1)q=n^{O(1)}q=nO(1) is prime and q−r=O(1)q-r=O(1)q−r=O(1). The best known algorithms \cite{CD07, Friedl} for HMS(q,n,r)(q,n,r)(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.
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 ϵ\epsilonϵ-approximate of an unknown quantum process c∗c^*c∗ from a known finite concept class CCC with probability 1−δ1-\delta1−δ using samples {(x1,c∗(x1)),(x2,c∗(x2)),… }\{(x_1,c^*(x_1)),(x_2,c^*(x_2)),\dots\}{(x1​,c∗(x1​)),(x2​,c∗(x2​)),…}, where {x1,x2,… }\{x_1,x_2, \dots\}{x1​,x2​,…} are computational basis states sampled from an unknown distribution DDD and {c∗(x1),c∗(x2),… }\{c^*(x_1),c^*(x_2),\dots\}{c∗(x1​),c∗(x2​),…} are the (possibly mixed) quantum states outputted by c∗c^*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∗c^*c∗ from an known finite set CCC, and we want to learn with probability 1−δ1-\delta1−δ an ϵ\epsilonϵ-approximate of c∗c^*c∗ with as few copies of c∗c^*c∗ as possible. We show that the problem of PAC learning quantum process can be solved with O(log⁡∣C∣+log⁡(1/δ)ϵ2)O\left(\frac{\log|C| + \log(1/ \delta)} { \epsilon^2}\right)O(ϵ2log∣C∣+log(1/δ)​) samples when the outputs are pure states and O(log⁡3∣C∣(log⁡∣C∣+log⁡(1/δ))ϵ2)O\left(\frac{\log^3 |C|(\log |C|+\log(1/ \delta))} { \epsilon^2}\right)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∣|C|∣C∣ is exponential in the number of qubits, an exponentially improvement over a full state tomography.
Exponential quantum speedup for F3n\mathbb{F}_3^nF3n​-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
We study vector subset sum over F3n\mathbb{F}_3^nF3n​: given mmm random vectors from F3n\mathbb{F}_3^nF3n​, find a nonempty subset that sums to zero; the smaller mmm, 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/2m\approx n^2/2m≈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/3m \approx n^2/3m≈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ε>0ε>0, our quantum algorithm solves F3\mathbb{F}_3F3​-subset sum in polynomial time with m=ε⋅n2m=ε\cdot n^2m=ε⋅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 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 ddd elements. The hidden functions of the generalized problem are not restricted to be linear but can also be mmm-variate polynomial functions of total degree n≥2n\geq 2n≥2. The problem of identifying hidden mmm-variate polynomials of degree less or equal to nnn for fixed nnn and mmm is hard on a classical computer since Ω(d)\Omega(\sqrt{d})Ω(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 ddd with constant probability and that has a running time that is only polylogarithmic in ddd.
Attempts to separate the power of classical and quantum models of computation have a long history. The ultimate goal are exponential separations for computational (promise) problems, however, these do not come a dime a dozen: while there were some early successes in the form of hidden subgroup problems for abelian groups–which generalizes Shor’s factoring algorithm perhaps most faithfully–only for a handful of non-abelian groups efficient quantum algorithms were found. Recently, problems have gotten increased attention that seek to identify hidden sub-structures of other combinatorial and algebraic objects besides groups, notably the quantum algorithms by Childs, Schulman, and Vazirani for shifted subset problems for spheres over a finite field. In this paper we provide new examples for exponential separations by considering hidden shift problems that are defined for several classes of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time with a constant number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms. We also give a quantum algorithm that solves the hidden shift problem for quadratic forms that might be of independent interest. This algorithm can also be used to find approximating polynomials and shifts for functions with large Gowers U3 norm. 1 1
Linear threshold functions are fw,θ(x)=sign(⟨x,w⟩−θ)f_{w,θ}(x)=\text{sign}(\langle x,w \rangle -θ)fw,θ​(x)=sign(⟨x,w⟩−θ), where the weight vector w∈Rnw\in\mathbb{R}^nw∈Rn is a unit vector, θ∈Rθ\in\mathbb Rθ∈R is a threshold, and typically x∈Rnx\in\mathbb{R}^nx∈Rn or x∈{−1,1}nx\in\{-1,1\}^nx∈{−1,1}n. When θ=0θ=0θ=0, the LTF is called homogeneous, and we write fw:=fw,0f_w:=f_{w,0}fw​:=fw,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 fw,θ(x)f_{w,θ}(x)fw,θ​(x) at any x∈Rnx\in\mathbb{R}^nx∈Rn of our choice. We give a quantum algorithm that learns fw,θf_{w,θ}fw,θ​ up to Euclidean error εεε using O(log⁡(n/ε))O(\log(n/ε))O(log(n/ε)) membership queries and O~(n)\widetilde{O}(n)O(n) other gates. Then we have also learned fw,θf_{w,θ}fw,θ​ up to error O(ε)O(ε)O(ε) when xxx is Gaussian. Classical algorithms need Ω(nlog⁡(1/ε))Ω(n\log(1/ε))Ω(nlog(1/ε)) queries. 2. A homogeneous LTF fwf_wfw​ on domain {−1,1}n\{-1,1\}^n{−1,1}n where www has only kkk nonzero entries of the same value, is the Majority function on the support of www. Belovs gave a bounded-error quantum algorithm that identifies the hidden support exactly (and hence learns fwf_wfw​) using O(k1/4)O(k^{1/4})O(k1/4) queries. We give an exponential improvement, using O(log⁡k)O(\log k)O(logk) queries. 3. Suppose we have a unitary UUU that can produce (discretized) quantum examples under Gaussian measure, corresponding to ∫xγn(x)∣x⟩∣fw(x)⟩dx\int_x \sqrt{γ_n(x)}|x\rangle |f_w(x)\rangle dx∫x​γn​(x)​∣x⟩∣fw​(x)⟩dx. This is a weaker access model than membership queries. We give a quantum algorithm based on the efficient Hermite transform of Jain et al. to learn homogeneous LTFs fwf_wfw​ with error εεε under the Gaussian distribution, using O(n1/4/ε)O(n^{1/4}/\sqrtε)O(n1/4/ε​) applications of UUU and U†U^\daggerU† and O~(n2/ε4)\widetilde{O}(n^2/ε^4)O(n2/ε4) other gates.