pdf icon
Theory of Computing Library
Graduate Surveys 2
Quantum Proofs for Classical Theorems
Published: March 9, 2011    (54 pages)
Download article from ToC site:
[PDF (472K)]    [PS (2214K)]    [PS.GZ (510K)]
[Source ZIP]
Keywords: quantum arguments, quantum computing, quantum information, 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.