Quantum walk algorithm for element distinctness

被引：133

作者：

Ambainis, A ^{[1
]}

机构：

[1] Inst Adv Study, Sch Math, Princeton, NJ 08540 USA

来源：

45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS | 2004年

关键词：

D O I：

10.1109/FOCS.2004.54

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We use quantum walks to construct a new quantum algorithm for element distinctness and its generalization. For element distinctness (the problem of finding two equal items among N given items), we get an O(N-2.3) query quantum algorithm. This improves the previous O(N-3/4) quantum algorithm of Buhrman et al. [10] and matches the lower bound by Shi [28]. We also give an O(N (k/(k+1))) query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.

引用

页码：22 / 31

页数：10

共 30 条

[1]

AARONSON S, P STOC 02, P635

[2]

AARONSON S, P FOCS 03, P200

[3]

AHARONOV D, 1998, ANN REV COMPUTATIONA, V6

[4]

AMBAINIS A, QUANTPH0402107

[5]

AMBAINIS A, IN PRESS P FOTFS 3

[6]

AMBAINIS A, QUANTPH0305179

[7] QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS [J].

Ambainis, Andris .

INTERNATIONAL JOURNAL OF QUANTUM INFORMATION, 2003, 1 (04) :507-518

[8] Time-space trade-off lower bounds for randomized computation of decision problems [J].

Beame, P ;

Saks, M ;

Sun, XD ;

Vee, E .

JOURNAL OF THE ACM, 2003, 50 (02) :154-195

[9]

BENIOFF P, 2002, AMS CONTEMPORARY MAT

[10]

Brassard G., 1998, LATIN '98: Theoretical Informatics. Third Latin American Symposium. Proceedings, P163, DOI 10.1007/BFb0054319

← 1 2 3 →