Comparative Study of the Performance of Quantum Annealing and Simulated Annealing

Abstract

Relations of simulated annealing and quantum annealing are studied by a mapping from the transition matrix of classical Markovian dynamics of the Ising model to a quantum Hamiltonian and vice versa. It is shown that these two operators, the transition matrix and the Hamiltonian, share the eigenvalue spectrum. Thus, if simulated annealing with slow temperature change does not encounter a difficulty caused by an exponentially long relaxation time at a first-order phase transition, the same is true for the corresponding process of quantum annealing in the adiabatic limit. One of the important differences between the classical-to-quantum mapping and the converse quantum-to-classical mapping is that the Markovian dynamics of a short-range Ising model is mapped to a short-range quantum system, but the converse mapping from a short-range quantum system to a classical one results in long-range interactions. This leads to a difference in efficiencies that simulated annealing can be efficiently simulated by quantum annealing but the converse is not necessarily true. We conclude that quantum annealing is easier to implement and is more flexible than simulated annealing. We also point out that the present mapping can be extended to accommodate explicit time dependence of temperature, which is used to justify the quantum-mechanical analysis of simulated annealing by Somma, Batista, and Ortiz. Additionally, an alternative method to solve the non-equilibrium dynamics of the one-dimensional Ising model is provided through the classical-to-quantum mapping.

19 pages

References in corpus (5)

• Mathematical Foundation of Quantum Annealing
• Quantum annealing with antiferromagnetic fluctuations
• A Quantum Approach to Classical Statistical Mechanics
• Many-body transverse interactions in the quantum annealing of the p-spin ferromagnet
• Approaching the Ground State of a Quantum Spin Glass using a Zero-Temperature Quantum Monte Carlo

Cited by in corpus (10)

• Decoherence in adiabatic quantum computation
• Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
• Algorithm engineering for a quantum annealing platform
• Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Exploring Unsupervised Anomaly Detection with Quantum Boltzmann Machines in Fraud Detection
• Towards Transfer Learning for Large-Scale Image Classification Using Annealing-based Quantum Boltzmann Machines
• Quantum Annealing and Graph Neural Networks for Solving TSP with QUBO
• Convergence condition of simulated quantum annealing for closed and open systems
• Convergence condition of simulated quantum annealing with a non-stoquastic catalyst