Computers are physical objects and thus obey the laws of physics. Although most computers nowadays are built of semiconductors governed by quantum effects, their computation is purely classical—at every instant the computer is in a classical state and the computational steps are fully deterministic. Quantum computers, on the other hand, are computers that exploit quantum effects to do computation. Unlike classical computers, they can be at any moment in a superposition of many classical states and perform several computations is parallel.
In 1994, Peter Shor discovered a ground-breaking polynomial time quantum algorithm for factoring integers, a task for which no efficient classical algorithm is known. In 1996, Lov Grover discovered another important quantum algorithm that searches an unordered database quadratically faster than the best classical algorithm. Since then, the field of quantum computing has significantly matured. Other important discoveries have also been made in related fields, such as quantum cryptography, information theory, error-correction codes, and communication complexity.
In this thesis, we investigate the power of quantum computers. We present a few new quantum algorithms, improve some quantum lower-bound techniques, and prove the first known quantum time-space tradeoffs.
The quantum search algorithm by Grover is very versatile and can be used as a subroutine in many classical algorithms. We apply it on the following graph problems: finding a maximal matching and finding a maximal flow in an integer network. In both cases we obtain a quantum algorithm that is polynomially faster than the best known classical algorithm.
We address the question of verifying whether a product of two n*n matrices is equal to a third one. This is easier than computing the actual matrix product, as there is a classical algorithm that runs in time O(n^2), whereas the best known matrix multiplication algorithm runs in time O(n^{2.376}). Our quantum algorithm for matrix verification is polynomially faster and it runs in time O(n^{5/3}).
A lower bound is a proof that some task cannot be computed faster than some value. There are two basic techniques for proving quantum lower bounds. The adversary method is based on the complexity of distinguishing inputs that lead to different outcomes. It is easy to use and often gives tight bounds, for example for the unordered search problem. The polynomial method expresses the acceptance probability of a quantum algorithm as a low-degree polynomial, and then bounds on the degree of approximate polynomials imply lower bounds on quantum computation. It is generally harder to apply, but gives stronger bounds for some problems.
Many variants of the adversary method were known. We clean up the forest and prove that there is just one method and that all known variants are just different formulations. We prove a limitation on the adversary bound in terms of the certificate complexity of the function, which implies that most of the best known lower bounds that are not known to be tight cannot be further improved by this method. We give tight formulas for adversary bounds of composite functions.
We prove tight direct product theorems for several functions. A DPT states that the complexity of computing k independent instances of a problem is k times bigger than the complexity of computing one instance, even if we are willing to only succeed with exponentially small probability. A statement of this type sounds plausible, however it is very hard to prove in general.
Besides answering a fundamental question about computation, DPT's have applications to time-space tradeoffs. A time-space tradeoff is a relation between the running time and space complexity of an algorithm. We use the polynomial method to obtain a DPT for the OR function, and apply it to get tight quantum time-space tradeoffs for sorting (in particular T^2 S = Theta(n^3), whereas T S = Theta(n^2) classically) and Boolean matrix multiplication, and also several communication-space tradeoffs. These are the first such tradeoffs known for quantum computation. We develop a new generalization of the adversary method in terms of analysis of subspaces of density matrices, and use it to get a DPT for all symmetric functions (functions that only depend on the number of ones in the input). This DPT implies a time-space tradeoff for the evaluation of solutions of systems of linear inequalities, which is tight and polynomially better than classical when the space is small.
Research for this dissertation was done at the Centrum voor Wiskunde en Informatica (CWI) in Amsterdam.