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.
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.
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 two combinatorial problems. The first we call ``search with wildcards'': given an unknown n-bit string x, and the ability to check whether any subset of the bits of x is equal to a provided query string, the goal is to output x. We give a nearly optimal O(nlogn) quantum query algorithm for search with wildcards, beating the classical lower bound of Ω(n) queries. Rather than using amplitude amplification or a quantum walk, our algorithm is ultimately based on the solution to a state discrimination problem. The second problem we consider is combinatorial group testing, which is the task of identifying a subset of at most k special items out of a set of n items, given the ability to make queries of the form ``does the set S contain any special items?''\ for any subset S of the n items. We give a simple quantum algorithm which uses O(k) queries to solve this problem, as compared with the classical lower bound of Ω(klog(n/k)) queries.
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.
Pattern matching is one of the fundamental problems in Computer Science. Both the classic version of the problem as well as the more sophisticated version where wildcards can also appear in the input can be solved in almost linear time O~(n) using the KMP algorithm and Fast Fourier Transform, respectively. In 2000, Ramesh and Vinay~\cite{ramesh2003string} give a quantum algorithm that solves classic pattern matching in sublinear time and asked whether the wildcard problem can also be solved in sublinear time? In this work, we give a quantum algorithm for pattern matching with wildcards that runs in time O~(nk) when the number of wildcards is bounded by k for k≥n. This leads to an algorithm that runs in sublinear time as long as the number of wildcards is sublinear.
We are presented with a graph, G, on n vertices with m edges whose edge set is unknown. Our goal is to learn the edges of G with as few queries to an oracle as possible. When we submit a set S of vertices to the oracle, it tells us whether or not S induces at least one edge in G. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of O(mlogn) for a general graph G with m edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where G has maximum degree d and is O(1)-colorable, Montanaro and Shao presented an algorithm that learns the edges of G in at most O~(d2m3/4) quantum queries. This gives an upper bound of O~(m3/4) quantum queries when G is a matching or a Hamiltonian cycle, which is far away from the lower bound of Ω(m) queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where G has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in O~(m) quantum queries, matching the theoretical lower bound up to logarithmic factors.
The general adversary bound is a semi-definite program (SDP) that lower-bounds the quantum query complexity of a function. We turn this lower bound into an upper bound, by giving a quantum walk algorithm based on the dual SDP that has query complexity at most the general adversary bound, up to a logarithmic factor. In more detail, the proof has two steps, each based on "span programs," a certain linear-algebraic model of computation. First, we give an SDP that outputs for any boolean function a span program computing it that has optimal "witness size." The optimal witness size is shown to coincide with the general adversary lower bound. Second, we give a quantum algorithm for evaluating span programs with only a logarithmic query overhead on the witness size. The first result is motivated by a quantum algorithm for evaluating composed span programs. The algorithm is known to be optimal for evaluating a large class of formulas. The allowed gates include all constant-size functions for which there is an optimal span program. So far, good span programs have been found in an ad hoc manner, and the SDP automates this procedure. Surprisingly, the SDP's value equals the general adversary bound. A corollary is an optimal quantum algorithm for evaluating "balanced" formulas over any finite boolean gate set. The second result extends span programs' applicability beyond the formula-evaluation problem. We extend the analysis of the quantum algorithm for evaluating span programs. The previous analysis shows that a corresponding bipartite graph has a large spectral gap, but only works when applied to the composition of constant-size span programs. We show generally that properties of eigenvalue-zero eigenvectors in fact imply an "effective" spectral gap around zero. A strong universality result for span programs follows. A good quantum query algorithm for a problem implies a good span program, and vice versa. Although nearly tight, this equivalence is nontrivial. Span programs are a promising model for developing more quantum algorithms.