2019/03/31 by Zheng Zhu, Andrew J. Ochoa, Helmut G. Katzgraber · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Binary number #Computer science #Condensed matter physics #Degenerate energy levels #Global optimization #Ground state #Heuristic #Heuristics #Hybrid Monte Carlo #Ising model #Markov chain Monte Carlo #Mathematical optimization #Mathematics #Monte Carlo method #Optimization problem #Parallel tempering #Physics #Quadratic unconstrained binary optimization #Quantum #Quantum Computing Algorithms and Architecture #Quantum Monte Carlo #Quantum annealing #Quantum computer #Quantum many-body systems #Quantum mechanics #Qubit #Simulated annealing #Spins #Statistical physics #Statistics #Theoretical and Computational Physics #cond-mat.dis-nn #quant-ph
paper · pdf · doi:10.1103/physreve.99.063314
published as Phys. Rev. E 99, 063314 (2019) · 7 pages, 7 figures, 2 tables
openalex publication_date 2019/06/25 · arxiv created 2019/06/26 · arxiv updated 2019/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 quantum annealer chimera topology. In addition, a simple heuristic to approximate the number of solutions of a degenerate problem is introduced.