General Bounds for Quantum Biased Oracles

DOI Web Site 8 References
  • Iwama Kazuo
    Graduate School of Informatics, Kyoto University Presently with Imai Quantum Computation and Information Project, ERATO, JST
  • Raymond Rudy
    Graduate School of Informatics, Kyoto University Presently with Imai Quantum Computation and Information Project, ERATO, JST
  • Yamashita Shigeru
    Graduate School of Information Science, Nara Institute of Science and Technology

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 logN/ε2). 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.

Journal

References(8)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top