Theory of Computing Library
Graduate Surveys 2
Graduate Surveys 2
Quantum Proofs for Classical Theorems
Published: March 9, 2011 (54 pages)
Keywords: quantum arguments, quantum computing, quantum information, polynomial approximation
Categories: graduate survey, quantum computing, quantum information, polynomials, polynomial approximation
ACM Classification: F.1.2
AMS Classification: 81P68
Abstract: [Plain Text Version]
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. In this paper we survey these results and the quantum toolbox they use.