Quantum optimization

被引：84

作者：

Hogg, T

Portnov, D

机构：

[1] Xerox Corp, Palo Alto Res Ctr, Palo Alto, CA 94304 USA

[2] Univ Washington, Dept Comp Sci & Engn, Seattle, WA 98105 USA

来源：

INFORMATION SCIENCES | 2000年 / 128卷 / 3-4期

关键词：

D O I：

10.1016/S0020-0255(00)00052-9

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a quantum algorithm for combinatorial optimization using the cost structure of the search states. Its behavior is illustrated for overconstrained satisfiability (SAT) and asymmetric traveling salesman problems (ATSP). Simulations with randomly generated problem instances show each step of the algorithm shifts amplitude preferentially towards lower cost states, thereby concentrating amplitudes into low-cost states, on average. These results are compared with conventional heuristics for these problems. (C) 2000 Elsevier Science Inc. All rights reserved.

引用

页码：181 / 197

页数：17

共 29 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Boyer M, 1996, P 4 WORKSH PHYS COMP, P36

[3]

BRASSARD G, 1998, P 25 INT C AUT LANG, P830

[4]

CERF NJ, APPL ALGEBRA ENG COM