# Hein Röhrig's PhD Thesis

Quantum Query Complexity and Distributed Computing

## Abstract

In complexity theory, the strengths and limitations of computers
are investigated on abstract models of computation. The choice of
these models is governed by three considerations: (1) how close is
the model to existing computers or computers that could be built in
principle? (2) how well does it lend itself to proving interesting
properties of computers? (3) how elegant is the model
mathematically?

Quantum computation appeals to all three criteria. In functional
analysis, quantum mechanics has a beautiful mathematical
underpinning, which benefits quantum computing through new
applications of linear algebra and matrix analysis. Nowadays it is
a widely-held belief that the physical theory of “quantum
mechanics” describes reality accurately at very small scales
of length, time, and energy. Where classical probabilistic Turing
machines may be seen as capturing the power of computers operating
according to finite- precision classical physics, the computational
model of “quantum circuits” aims at modeling what
realistic computers in a quantum mechanical world can do. Query
complexity, a variant of time complexity, has a close analogue for
quantum computers; as in the classical case, our current
mathematical tools are more amenable to this restricted complexity
measure than to general time complexity. Sometimes, the
implications of quantum query complexity shed new light even on
classical complexity theory.

This thesis investigates the properties and applications of
quantum query complexity and the related quantum communication
complexity. It suggests new cryptographic protocols and new
experiments for probing the predictions of quantum mechanics.
Quantum states are very sensitive; this thesis examines ways to
deal with imperfections and errors in a number of different
situations.

## Getting the thesis

Contact me for a copy of the thesis.