We compare the performance of quantum annealing (QA, through Schr\"odinger dynamics) and simulated annealing (SA, through a classical master equation) on the
p-spin infinite range ferromagnetic Ising model, by slowly driving the system across its equilibrium, quantum or classical, phase transition. When the phase transition is second order (
p=2, the familiar two-spin Ising interaction) SA shows a remarkable exponential speed-up over QA. For a first-order phase transition ($p\ensuremath{\ge}3$, i.e., with multispin Ising interactions), in contrast, the classical annealing dynamics appears to remain stuck in the disordered phase, while we have clear evidence that QA shows a residual energy which decreases towards zero when the total annealing time $\ensuremath{\tau}$ increases, albeit in a rather slow (logarithmic) fashion. This is one of the rare examples where a limited quantum speedup, a speedup by QA over SA, has been shown to exist by direct solutions of the Schr\"odinger and master equations in combination with a nonequilibrium Landau-Zener analysis. We also analyze the imaginary-time QA dynamics of the model, finding a $1/{\ensuremath{\tau}}^{2}$ behavior for all finite values of
p, as predicted by the adiabatic theorem of quantum mechanics. The Grover-search limit $p(\mathrm{odd})=\ensuremath{\infty}$ is also discussed.
The Potts model is a generalization of the Ising model with
Q>2 components. In the fully connected ferromagnetic Potts model, a first-order phase transition is induced by varying thermal fluctuations. Therefore, the computational time required to obtain the ground states by simulated annealing exponentially increases with the system size. This study analytically confirms that the transverse magnetic-field quantum annealing induces a first-order phase transition. This result implies that quantum annealing does not exponentially accelerate the ground-state search of the ferromagnetic Potts model. To avoid the first-order phase transition, we propose an iterative optimization method using a half-hot constraint that is applicable to both quantum and simulated annealing. In the limit of
Q→∞, a saddle point equation under the half-hot constraint is identical to the equation describing the behavior of the fully connected ferromagnetic Ising model, thus confirming a second-order phase transition. Furthermore, we verify the same relation between the fully connected Potts glass model and the Sherrington--Kirkpatrick model under assumptions of static approximation and replica symmetric solution. The proposed method is expected to obtain low-energy states of the Potts models with high efficiency using Ising-type computers such as the D-Wave quantum annealer and the Fujitsu Digital Annealer.
Ising machines have the potential to realize fast and highly accurate solvers for combinatorial optimization problems. They are classified based on their internal algorithms. Examples include simulated-annealing-based Ising machines (non-quantum-type Ising machines) and quantum-annealing-based Ising machines (quantum annealers). Herein we propose a hybrid optimization method, which utilizes the advantages of both types. In this hybrid optimization method, the preprocessing step is performed by solving the non-quantum-annealing Ising machine multiple times. Then sub-Ising models with a reduced size by spin fixing are solved using a quantum annealer. The performance of the hybrid optimization method is evaluated via simulations using Simulated Annealing (SA) as a non-quantum-type Ising machine and D-Wave Advantage as a quantum annealer. Additionally, we investigate the parameter dependence of the proposed hybrid optimization method. The hybrid optimization method outperforms the preprocessing SA and the quantum annealing machine alone in fully connected random Ising models.