Adiabatic Quantum Computing for Random Satisfiability Problems
Abstract
The discrete formulation of adiabatic quantum computing is compared with other search methods, classical and quantum, for random satisfiability (SAT) problems. With the number of steps growing only as the cube of the number of variables, the adiabatic method gives solution probabilities close to one for problem sizes feasible to evaluate. However, for these sizes the minimum energy gaps are fairly large, so may not reflect asymptotic behavior where costs are dominated by tiny gaps. Moreover, the resulting search costs are much higher than other methods, but can be reduced by using fewer steps. Variants of the quantum algorithm that do not match the adiabatic limit give lower costs, on average, and slower growth than the conventional GSAT heuristic method.Keywords
All Related Versions
This publication has 0 references indexed in Scilit: