Fair sampling of ground-state configurations of binary optimization problems
arXiv:1903.07600 · doi:10.1103/PhysRevE.99.063314
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 (35)
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing and Analog Quantum Computation
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- Mathematical Foundation of Quantum Annealing
- Architectural considerations in the design of a superconducting quantum annealing processor
- Experimental signature of programmable quantum annealing
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Quantum Optimization of Fully-Connected Spin Glasses
- Error corrected quantum annealing with hundreds of qubits
- Entanglement in a quantum annealing processor
- Probing for quantum speedup in spin glass problems with planted solutions
- A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Quantum annealing correction for random Ising problems
- Reexamining classical and quantum models for the D-Wave One processor
- Quantum Annealing Correction with Minor Embedding
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
- A deceptive step towards quantum speedup detection
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
- Unraveling Quantum Annealers using Classical Hardness
- MAX 2-SAT with up to 108 qubits
- The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
- Degeneracy, degree, and heavy tails in quantum annealing
- Assessment of Quantum Annealing for the Construction of Satisfiability Filters
Cited by in corpus (10)
- Efficient sampling of ground and low-energy Ising spin configurations with a coherent Ising machine
- Comparing Three Generations of D-Wave Quantum Annealers for Minor Embedded Combinatorial Optimization Problems
- Approximate optimization, sampling and spin-glass droplets discovery with tensor networks
- Sampling diverse near-optimal solutions via algorithmic quantum annealing
- Analysis of a Programmable Quantum Annealer as a Random Number Generator
- Mapping State Transition Susceptibility in Quantum Annealing
- Biased Degenerate Ground-State Sampling of Small Ising Models with Converged QAOA
- Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
- Boltzmann Sampling of Frustrated J1 - J2 Ising Models with Programmable Quantum Annealers