Skip to main content
SpringerLink
Log in

A quantum heuristic algorithm for the traveling salesman problem

  • Published:
Journal of the Korean Physical Society Aims and scope Submit manuscript

Abstract

We propose a quantum heuristic algorithm to solve the traveling salesman problem by generalizing the Grover search. Sufficient conditions are derived to greatly enhance the probability of finding the tours with the cheapest costs reaching almost to unity. These conditions are characterized by the statistical properties of tour costs and are shown to be automatically satisfied in the large-number limit of cities. In particular for a continuous distribution of the tours along the cost, we show that the quantum heuristic algorithm exhibits a quadratic speedup compared to its classical heuristic algorithm.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Springer, 1999).

  2. P. W. Shor, SIAM J. Comput. 26, 1484 (1997).

    Article  MathSciNet  MATH  Google Scholar 

  3. L. K. Grover, Phys. Rev. Lett. 79, 325 (1997).

    Article  ADS  Google Scholar 

  4. A. W. Harrow, A. Hassidim and S. Lloyd, Phys. Rev. Lett. 103, 150502 (2009).

    Article  MathSciNet  ADS  Google Scholar 

  5. A. M. Childs, Nat. Phys. 5, 861 (2009).

    Article  MathSciNet  Google Scholar 

  6. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman, San Francisco, 1979).

    MATH  Google Scholar 

  7. P. W. Shor, J. ACM 50, 87 (2003).

    Article  MathSciNet  Google Scholar 

  8. T. Hogg and D. Portov, Inform. Sciences 128, 181 (2000).

    Article  MATH  Google Scholar 

  9. T. Hogg, Phys. Rev. Lett. 80, 2473 (1998).

    Article  ADS  Google Scholar 

  10. C. A. Trugenburger, New J. Phys. 4, 26 (2002).

    Article  ADS  Google Scholar 

  11. L. K. Grover, Chaos, Soliton. Fract. 10, 1695 (1999).

    Article  MathSciNet  ADS  MATH  Google Scholar 

  12. S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Science 220, 671 (1983).

    Article  MathSciNet  ADS  MATH  Google Scholar 

  13. M. Znidaric and M. Horvat, Phys. Rev. A 73, 022329 (2006).

    Article  ADS  Google Scholar 

  14. E. Farhi, J. Goldstone, S. Gutmann and D. Nagaj, Int. J. Quantum Inf. 6, 503 (2008).

    Article  MATH  Google Scholar 

  15. D. L. Applegate, R. E. Bixby, V. Chvátal and W. J. Cook,, The Traveling Salesman Problem: A Computational Study (Princeton University Press, 2006).

  16. R. M. Karp, Oper. Res. Lett. 1, 49 (1982).

    Article  MathSciNet  MATH  Google Scholar 

  17. V. Cerny, Phys. Rev. A 48, 116 (1993).

    Article  ADS  Google Scholar 

  18. E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren and D. Preda, Science 292, 472 (2001).

    Article  MathSciNet  ADS  MATH  Google Scholar 

  19. R. Martonak, G. E. Santoro and E. Tosatti, Phys. Rev. E 70, 057701 (2004).

    Article  ADS  Google Scholar 

  20. C. Durr and P. Hoyer, e-print quant-ph/9607014 (1996).

  21. J. Beardwood, J. H. Halton and J. M. Hammersley, Proc. Cambridge Philos. Soc. 55, 229 (1959).

    Article  MathSciNet  Google Scholar 

  22. N. Burgess and M. A. Moore, J. Phys. A: Math. Gen. 22, 4599 (1989).

    Article  MathSciNet  ADS  MATH  Google Scholar 

  23. D. Goswami, H. Karnick, P. Jain and H. K. Maji, arXiv:quant-ph/0411013 (2004).

  24. P. Zanardi and M. Rasetti, Phys. Rev. Lett. 79, 3306 (1997).

    Article  ADS  Google Scholar 

  25. B. P. Lanyon, T. J. Weinhold, N. K. Langford, J. L. O’Brien, K. J. Resch, A. Gilchrist and A. G. White, Phys. Rev. Lett. 100, 060504 (2008).

    Article  ADS  Google Scholar 

  26. N. Schuch and J. Siewert, Phys. Rev. Lett. 91, 027902 (2003).

    Article  ADS  Google Scholar 

  27. L. K. Grover, Phys. Rev. Lett. 80, 4329 (1998).

    Article  ADS  Google Scholar 

  28. E. Biham, O. Biham, D. Biron, M. Grassl, D. A. Lidar and D. Shapira, Phys. Rev. A 63, 012310 (2000).

    Article  ADS  Google Scholar 

  29. G. L. Long, Y. S. Li, W. L. Zhang and L. Niu, Phys. Lett. A 262, 27 (1999).

    Article  MathSciNet  ADS  MATH  Google Scholar 

  30. M. Dobšíček, G. Johansson, V. Shumeiko and G. Wendin, Phys. Rev. A 76, 030306 (2007).

    Article  ADS  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Macroscopic Quantum Control & Department of Physics and Astronomy, Seoul National University, Seoul, 151-747, Korea

    Jeongho Bang & Jinhyoung Lee

  2. Department of Physics, Hanyang University, Seoul, 133-791, Korea

    Jeongho Bang, Junghee Ryu, Changhyoup Lee, Seokwon Yoo, James Lim & Jinhyoung Lee

  3. Institute of Theoretical Physics and Astrophysics, University of Gdańsk, 80-952, Gdańsk, Poland

    Junghee Ryu

  4. Centre for Quantum Technologies, National University of Singapore, 3 Science Drive 2, Singapore, Singapore, 117543

    Changhyoup Lee

  5. School of Computational Sciences, Korea Institute for Advanced Study, Seoul, 130-722, Korea

    Jinhyoung Lee

Authors
  1. Jeongho Bang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Junghee Ryu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Changhyoup Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Seokwon Yoo
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. James Lim
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Jinhyoung Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jeongho Bang.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bang, J., Ryu, J., Lee, C. et al. A quantum heuristic algorithm for the traveling salesman problem. Journal of the Korean Physical Society 61, 1944–1949 (2012). https://doi.org/10.3938/jkps.61.1944

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.3938/jkps.61.1944

Keywords

Search

Navigation