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 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
₂
n)/3.