Workshop on Provable Quantum Advantage – Present and Future

点击翻译按钮获取中文摘要

For nearly three decades quantum computation has been the only known model of feasible computation capable of obtaining exponential speedups over any efficient classical computer [11,29,30]. Despite this great promise, the theoretical quantum speedups developed in the early 1990’s are very difficult to implement as they require large-scale, nearly perfect quantum experiments. While this goal may still be quite far off, the push to develop quantum computers has already yielded incredible experimental progress in high-precision control over individual quantum systems across many different quantum architectures (see e.g.,[7,10,12,34,35]). Due to these experimental developments, we have now arrived in the so-called Noisy Intermediate Scale Quantum (“NISQ”) era, in which quantum systems of 50-70 qubits are currently being built in experimental laboratories around the world. For the first time, these experiments are approaching the complexity boundary after which it is unclear how to simulate them classically in a reasonable amount of time. This indicates that these systems may have the potential to achieve quantum speedups. However, these experiments have important limitations, such as uncorrected noise, which restrict their capabilities. The first major step for the NISQ era is to implement an experimental demonstration of a computational speedup relative to any classical computer, a goal known as “quantum supremacy” [27]. This goal is a watershed moment in the history of computation and a necessary milestone on the path toward developing fully scalable quantum computers. Moreover the goal appears to be rapidly approaching, and we have already seen the first claimed demonstrations of quantum supremacy [7, 36]. These experiments have attracted much attention but there are still many aspects of the claims that not well understood. While there is some rigorous evidence that such near-term quantum experiments are able to attain exponential speedups over classical computation (see, e.g., [3,4,14]) these theoretical results do not take into account many practical facets of these experiments such as uncorrected noise. Indeed, these gaps between theory and experiment have resulted in partial rebuttals of these initial quantum supremacy claims (see e.g., [8, 22, 25, 26]). Consequently, there is a great need to rigorously understand the capabilities of these near-term quantum experiments. To do this, we propose holding a workshop focusing on the prospects for achieving large computational speedups on near-term quantum experiments. Our goal will be not only be to better understand the present generation of quantum experiments, but also to understand the capabilities of tomorrow’s quantum experiments, with a view toward the ultimate goal of implementing a quantum speedup for solving a practically useful problem. Intellectual Merit:The proposed workshop will lead to a complete understanding of the computational power of near-term quantum experiments. The focus will be on three objectives which will together help understand the power of existing quantum computers, as well as pave the road toward understanding the power of future quantum devices capable of attaining dramatic speedups for useful computational problems. In addition to being critical for the current near-term quantum era, these aims will foster interdisciplinary collaborations and lead to exciting new insights at the intersection of computer science, engineering, and experimental physics. Broader Impacts:This workshop will contribute to sustaining and enhancing the recent worldwide explosion of interest in quantum computation. The program will feature invited speakers and participants from academia, government and industry to disseminate the most recent ideas on quantum computation to a wide variety of scientific communities.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.