Embedding Overhead Scaling of Optimization Problems in Quantum Annealing

In order to treat all-to-all-connected quadratic binary optimization problems (QUBOs) with hard- ware quantum annealers, an embedding of the original problem is required due to the sparsity of the topology of the hardware. The embedding of fully connected graphs-typically found in industrial applications incurs a quadratic space overhead and thus a significant overhead in the time to solution. Here, we investigate this embedding penalty of established planar embedding schemes such as square-lattice embedding, embedding on a chimera lattice, and the Lechner-Hauke-Zoller scheme, using simulated quantum annealing on classical hardware. Large-scale quantum Monte Carlo simulation suggests a polynomial time-to-solution overhead. Our results demonstrate that standard analog quantum annealing hardware is at a disadvantage in comparison to classical digital annealers, as well as gate-model quantum annealers, and could also serve as a benchmark for improvements of the standard quantum annealing protocol.