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.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.

IPSJ Digital CourierJan 1, 20056 citations

Upper bounds for quantum biased oracles with explicit bias rate(New Trends in Theory of Computation and Algorithm)

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi +1 more

We investigate the query complexity of quantum biased oracles. $\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{p}\mathrm{o}\mathrm{s}\epsilon$ that the biased oracles answer queries correctly with probability at least $1/2+\epsilon$ .Given such an oracle, we present an algorithm to simulate a single query to an oracle that answers queries $\mathrm{C}\mathrm{O}\alpha \mathrm{e}\mathrm{c}\mathrm{u}_{\mathrm{y}}$ with probability at least 2/3, using $0(1/\epsilon)$ queries to the given oracle.For searching problems, combining the algorithm with a known result.we can obtain an optimal algorithm.The simulating algorithm works effectively when we know the value of $\epsilon$ .We also consider the situation where no knowledge about $\epsilon$ is given.We investigate the query complexity of quantum biased oracles.$\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{p}\mathrm{o}\mathrm{s}\epsilon$ that the biased oracles answer queries correctly with probability at least $1/2+\epsilon$ .Given such an oracle, we present an algorithm to simulate a single query to an oracle that answers queries $\mathrm{C}\mathrm{O}\alpha \mathrm{e}\mathrm{c}\mathrm{u}_{\mathrm{y}}$ with probability at least 2/3, using $0(1/\epsilon)$ queries to the given oracle.For searching problems, combining the algorithm with a known result.we can obtain an optimal algorithm.The simulating algorithm works effectively when we know the value of $\epsilon$ .We also consider the situation where no knowledge about $\epsilon$ is given.

数理解析研究所講究録May 1, 20060 citations

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given $m$ Bernoulli distributions with unknown biases $p_1,\dots,p_m$ and a gap parameter $Δ$ , the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ( $p_i\ge1/2+Δ$ ) to within additive error $ε$ . We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ queries, achieving a quadratic speedup over the classical sample complexity. % of $Θ(ρ/Δ^2ε^2)$ . Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of $Ω(\sqrtρ/(Δε))$ via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap $Δ=Θ(1)$ , which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$ , thereby characterizing the query complexity of quantum counting with bounded-error oracles.Quantum counting is a fundamental quantum algorithm that estimates the fraction of marked elements using a membership oracle, achieving a quadratic speedup over classical sampling. The membership oracle, however, assumes exact labeling of each element, but this assumption fails when the labels are inherently probabilistic. We study quantum counting with \emph{Bernoulli oracles}, where given $m$ Bernoulli distributions with unknown biases $p_1,\dots,p_m$ and a gap parameter $Δ$, the goal is to estimate the fraction $ρ$ of \emph{positive} distributions ($p_i\ge1/2+Δ$) to within additive error $ε$. We prove an upper bound of $\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)$ queries, achieving a quadratic speedup over the classical sample complexity. % of $Θ(ρ/Δ^2ε^2)$. Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of $Ω(\sqrtρ/(Δε))$ via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap $Δ=Θ(1)$, which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to $\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)$ and $Ω(\frac{\sqrtρ}ε)$, thereby characterizing the query complexity of quantum counting with bounded-error oracles.

quant-pharXiv:2609.07604Sep 8, 20260 citations

We investigate the query complexity of quantum biased oracles.

\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{p}\mathrm{o}\mathrm{s}\epsilon

that the biased oracles answer queries correctly with probability at least

1/2+\epsilon

.Given such an oracle, we present an algorithm to simulate a single query to an oracle that answers queries

\mathrm{C}\mathrm{O}\alpha \mathrm{e}\mathrm{c}\mathrm{u}_{\mathrm{y}}

with probability at least 2/3, using

0(1/\epsilon)

queries to the given oracle.For searching problems, combining the algorithm with a known result.we can obtain an optimal algorithm.The simulating algorithm works effectively when we know the value of

\epsilon

.We also consider the situation where no knowledge about

\epsilon

is given.

m

Bernoulli distributions with unknown biases

p_1,\dots,p_m

and a gap parameter

Δ

, the goal is to estimate the fraction

ρ

of \emph{positive} distributions (

p_i\ge1/2+Δ

) to within additive error

ε

. We prove an upper bound of

\tilde{O}\!\big(\frac{\sqrtρ}{Δε}+\frac{1}{Δ\sqrtε}\big)

queries, achieving a quadratic speedup over the classical sample complexity. % of

Θ(ρ/Δ^2ε^2)

. Our algorithm first uses the Quantum Singular Value Transformation (QSVT) to coherently amplify the bias gap without collapsing the superposition over distributions, and then applies two-stage adaptive amplitude estimation. We complement this upper bound with a near-matching lower bound of

Ω(\sqrtρ/(Δε))

via a new composition theorem for the quantum adversary method in the Boolean-over-average-case direction. For the special case of a constant gap

Δ=Θ(1)

, which corresponds to the bounded-error oracle where each query returns the correct label with constant probability, our bounds specialize to

\tilde{O}\big(\frac{\sqrtρ}ε+\frac{1}{\sqrtε}\big)

and

Ω(\frac{\sqrtρ}ε)

, thereby characterizing the query complexity of quantum counting with bounded-error oracles.