Comparison of quantum annealing and simulated annealing

秀稔 西森, Hidetoshi Nishimori

Michael Streif, Martin Leib

We present a comparison between the Quantum Approximate Optimization Algorithm (QAOA) and two widely studied competing methods, Quantum Annealing (QA) and Simulated Annealing (SA). To achieve this, we define a class of optimization problems with respect to their spectral properties which are exactly solvable with QAOA. In this class, we identify instances for which QA and SA have an exponentially small probability to find the solution. Consequently, our results define a first demarcation line between QAOA, Simulated Annealing and Quantum Annealing, and highlight the fundamental differences between an interference-based search heuristic such as QAOA and heuristics that are based on thermal and quantum fluctuations like SA and QA respectively.

Daniel Vert, Madita Willsch, Berat Yenilen +3 more

We benchmark Quantum Annealing (QA) vs. Simulated Annealing (SA) with a focus on the impact of the embedding of problems onto the different topologies of the D-Wave quantum annealers. The series of problems we study are especially designed instances of the maximum cardinality matching problem that 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, we simulate the QA process by numerically solving the time-dependent Schrödinger equation. We find that the embedded problems can be significantly more difficult than the unembedded problems, and some parameters, such as the chain strength, can be very impactful for finding the optimal solution. Thus, finding a good embedding and optimal parameter values can improve the results considerably. Interestingly, we find that although SA succeeds for the unembedded problems, the SA results obtained for the embedded version scale quite poorly in comparison with what we can achieve on the D-Wave quantum annealers.

Matthias Troyer

Stéphane Louise

In this paper, we aim to compare Vector Annealing (VA), a quantum-inspired metaheuristic introduced by NEC, with other metaheuristics. For this comparison, we utilize Quantum Annealing (QA), as implemented by D-Wave, and the conventional Simulated Annealing (SA) as a reference point for the capabilities of classical hardware with classical algorithms. The applications used for performance evaluation are two important benchmark programs designed to assess quantum hardware. This comparison is relevant because, for benchmarking purposes, it is valuable to have reference points between classical and quantum computing. It is widely thought that quantum computers will take some time to reach the level of relevance currently held by classical computing. This research, focusing on the Q-Score benchmark and Maximum Cardinality Matching (MCM) problems -both part of the MetriQs/BACQ benchmarking initiative- demonstrates this point. Through this work, we also trace the evolution from VA 2.0 to VA 3.0. While VA 2.0 already showed a significant advantage over both QA and SA in constrained problems, VA 3.0 introduces substantial optimizations and overcomes previous limitations in unconstrained problems. This advancement highlights the potential of VA 3.0. Furthermore, this work paves the way for the comprehensive testing of VA within the context of the MetriQs/BACQ quantum benchmark, an application-oriented French benchmarking initiative for quantum computers.

秀稔 西森, Hidetoshi Nishimori, 淳一 津田 +2 more