KaleidosQope

The second quantum revolution is under way, carrying the promise of unparalleled computational power and opening up astonishing new possibilities e.g. in machine learning or simulation of quantum systems. Google's landmark empirical demonstration in late 2019 of a 53-qubit quantum computer outperforming top-line supercomputers was for a tailor-made task of little practical interest, yet served as a proof of concept for the capabilities even of imperfect quantum hardware. We have now entered the era of Noisy Intermediate-Scale Quantum (NISQ) devices and started to explore what they offer.

However, a precise understanding of the power and limitation of various models of quantum computation is still lacking. Indeed, a central theme in quantum computation theory is to delineate the scope of advantage offered by access to quantum resources and to elucidate its nature, i.e. the key ingredients that power it and how these compose and interact. This question is of fundamental scientific interest to our understanding of a new computational paradigm. But at the same time, it carries immediate practical importance e.g. to identify principles of quantum algorithm design, compare the power of various kinds of quantum resources, estimate the cost of classical simulations, and develop tools to support scalable programming and verification of quantum computers.

The starting point for this proposal is a simple observation: any informatic advantage afforded by quantum systems must come about through the exploitation of unique features of their observable behaviour, which defy classical explanation. Contextuality, whereby empirical observations preclude thinking of measurements as simply revealing pre-existing properties, is the archetypal nonclassical feature of quantum phenomenology, as shown by the Bell–Kochen–Specker no-go theorem. It thus arises as a natural candidate as a source of quantum computational power, and recent results (including by PI and team members) have established it as a necessary ingredient for quantum-over-classical advantage in various protocols and models of computation.

Our central aim is to offer a more general and systematic account of contextuality as a resource and its ubiquitous connection to quantum advantage. This ought to satisfy two desiderata:

1. to be flexible enough to accommodate refinements and variations, e.g. to deal robustly with noise or capture restrictions in circuit depth or classical control, allowing one to explore the evolving landscape of resource-constrained NISQ architectures.

2. to be actionable into techniques and tools that address near- and medium-term challenges in the development of quantum computers, e.g. informing near-term algorithm design, certification of NISQ devices, and scalable verification.

The main idea of KaleidosQope is to approach this question through a novel perspective based on logic. This follows a tried-and-tested blueprint that links theoretical foundations all the way through to effective reasoning tools. But though a well-trodden path in classical computer science, it remains underexplored in the quantum setting.

The key ingredient for this study of contextuality in logical form will be logics of partial information, arising from restricted observability. In contrast to classical physics, not all measurements may be performed jointly on a quantum system. Instead, access to a quantum system is mediated through a kaleidoscope of multiple partial, operationally-accessible, classical viewpoints provided by contexts of jointly measurable observables. Contextuality arises in the tension between local consistency (any two of these perspectives fit nicely together) and global inconsistency. In logical terms, we adopt the setting of partial Boolean algebras (and generalisations), wherein logical connectives are only partially defined, in the domain where they are operationally meaningful, namely on commeasurable propositions.

The project will develop the basic theory of such contextual logics (in algebraic logic style) and will explore this perspective as a convenient tool to study the resource theory of contextuality and its connection to quantum informatic advantage. These ideas will be applied to concrete problems in articulation with photonic quantum computing company Quandela, whose commitment of time and funds to this project attests to its practical relevance and timeliness.

The research plan will be carried out by an interdisciplinary team of INL researchers who bring complementary expertise in quantum computing, from foundational underpinnings to physical implementation, and in computer science logic. The project will contribute to the training of young researchers by integrating into its team four already funded PhD students in addition to hiring a junior researcher for 12 months. Two leading international experts on various aspects of the project will act as external consultants: S Abramsky and S Mansfield.