We benchmark Quantum Annealing (QA) vs. Simulated Annealing (SA) witha focus on the impact of the embedding of problems onto the differenttopologies of the D-Wave quantum annealers. The series of problems we studyare especially designed instances of the maximum cardinality matching problemthat are easy to solve classically but difficult for SA and, as found experimentally,not easy for QA either. In addition to using several D-Wave processors, wesimulate the QA process by numerically solving the time-dependent Schrödingerequation. We find that the embedded problems can be significantly moredifficult than the unembedded problems, and some parameters, such as thechain strength, can be very impactful for finding the optimal solution. Thus,finding a good embedding and optimal parameter values can improve theresults considerably. Interestingly, we find that although SA succeeds for theunembedded problems, the SA results obtained for the embedded versionscale quite poorly in comparison with what we can achieve on the D-Wavequantum annealers.
Vert et al. (Wed,) studied this question.