Efficient quantum and simulated annealing of Potts models using a half-hot constraint
arXiv:1904.01522 · doi:10.7566/JPSJ.89.094801
Abstract
The Potts model is a generalization of the Ising model with 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 , 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.
arXiv comment16 pages, 10 figures
References in corpus (27)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Theory of Quantum Annealing of an Ising Spin Glass
- Defining and detecting quantum speedup
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Mathematical Foundation of Quantum Annealing
- Quantum Boltzmann Machine
- Observation of topological phenomena in a programmable lattice of 1,800 qubits
- What is the Computational Value of Finite Range Tunneling?
- Quantum annealing of the Traveling Salesman Problem
- Application of Quantum Annealing to Training of Deep Neural Networks
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- 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
- Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
- Simple Glass Models and their Quantum Annealing
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Efficiency of quantum versus classical annealing in non-convex learning problems
- Optimization by Quantum Annealing: Lessons from Simple Cases
- Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
- Quantum annealing speedup over simulated annealing on random Ising chains
- 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