Efficient quantum and simulated annealing of Potts models using a half-hot constraint

Abstract

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\to \infty$, 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.

16 pages, 10 figures

References in corpus (12)

• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Mathematical Foundation of Quantum Annealing
• Observation of topological phenomena in a programmable lattice of 1,800 qubits
• Nonnegative/binary matrix factorization with a D-Wave quantum annealer
• Quantum annealing with antiferromagnetic fluctuations
• Energy gaps in quantum first-order mean-field-like transitions: The problems that quantum annealing cannot solve
• Simple Glass Models and their Quantum Annealing
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Dynamics of Order Parameters of Non-stoquastic Hamiltonians in the Adaptive Quantum Monte Carlo Method
• Exact expression of the energy gap at first-order quantum phase transitions of a non-stoquastic Hamiltonian
• Control of automated guided vehicles without collision by quantum annealer and digital devices

Cited by in corpus (3)

• Benchmark test of Black-box optimization using D-Wave quantum annealer
• CMOS-compatible Ising and Potts Annealing Using Single Photon Avalanche Diodes
• Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning