2003 | OriginalPaper | Buchkapitel
Quantum Search on Bounded-Error Inputs
verfasst von : Peter Høyer, Michele Mosca, Ronald de Wolf
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 $$ 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)).