Contextuality as a Resource in Quantum Computation

Lead Research Organisation: University of Oxford
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.

Planned Impact

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.


10 25 50

publication icon
Abramsky S (2019) Non-locality, contextuality and valuation algebras: a general theory of disagreement. in Philosophical transactions. Series A, Mathematical, physical, and engineering sciences

publication icon
Abramsky S (2017) Contextual Fraction as a Measure of Contextuality. in Physical review letters

publication icon
Abramsky S (2016) Possibilities determine the combinatorial structure of probability polytopes in Journal of Mathematical Psychology

publication icon
Abramsky S (2020) Whither semantics? in Theoretical Computer Science

publication icon
Abramsky, S (2017) A complete characterisation of All-versus-Nothing arguments for stabiliser states in Philosophical Transactions of the Royal Society A

publication icon
De Silva N (2019) Contextuality and Noncommutative Geometry in Quantum Mechanics in Communications in Mathematical Physics

Description We have obtained extensive results on contextuality as a resource for quantum computation during the project.
These include:
- an analysis of minimum quantum resources for strong non-locality
- a quantum monad for homomorphisms of relational structures, with applications to quantum constraint satisfaction, quantum graph invariants etc.
- the contextual fraction as a measure of contextuality, relating it to quantum advantage in a number of information-processing tasks by resource inequalities
- a resource theory for contextuality
- a comprehensive notion of simulation allowing to compare expressiveness of resources, structured using a comonad
Exploitation Route Those interested in novel or sytematic ways of exhibiting quantum advantage in information processing tasks.

Elements of this funding are being developed in the current EPSRC project on "Resources and Coresources: a junction between categorical semantics and descriptive complexity".
Sectors Digital/Communication/Information Technologies (including Software)

Description Resources and co-resources: a junction between semantics and descriptive complexity
Amount £400,335 (GBP)
Funding ID EP/T00696X/1 
Organisation Engineering and Physical Sciences Research Council (EPSRC) 
Sector Public
Country United Kingdom
Start 09/2019 
End 03/2023