Abstract
We study a special kind of interpolating paths in quantum adiabatic search algorithms. With this special kind of adiabatic paths, notably we find that even when the parameter n within it tends to infinity, the adiabatic evolution would be a failure if the initial state is orthogonal to the final target state. But superficially, it seems that the minimum gap of the quantum system happening at the end of the computation would not affect the validity of the algorithm, since each ground state of the problem Hamiltonian encodes a solution to the problem. When the beginning state has a nonzero overlap with the final state, again if the parameter n within the special interpolating paths tends to infinity, it may give ones the counterintuitive impression that the adiabatic evolution could be considerably faster than the usual simple models of adiabatic evolution, even possible with constant time complexity. However, the fact is that as in the usual case, the quadratic speedup is the quantum algorithmic performance limit for which this kind of interpolating functions can provide for the adiabatic evolution. We also expose other easily made mistakes which may lead to draw the wrong conclusions about the validity of the adiabatic search algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Cleve, R., Ekert, A., Macchiavello, C., Mosca, M.: Quantum algorithms revisited. Proc. R. Soc. Lond. A Math. Phys. Eng. Sci. 454(1969), 339–354 (1998)
Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A Math. Phys. Eng. Sci. 439(1907), 553–558 (1992)
Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science, Proceedings, pp. 124–134. IEEE (1994)
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., et al.: A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem. Science 292(5516), 472–475 (2001)
Hen, I., Young, A.P.: Exponential complexity of the quantum adiabatic algorithm for certain satisfiability problems. Phys. Rev. E 84(6), 061152 (2011)
Dickson, N.G., Amin, M.H.S.: Does adiabatic quantum optimization fail for NP-complete problems? Phys. Rev. Lett. 106(5), 050502 (2011)
Altshuler, B., Krovi, H., Roland, J.: Anderson localization makes adiabatic quantum optimization fail. Proc. Natl. Acad. Sci. 107(28), 12446–12450 (2010)
Garnerone, S., Zanardi, P., Lidar, D.A.: Adiabatic quantum algorithm for search engine ranking. Phys. Rev. Lett. 108(23), 230506 (2012)
Gaitan, F., Clark, L.: Ramsey numbers and adiabatic quantum computing. Phys. Rev. Lett. 108(1), 010501 (2012)
Somma, R.D., Nagaj, D., Kieferová, M.: Quantum speedup by quantum annealing. Phys. Rev. Lett. 109(5), 050501 (2012)
Aharonov, D., van Dam, W., Kempe, J., et al.: Adiabatic quantum computation is equivalent to standard quantum computation. SIAM Rev. 50(4), 755–787 (2008)
Mizel, A., Lidar, D.A., Mitchell, M.: Simple proof of equivalence between adiabatic quantum computation and the circuit model. Phys. Rev. Lett. 99(7), 070502 (2007)
Messiah, A.: Quantum Mechanics. Dover, New York (1999)
Tong, D.M., Singh, K., Kwek, L.C., Oh, C.H.: Sufficiency criterion for the validity of the adiabatic approximation. Phys. Rev. Lett. 98(15), 150402 (2007)
Farhi, E., Goldstone, J., Siper, M.: Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106
Hen, I., Young, A.P.: Solving the graph-isomorphism problem with a quantum annealer. Phys. Rev. A 86(4), 042310 (2012)
Gaitan, F., Clark, L.: Graph isomorphism and adiabatic quantum computing. Phys. Rev. A 89(2), 022342 (2014)
Roland, J., Cerf, N.J.: Quantum search by local adiabatic evolution. Phys. Rev. A 65(4), 042308 (2002)
Zhang, D.J., Yu, X.D., Tong, D.M.: Theorem on the existence of a nonzero energy gap in adiabatic quantum computation. Phys. Rev. A 90(4), 042321 (2014)
Sun, J., Lu, S.F., Braunstein, S.L.: On models of nonlinear evolution paths in adiabatic quantum algorithms. Commun. Theor. Phys. 59(1), 22–26 (2013)
Acknowledgment
This work are supported by the Natural Science Foundation of China under Grant No. 61402188, the Natural Science Foundation of Hubei Province of China under Grant No. 2016CFB541, the Applied Basic Research Program of Wuhan Science and Technology Bureau of China under Grant No. 2016010101010003 and the Science and Technology Program of Shenzhen of China under Grant No. JCYJ20170307160458368.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Sun, J., Lu, S., Gao, C. (2019). Quantum Adiabatic Evolution with a Special Kind of Interpolating Paths. In: Arai, K., Kapoor, S., Bhatia, R. (eds) Advances in Information and Communication Networks. FICC 2018. Advances in Intelligent Systems and Computing, vol 887. Springer, Cham. https://doi.org/10.1007/978-3-030-03405-4_51
Download citation
DOI: https://doi.org/10.1007/978-3-030-03405-4_51
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-03404-7
Online ISBN: 978-3-030-03405-4
eBook Packages: EngineeringEngineering (R0)