Recent years have seen major advances in the ability to control quantum devices with dozens of qubits. The advent of so-called "Noisy Intermediate Scale Quantum" (NISQ) computers raises major algorithmic challenges. The goal of this workshop is to present current techniques and to help distill the key questions and theoretical models moving forward.

Workshop topics will include a discussion of the state of the art on the experimental front, together with an examination of the extent to which existing devices can be used to demonstrate a computational advantage in the near term.

One of the foremost applications of small, non fault-tolerant quantum computers is expected to be the simulation of physical systems. While discussing existing algorithms for quantum simulation, the workshop will focus on basic questions such as: What are the relevant problems? When can it be claimed that a system has been successfully simulated? And is there a rigorous theoretical basis for analog simulation?

Another potential area of application is quantum machine learning, and more generally, quantum optimization. Key questions include: What are realistic models for quantum machine learning algorithms? In particular, what are the prospects for a QRAM? When do quantum optimizers exhibit success patterns that distinguish them from classical techniques?

As quantum devices become sufficiently large (perhaps with more than 50 reliable qubits), it will become hard to simulate them. Sustained experimental progress will only be achievable if suitable testing and verification techniques are developed. The workshop will cover recent progress in leveraging the theory of interactive proofs for quantum device testing, including delegated computation and homomorphic encryption. In addition, the workshop will consider prospects for extending and expanding these techniques to solve several remaining challenges, including proving a quantum PCP theorem.

Invited Participants

Scott Aaronson (University of Texas at Austin), Dorit Aharonov (Hebrew University of Jerusalem), Ryan Babbush (Google, Inc.), Michael Ben-Or (Hebrew University of Jerusalem), Adam Bouland (UC Berkeley), Zvika Brakerski (Weizmann Institute of Science), Anne Broadbent (University of Ottawa), Rui Chao (Aliyun Quantum Laboratory USC), Alessandro Chiesa (UC Berkeley), Andrew Childs (University of Maryland), Alexandru Cojocaru (University of Edinburgh), Elizabeth Crosson (Caltech), Ronald de Wolf (QuSoft, CWI and University of Amsterdam), Jens Eisert (Freie Universität Berlin), Glen Evenbly (University of Sherbrooke), Bill Fefferman (UC Berkeley), Joseph Fitzsimmons (Singapore University of Technology and Design), Sanjam Garg (UC Berkeley), Andras Pal Gilyen (Centrum Wiskunde & Informatica), Daniel Gottesman (Perimeter Institute), Ayal Green (Hebrew University of Jerusalem), Tom Gur (UC Berkeley), Jeongwan Haah (Microsoft Research), Matt Hastings (Microsoft Research), Patrick Hayden (Stanford University), Martin Head-Gordon (UC Berkeley), Jiachen Huang (Aliyun Quantum Laboratory University of Michigan), Stacey Jeffery (Centrum Wiskunde & Informatica), Yael Kalai (Microsoft Research), Iordanis Kerenidis (CNRS - Université Paris Diderot), Robin Kothari (Microsoft Research), John Mark Kreikebaum (Physics), Zeph Landau (UC Berkeley), James Lee (University of Washington), Maciej Lewenstein (Institute of Photonic Sciences), Tongyang Li (University of Maryland), Lin Lin (UC Berkeley), Mikhail Lukin (Harvard University), Shengqiao Luo (IQC), Urmila Mahadev (UC Berkeley), John Martinis (UCSB), Chris Monroe (UMD), Anand Natarajan (Massachusetts Institute of Technology), Chinmay Nirkhe (UC Berkeley), Prasad Raghavendra (UC Berkeley), Ben Reichardt (University of Southern California), Miklos Santha (Université Paris Diderot - Paris 7), Jonah Sherman (UC Berkeley), Mario Szegedy (Aliyun Quantum Laboratory), Yonathan Touati (Hebrew University), Vinod Vaikuntanathan (Massachusetts Institute of Technology), Umesh Vazirani (UC Berkeley), Thomas Vidick (Caltech), John Watrous (University of Waterloo), James Whitfield (Dartmouth College), Nathan Wiebe (Microsoft Research), Norman Yao (UC Berkeley), Henry Yuen (UC Berkeley), Quntao Zhuang (MIT).