Characteristics of Optimization Applications as Quantum Performance Benchmarks*

Combinatorial optimization is anticipated to be one of the primary use cases for quantum computation in the coming years. Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing (QA) are expected to demonstrate significant run-time performance benefits over classical solutions. We review existing methods for characterizing the performance of classical optimization algorithms and use these to compare solution quality obtained by solving Max-Cut problems using a quantum annealing device and gate-model quantum processors and simulators. This is used to guide the development of an advanced benchmarking framework for quantum computers designed to evaluate the trade-off between run-time execution performance and the quality of solution for iterative hybrid quantum-classical applications. Of particular relevance is how the nature of the problem input configuration impacts the solution quality, the length of time required to achieve a solution, and the algorithm limitations uncovered by the benchmarking approach. The framework is an enhancement to the existing open-source QED-C Application-Oriented Benchmark suite. The suite can be executed on various quantum simulators, quantum hardware backends, and a quantum annealing device.