Fair sampling of ground-state configurations of binary optimization problems

Abstract

Although many efficient heuristics have been developed to solve binary optimization problems, these typically produce correlated solutions for degenerate problems. Most notably, transverse-field quantum annealing - the heuristic employed in current commercially-available quantum annealing machines - has been shown to often be exponentially biased when sampling the solution space. Here we present an approach to sample ground-state (or low-energy) configurations for binary optimization problems. The method samples degenerate states with almost equal probability and is based on a combination of parallel tempering Monte Carlo with isoenergetic cluster moves. We illustrate the approach using two-dimensional Ising spin glasses, as well as spin glasses on the D-Wave Systems Inc. quantum annealer chimera topology. In addition, a simple heuristic to approximate the number of solutions of a degenerate problem is introduced.

7 pages, 7 figures, 2 tables

References in corpus (7)

• Mathematical Foundation of Quantum Annealing
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• Quantum annealing correction for random Ising problems
• Reexamining classical and quantum models for the D-Wave One processor
• Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo