The foundations of quantum computational advantage

量子计算（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.