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.