Quantum annealing for hard 2-SAT problems : Distribution and scaling of minimum energy gap and success probability
arXiv:2202.00118 · doi:10.1103/PhysRevA.105.062406
Abstract
In recent years, quantum annealing has gained the status of being a promising candidate for solving various optimization problems. Using a set of hard 2-satisfiabilty (2-SAT) problems, consisting of upto 18-variables problems, we analyze the scaling complexity of the quantum annealing algorithm and study the distributions of the minimum energy gap and the success probability. We extend the analysis of the standard quantum annealing Hamiltonian by introducing an additional term, the trigger Hamiltonian, which can be of two types : ferromagnetic and antiferromagnetic. We use these trigger Hamiltonians to study their influence on the success probability for solving the selected 2-SAT problems. We found that although the scaling of the run-time is exponential for the standard and modified quantum annealing Hamiltonians, the scaling constant in case of adding the trigger Hamiltonians can be significantly smaller. Furthermore, certain choices for the trigger Hamiltonian and annealing times can result in a better scaling than that for simulated annealing. Lastly, we also use the quantum annealers of D-Wave Systems Inc. to study their performance in solving the 2-SAT problems and compare it with the simulation results.
arXiv comment17 pages, 14 figures
References in corpus (37)
- Quantum Annealing in the Transverse Ising Model
- 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
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Defining and detecting quantum speedup
- Perspectives of quantum annealing: Methods and implementations
- Bounds for the adiabatic approximation with applications to quantum computation
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Quantum annealing of the Traveling Salesman Problem
- Demonstration of a scaling advantage for a quantum annealer over simulated annealing
- Error corrected quantum annealing with hundreds of qubits
- Entanglement in a quantum annealing processor
- Consistency of the Adiabatic Theorem
- Quantum Speedup by Quantum Annealing
- Probing for quantum speedup in spin glass problems with planted solutions
- Searching for quantum speedup in quasistatic quantum annealers
- A scheme for direct detection of qubit-environment entanglement generated during qubit pure dephasing
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Quantum annealing with antiferromagnetic fluctuations
- Benchmarking the Quantum Approximate Optimization Algorithm
- Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
- Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
- Scaling and diabatic effects in quantum annealing with a D-Wave device
- Tunneling and speedup in quantum optimization for permutation-symmetric problems
- Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
- Benchmarking Quantum Annealing Controls with Portfolio Optimization
- Scaling overhead of embedding optimization problems in quantum annealing
- GPU-accelerated simulations of quantum annealing and the quantum approximate optimization algorithm
- Schedule path optimization for quantum annealing and adiabatic quantum computing
- Steering random spin systems to speed up the quantum adiabatic algorithm
- Quantum Annealing with Trigger Hamiltonians: Application to 2-SAT and Nonstoquastic Problems
- Real-time simulation of flux qubits used for quantum annealing
- Improving nonstoquastic quantum annealing with spin-reversal transformations
Cited by in corpus (9)
- Guided quantum walk
- Unraveling Reverse Annealing: A Study of D-Wave Quantum Annealers
- Performance of quantum annealing for 2-SAT problems with multiple satisfying assignments
- Posiform Planting: Generating QUBO Instances for Benchmarking
- Increasing the Hardness of Posiform Planting Using Random QUBOs for Programmable Quantum Annealer Benchmarking
- Quantum-inspired dynamical models on quantum and classical annealers
- Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
- Quantum speed-up for solving the one-dimensional Hubbard model using quantum annealing
- Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems