We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether $S$ is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.
We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether S is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties.
We study the quantum query complexity of computing a semigroup product x1⋯xn, when one query reveals one input element and the multiplication table is given. For a finite aperiodic semigroup of size N−1, the argument of Aaronson, Grier, and Schaeffer gives an upper bound of n(Nlog(nN+2))O(N) queries.
To obtain query bounds that reflect algebraic structure, we study the product breadth β: the smallest bound such that every input word has a subsequence of at most β letters with the same product.
For nontrivial finite commutative aperiodic monoids, the bounded-error quantum query complexity is Θ(min{n,nβ}), and is thus characterized by product breadth. We further show that if such a monoid M has aperiodicity index k (the least positive integer satisfying xk=xk+1 for every x∈M), then β=O(klog(∣M∣+1)loglog(∣M∣+2)).
For monoids with a stable partial order in which the identity is the minimum element, we prove that the bounded-error quantum query complexity is at most n+1((β+2)log(n+2))O(log(β+2)).
For arbitrary finite aperiodic semigroups of order N−1, we improve the bound of Aaronson, Grier, and Schaeffer, obtaining a bounded-error quantum query complexity of at most min{n,nlogO((Nlog(N+2))1/3)(n+2)}. The dependence on semigroup size is nearly tight: the bounded-depth Dyck lower bound of Ambainis et al. yields aperiodic monoids requiring n2Ω(N1/3) quantum queries in the relevant parameter range.
Motivated by the quantum algorithm for testing commutativity of black-box groups (Magniez and Nayak, 2007), we study the following problem: Given a black-box finite ring by an additive generating set and a multilinear polynomial over that ring, also accessed as a black-box function (we allow the indeterminates of the polynomial to be commuting or noncommuting), we study the problem of testing if the polynomial is an \emph{identity} for the given ring. We give a quantum algorithm with query complexity sub-linear in the number of generators for the ring, when the number of indeterminates of the input polynomial is small (ideally a constant). Towards a lower bound, we also show a reduction from a version of the collision problem (which is well studied in quantum computation) to a variant of this problem.
Suppose we have k matrices of size n by n. We are given an oracle that knows all the entries of k matrices, that is, we can query the oracle an (i,j) entry of the l-th matrix. The goal is to test if each pair of k matrices commute with each other or not with as few queries to the oracle as possible. In order to solve this problem, we use a theorem of Mario Szegedy (quant-ph/0401053) that relates a hitting time of a classical random walk to that of a quantum walk. We also take a look at another method of quantum walk by Andris Ambainis (quant-ph/0311001). We apply both walks into triangle finding problem (quant-ph/0310134) and matrix verification problem (quant-ph/0409035) to compare the powers of the two different walks. We also present Ambainis's method of lower bounding technique (quant-ph/0002066) to obtain a lower bound for this problem. It turns out Szegedy's algorithm can be generalized to solve similar problems. Therefore we use Szegedy's theorem to analyze the problem of matrix set commutativity. We give an O(k^{4/5}n^{9/5}) algorithm as well as a lower bound of Omega(k^{1/2}n). We generalize the technique used in coming up with the upper bound to solve a broader range of similar problems. This is probably the first problem to be studied on the quantum query complexity using quantum walks that involves more than one parameter, here, k and n.
In this thesis we provide new upper and lower bounds on the quantum query complexity of a diverse set of problems. Specifically, we study quantum algorithms for Hamiltonian simulation, matrix multiplication, oracle identification, and graph-property recognition. \n \nFor the Hamiltonian simulation problem, we provide a quantum algorithm with query complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a new quantum algorithm for implementing unitary matrices that can be written as linear combinations of efficiently implementable unitary gates. This algorithm uses a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. \n \nIn the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set of size M, and our task is to identify x. We present the first quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2-norm semidefinite program. \n \nWe then study the quantum query complexity of matrix multiplication and related problems over rings, semirings, and the Boolean semiring in particular. Our main result is an output-sensitive algorithm for Boolean matrix multiplication that multiplies two n x n Boolean matrices with query complexity O(n sqrt{l}), where l is the sparsity of the output matrix. The algorithm is based on a reduction to the graph collision problem and a new algorithm for graph collision. \n \nFinally, we study the quantum query complexity of minor-closed graph properties and show that most minor-closed properties---those that cannot be characterized by a finite set of forbidden subgraphs---have quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be solved strictly faster, with o(n^{3/2}) queries. Our lower bound is based on a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems.
Motivated by the quantum algorithm in \cite{MN05} for testing commutativity of black-box groups, we study the following problem: Given a black-box finite ring R=∠r1,...,rk where {r1,r2,...,rk} is an additive generating set for R and a multilinear polynomial f(x1,...,xm) over R also accessed as a black-box function f:Rm→R (where we allow the indeterminates x1,...,xm to be commuting or noncommuting), we study the problem of testing if f is an \emph{identity} for the ring R. More precisely, the problem is to test if f(a1,a2,...,am)=0 for all ai∈R. We give a quantum algorithm with query complexity O(m(1+α)m/2km+1m) assuming k≥(1+1/α)m+1. Towards a lower bound, we also discuss a reduction from a version of m-collision to this problem. We also observe a randomized test with query complexity 4mmk and constant success probability and a deterministic test with km query complexity.
We consider the problem of testing the commutativity of a black-box group specified by its k generators. The complexity (in terms of k) of this problem was first considered by Pak, who gave a randomized algorithm involving O(k) group operations. We construct a quite optimal quantum algorithm for this problem whose complexity is in O (k^{2/3}). The algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Omega(k^{2/3}), we give a reduction from a special case of Element Distinctness to our problem. Along the way, we prove the optimality of the algorithm of Pak for the randomized model.