Energy landscapes of combinatorial optimization in Ising machines

Abstract

Physics-based Ising machines (IM) have been developed as dedicated processors for solving hard combinatorial optimization problems with higher speed and better energy efficiency. Generally, such systems employ local search heuristics to traverse energy landscapes in searching for optimal solutions. Here, we quantify and address some of the major challenges met by IMs by extending energy-landscape geometry visualization tools known as disconnectivity graphs. Using efficient sampling methods, we visually capture landscapes of problems having diverse structure and hardness manifesting as energetic and entropic barriers for IMs. We investigate energy barriers, local minima, and configuration space clustering effects caused by locality reduction methods when embedding combinatorial problems to the Ising hardware. To this end, we sample disconnectivity graphs of PUBO energy landscapes and their different QUBO mappings accounting for both local minima and saddle regions. We demonstrate that QUBO energy landscape properties lead to the subpar performance for quadratic IMs and suggest directions for their improvement.

References in corpus (28)

• Defining and detecting quantum speedup
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• The double-funnel energy landscape of the 38-atom Lennard-Jones cluster
• Phase Transitions in the Coloring of Random Graphs
• What is the Computational Value of Finite Range Tunneling?
• Clustering of solutions in the random satisfiability problem
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
• Probing for quantum speedup in spin glass problems with planted solutions
• A Cluster Monte Carlo Algorithm for 2-Dimensional Spin Glasses
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Energy landscapes, supergraphs, and "folding funnels" in spin systems
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• Readiness of Quantum Optimization Machines for Industrial Applications
• Scaling overhead of embedding optimization problems in quantum annealing
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Disordered Systems Insights on Computational Hardness
• Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
• Random Walk over Basins of Attraction to Construct Ising Energy Landscapes
• Walksat stalls well below the satisfiability threshold
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs
• A new method for analyzing ground-state landscapes: ballistic search
• Numerical Solution-Space Analysis of Satisfiability Problems
• Sampling diverse near-optimal solutions via algorithmic quantum annealing

Cited by in corpus (4)

• Solving Boolean satisfiability problems with resistive content addressable memories
• General Oscillator-Based Ising Machine Models with Phase-Amplitude Dynamics and Polynomial Interactions
• It's Quick to be Square: Fast Quadratisation for Quantum Toolchains
• Accelerating Hybrid XOR$-$CNF Boolean Satisfiability Problems Natively with In-Memory Computing