Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
arXiv:1706.07826 · doi:10.1103/PhysRevE.96.043312
Abstract
We present and apply a general-purpose, multi-start algorithm for improving the performance of low-energy samplers used for solving optimization problems. The algorithm iteratively fixes the value of a large portion of the variables to values that have a high probability of being optimal. The resulting problems are smaller and less connected, and samplers tend to give better low-energy samples for these problems. The algorithm is trivially parallelizable, since each start in the multi-start algorithm is independent, and could be applied to any heuristic solver that can be run multiple times to give a sample. We present results for several classes of hard problems solved using simulated annealing, path-integral quantum Monte Carlo, parallel tempering with isoenergetic cluster moves, and a quantum annealer, and show that the success metrics as well as the scaling are improved substantially. When combined with this algorithm, the quantum annealer's scaling was substantially improved for native Chimera graph problems. In addition, with this algorithm the scaling of the time to solution of the quantum annealer is comparable to the Hamze--de Freitas--Selby algorithm on the weak-strong cluster problems introduced by Boixo et al. Parallel tempering with isoenergetic cluster moves was able to consistently solve 3D spin glass problems with 8000 variables when combined with our method, whereas without our method it could not solve any.
15 pages, 12 figures
References in corpus (31)
- Ising formulations of many NP problems
- Exchange Monte Carlo Method and Application to Spin Glass Simulations
- Quantum Annealing in the Transverse Ising Model
- Quantum annealing with more than one hundred qubits
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Architectural considerations in the design of a superconducting quantum annealing processor
- What is the Computational Value of Finite Range Tunneling?
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Quantum versus Classical Annealing of Ising Spin Glasses
- Probing for quantum speedup in spin glass problems with planted solutions
- Optimized simulated annealing for Ising spin glasses
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- 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
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- 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
- Tunneling and speedup in quantum optimization for permutation-symmetric problems
- Benchmarking a quantum annealing processor with the time-to-target metric
- A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
- Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
- Population annealing: Theory and application in spin glasses
- Boosting quantum annealer performance via sample persistence
- The pitfalls of planar spin-glass benchmarks: Raising the bar for quantum annealers (again)
- borealis - A generalized global update algorithm for Boolean optimization problems
- Patch-planting spin-glass solution for benchmarking
Cited by in corpus (24)
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Temperature scaling law for quantum annealing optimizers
- Network Community Detection On Small Quantum Computers
- Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers
- Readiness of Quantum Optimization Machines for Industrial Applications
- From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems
- Quantum-Informed Recursive Optimization Algorithms
- Hybrid Quantum Annealing via Molecular Dynamics
- Quantum Annealing for Jet Clustering with Thrust
- Greedy parameter optimization for diabatic quantum annealing
- Viewing Vanilla Quantum Annealing Through Spin Glasses
- Patch-planting spin-glass solution for benchmarking
- Hybrid Optimization Method Using Simulated-Annealing-Based Ising Machine and Quantum Annealer
- Feeding the multitude: A polynomial-time algorithm to improve sampling
- Modernizing Quantum Annealing II: Genetic algorithms with the Inference Primitive Formalism
- Dynamical process of a bit-width reduced Ising model with simulated annealing
- Optimized QUBO formulation methods for quantum computing
- Advantages of fixing spins in quantum annealing
- Improving the efficiency of quantum annealing with controlled diagonal catalysts
- Enhancing Quantum Annealing in Digital-Analog Quantum Computing
- Impact of Fixing Spins in a Quantum Annealer with Energy Rescaling
- Performance of Domain-Wall Encoding for Quantum Annealing
- Optimization and benchmarking of the thermal cycling algorithm
- Frustration-enhanced quantum annealing correction models with additional inter-replica interactions