It is known that the dual of the general adversary bound can be used to build quantum query algorithms with optimal complexity. Despite this result, not many quantum algorithms have been designed this way. This paper shows another example of such algorithm. We use the learning graph technique from arXiv:1105.4024 to give a quantum algorithm for $k$-distinctness problem that runs in $o(n^{3/4})$ queries, for a fixed $k$, given some prior knowledge on the structure of the input. The best known quantum algorithm for the unconditional problem uses $O(n^{k/(k+1)})$ queries.
It is known that the dual of the general adversary bound can be used to build quantum query algorithms with optimal complexity. Despite this result, not many quantum algorithms have been designed this way. This paper shows another example of such algorithm. We use the learning graph technique from arXiv:1105.4024 to give a quantum algorithm for k-distinctness problem that runs in o(n3/4) queries, for a fixed k, given some prior knowledge on the structure of the input. The best known quantum algorithm for the unconditional problem uses O(nk/(k+1)) queries.
We present a quantum algorithm solving the k-distinctness problem in O(n1−2k−2/(2k−1)) queries with a bounded error. This improves the previous O(nk/(k+1))-query algorithm by Ambainis. The construction uses a modified learning graph approach. Compared to the recent paper by Belovs and Lee arXiv:1108.3022, the algorithm doesn't require any prior information on the input, and the complexity analysis is much simpler. Additionally, we introduce an O(nα1/6) algorithm for the graph collision problem where α is the independence number of the graph.
In the thesis, we use a recently developed tight characterisation of quantum query complexity, the adversary bound, to develop new quantum algorithms and lower bounds. Our results are as follows: * We develop a new technique for the construction of quantum algorithms: learning graphs. * We use learning graphs to improve quantum query complexity of the triangle detection and the k-distinctness problems. * We prove tight lower bounds for the k-sum and the triangle sum problems. * We construct quantum algorithms for some subgraph-finding problems that are optimal in terms of query, time and space complexities. * We develop a generalisation of quantum walks that connects electrical properties of a graph and its quantum hitting time. We use it to construct a time-efficient quantum algorithm for 3-distinctness.
We study the complexity of quantum query algorithms that make p queries in parallel in each timestep. This model is in part motivated by the fact that decoherence times of qubits are typically small, so it makes sense to parallelize quantum algorithms as much as possible. We show tight bounds for a number of problems, specifically Theta((n/p)^{2/3}) p-parallel queries for element distinctness and Theta((n/p)^{k/(k+1)} for k-sum. Our upper bounds are obtained by parallelized quantum walk algorithms, and our lower bounds are based on a relatively small modification of the adversary lower bound method, combined with recent results of Belovs et al. on learning graphs. We also prove some general bounds, in particular that quantum and classical p-parallel complexity are polynomially related for all total functions f when p is small compared to f's block sensitivity.
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.
The Element Distinctness problem is to decide whether each character of an input string is unique. The quantum query complexity of Element Distinctness is known to be Θ(N2/3); the polynomial method gives a tight lower bound for any input alphabet, while a tight adversary construction was only known for alphabets of size Ω(N2). We construct a tight Ω(N2/3) adversary lower bound for Element Distinctness with minimal non-trivial alphabet size, which equals the length of the input. This result may help to improve lower bounds for other related query problems.