Algorithms and complexity for quantum advantage

量子优势的算法和复杂性

• 批准号: RGPIN-2019-04198
• 负责人: Gosset, David
• 金额: $ 2.4万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=684526
• 关键词: Algorithms; complexity; 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.

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