Partial adiabatic quantum search algorithm and its extensions
Tóm tắt
In this paper, we again discuss quantum search by partial adiabatic evolution, which was first proposed by Zhang et al. In contrast to previous conclusions, we show that partial adiabatic search does not improve the time complexity of a local adiabatic algorithm. Firstly, we show a variant of this algorithm and find that it is equivalent to the original partial adiabatic algorithm, in the sense of the same time complexity. But we give two alternate viewpoints on this “new” adiabatic algorithm—“global” adiabatic evolution and local adiabatic evolution approaches, respectively. Then, we discuss how global and local adiabatic quantum search can be recast in the framework of partial adiabatic search algorithm. It is found here that the former two algorithms could be considered as special cases of the later one when appropriately tuning the evolution interval of it. Also this implies the flexibility of quantum search based on partial adiabatic evolution.
Từ khóa
Tài liệu tham khảo
Messiah, A.: Quantum Mechanics. Chap. XVII. Dover, New York (1999)
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., Preda, D.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292, 472 (2001)
Reichardt, B.: The quantum adiabatic optimization algorithm and local minima. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, Chicago, pp. 502–510 (2004).
Altshuler, B., Krovi, H., Roland, J.: Adiabatic quantum optimization fails for random instances of NP-complete problems. arXiv:quant-ph/0908.2782 (2009)
Dam, W.v., Mosca, M., Vazirani, U.: How powerful is adiabatic quantum computation? In: The 42rd Annual IEEE Symposium on Foundations of Computer Science, 2001, Las Vegas. pp. 279–287 (2001)
Dickson, N.G., Amin, M.H.S.: Does adiabatic quantum optimization fail for NP-complete problems? Phys. Rev. Lett. 106(5), 050502 (2011)
Choi, V.: Different adiabatic quantum optimization algorithms for the NP-complete exact cover problem. Proc. Natl. Acad. Sci. USA 108(7), E19–E20 (2011)
Grover, L.K.: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79(2), 325 (1997)
Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum Computation by Adiabatic, Evolution. arXiv:quant-ph/0001106 (2000)
Roland, J., Cerf, N.J.: Quantum search by local adiabatic evolution. Phys. Rev. A 65(4), 042308 (2002)
Åberg, J., Kult, D., Sjöqvist, E.: Robustness of the adiabatic quantum search. Phys. Rev. A 71(6), 060312(R) (2005)
Tulsi, A.: Adiabatic quantum computation with a one-dimensional projector Hamiltonian. Phys. Rev. A 80(5), 052328 (2009)
Zhang, Y.Y., Lu, S.F.: Quantum search by partial adiabatic evolution. Phys. Rev. A 82(3), 034304 (2010)
Zhang, Y.Y., Hu, H.P., Lu, S.F.: A quantum search algorithm based on partial adiabatic evolution. Chin. Phys. B 20(4), 040309 (2011)
Zalka, C.: Grover’s quantum searching algorithm is optimal. Phys. Rev. A 60(4), 2746 (1999)
Tong, D.M., Singh, K., Kwek, L.C.: Sufficiency criterion for the validity of the adiabatic approximation. Phys. Rev. Lett. 98(15), 150402 (2007)
Amin, M.H.S., Averin, D.V.: Decoherence in adiabatic quantum computation. Phys. Rev. A 79(2), 022107 (2009)
Childs, A.M., Farhi, E., Preskill, J.: Robustness of adiabatic quantum computation. Phys. Rev. A 65(1), 012322 (2001)