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

2008/10/01 by Michael Ben-Or, Avinatan Hassidim · 1 citation
Computer Science · #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Optimization and Search Problems

paper · doi:10.1109/focs.2008.58

openalex publication_date 2008/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

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 (log2n)/3.

Citations

• Quantum Search in an Ordered List via Adaptive Learning
• Searching games with errors—fifty years of coping with liars
• Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness
• Invariant Quantum Algorithms for Insertion into an Ordered List
• Quantum algorithms for the ordered search problem via semidefinite programming
• Searching with known error probability

Cited by

• Binary search [wikipedia]