The Quantum Optimization Benchmarking Library.

Abstract

Recent progress has brought benchmarking of (heuristic) quantum algorithms at scale within reach. Particularly in combinatorial optimization, it is key to empirically analyze and track progress towards quantum advantage. This work introduces a systematic, fair and comparable benchmarking framework for quantum optimization methods by presenting ten model-independent problem classes that are challenging for classical methods. Track records of specific instances and solutions are given in an accompanying open-source repository. While the individual properties of the problem classes vary, they all become challenging from less than 100 to, at most, an order of 100,000 decision variables. We reference results from state-of-the-art solvers for instances across all problem classes and demonstrate exemplary baseline results obtained with quantum solvers for selected problems, which illustrate standardized benchmark reporting. The presented problem instances may be approached with classical or quantum algorithms executed on varying hardware platforms to drive the field towards quantum advantage.