Quantum Proofs for Classical Theorems

Alongside the development of quantum algorithms and quantum complexity theory, in recent years quantum techniques have also proved instrumental in obtaining results in diverse classical (non-quantum) areas, such as coding theory, communication complexity, and polynomial approximations. Just like some results about real functions are most easily proved via complex numbers, and many results in combinatorics are most easily proved using the "probabilistic method", this development uses the mathematical framework provided by quantum information theory to analyze classical questions.  Of course, no physical quantum computer need ever be built for this application! In this talk I will survey this use of quantum information techniques as a proof tool, with a focus on two specific applications: lower bounds on certain error-correcting codes, and on the size of linear programs for hard optimization problems such as Traveling Salesman. (The talk is partially based on this survey paper by Andrew Drucker and myself: http://theoryofcomputing.org/articles/gs002/gs002.pdf)