Quantum Annealing amid Local Ruggedness and Global Frustration

Quantum annealers are designed to utilize quantum tunneling to find good solutions to hard optimization problems. When constructing a family of synthetic inputs to test the potential of a quantum annealing platform, one should therefore ensure that the inputs a) have locally rugged energy landscapes so that solvers can benefit from quantum tunneling, and b) are hard optimization problems with global frustration so that they are computationally meaningful. A recent Google study [Phys. Rev. X 6, 031015 (2016)] introduced such an input class, but the amount of global frustration is limited and they utilize gadgets that are tailored to deceive classical annealing algorithms. In this study we extend their work by introducing a problem class that contains more global frustration and uses only simple clusters to induce ruggedness. Further, our problem class has tunable levels of ruggedness and frustration, making it ideal for the analysis of quantum annealers and classical approximations of quantum annealing. Like the Google inputs, these inputs are built from easy-to-solve logical problems that can be extracted by tailored solvers. However, they provide a meaningful testbed for solvers agnostic to the planted problem class. We compare the latest-generation D-Wave quantum processing unit (QPU) to classical alternatives, examining both optimization and sampling, and measure the response of these solvers to increasing levels of local ruggedness.