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:2609.40331

Fast Quantum Algorithms for Learning Linear Threshold Functions

Aleksandrs Krivcenko, Tuyen Nguyen, Ronald de Wolf

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
v1 · Sep 30, 2026v2 · Oct 5, 2026v3 · Nov 3, 2026
arXivHTMLPDF

Abstract

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) \emph{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 \emph{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.

Related papers

Quantum Search With Generalized Wildcards

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro +2 more

In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string $x \in \{-1,1\}^n$. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost $O(\sqrt{n} \log n)$ and a near-matching lower bound of $Ω(\sqrt{n})$. Belovs [Comput.~Comp.'15] subsequently showed a tight $O(\sqrt{n})$ upper bound. We consider a natural generalization of this problem, parametrized by a subset $\cal{Q} \subseteq 2^{[n]}$, where an algorithm may test whether $x_S = b$ for an arbitrary $S \in \cal{Q}$ and $b \in \{-1,1\}^S$ of its choice, at unit cost. We show near-tight bounds when $\cal{Q}$ is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set. All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning $x$ is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions $f : \{-1,1\}^n \to \mathbb{R}$ the ratio of the maximum value of $f$ to the maximum (over $T \in \cal{Q}$) standard deviation of $f$ on a subcube whose free variables are exactly $T$.' To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.

quant-pharXiv:2511.04669•Leibniz international proceedings in informatics•Nov 7, 2025•1 citation

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

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

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.

arXiv:1806.09660•Jun 25, 2018•4 citations

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given $m$ Bernoulli distributions with unknown biases $p_1,\dots,p_m$ and a gap parameter $Δ$, the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ($p_i\ge1/2+Δ$) to within additive error $ε$. We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ queries, achieving a quadratic speedup over the classical sample complexity. % of $Θ(ρ/Δ^2ε^2)$. Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of $Ω(\sqrtρ/(Δε))$ via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap $Δ=Θ(1)$, which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$, thereby characterizing the query complexity of quantum counting with bounded-error oracles.

quant-pharXiv:2609.07604•Sep 8, 2026•0 citations

An Optimal Quantum Linear Systems Algorithm

Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari

In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $κ$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $ε$-approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$, while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$. We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.

quant-pharXiv:2609.35660•Sep 29, 2026•9 citations

Quantum algorithms and learning theory

Srinivasan Arunachalam

This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.

•Apr 25, 2018•1 citation

Quadratic quantum speedup for perceptron training

Pengcheng Liao, Barry C. Sanders, Tim Byrnes

Perceptrons, which perform binary classification, are the fundamental building blocks of neural networks. Given a data set of size $N$ and margin $\ensuremath{\gamma}$ (how well the given data are separated), the query complexity of the best-known quantum training algorithm scales as either $(\sqrt{N}/{\ensuremath{\gamma}}^{2})log(1/{\ensuremath{\gamma}}^{2})$ or $N/\sqrt{\ensuremath{\gamma}}$, which is achieved by a hybrid of classical and quantum search. In this paper, we improve the version space quantum training method for perceptrons such that the query complexity of our algorithm scales as $\sqrt{N/\ensuremath{\gamma}}$. This is achieved by constructing an oracle for the perceptrons using quantum counting of the number of data elements that are correctly classified. Once such an oracle is constructed, bounded-error quantum search can be used to search over the hyperplane instances. The optimality of our algorithm is proven by reducing the evaluation of a two-level and-or tree (for which the query complexity lower bound is known) to a multicriterion search. Our quantum training algorithm can be generalized to train more complex machine learning models such as neural networks, which are built on a large number of perceptrons.

arXiv:2109.04695•Physical Review A•Dec 9, 2024•10 citations
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) \emph{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 \emph{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.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}nx \in \{-1,1\}^nx∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlog⁡n)O(\sqrt{n} \log n)O(n​logn) and a near-matching lower bound of Ω(n)Ω(\sqrt{n})Ω(n​). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n)O(\sqrt{n})O(n​) upper bound. We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n]\cal{Q} \subseteq 2^{[n]}Q⊆2[n], where an algorithm may test whether xS=bx_S = bxS​=b for an arbitrary S∈QS \in \cal{Q}S∈Q and b∈{−1,1}Sb \in \{-1,1\}^Sb∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q\cal{Q}Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set. All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning xxx is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→Rf : \{-1,1\}^n \to \mathbb{R}f:{−1,1}n→R the ratio of the maximum value of fff to the maximum (over T∈QT \in \cal{Q}T∈Q) standard deviation of fff on a subcube whose free variables are exactly TTT.' To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
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.
Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given mmm Bernoulli distributions with unknown biases p1,…,pmp_1,\dots,p_mp1​,…,pm​ and a gap parameter ΔΔΔ, the goal is to estimate the fraction ρρρ of \emph{positive} distributions (pi≥1/2+Δp_i\ge1/2+Δpi​≥1/2+Δ) to within additive error εεε. We prove an upper bound of O~ ⁣(ρΔε+1Δε)\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)O~(Δερ​​+Δε​1​) queries, achieving a quadratic speedup over the classical sample complexity. % of Θ(ρ/Δ2ε2)Θ(ρ/Δ^2ε^2)Θ(ρ/Δ2ε2). Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of Ω(ρ/(Δε))Ω(\sqrtρ/(Δε))Ω(ρ​/(Δε)) via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap Δ=Θ(1)Δ=Θ(1)Δ=Θ(1), which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to O~(ρε+1ε)\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)O~(ερ​​+ε​1​) and Ω(ρε)Ω(\frac{\sqrtρ}ε)Ω(ερ​​), thereby characterizing the query complexity of quantum counting with bounded-error oracles.
In the quantum linear systems problem (QLSP), we are given query access to a ddd-sparse N×NN\times NN×N matrix AAA with condition number κκκ, and the ability to prepare a quantum state proportional to a vector b⃗\vec bb. The goal is to output an εεε-approximation to the quantum state proportional to the solution x⃗\vec xx of Ax⃗=b⃗A\vec{x}=\vec{b}Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog⁡(1/ε))O(κd\log(1/ε))O(κdlog(1/ε)) and κd(κd/ε)o(1)κ\sqrt d(κd/ε)^{o(1)}κd​(κd/ε)o(1), while the best known lower bounds were Ω(κlog⁡(1/ε))Ω(κ\log(1/ε))Ω(κlog(1/ε)) and Ω(κd)Ω(κ\sqrt d)Ω(κd​). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog⁡(1/ε))Θ(κ\sqrt d\log(1/ε))Θ(κd​log(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×NN\times NN×N unitary can be implemented with bounded error using O(N)O(\sqrt N)O(N​) queries to its matrix entries.
This thesis studies strengths and weaknesses of quantum computers. In the first part we present three contributions to quantum algorithms. 1) consider a search space of N elements. One of these elements is "marked" and our goal is to find this. We describe a quantum algorithm to solve this problem using essentially sqrt{N} queries and other operations, improving over the gate count of Grover's algorithm. 2) We give a succinct characterization of quantum algorithms in terms of polynomials, and develop a new technique for showing upper and lower bounds on quantum query complexity based on this. 3) One generic technique used to compute the minimum of a given function is "gradient descent". We present a quantum gradient-calculation algorithm and a gradient-optimization algorithm that is quadratically faster than classical algorithms. In the second part of this thesis we look at quantum learning theory. 1) We survey quantum learning theory, describing the main results known for three models of learning, using classical as well as quantum data: exact learning from membership queries, the probably approximately correct (PAC) learning model, and the agnostic learning model. 2) We then consider if a quantum learner can PAC-learn a given concept class from fewer quantum examples. We give a negative answer by showing that quantum examples are not more powerful than classical random examples, both for PAC learning and for agnostic learning.
Perceptrons, which perform binary classification, are the fundamental building blocks of neural networks. Given a data set of size NNN and margin $\ensuremath{\gamma}$ (how well the given data are separated), the query complexity of the best-known quantum training algorithm scales as either $(\sqrt{N}/{\ensuremath{\gamma}}^{2})log(1/{\ensuremath{\gamma}}^{2})$ or $N/\sqrt{\ensuremath{\gamma}}$, which is achieved by a hybrid of classical and quantum search. In this paper, we improve the version space quantum training method for perceptrons such that the query complexity of our algorithm scales as $\sqrt{N/\ensuremath{\gamma}}$. This is achieved by constructing an oracle for the perceptrons using quantum counting of the number of data elements that are correctly classified. Once such an oracle is constructed, bounded-error quantum search can be used to search over the hyperplane instances. The optimality of our algorithm is proven by reducing the evaluation of a two-level and-or tree (for which the query complexity lower bound is known) to a multicriterion search. Our quantum training algorithm can be generalized to train more complex machine learning models such as neural networks, which are built on a large number of perceptrons.