Columbia Quantum Initiative Faculty Recruiting
Nathan Wiebe

Abstract:
Since Shor first captured the public's imagination by showing that quantum computing can provide super-polynomial speedups for certain problems, an uncomfortable question has lingered over the field: “What will quantum computing's first killer application be?"
In this talk I will examine two areas where such a killer application may be found: simulating physical systems and quantum machine learning.
In the first part of my talk I will discuss recent work that I have done that has reduced the complexity of simulating physical systems down by 14 orders of magnitude from initial estimates and pushes quantum simulation within the reach of early fault-tolerant quantum computers. From these estimates I will argue that simulation clearly constitutes a killer application that may be attainable before even quantum factoring is realized.
The second topic that I will discuss is quantum machine learning. While comparably less developed than quantum simulation, I will present recent work that shows that quantum speedups also can be attained in this space.
In particular, I will present a new result that shows that a form of recurrent quantum neural networks known as quantum Boltzmann machines can not only be efficiently trained but also have provably greater representational power than classical neural networks (under reasonable complexity theoretic conjectures). This suggests that quantum machine learning may also be such an application.
Finally, I will conclude by discussing open problems in both fields and argue that recent breakthroughs in quantum algorithms, such as the block encoding paradigm myself and collaborators have developed, will continue to reveal new killer applications for quantum computers in these fields and beyond.

Bio:
Nathan Wiebe is a researcher in quantum computing who focuses on quantum methods for machine learning and simulation of physical systems. His work has provided the first quantum algorithms for deep learning, least squares fitting, quantum simulations using linear-combinations of unitaries, quantum Hamiltonian learning, near-optimal simulation of time-dependent physical systems, efficient Bayesian phase estimation and also has pioneered the use of particle filters for characterizing quantum devices as well as many other contributions ranging from the foundations of thermodynamics to adiabatic quantum computing and quantum chemistry simulation.
He received his PhD in 2011 from the University of Calgary studying quantum computing before accepting a post-doctoral fellowship at the University of Waterloo and then finally joining Microsoft Research in 2013.