Performance Evaluation for Annealing Based Quantum Computers

A D-Wave quantum processing unit (QPU) implements an algorithm in hardware that exploits quantum properties (such as superposition and entanglement), to heuristically solve instances of the Ising model problem, which may be more familiar as quadratic unconstrained binary optimization (QUBO). The current 2000Q model contains 2000 qubits.

The algorithmic approach it uses, called Quantum Annealing (QA), falls in the adiabatic quantum model of computation (AQC), which is an alternative to the more familiar gate model (GM) of quantum computation. Relatively little is known theoretically about QA and AQC; but on the other hand the existence of quantum computing systems of reasonable size make empirical approaches to performance analysis possible.

I will give an introductory overview of quantum annealing and D-Wave processors, show how to solve Max Cut problems on these novel computing platforms, and survey what is known about performance on this problem. No background in Physics is assumed.

Bio

Catherine McGeoch received her PhD from Carnegie Mellon University in 1987. She spent almost 30 years contentedly in academia, on the faculty at Amherst College. In 2014 she decided to shake things up, and joined the benchmarking team at D-Wave Systems.

Her research interests are in experimental methods for evaluating algorithms and heuristics, with recent emphasis on quantum algorithms and platforms. She co-founded the DIMACS Challenges and the ALENEX Workshops, and is past Editor in Chief of the ACM Journal on Experimental Algorithmics. She has written a book on experimental algorithmics and a book on AQC and quantum annealing.