Quest for fast partial search algorithm

被引：16

作者：

Korepin, Vladimir E. ^{[1
]}

Liao, Jinfeng

机构：

[1] SUNY Stony Brook, CN Yang Inst Theoret Phys, Stony Brook, NY 11794 USA

[2] SUNY Stony Brook, Dept Phys & Astron, Stony Brook, NY 11794 USA

来源：

QUANTUM INFORMATION PROCESSING | 2006年 / 5卷 / 03期

基金：

美国国家科学基金会;

关键词：

quantum algorithms; searching and sorting; Groves algorithm; partial search;

D O I：

10.1007/s11128-006-0024-3

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

The Grover quantum algorithm can fired a target item in a database faster than any classical algorithm. In partial search, one trades accuracy for speed, and a part of the database (a block) containing the target item can be found even faster. We consider different partial search algorithms and argue that the algorithm originally suggested by Grover and Radhakrishnan and modified by Korepin is the optimal one. The efficiency of an algorithm is measured by the number of queries to the oracle.

引用

页码：209 / 226

页数：18

共 10 条

[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]

Boyer M, 1998, FORTSCHR PHYS, V46, P493, DOI 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO

[3]

2-P

[4]

Brassard G., 2000, QUANTUM COMPUTATION, V305, P53, DOI [DOI 10.1090/CONM/305/05215, 10.1090/conm/305/05215]

[5]

CHOI BS, 2006, QUANTPH0603136

[6]

Grover L. K., 2005, P 17 ANN ACM S PAR A, P186

[7]

GROVER LK, 1996, STOC, V1, P212

[8]

HEILIGMAN M, 2000, QUANTPH0006136

[9] Optimization of partial search [J].

Korepin, VE .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 2005, 38 (44) :L731-L738

[10] Simple algorithm for partial quantum search [J].

Korepin, Vladimir E. ;

Grover, Lov K. .

QUANTUM INFORMATION PROCESSING, 2006, 5 (01) :5-10

← 1 →