  This paper considers the quantum query complexity of {\it $\eps$-biased
oracles} that return the correct value with probability only $1/2 + \eps$. In
particular, we show a quantum algorithm to compute $N$-bit OR functions with
$O(\sqrt{N}/{\eps})$ queries to $\eps$-biased oracles. This improves the known
upper bound of $O(\sqrt{N}/{\eps}^2)$ and matches the known lower bound; we
answer the conjecture raised by the paper by Iwama et al. affirmatively. We
also show a quantum algorithm to cope with the situation in which we have no
knowledge about the value of $\eps$. This contrasts with the corresponding
classical situation, where it is almost hopeless to achieve more than a
constant success probability without knowing the value of $\eps$.
