ACM Prize awarded to pioneer in quantum computing

ACM, the Association for Computing Machinery, today announced that Scott Aaronson has been named the recipient of the 2020 ACM Prize in Computing for groundbreaking contributions to quantum computing. Aaronson is the David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin.

The goal of quantum computing is to harness the laws of quantum physics to build devices that can solve problems that classical computers either cannot solve, or not solve in any reasonable amount of time. 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 helped develop the concept of quantum supremacy, which denotes the milestone that is achieved when a quantum device can solve a problem that no classical computer can solve in a reasonable amount of time. Aaronson established many of the theoretical foundations of quantum supremacy experiments. Such experiments allow scientists to give convincing evidence that quantum computers provide exponential speedups without having to first build a full fault-tolerant quantum computer.

The ACM Prize in Computing recognizes early-to-mid-career computer scientists whose research contributions have fundamental impact and broad implications. The award carries a prize of $250,000, from an endowment provided by Infosys Ltd.

“Few areas of technology have as much potential as quantum computation,” said ACM President Gabriele Kotsis. “Despite being at a relatively early stage in his career, Scott Aaronson is esteemed by his colleagues for the breadth and depth of his contributions. He has helped guide the development of this new field, while clarifying its possibilities as a leading educator and superb communicator. Importantly, his contributions have not been confined to quantum computation, but have had significant impact in areas such as computational complexity theory and physics.”

Notable Contributions
Boson Sampling: In the paper “The Computational Complexity of Linear Optics,” Aaronson and co-author Alex Arkhipov gave evidence that rudimentary quantum computers built entirely out of linear-optical elements cannot be efficiently simulated by classical computers.

Aaronson has since explored how quantum supremacy experiments could deliver a key application of quantum computing, namely the generation of cryptographically random bits.

Fundamental Limits of Quantum Computers: In his 2002 paper “Quantum lower bound for the collision problem,” Aaronson 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.

Classical Complexity Theory: Aaronson 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.

Making Quantum Computing Accessible: Beyond his technical contributions, Aaronson is credited with making quantum computing understandable to a wide audience. Through his many efforts, he has become recognized as a leading spokesperson for the field. He maintains a popular blog, Shtetl Optimized, where he explains timely and exciting topics in quantum computing in a 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.

Aaronson also authored Quantum Computing Since Democritus, a respected book on quantum computing, written several articles for a popular science audience, and presented TED Talks to dispel misconceptions and provide the public with a more accurate overview of the field.

“Infosys is proud to fund the ACM Prize in Computing and we congratulate Scott Aaronson on being this year’s recipient,” said Pravin Rao, COO of Infosys. “When the effort to build quantum computation devices was first seriously explored in the 1990s, some labeled it as science fiction. While the realization of a fully functional quantum computer may still be in the future, this is certainly not science fiction. The successful quantum hardware experiments by Google and others have been a marvel to many who are following these developments. Scott Aaronson has been a leading figure in this area of research and his contributions will continue to focus and guide the field as it reaches its remarkable potential.”

###

Scott Aaronson is the David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin. His primary area of research is theoretical computer science, and his research interests center around the capabilities and limits of quantum computers, and computational complexity theory more generally.

A graduate of Cornell University, Aaronson earned a PhD in Computer Science from the University of California, Berkeley. His honors include the Tomassoni-Chisesi Prize in Physics (2018), a Simons Investigator Award (2017), and the Alan T. Waterman Award of the National Science Foundation (2012).

The ACM Prize in Computing recognizes an early to mid-career fundamental innovative contribution in computing that, through its depth, impact and broad implications, exemplifies the greatest achievements in the discipline. The award carries a prize of $250,000. Financial support is provided by an endowment from Infosys Ltd. The ACM Prize in Computing was previously known as the ACM-Infosys Foundation Award in the Computing Sciences from 2007 through 2015. ACM Prize recipients are invited to participate in the Heidelberg Laureate Forum, an annual networking event that brings together young researchers from around the world with recipients of the ACM A.M. Turing Award, the Abel Prize, the Fields Medal, and the Nevanlinna Prize.

ACM, the Association for Computing Machinery, is the world’s largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field’s challenges. ACM strengthens the computing profession’s collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.

Infosys is a global leader in next-generation digital services and consulting. We enable clients in 46 countries to navigate their digital transformation. With over three decades of experience in managing the systems and workings of global enterprises, we expertly steer our clients through their digital journey. We do it by enabling the enterprise with an AI-powered core that helps prioritize the execution of change. We also empower the business with agile digital at scale to deliver unprecedented levels of performance and customer delight. Our always-on learning agenda drives their continuous improvement through building and transferring digital skills, expertise, and ideas from our innovation ecosystem.