| GENERAL |
|
|
|
|
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 |
|
| Cite this article: |
|
Hongye Yu, Yuliang Huang, Biao Wu 2018 Chin. Phys. Lett. 35 110303 |
|
|
|
|
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.
|
|
Received: 07 October 2018
Published: 23 October 2018
|
|
| PACS: |
03.67.Ac
|
(Quantum algorithms, protocols, and simulations)
|
| |
03.67.Lx
|
(Quantum computation architectures and implementations)
|
| |
89.70.Eg
|
(Computational complexity)
|
|
|
| Fund: 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. |
|
|
|
| [1] | Nielsen M A and Chuang I L 2000 Quantum Computation and Quantum Information (Cambridge: Cambridge University Press) | | [2] | Farhi E, Goldstone J, Gutmann S and Sipser M 2000 arXiv:quant-ph/0001106v1 | | [3] | Zhang Q, Gong J and Wu B 2014 New J. Phys. 16 123024 | | [4] | Aharonov D, van Dam W, Kempe J, Landau Z, Lloyd S and Regev O 2007 SIAM J. Comput. 37 166 | | [5] | van Dam W, Mosca M and Vazirani U 2001 Proceedings 2001 IEEE International Conference on Cluster Computing (Las Vegas, Vevada, USA 14–17 October 2001) p 279 | | [6] | Kitaev A Y, Shen A H and Vyalyi M N 2002 Classical and Quantum Computatation (Rhode Island: American Mathematical Society) | | [7] | Diener R B, Wu B, Raizen M G and Niu Q 2002 Phys. Rev. Lett. 89 070401 |
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
