Optimally Stopped Optimization

Abstract

We combine the fields of heuristic optimization and optimal stopping. We propose a strategy for benchmarking randomized optimization algorithms that minimizes the expected total cost for obtaining a good solution with an optimal number of calls to the solver. To do so, rather than letting the objective function alone define a cost to be minimized, we introduce a further cost-per-call of the algorithm. We show that this problem can be formulated using optimal stopping theory. The expected cost is a flexible figure of merit for benchmarking probabilistic solvers that can be computed when the optimal solution is not known, and that avoids the biases and arbitrariness that affect other measures. The optimal stopping formulation of benchmarking directly leads to a real-time, optimal-utilization strategy for probabilistic optimizers with practical impact. We apply our formulation to benchmark simulated annealing on a class of MAX2SAT problems. We also compare the performance of a D-Wave 2X quantum annealer to the HFS solver, a specialized classical heuristic algorithm designed for low tree-width graphs. On a set of frustrated-loop instances with planted solutions defined on up to N = 1098 variables, the D-Wave device is two orders of magnitude faster than the HFS solver, and, modulo known caveats related to suboptimal annealing times, exhibits identical scaling with problem size.

21 pages, 8 figures

References in corpus (17)

• Quantum Annealing in the Transverse Ising Model
• Quantum annealing with more than one hundred qubits
• Quantum Annealing and Analog Quantum Computation
• Defining and detecting quantum speedup
• Architectural considerations in the design of a superconducting quantum annealing processor
• Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
• What is the Computational Value of Finite Range Tunneling?
• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Quantum Optimization of Fully-Connected Spin Glasses
• Quantum Speedup by Quantum Annealing
• A scalable control system for a superconducting adiabatic quantum optimization processor
• 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
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• A scalable readout system for a superconducting adiabatic quantum optimization system
• Tunneling and speedup in quantum optimization for permutation-symmetric problems

Cited by in corpus (17)

• Demonstration of a scaling advantage for a quantum annealer over simulated annealing
• Probing the Universality of Topological Defect Formation in a Quantum Annealer: Kibble-Zurek Mechanism and Beyond
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Temperature scaling law for quantum annealing optimizers
• Demonstration of algorithmic quantum speedup
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Performance of a Quantum Annealer for Ising Ground State Computations on Chimera Graphs
• Quantum-assisted associative adversarial network: Applying quantum annealing in deep learning
• Nested Quantum Annealing Correction at Finite Temperature: $p$-spin models
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Diabatic Quantum Annealing for the Frustrated Ring Model
• A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
• Advantage of pausing: parameter setting for quantum annealers
• Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Optimally Stopped Variational Quantum Algorithms
• Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments