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.
Supported by the The National Key Research and Development Program of China under Grant Nos 2017YFA0303302 and 2018YFA030562, and the National Natural Science Foundation of China under Grant Nos 11334001 and 11429402.
- Hongye Yu, Yuliang Huang, Biao Wu. Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm[J]. CPL, 2018, 35(11): 110303.