Quantum Query Complexity and Distributed Computing

Doctoral dissertation (PhD Thesis) of Hein Röhrig

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.