Quantum Query Complexity and Distributed Computing
Hein Philipp Röhrig

Abstract:
Quantum Query Complexity and Distributed Computing
Hein Roehrig

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.