Why haven't more quantum algorithms been found?

被引：43

作者：

Shor, PW ^{[1
]}

机构：

[1] AT&T Labs Res, Florham Pk, NJ 07932 USA

来源：

JOURNAL OF THE ACM | 2003年 / 50卷 / 01期

关键词：

Polynomial factor speed-ups - Quantum algorithms - Quantum information theory - Superpolynomials;

D O I：

10.1145/602382.602408

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

I examine the question of why so few classes of quantum algorithms have been discovered. I give two possible explanations for this, and some thoughts about what lines of research might lead to the discovery of more quantum algorithms.

引用

页码：87 / 90

页数：4

共 11 条

[1] Strengths and weaknesses of quantum computing [J].

Bennett, CH ;

Bernstein, E ;

Brassard, G ;

Vazirani, U .

SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1510-1523

[2]

Cook S.A., 1971, P 3 ANN ACM S THEOR, P151, DOI DOI 10.1145/800157.805047

[3] SIMULATING PHYSICS WITH COMPUTERS [J].

FEYNMAN, RP .

INTERNATIONAL JOURNAL OF THEORETICAL PHYSICS, 1982, 21 (6-7) :467-488

[4] Quantum mechanics helps in searching for a needle in a haystack [J].

Grover, LK .

PHYSICAL REVIEW LETTERS, 1997, 79 (02) :325-328

[5]

GROVER LK, 1922, MATH QUANTUM COMPUTA, P119

[6]

Hallgren S., 2002, P 34 ANN ACM S THEOR, P653

[7]

KARP R. M., 1972, COMPLEXITY COMPUTER, P85, DOI DOI 10.1007/978-1-4684-2001-2_9

[8]

Kitaev A. Y., 1996, TR96003 ECCC

[9]

Levin L. A., 1973, Problems of Information Transmission, V9, P265

[10]

Shor PW, 1997, SIAM J COMPUT, V26, P1484, DOI [10.1137/S0097539795293172, 10.1137/S0036144598347011]

← 1 2 →