New Quantum Algorithms and Quantum Lower Bounds

Abstract:

The last decade witnessed a great surge of fruitful studies in the
new paradigm of quantum computing. Remarkable progress has been made
in all the areas including quantum algorithms, quantum complexity
theory, quantum error-correcting code, quantum information theory,
quantum cryptography and physical implementations of quantum
computers. However, quantum algorithm design, probably the most
important task in quantum computing, did not make as much progress
as people expected. This thesis aims at both designing new quantum
algorithms and studying why efficient quantum algorithms are so hard
to design by proving many lower bounds on quantum query complexity
for various problems.

We first review (and generalize) known techniques for designing
quantum algorithms and for proving quantum lower bounds. Using these
techniques, we then study the quantum query complexity for many
problems, including some specific problems such as Graph Matching
and other natural graph properties, the general tuple search, and
local search. We also study the lowest possible quantum query
complexity for a class of functions as a whole, such as graph
properties, circular functions, and functions invariant of a
transitive permutation group, where tight results are given in all
these cases.

Finally for the quantum lower bounds techniques themselves, we study
the main two techniques and show that they are incomparable in
power. For the most widely used one, which has a lot of parameters
to choose, we show limitations for it in terms of certificate
complexity. This implies that we cannot use the method to prove
better lower bounds for almost all known open problems in this area.