Summer 2022

Extended Reunion: The Quantum Wave in Computing

May 23Jun. 24, 2022

This extended reunion is for long-term participants in the program The Quantum Wave in Computing, held in the spring 2020 semester. It will provide an opportunity to meet old and new friends. Moreover, we hope that it will give everyone a chance to reflect on the progress made during the semester and since, and sketch in which directions the field should go in the future. In an effort to keep things informal and to encourage open discussion, none of the activities will be recorded. 

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 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.

Organizers: Umesh Vazirani (UC Berkeley; chair) Sandy Irani (UC Irvine), Urmila Mahadev (California Institute of Technology), James Whitfield (Dartmouth College), Henry Yuen (Columbia University)

Long-Term Participants (including Organizers):

Prabhanjan Ananth (UC Santa Barbara), Anurag Anshu (Harvard University), Daniel Bernstein (University of Illinois at Chicago and Ruhr University Bochum), Zvika Brakerski (Weizmann Institute of Science), Sergey Bravyi (IBM T.J. Watson Research Center), Alex Bredariol Grilo (CNRS), Yongshan Ding (Yale University), Bill Fefferman (University of Chicago), Joseph Fitzsimons (Horizon Quantum Computing), Xun Gao (Department of Physics, Harvard), Alexandru Gheorghiu (ETH Zurich), András Gilyén (Alfréd Rényi Institute of Mathematics), Daniel Gottesman (University of Maryland), Dominik Hangleiter (QuICS), Artur Izmaylov (University of Toronto), Robin Kothari (Microsoft Quantum), Greg Kuperberg (UC Davis), Jerry Li (Microsoft Research), Seth Lloyd (Massachusetts Institute of Technology), Urmila Mahadev (California Institute of Technology), Anand Natarajan (MIT), Ryan O'Donnell (Carnegie Mellon University), Bryan O'Gorman (UC Berkeley / NASA Ames), Ben Reichardt (University of Southern California), Norbert Schuch (University of Vienna), Mehdi Soleimanifar (MIT), Umesh Vazirani (UC Berkeley), Thomas Vidick (California Institute of Technology), Nathan Wiebe (University of Toronto), Henry Yuen (Columbia University)

Visiting Graduate Students and Postdocs:

Naresh Goud Boddu (National University of Singapore), Hsin-yuan Huang (California Institute of Technology), Jiaqing Jiang (California Institute of Technology), Robbie King (Caltech), William Kretschmer (UT Austin), Jiahui Liu (University of Texas Austin), Jin-Peng Liu (University of Maryland), Tony Metger (ETH Zürich), Seyyed Hamoon Mousavi Haji (Columbia University), Alexander Poremba (Caltech), Noah Shutty (Stanford University), Arkin Tikku (University of Sydney), Kianna Wan (Stanford University), Lisa Yang (Massachusetts Institute of Technology), Jiayu Zhang (California Institute of Technology), Tina Zhang (Massachusetts Institute of Technology), Shangnan Zhou (Stanford University)


Monday, Jun. 13Friday, Jun. 17, 2022


Shafi Goldwasser (UC Berkeley), Urmila Mahadev (California Institute of Technology), Vinod Vaikuntanathan (Massachusetts Institute of Technology), Umesh Vazirani (UC Berkeley), Henry Yuen (Columbia University)