3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
arXiv:2103.08464 · doi:10.1088/2058-9565/ac4d1b
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.
arXiv comment14 pages, 3 figures. v2: Updated to published version
References in corpus (58)
- 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
- Adiabatic Quantum Computing
- Roulette-wheel selection via stochastic acceptance
- Quantum Search by Local Adiabatic Evolution
- Defining and detecting quantum speedup
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Bounds for the adiabatic approximation with applications to quantum computation
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Architectural considerations in the design of a superconducting quantum annealing processor
- Experimental Investigation of an Eight Qubit Unit Cell in a Superconducting Optimization Processor
- Feedback-optimized parallel tempering Monte Carlo
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- A practical heuristic for finding graph minors
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network: Toward quantum soft computing
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- A scalable control system for a superconducting adiabatic quantum optimization processor
- Quantum annealing with a network of all-to-all connected, two-photon driven Kerr nonlinear oscillators
- Probing for quantum speedup in spin glass problems with planted solutions
- Searching for quantum speedup in quasistatic quantum annealers
- A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
- Rejection-free Monte-Carlo sampling for general potentials
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Tunable Quantum Tunneling of Magnetic Domain Walls
- Consistency Tests of Classical and Quantum Models for a Quantum Annealer
- A ferromagnet with a glass transition
- A scalable readout system for a superconducting adiabatic quantum optimization system
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Quantum Computation Based on Quantum Adiabatic Bifurcations of Kerr-Nonlinear Parametric Oscillators
- Efficient Cluster Algorithm for Spin Glasses in Any Space Dimension
- Coherent coupled qubits for quantum annealing
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Domain-Wall Free-Energy of Spin Glass Models:Numerical Method and Boundary Conditions
- Memcomputing: Leveraging memory and physics to compute efficiently
- Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
- Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities
- Temperature scaling law for quantum annealing optimizers
- Next-Generation Topology of D-Wave Quantum Processors
- Readiness of Quantum Optimization Machines for Industrial Applications
- Analog Errors in Ising Machines
- Efficient sampling of ground and low-energy Ising spin configurations with a coherent Ising machine
- Exploring More-Coherent Quantum Annealing
- Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
- Equation Planting: A Tool for Benchmarking Ising Machines
- Optimally Stopped Optimization
- Garden optimization problems for benchmarking quantum annealers
- Perils of Embedding for Sampling Problems
- How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
- Jump Markov Chains and Rejection-Free Metropolis Algorithms
- MemComputing Integer Linear Programming
- 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
- Memcomputing for Accelerated Optimization
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 -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 XORCNF Boolean Satisfiability Problems Natively with In-Memory Computing
- Acceleration of digital memcomputing by jumps
- Families of 2D subsystem stabilizer codes for universal Hamiltonian quantum computation with two-body interactions