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.