Time and Location

  • Date: Monday, April 29
  • Time: 4:00 PM-5:00 PM
  • Location: Luddy Hall 4063 (BLIF-4063)

Abstract

Quantum information processing is believed to revolutionize classical optimization algorithms, classical search algorithms, and classical learning theories. Although there is indeed much evidence for such a potentiality, there are — to date — no definitive theoretical or practical demonstrations of any quantum computational advantage.

Part of the reason for this uncertain state of affairs is that the boundary between classical and quantum computing is not well-understood. In this talk, we will explore the foundations of quantum computing and their connections to classical computing from a variety of semantically motivated perspectives. We will first review how some of the ingredients of quantum computing (e.g., reversibility and the complex numbers) are irrelevant for separating classical from quantum computing. We will then explore two recently developed characterizations of quantum computing that are “almost” classical.

Our technical approach is to design computationally universal quantum programming languages by, as modest as possible, extensions to classical programming languages. The first approach demonstrates that a computationally universal quantum programming language emerges from the amalgamation of two classical languages glued by complementarity. The second approach demonstrates that a computationally universal quantum programming language emerges from a classical programming language extended with just a few square roots of certain key functions. These more subtle perspectives provide some insight at the possible semantic sources of quantum advantage and may suggest new classes of applications in which quantum computing could provide an advantage over classical computing.