Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
arXiv:2206.06876 · doi:10.1103/PhysRevResearch.5.023151
Abstract
An algorithm for a particular problem may find some instances of the problem easier and others harder to solve, even for a fixed input size. We numerically analyse the relative hardness of MAX 2-SAT problem instances for various continuous-time quantum algorithms and a comparable classical algorithm. This has two motivations: to investigate whether small-sized problem instances, which are commonly used in numerical simulations of quantum algorithms for benchmarking purposes, are a good representation of larger instances in terms of their hardness to solve, and to determine the applicability of continuous-time quantum algorithms in a portfolio approach, where we take advantage of the variation in the hardness of instances between different algorithms by running them in parallel. We find that, while there are correlations in instance hardness between all of the algorithms considered, they appear weak enough that a portfolio approach would likely be desirable in practice. Our results also show a widening range of hardness of randomly generated instances as the problem size is increased, which demonstrates both the difference in the distribution of hardness at small sizes and the value of a portfolio approach that can reduce the number of extremely hard instances. We identify specific weaknesses of these quantum algorithms that can be overcome with a portfolio approach, such their inability to efficiently solve satisfiable instances (which is easy classically).
arXiv comment14 pages, 9 figures. Published in Physical Review Research with minor differences
References in corpus (25)
- SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
- Array Programming with NumPy
- Adiabatic Quantum Computing
- Quantum Computation and Decision Trees
- A Quantum Random Walk Search Algorithm
- Quantum Search by Local Adiabatic Evolution
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Reachability Deficits in Quantum Approximate Optimization
- Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Reverse annealing for the fully connected -spin model
- Modernizing Quantum Annealing using Local Searches
- Training A Quantum Optimizer
- MAX 2-SAT with up to 108 qubits
- Parallel Quantum Annealing
- Quantum annealing with longitudinal bias fields
- Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
- Finding spin-glass ground states using quantum walks
- Heavy tails in the distribution of time-to-solution for classical and quantum annealing
- An energetic perspective on rapid quenches in quantum annealing
- Optimally Stopped Optimization
- Quantum Annealing Algorithms for Boolean Tensor Networks
- Search range in experimental quantum annealing
- Irreconcilable Difference Between Quantum Walks and Adiabatic Quantum Computing
- Quantum Portfolios
Cited by in corpus (5)
- Continuous-time quantum walks for MAX-CUT are hot
- Adiabatic Bottlenecks in Quantum Annealing and Nonequilibrium Dynamics of Paramagnons
- Posiform Planting: Generating QUBO Instances for Benchmarking
- Quantum annealing and condensed matter physics
- Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems