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.
No takes yet. Share an insight, caveat, or question.
Marko Žnidarič (2005) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: