Optimization by Quantum Annealing: Lessons from hard 3-SAT cases

Abstract

The Path Integral Monte Carlo simulated Quantum Annealing algorithm is applied to the optimization of a large hard instance of the Random 3-SAT Problem (N=10000). The dynamical behavior of the quantum and the classical annealing are compared, showing important qualitative differences in the way of exploring the complex energy landscape of the combinatorial optimization problem. At variance with the results obtained for the Ising spin glass and for the Traveling Salesman Problem, in the present case the linear-schedule Quantum Annealing performance is definitely worse than Classical Annealing. Nevertheless, a quantum cooling protocol based on field-cycling and able to outperform standard classical simulated annealing over short time scales is introduced.

10 pages, 6 figures, submitted to PRE

References in corpus (12)

• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Theory of Quantum Annealing of an Ising Spin Glass
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Quantum annealing of the Traveling Salesman Problem
• Boosting search by rare events
• Separation of time and length scales in spin-glasses: temperature as a microscope
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Study of Optimization Problems by Quantum Annealing
• The stochastic traveling salesman problem: Finite size scaling and the cavity prediction
• Minimizing energy below the glass thresholds

Cited by in corpus (55)

• Quantum annealing with more than one hundred qubits
• Quantum Annealing and Analog Quantum Computation
• Perspectives of quantum annealing: Methods and implementations
• Efficient partition of integer optimization problems with one-hot encoding
• Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
• Quantum Annealing: An Overview
• Adiabatic quantum dynamics of a random Ising chain across its quantum critical point
• Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• MAX 2-SAT with up to 108 qubits
• Optimization by Quantum Annealing: Lessons from Simple Cases
• Convergence theorems for quantum annealing
• Building an iterative heuristic solver for a quantum annealer
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Quantum annealing of the random-field Ising model by transverse ferromagnetic interactions
• Simulated quantum annealing as a simulator of non-equilibrium quantum dynamics
• A dissipative environment may improve the quantum annealing performances of the ferromagnetic p-spin model
• Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning
• Quantum Monte Carlo Simulations of Tunneling in Quantum Adiabatic Optimization
• Boosting quantum annealer performance via sample persistence
• Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
• Quantum annealing speedup over simulated annealing on random Ising chains
• A Numerical Optimization Algorithm Inspired by the Strawberry Plant
• Simulated quantum annealing of double-well and multi-well potentials
• Monte Carlo studies of quantum and classical annealing on a double-well
• Assessment of Quantum Annealing for the Construction of Satisfiability Filters
• Quantum annealing of an Ising spin-glass by Green's function Monte Carlo
• Standard quantum annealing outperforms adiabatic reverse annealing with decoherence
• Understanding Quantum Tunneling using Diffusion Monte Carlo Simulations
• Design of quantum optical experiments with logic artificial intelligence
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Optimization in random field Ising models by quantum annealing
• Deep learning optimal quantum annealing schedules for random Ising models
• Cyclic Quantum Annealing: Searching for Deep Low-Energy States in 5000-Qubit Spin Glass
• Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem
• Efficient quantum and simulated annealing of Potts models using a half-hot constraint
• Tunneling through high energy barriers in simulated quantum annealing
• Why adiabatic quantum annealing is unlikely to yield speed-up
• Path-Integral Quantum Monte Carlo simulation with Open-Boundary Conditions
• Fully-programmable universal quantum simulator with a one-dimensional quantum processor
• Difference between quantum annealing by imaginary-time and real-time Schrödinger equation of Grover's search
• The performance of the quantum adiabatic algorithm on spike Hamiltonians
• Physical consequences of P$\ne$NP and the DMRG-annealing conjecture
• A method to reduce the rejection rate in Monte Carlo Markov Chains
• Quantum wavefunction annealing of spin glasses
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
• Phase transitions and gaps in quantum random energy models
• Quantum-thermal annealing with cluster-flip algorithm
• Absence of small-world effects at the quantum level and stability of the quantum critical point
• Development of research network on Quantum Annealing Computation and Information using Google Scholar data
• Microscopics of Quantum Annealing in the Disordered Dipolar Ising Ferromagnet LiHo${}_x$Y${}_{1-x}$F${}_4$
• Discrepancies between Asymptotic and Exact Spectral Gap Analyses of Quantum Adiabatic Barrier Tunneling
• Extracting the trustworthiest way to service provider in complex online social networks
• Finding Hadamard matrices by a quantum annealing machine