Dr. Scott J Aaronson

Digital Library

ACM Prize in Computing

USA - 2020


For groundbreaking contributions to quantum computing

Scott Aaronson is a pioneer in the field of quantum computing. Quantum computing centers on leveraging the laws of quantum physics to build computational devices that can solve classes of problems that are intractable on classical computers. Aaronson showed how results from computational complexity theory can provide new insights into the laws of quantum physics, and brought clarity to what quantum computers will and will not be able to do. Aaronson's work established the theoretical foundations of "quantum supremacy" experiments. Such experiments allow scientists give evidence that quantum computers provide exponential speedups, without having to first build a full fault-tolerant quantum computer. Aaronson's work on Boson sampling, with his student Alex Arkhipov, is a centerpiece of such analyses. Aaronson has since explored how these experiments could deliver a key application of quantum computing, namely the generation of cryptographically random bits.

Aaronson also established several fundamental limits of quantum computers. Most notably, he proved the quantum lower bound for the collision problem, which was a major open problem for years. This work bounds the minimum time for a quantum computer to find collisions in many-to-one functions, giving evidence that a basic building block of cryptography will remain secure for quantum computers.

Aaronson has also made fundamental contributions to classical complexity theory. He is well-known for his work on "algebrization" a technique he invented with Avi Wigderson to understand the limits of algebraic techniques for separating and collapsing complexity classes.

Beyond his technical contributions, Aaronson is credited with making quantum computing accessible to a wider audience. He maintains a popular blog, where he explains some of the deepest and unintuitive ideas in quantum computing in a remarkably simple and effective way. His posts, which range from fundamental theory questions to debates about current quantum devices, are widely read and trigger many interesting discussions. He has also written a major book on quantum computing and several articles for a popular science audience. He is a great expositor and has become a major spokesperson for quantum computing.

Press Release

ACM Fellows

USA - 2019


For contributions to quantum computing and computational complexity

Press Release