Spring 2020

The Quantum Wave in Computing

Jan. 14May 15, 2020

Quantum computation is entering an exciting new period. Small- to medium-scale quantum computers are around the corner, and the biggest upcoming challenges are expected to be algorithmic. The first major challenge is identifying what kinds of computational tasks such computers will be useful for, given that for the foreseeable future, the scale issue will be compounded by minimal or nonexistent error correction. The second challenge is the testing of such devices, as direct simulation by classical computers is all but impossible and running a trace on the quantum program is ruled out by the basic laws of quantum physics.

Providing answers to these questions requires a collaboration between classical theoretical computer science and physics, chemistry, and mathematics. On the quantum algorithms front, there are great challenges in proposals for quantum machine learning and quantum annealing, with connections to classical machine learning, algorithms for low-rank matrix completion, and MCMC algorithms. The most promising algorithmic application for quantum computers in the long run, their "killer app," is expected to be the simulation of quantum systems and quantum chemistry.

On the theoretical computer science end, existing work on testing quantum devices has already led to exciting connections with the theory of interactive proof systems and theoretical cryptography. These connections will evolve into a beautiful and deep theory as the challenges in complexity theory, cryptography, and security raised by interactions with quantum devices are more systematically explored.

This semester-long program brought together researchers from computer science, physics, chemistry, and mathematics to collaborate on formalizing and tackling these questions.


Andrew Childs (University of Maryland), Ignacio Cirac (Max-Planck-Institut für Quantenoptik), Umesh Vazirani (UC Berkeley), Thomas Vidick (California Institute of Technology)

Long-Term Participants (including Organizers):

Scott Aaronson (University of Texas at Austin), Dorit Aharonov (Hebrew University of Jerusalem), Gorjan Alagic (QuICS, University of Maryland), Ehud Altman (UC Berkeley), Anurag Anshu (Institute for Quantum Computing), Boaz Barak (Harvard University), Dan Bernstein (University of Illinois at Chicago and Ruhr University Bochum), Dan Boneh (Stanford University), Adam Bouland (UC Berkeley), Zvika Brakerski (Weizmann Institute of Science), Fernando Brandao (California Institute of Technology), Sergey Bravyi (IBM T.J. Watson Research Center), Andrew Childs (University of Maryland), Isaac Chuang (MIT), Matthew Coudron (University of Waterloo), Elizabeth Crosson (University of New Mexico), David DiVincenzo (RWTH Aachen), Vedran Dunjko (University of Leiden), Kirsten Eisentrager (Penn State), Jens Eisert (Freie Universität Berlin), Bill Fefferman (University of Chicago), Sanjam Garg (UC Berkeley), Sevag Gharibian (University of Padderborn), Daniel Gottesman (Perimeter Institute), Sean Hallgren (Pennsylvania State University), Patrick Hayden (Stanford University), Martin Head-Gordon (UC Berkeley), Nick Hunter-Jones (Perimeter Institute), Sandy Irani (UC Irvine), Stacey Jeffery (Centrum Wiskunde & Informatica), Iordanis Kerenidis (CNRS - Université Paris Diderot & QC Ware), Robin Kothari (Microsoft Research), Greg Kuperberg (UC Davis), Tanja Lange (Technische Universiteit Eindhoven), Debbie Leung (University of Waterloo), Lin Lin (UC Berkeley), Guang-Hao Low (Microsoft Research), Nick Mayhall (Virginia Tech), Joel Moore (UC Berkeley), Prasad Raghavendra (UC Berkeley), Ben Reichardt (University of Southern California), Christian Schaffner (University of Amsterdam), Norbert Schuch (Max-Planck Institute of Quantum Optics), Mario Szegedy (Alibaba Cloud Quantum Lab), Barbara Terhal (Delft University of Technology), Umesh Vazirani (UC Berkeley), Thomas Vidick (California Institute of Technology), Birgitta Whaley (UC Berkeley), Alec White (Caltech), James Whitfield (Dartmouth College), Nathan Wiebe (University of Washington), Xiaodi Wu (Massachusetts Institute of Technology), Norman Yao (UC Berkeley), Penghui Yao (Nanjing University), Michael Zaletel (UC Berkeley)

Research Fellows:

Alex Bredariol Grilo (CWI and QuSoft), Andrea Coladangelo (Caltech), Yfke Dulek (University of Amsterdam), András Gilyén (Caltech; Google Research Fellow), Urmila Mahadev (Microsoft Research; Microsoft Research Fellow), Saeed Mehraban (Massachusetts Institute of Technology), Henry Yuen (University of Toronto)

Visiting Graduate Students and Postdocs:

Thomas Espitau (Rennes University), Dhiraj Holden (MIT), Jonas Landman (University of Paris), Jin-Peng Liu (University of Maryland), Alessandro Luongo (University of Paris), Christian Majenz (University of Amsterdam), Tony Metger (Caltech), Hamoon Mousavi (University of Toronto), Lorenz Panny (Eindhoven University of Technology), Alexander Poremba (Caltech), Kanav Setia (Dartmouth College), Omri Shmueli (Tel Aviv University), Mehdi Soleimanifar (MIT), Jana Sotakova (QuSoft and University of Amsterdam), Yuan Su (University of Maryland), Arkin Tikku (University of Sydney)


Monday, Jan. 27Friday, Jan. 31, 2020


Thomas Vidick (California Institute of Technology; chair), Andrew Childs (University of Maryland), Ignacio Cirac (Max-Planck-Institut für Quantenoptik), Umesh Vazirani (UC Berkeley)
Saturday, Feb. 22Monday, Feb. 24, 2020


Stacey Jeffery (Centrum Wiskunde & Informatica), Elena Kirshanova (Immanuel Kant Baltic Federal University), Vadim Lyubashevsky (IBM Research)
Tuesday, Feb. 25Friday, Feb. 28, 2020


Iordanis Kerenidis (CNRS - Université Paris Diderot & QC Ware; chair), Fernando Brandao (California Institute of Technology), Stacey Jeffery (Centrum Wiskunde & Informatica)
Monday, Mar. 30Thursday, Apr. 2, 2020


Henry Yuen (University of Toronto; chair), Dorit Aharonov (Hebrew University of Jerusalem), Yael Kalai (Microsoft Research New England), Thomas Vidick (California Institute of Technology)
Monday, May 4Friday, May 8, 2020


David DiVincenzo (RWTH Aachen; chair), Ignacio Cirac (Max-Planck-Institut für Quantenoptik), Barbara Terhal (Delft University of Technology)
Monday, Jul. 12Friday, Jul. 16, 2021


Andrew Childs (University of Maryland), Ignacio Cirac (Max-Planck-Institut für Quantenoptik), Umesh Vazirani (UC Berkeley), Thomas Vidick (California Institute of Technology)

 Subscribe to the program calendar.

Past Internal Program Activities

Tuesday, May 12th, 11:00 am12:00 pm
Lin Lin (UC Berkeley)
Tuesday, April 28th, 11:00 am12:00 pm
Yuan Su (UMD)
Tuesday, April 21st, 11:00 am12:00 pm
Ronald de Wolf (QuSoft, CWI and University of Amsterdam)
Friday, March 27th, 10:15 am11:15 am
Friday, March 20th, 9:00 am10:00 am
Tuesday, March 17th, 4:00 pm5:00 pm
Chris Schaffner (University of Amsterdam & QuSoft)
Tuesday, March 10th, 4:00 pm5:00 pm
Andrea Coladangelo (Simons Institute Fellow)
Tuesday, February 18th, 4:00 pm5:00 pm
Robin Kothari (Microsoft Research)