Contextuality as a Resource in Quantum Computation

Lead Research Organisation: University College London
Department Name: Computer Science


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.


10 25 50