Physical review. A/Physical review, A · 2018 · 58 citations · 48 references
Natural SciencesPhysicsComputational PhysicsCondensed Matter PhysicsQuantum MechanicsPhase TransitionsQuantum AnnealingQuantum TunnelingAnnealingClassical Simulated Annealing ComparisonFirst-order Phase TransitionsQuantum AdvantageQuantum Annealing SimulationQuantum Phase TransitionsQuantum Phase Transitions In MagnetismSimulated Annealing
We solve the mean-field-like $p$-spin Ising model under a spatiotemporal inhomogeneous transverse field to study the effects of inhomogeneity on the performance of quantum annealing. We previously found that the problematic first-order quantum phase transition that arises under the conventional homogeneous field protocol can be avoided if the temperature is zero and the local field is completely turned off site by site after a finite time. We show in the present paper that, when these ideal conditions are not satisfied, another series of first-order transitions appear, which prevents us from driving the system while avoiding first-order transitions. Nevertheless, under these nonideal conditions, quantitative improvements can be obtained in terms of narrower tunneling barriers in the free-energy landscape. A comparison with classical simulated annealing establishes a limited quantum advantage in the ideal case, since inhomogeneous temperature driving in simulated annealing cannot remove a first-order transition, in contrast to the quantum case. The classical model of spin-vector Monte Carlo is also analyzed, and we find it to have the same thermodynamic phase diagram as the quantum model in the ideal case, with deviations arising at nonzero temperature.
48
Optimization by Simulated Annealing
Scott Kirkpatrick, C. D. Gelatt, M.P. Vecchi · Science · 1983 · 44.6K citations
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Lov K. Grover · Physical Review Letters · 1997 · 4.4K citations · Full text
Computing, Computer Science, Physics +11
Ising formulations of many NP problems
Andrew Lucas · Frontiers in Physics · 2014 · 2.5K citations · Full text
Computing, Computer Science, Physics +15
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Edward Farhi, Jeffrey Goldstone, Sam Gutmann et al. · Science · 2001 · 2.1K citations · Full text
Computing, Computer Science, Physics +15