The foundations of quantum computational advantage

点击翻译按钮获取中文摘要

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.