Equation Planting: A Tool for Benchmarking Ising Machines
arXiv:1903.10928 · doi:10.1103/PhysRevApplied.12.011003
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.
arXiv comment8 pages, 4 figures
References in corpus (48)
- 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
- Parallel Tempering: Theory, Applications, and New Perspectives
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital 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
- Critical Behavior of the Three-Dimensional Ising Spin Glass
- A practical heuristic for finding graph minors
- Estimation of effective temperatures in quantum annealers for sampling applications: A case study with possible applications in deep learning
- Quantum Optimization of Fully-Connected Spin Glasses
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Thermal and Residual Excited-State Population in a 3D Transmon Qubit
- Application of Quantum Annealing to Training of Deep Neural Networks
- Fabrication Process and Properties of Fully-Planarized Deep-Submicron Nb/Al-AlOx/Nb Josephson Junctions for VLSI Circuits
- A scalable control system for a superconducting adiabatic quantum optimization processor
- Probing for quantum speedup in spin glass problems with planted solutions
- Low-temperature behavior of two-dimensional Gaussian Ising spin glasses
- A ferromagnet with a glass transition
- A scalable readout system for a superconducting adiabatic quantum optimization system
- The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- First-order transitions and the performance of quantum algorithms in random optimization problems
- 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
- Temperature scaling law for quantum annealing optimizers
- Unraveling Quantum Annealers using Classical Hardness
- Temperature chaos in 3D Ising Spin Glasses is driven by rare events
- Why temperature chaos in spin glasses is hard to observe
- Correlation length of the two-dimensional Ising spin glass with bimodal interactions
- Performance evaluation of coherent Ising machines against classical neural networks
- Thermalization, freeze-out and noise: deciphering experimental quantum annealers
- Analog Errors in Ising Machines
- Temperature Cycles in the Heisenberg Spin Glass
- Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
- Practical engineering of hard spin-glass instances
- Ground State Structure of Random Magnets
- The wormhole move: A new algorithm for polymer simulations
- Correlation Length of the Two-Dimensional Ising Spin Glass with Gaussian Interactions
- Advantages of Unfair Quantum Ground-State Sampling
- Complexity of several constraint satisfaction problems using the heuristic, classical, algorithm, WalkSAT
- 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 -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