Evolutionary Approaches to Optimization Problems in Chimera Topologies

Abstract

Chimera graphs define the topology of one of the first commercially available quantum computers. A variety of optimization problems have been mapped to this topology to evaluate the behavior of quantum enhanced optimization heuristics in relation to other optimizers, being able to efficiently solve problems classically to use them as benchmarks for quantum machines. In this paper we investigate for the first time the use of Evolutionary Algorithms (EAs) on Ising spin glass instances defined on the Chimera topology. Three genetic algorithms (GAs) and three estimation of distribution algorithms (EDAs) are evaluated over $1000$ hard instances of the Ising spin glass constructed from Sidon sets. We focus on determining whether the information about the topology of the graph can be used to improve the results of EAs and on identifying the characteristics of the Ising instances that influence the success rate of GAs and EDAs.

8 pages, 5 figures, 3 tables

References in corpus (9)

• Quantum Annealing in the Transverse Ising Model
• Theory of Quantum Annealing of an Ising Spin Glass
• Optimized simulated annealing for Ising spin glasses
• Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
• Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
• From local to global ground states in Ising spin glasses
• Efficient subgraph-based sampling of Ising-type models with frustration
• A note on QUBO instances defined on Chimera graphs
• Analysis of Evolutionary Algorithms on the One-Dimensional Spin Glass with Power-Law Interactions