A Quantum Heuristic Algorithm for the Traveling Salesman Problem
- Title
- A Quantum Heuristic Algorithm for the Traveling Salesman Problem
- Author
- 이진형
- Keywords
- Quantum Physics; Quantum computation; Quantum algorithm; Traveling salesman problem
- Issue Date
- 2012-10
- Publisher
- 한국물리학회
- Citation
- Journal of the Korean Physical Society, Vol.61, No.12 [2012], p1944-1949
- Abstract
- We propose a quantum heuristic algorithm to solve a traveling salesman problem by generalizing Grover search. Sufficient conditions are derived to greatly enhance the probability of finding thetours with the cheapest costs reaching almost to unity. These conditions are characterized by statistical properties of tour costs and shown to be automatically satisfied in the large number limitof cities. In particular for a continuous distribution of the tours along the cost we show that the quantum heuristic algorithm exhibits the quadratic speedup over its classical heuristic algorithm.
- URI
- https://arxiv.org/abs/1004.4124?http://hdl.handle.net/20.500.11754/39984
- ISSN
- 0374-4884
- DOI
- 10.3938/jkps.61.1944
- Appears in Collections:
- COLLEGE OF NATURAL SCIENCES[S](자연과학대학) > PHYSICS(물리학과) > Articles
- Files in This Item:
There are no files associated with this item.
- Export
- RIS (EndNote)
- XLS (Excel)
- XML