Algorithms and complexity for quantum advantage

使用量子纠错来保护其免受环境影响的大型量子计算机预计将比任何经典计算机都强大得多。 但在如此大型的量子计算机问世之前，还会有更小的、没有量子纠错的量子设备。由于大量的学术和商业投资，我们开始看到这些小型且嘈杂的量子计算机的可用性。此外，预计很快就会出现现有经典计算机无法模拟的量子设备，从而为展示某种量子优势的可能性打开了大门。 虽然这些进展令人兴奋，但它们也凸显了构建量子计算机的努力与量子算法研究的现有状态之间的不匹配。事实上，一个紧迫的问题是：我们应该如何处理近期的量子计算机？可以说我们还没有得到满意的答案。在下一代设备的背景下狭义地解释，它可以翻译为：在由架构确定的门集上，使用短深度电路，无需纠错，可以实现什么？不幸的是，这些限制排除了大多数已知的量子算法原语，并且没有为创造性算法设计留下太多空间。 在接下来的几年里，理论工作有机会（也需要）影响量子计算机的潜在应用。我们并不致力于特定的架构或设备，而是建议通过量子算法和复杂性的基础研究来为这项工作做出贡献，并以以下基本问题为指导：哪种受限量子计算可以比经典计算机更强大？哪些是经典可模拟的？ 这些问题是实现近期量子计算机潜力的挑战的核心。为了取得成功，我们必须了解量子计算机在运行受到限制（例如，现有硬件的限制）的情况下能够比传统计算机取得优势的新方法。事实上，近期演示的几个主要提案都起源于量子计算受限模型的早期研究，例如恒定深度量子电路、玻色子采样和瞬时量子计算。 我们建议围绕这一主题在三个领域进行研究。首先，我们将开发使用更少量子资源的量子算法，并可能展示新形式的量子优势。其次，我们将改进经典模拟小型或受限量子计算的方法；除了直接用于验证小型量子计算机之外，此类方法还有助于识别量子加速所需的量子资源。最后，我们将研究量子多体系统的复杂性，并确定此类系统的结构特征，这些特征可以通过有效的经典或量子算法来利用。

A large quantum computer which is protected from its environment using quantum error correction is expected to be vastly more powerful than any classical computer. But before such a large quantum computer is available, there will be smaller quantum devices without quantum error correction. And as a result of enormous academic and commercial investment we are beginning to see the availability of these small and noisy quantum computers. Moreover, it is expected that there will soon be quantum devices that cannot be simulated by existing classical computers, opening the door to the possibility of demonstrating some kind of quantum advantage. While these developments are exciting, they also highlight a mismatch between the efforts to build a quantum computer and the existing state of quantum algorithms research. Indeed, a pressing question is: what should we do with a near-term quantum computer? Arguably we do not yet have a satisfactory answer. Interpreted narrowly in the context of the next-generation of devices, it translates as: what can be achieved without error correction, using short-depth circuits, over a gate set determined by architecture? Unfortunately these restrictions rule out most known quantum algorithmic primitives, and do not leave much room for creative algorithm design. In the next several years there is an opportunity (and need) for theoretical work to impact potential applications of quantum computers. Rather than commit ourselves to a particular architecture or device, we propose to contribute to this effort through fundamental research in quantum algorithms and complexity, guided by the basic questions: Which restricted quantum computations can be more powerful than classical computers? Which are classically simulable? These questions are central to the challenge of realizing the potential of near-term quantum computers. To succeed we must understand new ways that quantum computers can eke out an advantage over classical computers in the presence of restrictions on their operation (e.g., from limitations of existing hardware). In fact, several of the leading proposals for near-term demonstrations have their origins in early studies of restricted models of quantum computation such as constant-depth quantum circuits, BosonSampling, and Instantaneous Quantum Computation. We propose research in three areas centered around this theme. First, we will develop quantum algorithms that use fewer quantum resources and may demonstrate new forms of quantum advantage. Second, we will improve methods for classically simulating small or restricted quantum computations; in addition to their direct use in verifying small quantum computers, such methods help to identify the quantum resources necessary for quantum speedup. Finally, we will investigate the complexity of quantum many-body systems, and identify structural features of such systems which can be leveraged by efficient classical or quantum algorithms.