Ezra's Round Table / Systems Seminar: Scott Pakin (LANL) - Running Classical Programs on a Quantum Annealer

Description

A quantum annealer is a special-purpose quantum computer that does only one thing: rapidly (as in a millionth of a second, regardless of problem complexity) approximate the solution to a fixed-form optimization problem. Specifically, given the linear and quadratic coefficients to a pseudo-Boolean function, a quantum annealer returns the (Boolean) variables that minimize that function. Or not; its behavior is both heuristic and stochastic. There is no “programming” per se. There are no loops, no functions, no branches, no variable modifications—nothing one would expect from a programming system. Beyond coefficient selection, there are not even any inputs! A quantum annealer is effectively a big calculator with one operator button, labeled “optimize”. Or is it? In this lecture, we explore how to engineer conventional computer programming (or a reasonable facsimile thereof) in terms of a quantum annealer's native capabilities. Step-by-step and abstraction-by-abstraction, we construct a system for mapping programs written in classical programming languages into a minimization problem suitable for execution on a quantum annealer. We argue that with this approach, efficient, approximate solutions to difficult (i.e., NP) problems can in fact be easier to express than with conventional, classical techniques.

Bio:
Scott Pakin has worked since 2002 as a scientist at Los Alamos National Laboratory. He has researched over time a variety of Computer Science topics related to high-performance computing, including programming models, application performance analysis, energy efficiency, and high-speed communication. Scott has recently begun investigating quantum computing and is currently leading a few exciting research efforts related to both circuit-model quantum computing and quantum annealing. Scott holds an M.S. and a Ph.D. in computer science from the University of Illinois at Urbana-Champaign and a B.S. in mathematics/computer science from Carnegie Mellon University.