Quantum Search on Bounded-Error Inputs
<|reference_start|>Quantum Search on Bounded-Error Inputs: Suppose we have n algorithms, quantum or classical, each computing some bit-value with bounded error probability. We describe a quantum algorithm that uses O(sqrt{n}) repetitions of the base algorithms and with high probability finds the index of a 1-bit among these n bits (if there is such an index). This shows that it is not necessary to first significantly reduce the error probability in the base algorithms to O(1/poly(n)) (which would require O(sqrt{n}log n) repetitions in total). Our technique is a recursive interleaving of amplitude amplification and error-reduction, and may be of more general interest. Essentially, it shows that quantum amplitude amplification can be made to work also with a bounded-error verifier. As a corollary we obtain optimal quantum upper bounds of O(sqrt{N}) queries for all constant-depth AND-OR trees on N variables, improving upon earlier upper bounds of O(sqrt{N}polylog(N)).<|reference_end|>
@article{hoyer2003quantum,
    title={Quantum Search on Bounded-Error Inputs},
    author={Peter Hoyer (Calgary), Michele Mosca (Waterloo, Perimeter Institute),
  Ronald de Wolf (CWI, Amsterdam)},
    journal={30th Intl. Colloquium on Automata, Languages, and Programming
  (ICALP), LNCS 2719, pp. 291-299, 2003},
    year={2003},
    doi={10.1007/3-540-45061-0_25},
    archivePrefix={arXiv},
    eprint={quant-ph/0304052},
    primaryClass={quant-ph cs.CC}
}