Relation between classical stochastic dynamics and quantum annealing

秀稔 西森, Hidetoshi Nishimori

Hidetoshi Nishimori

Non-equilibrium dynamics of the Ising model is a classical stochastic process whereas quantum mechanics has no stochastic elements in the classical sense. Nevertheless, it has been known that there exists a close formal relationship between these two processes. We reformulate this relationship and use it to compare the efficiency of simulated annealing that uses classical stochastic processes and quantum annealing to solve combinatorial optimization problems. It is shown that classical dynamics can be efficiently simulated by quantum- mechanical processes whereas the converse is not necessarily true. This may imply that quantum annealing may be regarded as a more powerful tool than simulated annealing for optimization problems.

悟史 森田, Satoshi Morita, 秀稔 西森 +1 more

Satoshi Morita, Hidetoshi Nishimori

Quantum annealing is a generic name of quantum algorithms that use quantum-mechanical fluctuations to search for the solution of an optimization problem. It shares the basic idea with quantum adiabatic evolution studied actively in quantum computation. The present paper reviews the mathematical and theoretical foundations of quantum annealing. In particular, theorems are presented for convergence conditions of quantum annealing to the target optimal state after an infinite-time evolution following the Schrödinger or stochastic (Monte Carlo) dynamics. It is proved that the same asymptotic behavior of the control parameter guarantees convergence for both the Schrödinger dynamics and the stochastic dynamics in spite of the essential difference of these two types of dynamics. Also described are the prescriptions to reduce errors in the final approximate solution obtained after a long but finite dynamical evolution of quantum annealing. It is shown there that we can reduce errors significantly by an ingenious choice of annealing schedule (time dependence of the control parameter) without compromising computational complexity qualitatively. A review is given on the derivation of the convergence condition for classical simulated annealing from the view point of quantum adiabaticity using a classical-quantum mapping.

Taiga Kubuta, Duckgyu Shin, Naoya Onizawa +1 more

It is well-known that quantum annealing (QA) is an excellent algorithm for solving combinatorial optimization problems (COPs). However, its hardware implementation poses challenges, requiring quantum devices. Therefore, a quantum Monte Carlo (QMC) method-based annealing approach called Simulated Quantum Annealing (SQA), which aims to emulate quantum annealing using classical computers, has been proposed. In the demo-night session, we will demonstrate a SQA based on stochastic computing (SC) on a standard FPGA board, called “PYNQ”. The use of SC-based data representation, along with the realization of SC-based spin-gate circuits, makes it possible to drastically reduce hardware costs compared to QA. This enhances the suitability for extending large-scale COPs.

Adam Majewski, Bogusław Zegarliński