Quantum walk algorithm for element distinctness

被引：436

作者：

Ambainis, Andris ^{[1
]}

机构：

[1] Univ Waterloo, Fac Math, Dept Combinator & Optimizat, Waterloo, ON N2L 2T2, Canada

来源：

SIAM JOURNAL ON COMPUTING | 2007年 / 37卷 / 01期

关键词：

quantum computing; quantum query algorithms; element distinctness;

D O I：

10.1137/S0097539705447311

中图分类号：

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. [SIAM J. Comput., 34 ( 2005), pp. 1324-1330] and matches the lower bound of Aaronson and Shi [J. ACM, 51 ( 2004), pp. 595-605]. We also give an O(Nk/(k+1)) query quantum algorithm for the generalization of element distinctness in which we have to find k equal items among N items.

引用

页码：210 / 239

页数：30

共 40 条

[1] Quantum lower bounds for the collision and the element distinctness problems [J].

Aaronson, S ;

Shi, YY .

JOURNAL OF THE ACM, 2004, 51 (04) :595-605

[2] Quantum search of spatial regions (extended abstract) [J].

Aaronson, S ;

Ambainis, A .

44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2003, :200-209

[3]

Aaronson S., 2005, Theory Comput, V1, P47, DOI [10.4086/toc.2005.v001a004, DOI 10.4086/TOC.2005.V001A004]

[4]

Aharonov D., 1999, ANN REV COMPUTATIONA, V1999, P259, DOI DOI 10.1142/9789812815569_0007

[5] A FAST AND SIMPLE RANDOMIZED PARALLEL ALGORITHM FOR THE MAXIMAL INDEPENDENT SET PROBLEM [J].

ALON, N ;

BABAI, L ;

ITAI, A .

JOURNAL OF ALGORITHMS, 1986, 7 (04) :567-583

[6]

Ambainis A, 2004, TR LOG STUD LOG LIB, V23, P15

[7]

Ambainis A., 2005, THEORY COMPUTING, V1, P37, DOI [10.4086/toc.2005.v001a003, DOI 10.4086/TOC.2005.V001A003]

[8]

Ambainis A, 2005, PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P1099

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

Ambainis, Andris .

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

[10] ELEMENTARY GATES FOR QUANTUM COMPUTATION [J].

BARENCO, A ;

BENNETT, CH ;

CLEVE, R ;

DIVINCENZO, DP ;

MARGOLUS, N ;

SHOR, P ;

SLEATOR, T ;

SMOLIN, JA ;

WEINFURTER, H .

PHYSICAL REVIEW A, 1995, 52 (05) :3457-3467

← 1 2 3 4 →