The Bayesian Learner is Optimal for Noisy Binary Search  (and Pretty Good for Quantum as Well)

We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants:1. Each comparison is erroneous with independent probability 1-p. 2. At each stage k comparisons can be performed in parallel and a noisy answer is returned. We present a (classical) algorithm wh...

Full description

Saved in:
Bibliographic Details
Main Authors: Ben Or, M., Hassidim, A.
Format: Conference Proceeding
Language:English
Subjects:
algorithms
Bayesian methods
binary search
Computer science
Entropy
Error correction
Error probability
Information theory
noise
Quantum computing
quantum search
search
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We use a Bayesian approach to optimally solve problems in noisy binary search. We deal with two variants:1. Each comparison is erroneous with independent probability 1-p. 2. At each stage k comparisons can be performed in parallel and a noisy answer is returned. We present a (classical) algorithm which solves both variants optimally (with respect to p and k), up to an additive term of O(loglog n), and prove matching information-theoretic lower bounds. We use the algorithm to improve the results of Farhi et al., presenting an exact quantum search algorithm in an ordered list of expected complexity less than (log 2 n)/3.
ISSN:0272-5428
DOI:10.1109/FOCS.2008.58