Contextuality as a Resource in Quantum Computation

Realizing the potential of applications of quantum theory to information processing, which include quantum communication and quantum computation, is one of the primary goals of contemporary engineering and physics. The key theoretical breakthroughs enabling quantum communication technologies were the discovery of the phenomenon of quantum entanglement in the 1930s and the realisation that entanglement represented not merely a curiosity of quantum theory but a critical resource which could be exploited to achieve heretofore impossible communication tasks in the 1980s. Bell indentified quantum nonlocality as the essentially quantum aspect of entanglement in the 1960s.

While it is widely understood that quantum computation offers substantial efficiency advantages over classical computation for particular problems, it is neither understood what the precise class of such problems is nor what the particular aspect or aspects of quantum theory enabling these advantages are. The applications for QC which have been identified are likely only a fraction of the full potential, however, as only a handful of quantum algorithms have been discovered. Peter Shor, whose discovery of the first practical quantum algorithm founded modern quantum computer science, contemplated why so few quantum algorithms have been discovered and suggested that, "quantum computers operate in a manner so different from classical computers that our techniques for designing algorithms and our intuitions for understanding the process of computation no longer work". In seeking quantum algorithms without a clear idea of the essential quantum phenomenon accounting for quantum computational advantage, we are working in the dark.

Despite decades of research, the key feature of quantum theory enabling quantum advantage over classical computers remains elusive. Several of quantum theory's novel features---such as entanglement, superposition, and discord---have been proposed as candidates but have subsequently proven insufficient. Recent evidence, such as that provided by Rausendorff (Phys. Rev. A, 88) and Howard et al. (Nature, 510), demonstrates that a generalization of nonlocality called contextuality plays an important role in QC and suggests that it is, perhaps, a sought-after key to understanding the unique capabilities of QC.

Our vision is to deepen the theory of contextuality with the goals of achieving an understanding of the precise role it plays in QC and how it is a resource for computational advantage. Our team is uniquely positioned to tackle this challenge: the PIs are co-inventors of the two leading theoretical frameworks for contextuality. We will achieve our goal by collaborating with an international, interdisciplinary team of experts including those responsible for the initial evidence linking contextuality and QC as well as recognized leaders in quantum algorithms and the resource theory of nonlocality.

Quantum technologies are widely predicted to be a major driver of scientific progress and economic growth and are expected to constitute a multi-billion pound industry within the near- to mid-term. As one example, quantum communication technologies in the process of commercialization will provide the backbone of highly efficient, unconditionally secure networks with myriad defense, commercial, and consumer applications, from financial transactions to cloud computing. Among these emerging technologies, quantum computation has the greatest potential for far-reaching impact. By offering a completely novel set of extraordinarily powerful computational tools, QC holds consequences for virtually every field of endeavour involving computation, from the design of pharmaceuticals to optimizing flight schedules. The UK Quantum Technologies Strategic Advisory Board estimates that commercial prototypes of such devices will be built in ten years and that quantum co-processors for consumer computing will be built in twenty years.

This project aims to improve theoretical understanding of this fundamentally new paradigm of computing. We aim to clarify the source of quantum computing's power and, in doing so, will facilitate the complete exploitation of quantum information processing devices. The improved understanding of the source of quantum computing's power will lead to a better idea of the class of problems for which quantum computers offer an advantage and to methods of developing more efficient quantum computing architectures. By maximizing the academic impacts of the project, we will ensure the adoption of our results downstream and contribute to the realization of the vast economic and social impacts of QC.