Can Quantum Computing Solve my Favorite Problem?

Amr Sabry

Indiana University, USA

Abstract

It seems that everyone is talking about the promises of quantum computing. In addition to the famous Shor algorithm for factoring in polynomial time, 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 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 quantum computing and its connection to classical computing from a number of semantically motivated perspectives. Each perspective will provide some insight at a possible semantic source of quantum advantage and new classes of applications in which quantum computing would potentially provide an advantage over classical computing.

Short Bio

Amr Sabry is a Professor of Computer Science at Indiana University. His research interests are in the semantics, logical foundations, and implementations of programming languages. He has published on a range of themes including the typing, logical foundations, and programming applications of continuations and continuation-passing style, reasoning about monadic effects and staged computation, and programming language models of quantum computing. Together with Matthias Felleisen, Sabry wrote a series of papers on the use of continuations in the compilation of functional languages which includes one of the fifty most influential papers in the last twenty years of the ACM SIGPLAN Conference Programming Language Design and Implementation (PLDI). Together with Eugenio Moggi, Sabry gave what is considered the long-awaited definitive answer that monadic encapsulation of effects using rank-2 polymorphism is correct. His most recent research interests are related to quantum computing.