Posiform Planting: Generating QUBO Instances for Benchmarking
arXiv:2308.05859 · doi:10.3389/fcomp.2023.1275948
Abstract
We are interested in benchmarking both quantum annealing and classical algorithms for minimizing Quadratic Unconstrained Binary Optimization (QUBO) problems. Such problems are NP-hard in general, implying that the exact minima of randomly generated instances are hard to find and thus typically unknown. While brute forcing smaller instances is possible, such instances are typically not interesting due to being too easy for both quantum and classical algorithms. In this contribution, we propose a novel method, called posiform planting, for generating random QUBO instances of arbitrary size with known optimal solutions, and use those instances to benchmark the sampling quality of four D-Wave quantum annealers utilizing different interconnection structures (Chimera, Pegasus, and Zephyr hardware graphs) as well as the simulated annealing algorithm. Posiform planting differs from many existing methods in two key ways. It ensures the uniqueness of the planted optimal solution, thus avoiding groundstate degeneracy, and it enables the generation of QUBOs that are tailored to a given hardware connectivity structure, provided that the connectivity is not too sparse. Posiform planted QUBOs are a type of 2-SAT boolean satisfiability combinatorial optimization problems. Our experiments demonstrate the capability of the D-Wave quantum annealers to sample the optimal planted solution of combinatorial optimization problems with up to qubits.
References in corpus (45)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- A Quantum Approximate Optimization Algorithm
- Quantum annealing with more than one hundred qubits
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Annealing and Analog Quantum Computation
- Perspectives of quantum annealing: Methods and implementations
- Statistical physics of inference: Thresholds and algorithms
- Mathematical Foundation of Quantum Annealing
- Experimental signature of programmable quantum annealing
- What is the Computational Value of Finite Range Tunneling?
- Quantum critical dynamics in a 5000-qubit programmable spin glass
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Coherent quantum annealing in a programmable 2000-qubit Ising chain
- Quantum Optimization of Fully-Connected Spin Glasses
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Entanglement in a quantum annealing processor
- Probing for quantum speedup in spin glass problems with planted solutions
- Scaling advantage in quantum simulation of geometrically frustrated magnets
- Hiding Quiet Solutions in Random Constraint Satisfaction Problems
- Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
- Hiding solutions in random satisfiability problems: A statistical mechanics approach
- Benchmarking a quantum annealing processor with the time-to-target metric
- The asymptotic -SAT threshold
- Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
- Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
- Pegasus: The second connectivity graph for large-scale quantum annealing hardware
- MAX 2-SAT with up to 108 qubits
- Benchmarking Hamiltonian Noise in the D-Wave Quantum Annealer
- 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
- Uncertain fate of fair sampling in quantum annealing
- Scaling overhead of embedding optimization problems in quantum annealing
- Advantages of Unfair Quantum Ground-State Sampling
- On the Emerging Potential of Quantum Annealing Hardware for Combinatorial Optimization
- Equation Planting: A Tool for Benchmarking Ising Machines
- Computational hardness of spin-glass problems with tile-planted solutions
- Estimating the Density of States of Frustrated Spin Systems
- Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
- Noise Dynamics of Quantum Annealers: Estimating the Effective Noise Using Idle Qubits
- Achieving fair sampling in quantum annealing
- Patch-planting spin-glass solution for benchmarking
- Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
- Chook -- A comprehensive suite for generating binary optimization problems with planted solutions
- Probing Environmental Spin Polarization with Superconducting Flux Qubits
- Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms