Equation Planting: A Tool for Benchmarking Ising Machines

Abstract

We introduce a methodology for generating benchmark problem sets for Ising machines---devices designed to solve discrete optimization problems cast as Ising models. In our approach, linear systems of equations are cast as Ising cost functions. While linear systems are easily solvable, the corresponding optimization problems are known to exhibit some of the salient features of NP-hardness, such as strong exponential scaling of heuristic solvers' runtimes and extensive distances between ground and low-lying excited states. We show how the proposed technique, which we refer to as `equation planting,' can serve as a useful tool for evaluating the utility of Ising solvers functioning either as optimizers or as ground-state samplers. We further argue that equation-planted problems can be used to probe the mechanisms underlying the operation of Ising machines.

8 pages, 4 figures

References in corpus (17)

• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Feedback-optimized parallel tempering Monte Carlo
• A practical heuristic for finding graph minors
• Thermal and Residual Excited-State Population in a 3D Transmon Qubit
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Memcomputing: Leveraging memory and physics to compute efficiently
• Phase transition in the three dimensional Heisenberg spin glass: Finite-size scaling analysis
• Memcomputing NP-complete problems in polynomial time using polynomial resources and collective states
• Inductance of Circuit Structures for MIT LL Superconductor Electronics Fabrication Process with 8 Niobium Layers
• A deceptive step towards quantum speedup detection
• Correlation length of the two-dimensional Ising spin glass with bimodal interactions
• Performance evaluation of coherent Ising machines against classical neural networks
• Analog Errors in Ising Machines
• Correlation Length of the Two-Dimensional Ising Spin Glass with Gaussian Interactions
• Mean-value identities as an opportunity for Monte Carlo error reduction
• MemComputing Integer Linear Programming
• Ground-state statistics from annealing algorithms: Quantum vs classical approaches

Cited by in corpus (16)

• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Finding spin-glass ground states using quantum walks
• Simulated bifurcation for higher-order cost functions
• The Wishart planted ensemble: A tunably-rugged pairwise Ising model with a first-order phase transition
• All-to-all reconfigurability with sparse and higher-order Ising machines
• Computational hardness of spin-glass problems with tile-planted solutions
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• Chook -- A comprehensive suite for generating binary optimization problems with planted solutions
• Boltzmann sampling with quantum annealers via fast Stein correction
• QUBO.jl: A Julia Ecosystem for Quadratic Unconstrained Binary Optimization
• Generating Hard Ising Instances With Planted Solutions Using Post-Quantum Cryptographic Protocols
• Posiform Planting: Generating QUBO Instances for Benchmarking
• Tensor networks for $p$-spin models
• Continuous Approximation of the Ising Hamiltonian: Exact Ground States and Applications to Fidelity Assessment in Ising Machines
• Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking