Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm
Hongye Yu, Yuliang Huang, Biao Wu · Chinese Physics Letters · 2018
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 .