Scaling of the running time of the quantum adiabatic algorithm for propositional satisfiability
Marko Žnidarič · Physical Review A · 2005
We numerically study the quantum adiabatic algorithm for propositional satisfiability. A new class of previously unknown hard instances is identified among random problems. We numerically find that the running time for such instances grows exponentially with their size. The worst case complexity of the quantum adiabatic algorithm therefore seems to be exponential.