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.
Comments
v2: In section 3, new optimal lower bound. Small improvements in the presentation
Linear threshold functions are fw,θ(x)=sign(⟨x,w⟩−θ), where the weight vector w∈Rn is a unit vector, θ∈R is a threshold, and typically x∈Rn or x∈{−1,1}n. When θ=0, the LTF is called homogeneous, and we write 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:
Suppose we can make real-domain queries, meaning we can compute fw,θ(x) at any x∈Rn of our choice. We give a quantum algorithm that learns fw,θ up to Euclidean error ε using O(log(n/ε)) membership queries and O(n) other gates. Then we have also learned fw,θ up to error O(ε) when x is Gaussian. Classical algorithms need Ω(nlog(1/ε)) queries.
A homogeneous LTF fw 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 fw) using O(k1/4) queries. We give an exponential improvement, using O(logk) queries.
Suppose we have a unitary U that can produce (discretized) quantum examples under Gaussian measure, corresponding to ∫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 fw with error ε under the Gaussian distribution, using O(n1/4/ε) applications of U and U† and 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}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(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when 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→R the ratio of the maximum value of f to the maximum (over T∈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.
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.
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 p1,…,pm and a gap parameter Δ, the goal is to estimate the fraction ρ of \emph{positive} distributions (pi≥1/2+Δ) to within additive error ε. We prove an upper bound of O~(Δερ+Δε1) 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 Ω(ρ/(Δε)) 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 O~(ερ+ε1) and Ω(ερ), 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 d-sparse N×N matrix A with condition number κ, and the ability to prepare a quantum state proportional to a vector b. The goal is to output an ε-approximation to the quantum state proportional to the solution x of Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog(1/ε)) and κd(κd/ε)o(1), while the best known lower bounds were Ω(κlog(1/ε)) and Ω(κd). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×N unitary can be implemented with bounded error using 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 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.