Exact Equivalence between Quantum Adiabatic Algorithm and Quantum Circuit Algorithm
Hongye Yu1, Yuliang Huang2,1, Biao Wu1,3**
1International Center for Quantum Materials, Peking University, Beijing 100871 2Department of Radiation Oncology, Peking University Cancer Hospital and Institute, Beijing 100142 3Wilczek Quantum Center, School of Physics and Astronomy, Shanghai Jiao Tong University, Shanghai 200240
Abstract：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.
2018, Vol. 35 
