IPSJ Digital Courier
Online ISSN : 1349-7456
ISSN-L : 1349-7456
General Bounds for Quantum Biased Oracles
Kazuo IwamaRudy RaymondShigeru Yamashita
Author information
JOURNAL FREE ACCESS

2005 Volume 1 Pages 415-425

Details
Abstract

An oracle with bias ε is an oracle that answers queries correctly with a probability of at least 1/2+ε. In this paper, we study the upper and lower bounds of quantum query complexity of oracles with bias ε. For general upper bounds, we show that for any quantum algorithm solving some problem with high probability using T queries of perfect quantum oracles, i.e., oracles with ε =1/2, there exists a quantum algorithm solving the same problem, also with high probability, using O(T/ε) queries of the corresponding biased quantum oracles. As corollaries we can show robust quantum algorithms and gaps between biased quantum and classical oracles, e.g., by showing a problem where the quantum query complexity is O(N/ε) but the classical query complexity is lower bounded by Ω(N logN2). For general lower bounds, we generalize Ambainis' quantum adversary argument to biased quantum oracles and obtain the first lower bounds with explicit bias factor. As one of its applications we can provide another proof of the optimality of quantum algorithms for the so-called quantum Goldreich-Levin problem which was proved before by Adcock, et al. using different and more complicated methods.

Content from these authors
© 2005 by the Information Processing Society of Japan
Previous article Next article
feedback
Top