The foundations of quantum computational advantage

量子计算（QC）是直接基于量子力学第一原理的一种新的计算范式。虽然传统智慧长期以来一直认为量子物体的反直觉和随机行为会阻碍计算机器的构建，但最近人们意识到，一旦适当利用，它们实际上可以成为强大的资源。有一天，使用QC解决任何传统计算机都无法解决的计算问题将成为可能。量子计算机从根本上超越现有经典技术的能力被称为量子优势。QC的潜力将改变我们生活的方方面面——从国家安全到物流；气候和金融预测；材料和药物设计引发了大量的政府和商业投资。然而，尽管最近的头条新闻预示着QC的快速发展，但关于量子计算机的能力的许多最基本的问题尚未得到回答。目前尚不清楚量子计算机如何以及在哪些问题上具有优势。我的新NSERC发现研究项目的长期愿景是了解量子理论的关键物理和逻辑特征，使量子计算优势。这将是设计量子软件和最高效量子硬件的基础。我的研究旨在通过结合物理学、计算机科学和纯数学的思想和工具来回答这个基本问题。特别是，我专注于发展新兴的和令人兴奋的假设，即情境性，一个来自量子力学基础的概念，否认了经典的现实概念，是实现量子优势的关键资源。最近，上下文性和数学逻辑之间的丰富联系已经被发现：我们现在明白，逻辑悖论是上下文性的核心。我正在采取独特的方法，利用这些联系来解释量子优势。我的计划将解决以下短期目标：目标A：严格建立量子优势在计算和通信任务。目标B：开发设计最优效率量子软件和硬件的方法。目标C：寻找新的量子算法的线索。我将通过数学将量子理论的悖论与量子计算机的力量联系起来，并提供清晰、高层次的计算优势描述，以释放QC的全部潜力，从而实现这一目标。这将导致量子计算机的建造速度更快，并且能够解决比目前想象的更多的问题。因此，加拿大将在这一新兴产业中获得领先地位的经济效益，并在所有科学和工程领域获得创新的技术效益。

Quantum computation (QC) is a new paradigm of computing that is based directly on quantum mechanical first principles. While conventional wisdom had long held that the counterintuitive and random behaviours of quantum objects would be a hindrance to the construction of computational machines, it was recently realized that they can, in fact, be powerful resources once properly harnessed. It will one day be possible to solve computational problems using QC that are beyond the capabilities of any conventional computer. This ability for quantum computers to fundamentally outperform existing classical technology is known as quantum advantage. The potential of QC to transform every aspect of our lives-from national security to logistics; climate and financial prediction; material and pharmaceutical design-has triggered massive governmental and commercial investment. However, recent headlines heralding rapid progress in QC notwithstanding, many of the most basic questions about the power of quantum computers are yet to be answered. It is not known exactly how and for which problems quantum computers offer any advantage. The long-term vision of my new NSERC Discovery research program is to understand the key physical and logical features of quantum theory that enable quantum computational advantage. This will be the basis for the design of quantum software and optimally efficient quantum hardware. My research aims to answer this fundamental question by combining ideas and tools from physics, computer science, and pure mathematics. In particular, I focus on developing the emerging and exciting hypothesis that contextuality, a concept from the foundations of quantum mechanics that denies classical notions of reality, is a key resource for achieving quantum advantage. Recently, rich connections between contextuality and mathematical logic have been uncovered: we now understand that logical paradoxes lie at the heart of contextuality. I am taking the unique approach of utilizing these connections to explain quantum advantage. My program will tackle the following short-term objectives: Objective A: Rigorously establish quantum advantage in computational and communicational tasks. Objective B: Develop methods for designing optimally efficient quantum software and hardware. Objective C: Identify clues toward novel quantum algorithms. I will achieve this by mathematically connecting the paradoxes of quantum theory to the power of quantum computers and providing the clear, high-level delineation of computational advantage needed to unlock the full potential of QC. This will result in quantum computers that will be constructed sooner and capable of solving more problems than currently thought possible. As a consequence, Canada will reap the economic benefits of leadership in this emerging industry and the technological benefits of innovations across all areas of science and engineering.