Rolf Landauer and Charles H. Bennett Award talk on the mathematics of quantum information, and the development of new algorithmic primitives for quantum computers*

The field of quantum algorithms has developed around a set of basic building blocks such as the quantum Fourier transform, amplitude amplification and so on, which are then combined with classical algorithms in order to achieve quantum speedups. Likewise quantum information combines classical tools such as Shannon's theorem with new elements such as teleportation and super-dense coding. Ultimately we hope that these primitives both tell us what we can do with a quantum computing or communication network, but also something about the nature of quantum information and how it differs from classical information.

In this talk, I will describe some of my own contributions to quantum algorithms and information theory, and will discuss their significance both operationally and conceptually.