|
| related topics |
| {algorithm, log, probability} |
| {information, entropy, channel} |
| {error, code, errors} |
| {cos, sin, state} |
|
Quantum Search in an Ordered List via Adaptive Learning
M. Ben-Or, Avinatan Hassidim
abstract: We use a Bayesian approach to optimally solve problems in noisy binary
search. We deal with two variants:
1. Each comparison can be erroneous with some probability $1 - p$. 2. At each
stage $k$ comparisons can be performed in parallel and a noisy answer is
returned
We present a (classic) algorithm which optimally solves both variants
together, up to an additive term of O(\log \log(n)), and prove matching
information theoretic lower bounds. We use the algorithm to improve the results
of Farhi et al \cite{FGGS99} presenting a quantum (error free) search algorithm
in an ordered list of expected complexity less than (\log_2n) / 3.
- oai_identifier:
- oai:arXiv.org:quant-ph/0703231
- categories:
- quant-ph
- comments:
- 10 pages no figures
- arxiv_id:
- quant-ph/0703231
- created:
- 2007-03-24
- updated:
- 2007-11-09
Full article ▸
|
|
| related documents |
| 9910033v4 |
| 0408119v1 |
| 0603135v1 |
| 0510185v1 |
| 0504083v2 |
| 0408150v2 |
| 9904079v3 |
| 0510230v3 |
| 9802040v2 |
| 0008059v3 |
| 0612089v3 |
| 0206023v2 |
| 0702007v2 |
| 0612052v2 |
| 0702155v3 |
| 0703193v2 |
| 0612033v1 |
| 0701198v1 |
| 0701079v1 |
| 0701054v1 |
| 0702143v1 |
| 0612123v2 |
| 0702270v1 |
| 0702140v1 |
| 0702033v1 |
|