Sure success partial search

被引：41

作者：

Choi, Byung-Soo ^{[1
]}

Walker, Thomas A. ^{[1
]}

Braunstein, Samuel L. ^{[1
]}

机构：

[1] Univ York, Dept Comp Sci, York YO10 5DD, N Yorkshire, England

来源：

QUANTUM INFORMATION PROCESSING | 2007年 / 6卷 / 01期

关键词：

quantum database search; Grover's algorithm; partial search; sure success;

D O I：

10.1007/s11128-006-0037-y

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

Partial search has been proposed recently for finding the target block containing a target element with fewer queries than the full Grover search algorithm which can locate the target precisely. Since such partial searches will likely be used as subroutines for larger algorithms their success rate is important. We propose a partial search algorithm which achieves success with unit probability.

引用

页码：1 / 8

页数：8

共 12 条

[1]

Brassard G., 2002, Contemporary Mathematics, V305, P53, DOI 10.1090/conm/305

[2]

BRAUNSTEIN SL, QUANTPH0410043

[3] RAPID SOLUTION OF PROBLEMS BY QUANTUM COMPUTATION [J].

DEUTSCH, D ;

JOZSA, R .

PROCEEDINGS OF THE ROYAL SOCIETY OF LONDON SERIES A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 1992, 439 (1907) :553-558

[4] QUANTUM-THEORY, THE CHURCH-TURING PRINCIPLE AND THE UNIVERSAL QUANTUM COMPUTER [J].

DEUTSCH, D .

PROCEEDINGS OF THE ROYAL SOCIETY OF LONDON SERIES A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES, 1985, 400 (1818) :97-117

[5]

Grover L. K., 2005, Proc. of the seventeenth annual ACM Symp. on Parallelism in Algorithms and Architectures, P186

[6]

Grover L.K., 1996, P 28 ANN ACM S THEOR, P212, DOI DOI 10.1145/237814.237866

[7] Arbitrary phases in quantum amplitude amplification [J].

Hoyer, P .

PHYSICAL REVIEW A, 2000, 62 (05) :052304-052301

[8] Optimization of partial search [J].

Korepin, VE .

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

[9] Quest for fast partial search algorithm [J].

Korepin, Vladimir E. ;

Liao, Jinfeng .

QUANTUM INFORMATION PROCESSING, 2006, 5 (03) :209-226

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

Korepin, Vladimir E. ;

Grover, Lov K. .

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

← 1 2 →