The Polynomial Method in Quantum and Classical Computing

In 1889, A. A. Markov proved a powerful result about low-degree real polynomials: roughly speaking, that such polynomials cannot have a sharp jump followed by a long, relatively flat part. A century later, this result - as well as other results from the field of approximation theory - came to play a surprising role in classical and quantum complexity theory. In this article, the author tries to tell this story in an elementary way, beginning with classic results in approximation theory and ending with some recent applications.

Authors

• Scott Aaronson

Keywords

• Quantum computing
• Polynomials
• Quantum mechanics
• Complexity theory
• Approximation methods
• Computational complexity
• Boolean functions
• Computer science
• Numerical analysis
• Classical Computer
• Polynomial Method
• Complex Communication
• Approximation Theory
• Boolean Function
• Quantum Algorithms
• quantum