# The Foundations of Quantum Computational Advantage

## Abstract

Quantum computation is a novel paradigm of computation based on quantum mechanical first principles in order to solve important problems beyond the abilities of any classical machine. However, confusion about precisely how and for which problems quantum computers offer an advantage stymies both fundamental understanding and technological progress.

What are the key features of quantum theory that enable quantum advantages in communicational and computational tasks? Nonlocality is a special case of contextuality; both notions are concepts of foundational quantum theory that crystallise ways in which quantum behaviours can transcend classical constraints. They have recently emerged as promising hypothetical origins of quantum advantage. Many early proofs of contextuality used formal logical paradoxes to probe the classical- quantum boundary. Richer connections between contextuality and logic have recently been uncovered creating an opportunity to gain the deep, structural understanding of quantum advantage needed to design quantum algorithms and optimally efficient quantum hardware.

I will introduce nonlocality and contextuality with an emphasis on their underlying logical structure and review results of quantum information that provide persuasive evidence of their usefulness as computational resources in restricted computational models. I will then present evidence of the power of paradoxes to drive the full capabilities of quantum computation and outline how a logical perspective can contribute to tackling important problems in quantum computer science.

This talk will be a high-level overview and no prior knowledge of quantum computation will be assumed.

Bio:

Nadish de Silva is a Research Associate in the Centre for Quantum Information and Foundations (Department of Applied Mathematics and Theoretical Physics, University of Cambridge). Previously, he was the Researcher Co-Investigator of the EPSRC-funded project Contextuality as a resource in quantum computation: a collaboration between University College London and the University of Oxford. He holds a DPhil in Computer Science from the University of Oxford and a MSc in Mathematics & Hons BSc in Mathematics and Physics from the University of Toronto. Broadly, his research interests include quantum information & computation; nonlocality & contextuality; and operator algebras & noncommutative geometry.

Join meeting in Sococo VH 102, or Zoom:

Join Zoom Meeting: https://tufts.zoom.us/j/98610939077

Meeting ID: 986 1093 9077

Passcode: see colloquium email

Dial by your location: +1 646 558 8656 US (New York)

Meeting ID: 986 1093 9077

Passcode: see colloquium email