|
Friday, June 18, 2010 |
|
|
|
|
Quantum proofs for classical theorems |
|
|
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 by Andrew Drucker and myself, which is available at http://arxiv.org/abs/0910.3376 |