Résumé |
Quantum annealing (QA), or quantum adiabatic computation, is one of the quantum computing technologies
used to
search for solutions to combinatorial optimization problems. While its application in real machines has been
actively
studied, it is not believed to efficiently solve NP problems, a class of difficult problems in computational
complexity
theory. For this reason, the physical mechanisms by which QA fails to solve the problem have been studied,
and one
scenario of failure has been proposed to be the emergence of a first-order phase transition during the QA
computation
process. We have shown mathematically that a certain first-order phase transition can be easily avoided in
random spin
systems on finite-dimensional lattices, including the three-dimensional Ising spin-glass model, which is one
of the NP-
hard problems[1]. I would like to discuss the implications of this finding.
[1] Mizuki Yamaguchi, Naoto Shiraishi, Koji Hukushima, Proof of avoidability of the quantum first-order
transition in
transverse magnetization in quantum annealing of finite-dimensional spin glasses,
https://arxiv.org/abs/2307.00791 |