Workshop on Provable Quantum Advantage – Present and Future

近三十年来，量子计算一直是已知的唯一一种可行计算模型，能够比任何高效的经典计算机[11，29，30]获得指数级的加速比。尽管有这个巨大的希望，但在20世纪90年代初S提出的理论量子加速是非常困难的，因为它们需要大规模的、近乎完美的量子实验。虽然这一目标可能还很遥远，但发展量子计算机的努力已经在跨越许多不同量子体系结构的单个量子系统的高精度控制方面取得了令人难以置信的实验进展(例如，见[7，10，12，34，35])。由于这些实验的发展，我们现在已经进入了所谓的噪声中间尺度量子(NISQ)时代，在这个时代，世界各地的实验实验室正在建立50-70个量子比特的量子系统。第一次，这些实验正在接近复杂的边界，在此之后，如何在合理的时间内对它们进行经典模拟尚不清楚。这表明这些系统可能具有实现量子加速的潜力。然而，这些实验有重要的局限性，如未校正的噪声，这限制了它们的能力。NISQ时代的第一个重要步骤是实现相对于任何经典计算机的计算加速的实验演示，这一目标被称为“量子至上”[27]。这一目标是计算史上的一个分水岭，也是发展完全可扩展量子计算机道路上的一个必要里程碑。此外，这一目标似乎正在迅速接近，我们已经看到了第一批声称量子优势的演示[7，36]。这些实验引起了人们的极大关注，但其中仍有许多方面没有得到很好的理解。虽然有一些严格的证据表明，这样的近期量子实验能够达到经典计算的指数加速(参见[3，4，14])，但这些理论结果没有考虑到这些实验的许多实际方面，如未校正的噪声。事实上，理论和实验之间的这些差距导致了对这些最初的量子至上主张的部分反驳(例如，参见[8，22，25，26])。因此，非常需要严格理解这些近期量子实验的能力。为了做到这一点，我们建议举办一次研讨会，重点关注在近期量子实验中实现大规模计算加速的前景。我们的目标不仅是更好地理解当代量子实验，而且还将了解明天量子实验的能力，以期实现量子加速的最终目标，以解决一个实际有用的问题。智力优势：拟议的研讨会将导致对近期量子实验的计算能力的全面理解。重点将放在三个目标上，这三个目标将共同帮助理解现有量子计算机的能力，并为了解未来量子设备的能力铺平道路，这些设备能够为有用的计算问题实现显著的加速。除了对当前的短期量子时代至关重要外，这些目标还将促进跨学科合作，并在计算机科学、工程和实验物理的交叉领域产生令人兴奋的新见解。更广泛的影响：这次研讨会将有助于维持和加强最近世界范围内对量子计算的兴趣的激增。该计划将邀请来自学术界、政府和工业界的演讲者和参与者向广泛的科学界传播量子计算的最新想法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.