Scott Wins a Prize

Scott Answers Big Questions source

Scott Aaronson has just been named the 2020 ACM Prize in Computing for groundbreaking contributions to quantum computing, Penrose’s comment notwithstanding. The prize citation also credits Scott’s multifaceted public outreach for making our fields accessible to many.

Today Ken and I send congrats to Scott for this singular honor.

The ACM Prize was founded in 2007. It does not have the age limit of a Fields Medal but is similarly positioned. Scott joins a impressive list of winners:

Not Why He Did Win?

Scott perhaps could have won for the following three accomplishments:

His wonderful blog. About the prize, he says there:

Last week I got an email from Dina Katabi, my former MIT colleague, asking me to call her urgently. Am I in trouble? … Luckily, Dina only wanted to tell me that I’d been selected to receive the 2020 ACM Prize in Computing, a mid-career award founded in 2007 that comes with $250,000 from Infosys. Not the Turing Award but I’d happily take it! And I could even look back on 2020 fondly for something.

His book on quantum:

Democritus was known as “the laughing philosopher,” though some other depictions of the laugh range from world-weary to pained.

His sense of humor.

This is my returning thanks, in a way. Ken says that what impresses him is not the floor-length garment but the floor-length blackboard. Both of us hope that after handling “For All” and “Exists,” he went on to solve the problem of placing “Not” in English—for instance, “Why He Did Not Win?” is more grammatically natural but wrong.

Why He Did Win?

Scott perhaps did win for the following four accomplishments:

The theoretical foundations of the sampling-based quantum supremacy experiments—joint with Lijie Chen. Ken adds that this paper is also known for the “Schrödinger” and “Feynman” nomenclature for simulating quantum classically, and the idea of hybridizing those approaches.

The algebrization barrier in complexity theory—joint with Avi Wigderson. About Avi’s talk on this at my 60th birthday workshop, Ken wrote that it “planted a Monty Python foot on further progress” on lower bounds.

Limitations on quantum computers—work on the quantum lower bound for the collision problem.

The opposite of limitations—getting quantum advantage from the simplest of components in linear optics. And this, likewise joint with Alex Arkhipov. This approach has been followed by many, notably last December by a large team in China. We just wrote about envy of big experiments, but Scott has arguably done the most of anyone in our field to launch them.

There are many more. But maybe the one that will get us all rich is Scott’s work on quantum money. Qubitcoin, anyone?

Open Problems

Wonderful to add Scott to the list of winners of this award. Congrats again.

We also congratulate Paul Beame on the SIGACT Distinguished Service Award.