Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
arXiv:2502.01423 · doi:10.1103/n7r5-s63q
Abstract
Using a specially constructed set of hard 2-SAT problems with four satisfying assignments, we study the scaling and sampling performance of numerical simulation of quantum annealing as well as that of the physical quantum annealers offered by D-Wave. To this end, we use both the standard quantum annealing and reverse annealing protocols in both our simulations and on the D-Wave quantum annealer. In the case of ideal quantum annealing the sampling behavior can be explained by perturbation theory and the scaling behavior of the time to solution depends on the scaling behavior of the minimum energy gap between the ground state and the first excited state of the annealing Hamiltonian. The corresponding results from the D-Wave quantum annealers do not fit to this ideal picture, but suggest that the scaling of the time to solution from the quantum annealers matches those calculated from the equilibrium probability distribution.
References in corpus (38)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Adiabatic Quantum Computing
- Quantum annealing with more than one hundred qubits
- Quantum computing for finance: overview and prospects
- Defining and detecting quantum speedup
- Mathematical Foundation of Quantum Annealing
- Bounds for the adiabatic approximation with applications to quantum computation
- Observation of topological phenomena in a programmable lattice of 1,800 qubits
- Quantum Risk Analysis
- What is the Computational Value of Finite Range Tunneling?
- Reverse Quantum Annealing Approach to Portfolio Optimization Problems
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Error corrected quantum annealing with hundreds of qubits
- Quantum versus Classical Annealing of Ising Spin Glasses
- A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
- Probing for quantum speedup in spin glass problems with planted solutions
- A scheme for direct detection of qubit-environment entanglement generated during qubit pure dephasing
- Benchmarking the Quantum Approximate Optimization Algorithm
- Benchmarking Advantage and D-Wave 2000Q quantum annealers with exact cover problems
- Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
- Reverse annealing for the fully connected -spin model
- Traffic Signal Optimization on a Square Lattice with Quantum Annealing
- Modernizing Quantum Annealing using Local Searches
- Biology and medicine in the landscape of quantum advantages
- Tunneling and speedup in quantum optimization for permutation-symmetric problems
- Dynamics of reverse annealing for the fully-connected -spin model
- Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians
- MAX 2-SAT with up to 108 qubits
- Reverse quantum annealing of the -spin model with relaxation
- Improving quantum annealing of the ferromagnetic -spin model through pausing
- Polymer Physics by Quantum Computing
- Uncertain fate of fair sampling in quantum annealing
- Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
- Why and when is pausing beneficial in quantum annealing?
- Optimally Stopped Optimization
- Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
- Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
- Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering