The complexity of the Quantum Adiabatic Algorithm

Edward Farhi

Itay Hen

The Quantum Adiabatic Algorithm (QAA) has been proposed as a mechanism for efficiently solving optimization problems on a quantum computer. Since adiabatic computation is analog in nature and does not require the design and use of quantum gates, it can be thought of as a simpler and perhaps more profound method for performing quantum computations that might also be easier to implement experimentally. While these features have generated substantial research in QAA, to date there is still a lack of solid evidence that the algorithm can outperform classical optimization algorithms.

Jie Sun, Songfeng Lu, Fang Liu

Hongye Yu, Yuliang Huang, Biao Wu

We present a rigorous proof that quantum circuit algorithm can be transformed into quantum adiabatic algorithm with the exact same time complexity. This means that from a quantum circuit algorithm of L gates we can construct a quantum adiabatic algorithm with time complexity of O(L). Additionally, our construction shows that one may exponentially speed up some quantum adiabatic algorithms by properly choosing an evolution path .

Catherine C. McGeoch

Itay Hen, A. P. Young

We determine the complexity of several constraint satisfaction problems using the quantum adiabatic algorithm in its simplest implementation. We do so by studying the size dependence of the gap to the first excited state of "typical" instances. We find that, at large sizes N, the complexity increases exponentially for all models that we study. We also compare our results against the complexity of the analogous classical algorithm WalkSAT and show that the harder the problem is for the classical algorithm, the harder it is also for the quantum adiabatic algorithm.