Tutte seminar - Ronald de Wolf

Quantum proofs for classical theorems

Abstract:

Quantum computing provides us with new algorithms and communication protocols, but the techniques developed in this field can also be used as tools for analyzing and proving results about *classical* algorithms and mathematical constructions. This is analogous to the use of complex numbers to prove statements about real functions, or the use of the probabilistic method. This talk will survey some recent examples of this phenomenon, in the areas of coding theory and polynomial approximations. It will cover a subset of the recent survey paper, Quantum Proofs for Classical Theorems, by Andrew Drucker and myself, which is available at the Cornell University Library.