Quantum Advantage for All

Are quantum computers and their obscure programming models a mystery to you? Do you think they are never going to deliver actual benefit over classical machines? Well, this talk is not going to help you answer those questions. But, it does give you an idea of how to connect standard programming with quantum machines which may eventually turn them into super-polynomial accelerators. Don’t get too excited though, it will take a while or maybe forever until then. The idea we present is as follows: given a program, say, written in C, we (logically) execute that program for all (!) possible inputs up to a given depth into the program’s control-flow structure, to see if there is input that makes the program reach a certain state such as where it returns, say, 0. If yes, great, if no, we may execute it even deeper into its control-flow structure until we run out of resources. In any case, such program execution can be encoded in SAT formulae that are essentially not larger than the program, and satisfiable if and only if there is such input. We show how to generate such formulae and then solve them using so-called quantum annealers. Those machines are easy to understand, at least compared to universal gate-model machines. We also propose a quantitative notion of quantum advantage trading off classical and quantum computation

This is joint work with Stefanie Muroya.

Recording