3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers

Abstract

With current semiconductor technology reaching its physical limits, special-purpose hardware has emerged as an option to tackle specific computing-intensive challenges. Optimization in the form of solving Quadratic Unconstrained Binary Optimization (QUBO) problems, or equivalently Ising spin glasses, has been the focus of several new dedicated hardware platforms. These platforms come in many different flavors, from highly-efficient hardware implementations on digital-logic of established algorithms to proposals of analog hardware implementing new algorithms. In this work, we use a mapping of a specific class of linear equations whose solutions can be found efficiently, to a hard constraint satisfaction problem (3-regular 3-XORSAT, or an Ising spin glass) with a 'golf-course' shaped energy landscape, to benchmark several of these different approaches. We perform a scaling and prefactor analysis of the performance of Fujitsu's Digital Annealer Unit (DAU), the D-Wave Advantage quantum annealer, a Virtual MemComputing Machine, Toshiba's Simulated Bifurcation Machine (SBM), the SATonGPU algorithm from Bernaschi et al., and our implementation of parallel tempering. We identify the SATonGPU and DAU as currently having the smallest scaling exponent for this benchmark, with SATonGPU having a small scaling advantage and in addition having by far the smallest prefactor thanks to its use of massive parallelism. Our work provides an objective assessment and a snapshot of the promise and limitations of dedicated optimization hardware relative to a particular class of optimization problems.

14 pages, 3 figures. v2: Updated to published version

References in corpus (16)

• Bounds for the adiabatic approximation with applications to quantum computation
• Feedback-optimized parallel tempering Monte Carlo
• Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
• A practical heuristic for finding graph minors
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Consistency Tests of Classical and Quantum Models for a Quantum Annealer
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
• Next-Generation Topology of D-Wave Quantum Processors
• Efficient sampling of ground and low-energy Ising spin configurations with a coherent Ising machine
• Optimally Stopped Optimization
• Garden optimization problems for benchmarking quantum annealers
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• Performance benefits of increased qubit connectivity in quantum annealing 3-dimensional spin glasses
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• Digital Annealer for quadratic unconstrained binary optimization: a comparative performance analysis

Cited by in corpus (25)

• Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
• Simulated bifurcation for higher-order cost functions
• All-to-all reconfigurability with sparse and higher-order Ising machines
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Energy landscapes of combinatorial optimization in Ising machines
• Signatures of Open and Noisy Quantum Systems in Single-Qubit Quantum Annealing
• Noise-augmented Chaotic Ising Machines for Combinatorial Optimization and Sampling
• Towards an Automatic Framework for Solving Optimization Problems with Quantum Computers
• Hybrid Optimization Method Using Simulated-Annealing-Based Ising Machine and Quantum Annealer
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Dynamical process of a bit-width reduced Ising model with simulated annealing
• QUBO.jl: A Julia Ecosystem for Quadratic Unconstrained Binary Optimization
• Accelerating Optimal Elemental Configuration Search in Crystal using Ising Machine
• Fully parallel implementation of digital memcomputing on FPGA
• SPICE Modeling of Memcomputing Logic Gates
• Deep Unfolded Local Quantum Annealing
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Mapping State Transition Susceptibility in Quantum Annealing
• Tensor networks for $p$-spin models
• Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo
• A Statistical Analysis for Per-Instance Evaluation of Stochastic Optimizers: Avoiding Unreliable Conclusions
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
• Accelerating Hybrid XOR$-$CNF Boolean Satisfiability Problems Natively with In-Memory Computing
• Acceleration of digital memcomputing by jumps
• Families of $d=2$ 2D subsystem stabilizer codes for universal Hamiltonian quantum computation with two-body interactions