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• Revised Nov 3, 2026 (v3)
v1 · Sep 30, 2026v2 · Oct 5, 2026v3 · Nov 3, 2026
arXivHTMLPDF

Abstract

Linear threshold functions (LTFs) are $\{-1,1\}$-valued functions $f_{w,θ}(x)=\text{sgn}(\langle w,x\rangle-θ)$, where $w\in\mathbb R^n$ has unit norm, $θ\in\mathbb R$, and $x\in\mathbb R^n$ or $\{-1,1\}^n$. If $θ=0$, the LTF is homogeneous, denoted $f_w=f_{w,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 $f_{w,θ}(x)$ at any chosen $x\in\mathbb R^n$, we learn an LTF with classification error at most $\varepsilon$ under the standard Gaussian distribution using $O(\log(n/\varepsilon))$ queries and $\widetilde{O}(n)$ other gates. Classically, $Ω(n\log(1/\varepsilon))$ queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF $f_w$ 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(\log k)$ queries, exponentially improving Belovs' $O(k^{1/4})$ upper bound. Our algorithm uses $O(n\log n\log k)$ gates and has $O(\log n\log k)$ non-oracle depth. Classical algorithms require $Ω(k\log(n/k))$ queries. (3) Suppose a unitary $U$ prepares discretized Gaussian quantum examples, corresponding to $\int_x\sqrt{γ_n(x)}|x\rangle|f_w(x)\rangle\,dx$. This is weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most $\varepsilon$ under the Gaussian distribution using $O(n^{1/4}/\sqrt{\varepsilon})$ applications of $U$ and $U^\dagger$ and $\widetilde{O}\!(\frac{n^{5/4}}{\sqrt{\varepsilon}}+\frac{n}{\varepsilon^2})$ other gates. Classically, $Ω(n/\varepsilon)$ 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.

AI Summary

The paper studies quantum learning of linear threshold functions $f_{w,\theta}(x)=\operatorname{sgn}(\langle w,x\rangle-\theta)$ in three oracle models, giving algorithms and matching quantum query lower bounds. With coherent membership queries at real inputs, general halfspaces can be learned to Gaussian classification error $\varepsilon$ using $\Theta(\log(n/\varepsilon))$ queries and $\widetilde O(n)$ non-oracle gates, versus a classical lower bound of $\Omega(n\log(1/\varepsilon))$. The algorithm implements an affine boundary-height function by coherent binary search, then recovers its gradient using Jordan’s algorithm. The lower bound uses a continuous-parameter multiplicative adversary argument. For Boolean membership queries to a Majority function on an unknown support of size at most $k$, exact support recovery takes $\Theta(\log k)$ queries, improving the previous $O(k^{1/4})$ upper bound. The construction uses explicit dual-adversary solutions expressed through Krawtchouk polynomials and a transducer implementation requiring $O(n\log n\log k)$ gates and $O(\log n\log k)$ non-oracle depth. For support size exactly $k$, the matching lower bound assumes $n\geq2k$. For homogeneous halfspaces, access to a discretized Gaussian quantum-example preparation unitary and its inverse gives optimal query complexity $\Theta(n^{1/4}/\sqrt\varepsilon)$, compared with $\Theta(n/\varepsilon)$ classical examples. A quantum Hermite transform isolates high-degree components encoding many copies of the weight state; amplitude amplification and tomography recover the direction. Gate complexity is $\widetilde O(n^{5/4}/\sqrt\varepsilon+n/\varepsilon^2)$. The lower bound combines hypercube testing with a quantum hybrid argument. This model requires inverse access, not merely example-state copies. Extensions to nonzero thresholds in the example model, other symmetric juntas, and polynomial threshold functions remain open.

Little sign of AI-generated textAI use disclosedStrong assumptions
Finally, GPT-6-Astra and Claude Fable 5.1 were used for help with proofreading.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
v2: In section 3, new optimal lower bound. Small improvements in the presentation v3: Added new optimal lower bounds in Section 3 and 5, added gate complexity upper bound in Section 4, and improved the presentation in several places

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

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

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 (LTFs) are {−1,1}\{-1,1\}{−1,1}-valued functions fw,θ(x)=sgn(⟨w,x⟩−θ)f_{w,θ}(x)=\text{sgn}(\langle w,x\rangle-θ)fw,θ​(x)=sgn(⟨w,x⟩−θ), where w∈Rnw\in\mathbb R^nw∈Rn has unit norm, θ∈Rθ\in\mathbb Rθ∈R, and x∈Rnx\in\mathbb R^nx∈Rn or {−1,1}n\{-1,1\}^n{−1,1}n. If θ=0θ=0θ=0, the LTF is homogeneous, denoted fw=fw,0f_w=f_{w,0}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)f_{w,θ}(x)fw,θ​(x) at any chosen x∈Rnx\in\mathbb R^nx∈Rn, we learn an LTF with classification error at most ε\varepsilonε under the standard Gaussian distribution using O(log⁡(n/ε))O(\log(n/\varepsilon))O(log(n/ε)) queries and O~(n)\widetilde{O}(n)O(n) other gates. Classically, Ω(nlog⁡(1/ε))Ω(n\log(1/\varepsilon))Ω(nlog(1/ε)) queries are required, giving an exponential quantum query speedup. (2) A homogeneous LTF fwf_wfw​ over {−1,1}n\{-1,1\}^n{−1,1}n whose kkk nonzero weights are equal and positive is Majority on the support of www. We identify this hidden support exactly using O(log⁡k)O(\log k)O(logk) queries, exponentially improving Belovs' O(k1/4)O(k^{1/4})O(k1/4) upper bound. Our algorithm uses O(nlog⁡nlog⁡k)O(n\log n\log k)O(nlognlogk) gates and has O(log⁡nlog⁡k)O(\log n\log k)O(lognlogk) non-oracle depth. Classical algorithms require Ω(klog⁡(n/k))Ω(k\log(n/k))Ω(klog(n/k)) queries. (3) Suppose a unitary UUU prepares discretized Gaussian quantum examples, 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 weaker than membership queries. Using the efficient quantum Hermite transform circuit, we learn homogeneous LTFs with classification error at most ε\varepsilonε under the Gaussian distribution using O(n1/4/ε)O(n^{1/4}/\sqrt{\varepsilon})O(n1/4/ε​) applications of UUU and U†U^\daggerU† and O~ ⁣(n5/4ε+nε2)\widetilde{O}\!(\frac{n^{5/4}}{\sqrt{\varepsilon}}+\frac{n}{\varepsilon^2})O(ε​n5/4​+ε2n​) other gates. Classically, Ω(n/ε)Ω(n/\varepsilon)Ω(n/ε) examples are needed, giving a quartic quantum speedup in nnn. We show that the quantum query complexities in all three cases are optimal by proving matching lower bounds.
The paper studies quantum learning of linear threshold functions fw,θ(x)=sgn⁡(⟨w,x⟩−θ)f_{w,\theta}(x)=\operatorname{sgn}(\langle w,x\rangle-\theta)fw,θ​(x)=sgn(⟨w,x⟩−θ) in three oracle models, giving algorithms and matching quantum query lower bounds.
With coherent membership queries at real inputs, general halfspaces can be learned to Gaussian classification error ε\varepsilonε using Θ(log⁡(n/ε))\Theta(\log(n/\varepsilon))Θ(log(n/ε)) queries and O~(n)\widetilde O(n)O(n) non-oracle gates, versus a classical lower bound of Ω(nlog⁡(1/ε))\Omega(n\log(1/\varepsilon))Ω(nlog(1/ε)). The algorithm implements an affine boundary-height function by coherent binary search, then recovers its gradient using Jordan’s algorithm. The lower bound uses a continuous-parameter multiplicative adversary argument.
For Boolean membership queries to a Majority function on an unknown support of size at most kkk, exact support recovery takes Θ(log⁡k)\Theta(\log k)Θ(logk) queries, improving the previous O(k1/4)O(k^{1/4})O(k1/4) upper bound. The construction uses explicit dual-adversary solutions expressed through Krawtchouk polynomials and a transducer implementation requiring O(nlog⁡nlog⁡k)O(n\log n\log k)O(nlognlogk) gates and O(log⁡nlog⁡k)O(\log n\log k)O(lognlogk) non-oracle depth. For support size exactly kkk, the matching lower bound assumes n≥2kn\geq2kn≥2k.
For homogeneous halfspaces, access to a discretized Gaussian quantum-example preparation unitary and its inverse gives optimal query complexity Θ(n1/4/ε)\Theta(n^{1/4}/\sqrt\varepsilon)Θ(n1/4/ε​), compared with Θ(n/ε)\Theta(n/\varepsilon)Θ(n/ε) classical examples. A quantum Hermite transform isolates high-degree components encoding many copies of the weight state; amplitude amplification and tomography recover the direction. Gate complexity is O~(n5/4/ε+n/ε2)\widetilde O(n^{5/4}/\sqrt\varepsilon+n/\varepsilon^2)O(n5/4/ε​+n/ε2). The lower bound combines hypercube testing with a quantum hybrid argument. This model requires inverse access, not merely example-state copies. Extensions to nonzero thresholds in the example model, other symmetric juntas, and polynomial threshold functions remain open.
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.
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.
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.
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.