Guiding Principle for Minor-Embedding in Simulated-Annealing-Based Ising Machines
arXiv:2012.02372 · doi:10.1109/ACCESS.2020.3040017
Abstract
We propose a novel type of minor-embedding (ME) in simulated-annealing-based Ising machines. The Ising machines can solve combinatorial optimization problems. Many combinatorial optimization problems are mapped to find the ground (lowest-energy) state of the logical Ising model. When connectivity is restricted on Ising machines, ME is required for mapping from the logical Ising model to a physical Ising model, which corresponds to a specific Ising machine. Herein we discuss the guiding principle of ME design to achieve a high performance in Ising machines. We derive the proposed ME based on a theoretical argument of statistical mechanics. The performance of the proposed ME is compared with two existing types of MEs for different benchmarking problems. Simulated annealing shows that the proposed ME outperforms existing MEs for all benchmarking problems, especially when the distribution of the degree in a logical Ising model has a large standard deviation. This study validates the guiding principle of using statistical mechanics for ME to realize fast and high-precision solvers for combinatorial optimization problems.
arXiv comment13 pages, 8 figures
References in corpus (18)
- Statistical mechanics of complex networks
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Quantum annealing with more than one hundred qubits
- Defining and detecting quantum speedup
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Observation of topological phenomena in a programmable lattice of 1,800 qubits
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Architectural considerations in the design of a superconducting quantum annealing processor
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- A practical heuristic for finding graph minors
- Expanding the horizon of automated metamaterials discovery via quantum annealing
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
- Training a Binary Classifier with the Quantum Adiabatic Algorithm
- Pegasus: The second connectivity graph for large-scale quantum annealing hardware
- Toward Practical-Scale Quantum Annealing Machine for Prime Factoring
- A Performance Estimator for Quantum Annealers: Gauge selection and Parameter Setting