A Quantum Heuristic Algorithm for the Traveling Salesman Problem

被引：9

作者：

Bang, Jeongho ^{[1
,2
,3
]}

Ryu, Junghee ^{[3
,4
]}

Lee, Changhyoup ^{[3
,5
]}

Yoo, Seokwon ^{[3
]}

Lim, James ^{[3
]}

Lee, Jinhyoung ^{[1
,2
,3
,6
]}

机构：

[1] Seoul Natl Univ, Ctr Macroscop Quantum Control, Seoul 151747, South Korea

[2] Seoul Natl Univ, Dept Phys & Astron, Seoul 151747, South Korea

[3] Hanyang Univ, Dept Phys, Seoul 133791, South Korea

[4] Univ Gdansk, Inst Theoret Phys & Astrophys, PL-80952 Gdansk, Poland

[5] Natl Univ Singapore, Ctr Quantum Technol, Singapore 117543, Singapore

[6] Korea Inst Adv Study, Sch Computat Sci, Seoul 130722, South Korea

来源：

JOURNAL OF THE KOREAN PHYSICAL SOCIETY | 2012年 / 61卷 / 12期

基金：

新加坡国家研究基金会;

关键词：

Quantum computation; Quantum algorithm; Traveling salesman problem; NP-COMPLETE PROBLEM; ADIABATIC ALGORITHM; OPTIMIZATION; COMPUTERS; SEARCHES;

D O I：

10.3938/jkps.61.1944

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

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.

引用

页码：1944 / 1949

页数：6

共 30 条

[1] [Anonymous], 1996, QUANTPH9607014
[2] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[3] Applegate David L, 2006, TRAVELING SALESMAN P
[4] Beardwood J., 1959, P CAMBRIDGE PHILOS S, V55, P229
[5] Analysis of generalized Grover quantum search algorithms using recursion equations
Biham, E
Biham, O
Biron, D
Grassl, M
Lidar, DA
Shapira, D
[J]. PHYSICAL REVIEW A, 2001, 63 (01) : 012310 - 012311
[6] COST DISTRIBUTIONS IN LARGE COMBINATORIAL OPTIMIZATION PROBLEMS
BURGESS, N
MOORE, MA
[J]. JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1989, 22 (21): : 4599 - 4609
[7] QUANTUM COMPUTERS AND INTRACTABLE (NP-COMPLETE) COMPUTING PROBLEMS
CERNY, V
[J]. PHYSICAL REVIEW A, 1993, 48 (01): : 116 - 119
[8] QUANTUM ALGORITHMS Equation solving by simulation
Childs, Andrew M.
[J]. NATURE PHYSICS, 2009, 5 (12) : 861 - 861
[9] Arbitrary accuracy iterative quantum phase estimation algorithm using a single ancillary qubit:: A two-qubit benchmark
Dobsicek, Miroslav
Johansson, Goran
Shumeiko, Vitaly
Wendin, Goran
[J]. PHYSICAL REVIEW A, 2007, 76 (03):
[10] A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
Farhi, E
Goldstone, J
Gutmann, S
Lapan, J
Lundgren, A
Preda, D
[J]. SCIENCE, 2001, 292 (5516) : 472 - 476

← 1 2 3 →