Running Classical Programs on a Quantum Annealer
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.
Dr. 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.
