|
| related topics |
| {cos, sin, state} |
| {state, algorithm, problem} |
| {algorithm, log, probability} |
|
Quest for Fast Partial Search Algorithm
Vladimir Korepin, Jinfeng Liao
abstract: Quantum algorithm can find target item in a database faster than any
classical. One can trade accuracy for speed and find a part of the database (a
block) containing the target item even faster: this is partial search. One can
think of partial search in following terms: an exact address of the target item
is given by a sequence of many bites, but we want to find only several first
bites of the address. We consider different partial search algorithms
consisting of a sequence of global and local searches and suggest the optimal
one. Global search consists of the standard Grover iterations for the whole
database. Local search consists of Grover iterations in each individual block
made simultaneously in all blocks. Efficiency of an algorithm is measured by
number of queries to the oracle.
- oai_identifier:
- oai:arXiv.org:quant-ph/0510179
- categories:
- quant-ph
- comments:
- 11 pages 4 figures
- doi:
- 10.1007/s11128-006-0024-3
- arxiv_id:
- quant-ph/0510179
- journal_ref:
- Quantum Information Processing, ISSN: 1570-0755 (Paper) 1573-1332
, 2006
- report_no:
- YITP-SB-05-35
- created:
- 2005-10-23
Full article ▸
|
|
| related documents |
| 0305171v1 |
| 0204019v1 |
| 0403184v2 |
| 0702069v1 |
| 0512025v1 |
| 0610047v1 |
| 0703124v2 |
| 0611058v2 |
| 0609125v1 |
| 0703016v1 |
| 0511021v2 |
| 0602135v1 |
| 0612175v1 |
| 0605002v1 |
| 0610125v1 |
| 0611125v1 |
| 0602089v1 |
| 0606171v1 |
| 0602016v3 |
| 0703193v2 |
| 0608156v1 |
| 0603155v1 |
| 0612123v2 |
| 0612052v2 |
| 0606242v3 |
|