276 0

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


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE