arXiv:quant-ph/0605077

Robust Quantum Algorithms with $\eps$-Biased Oracles

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi, Katsumasa Watanabe

Published May 8, 2006• 3 citations

Abstract

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

DOI: 10.48550/arxiv.quant-ph/0605077

Related papers

Robust Quantum Algorithms Computing OR with -Biased Oracles

T. SUZUKI, Shigeru Yamashita, Masaki Nakanishi +1 more

IEICE Transactions on Information and SystemsFeb 1, 20070 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

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

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

quant-pharXiv:2609.07604Sep 8, 20260 citations

General Bounds for Quantum Biased Oracles

Kazuo Iwama, Rudy Raymond, Shigeru Yamashita

IPSJ Digital CourierJan 1, 20056 citations

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

quant-pharXiv:2610.06803Oct 6, 20260 citations

Robust Quantum Algorithms for Oracle Identification

Andris Ambainis, Kazuo Iwama, Akinori Kawachi +2 more

arXiv:quant-ph/0411204IPSJ SIG NotesNov 30, 200411 citations

arXiv:quant-ph/0605077

Robust Quantum Algorithms with $\eps$-Biased Oracles

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi, Katsumasa Watanabe

Published May 8, 2006• 3 citations

arXiv HTML PDF

Abstract

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

DOI: 10.48550/arxiv.quant-ph/0605077

Related papers

Robust Quantum Algorithms Computing OR with -Biased Oracles

T. SUZUKI, Shigeru Yamashita, Masaki Nakanishi +1 more

This paper considers the quantum query complexity of e-biased oracles that return the correct value with probability only 1/2 + e. In particular, we show a quantum algorithm to compute N-bit OR functions with O(√N/e) queries to e-biased oracles. This improves the known upper bound of O(√N/e2) and matches the known lower bound; we answer the conjecture raised by the paper yamashita affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of e. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of e.This paper considers the quantum query complexity of e-biased oracles that return the correct value with probability only 1/2 + e. In particular, we show a quantum algorithm to compute N-bit OR functions with O(√N/e) queries to e-biased oracles. This improves the known upper bound of O(√N/e2) and matches the known lower bound; we answer the conjecture raised by the paper yamashita affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of e. This contrasts with the corresponding classical situation, where it is almost hopeless to construct a bounded error algorithm without knowing the value of e.

IEICE Transactions on Information and SystemsFeb 1, 20070 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

General Bounds for Quantum Biased Oracles

Kazuo Iwama, Rudy Raymond, Shigeru Yamashita

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

Tight bounds for hybrid quantum-classical query algorithms

Andris Ambainis, András Gilyén, Martins Kokainis

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$ , the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most $q$ oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision $ε$ requires $Θ(\frac{1}{q ε^2})$ queries; (ii) (Unbiased) Amplitude estimation up to a precision $ε$ requires $Θ(\frac{p(1-p)}{q ε^2})$ queries; (iii) Search among $N$ items requires $Θ(\frac{N}{q})$ queries; (iv) Two level AND-OR tree (AND of $m$ ORs, with $n$ inputs to each OR) requires $Θ(\frac{nm}{q})$ queries. All of these bounds are optimal up to a constant factor, for all $q$ from 1, corresponding to the classical complexity, to $Q(f)$, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

quant-pharXiv:2610.06803Oct 6, 20260 citations

Robust Quantum Algorithms for Oracle Identification

Andris Ambainis, Kazuo Iwama, Akinori Kawachi +2 more

The oracle identification problem (OIP) was introduced by Ambainis et al. \cite{AIKMRY04}. It is given as a set $S$ of $M$ oracles and a blackbox oracle $f$ . Our task is to figure out which oracle in $S$ is equal to the blackbox $f$ by making queries to $f$ . OIP includes several problems such as the Grover Search as special cases. In this paper, we improve the algorithms in \cite{AIKMRY04} by providing a mostly optimal upper bound of query complexity for this problem: ( $i$ ) For any oracle set $S$ such that $|S| \le 2^{N^d}$ ( $d < 1$ ), we design an algorithm whose query complexity is $O(\sqrt{N\log{M}/\log{N}})$ , matching the lower bound proved in \cite{AIKMRY04}. ( $ii$ ) Our algorithm also works for the range between $2^{N^d}$ and $2^{N/\log{N}}$ (where the bound becomes O(N)), but the gap between the upper and lower bounds worsens gradually. ( $iii$ ) Our algorithm is robust, namely, it exhibits the same performance (up to a constant factor) against the noisy oracles as also shown in the literatures \cite{AC02,BNRW03,HMW03} for special cases of OIP.The oracle identification problem (OIP) was introduced by Ambainis et al. \cite{AIKMRY04}. It is given as a set $S$ of $M$ oracles and a blackbox oracle $f$. Our task is to figure out which oracle in $S$ is equal to the blackbox $f$ by making queries to $f$. OIP includes several problems such as the Grover Search as special cases. In this paper, we improve the algorithms in \cite{AIKMRY04} by providing a mostly optimal upper bound of query complexity for this problem: ($i$) For any oracle set $S$ such that $|S| \le 2^{N^d}$ ($d < 1$), we design an algorithm whose query complexity is $O(\sqrt{N\log{M}/\log{N}})$, matching the lower bound proved in \cite{AIKMRY04}. ($ii$) Our algorithm also works for the range between $2^{N^d}$ and $2^{N/\log{N}}$ (where the bound becomes O(N)), but the gap between the upper and lower bounds worsens gradually. ($iii$) Our algorithm is robust, namely, it exhibits the same performance (up to a constant factor) against the noisy oracles as also shown in the literatures \cite{AC02,BNRW03,HMW03} for special cases of OIP.

arXiv:quant-ph/0411204IPSJ SIG NotesNov 30, 200411 citations

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)

\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

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.

We study hybrid quantum-classical algorithms in the query model. The computation consists of quantum subroutines that make at most

q

oracle queries; between subroutines, all qubits are measured and discarded. We prove matching upper and lower bounds for several problems in this model: (i) (Unbiased) Phase estimation up to a precision

ε

requires

Θ(\frac{1}{q ε^2})

queries; (ii) (Unbiased) Amplitude estimation up to a precision

ε

requires

Θ(\frac{p(1-p)}{q ε^2})

queries; (iii) Search among

N

items requires

Θ(\frac{N}{q})

queries; (iv) Two level AND-OR tree (AND of

m

ORs, with

n

inputs to each OR) requires

Θ(\frac{nm}{q})

queries. All of these bounds are optimal up to a constant factor, for all

q

from 1, corresponding to the classical complexity, to

Q(f)

, the unrestricted quantum query complexity of the respective problem. We also derive a hybrid lower bound for distinguishing two distributions specified by a state-preparation unitary; this bound is tight up to a logarithmic factor. Besides specific lower bounds, an important contribution is developing methods for proving lower bounds on hybrid quantum algorithms (which have been very ad-hoc up to now). The first two bounds follow from a common framework: we analyze probability distributions over measurement transcripts and bound a progress measure that captures their distinguishability. The AND-OR bound requires a more delicate argument, combining two progress measures that track the information available to the algorithm classically and in quantum form, respectively.

The oracle identification problem (OIP) was introduced by Ambainis et al. \cite{AIKMRY04}. It is given as a set

S

M

oracles and a blackbox oracle

f

. Our task is to figure out which oracle in

S

is equal to the blackbox

f

by making queries to

f

. OIP includes several problems such as the Grover Search as special cases. In this paper, we improve the algorithms in \cite{AIKMRY04} by providing a mostly optimal upper bound of query complexity for this problem: (

i

) For any oracle set

S

such that

|S| \le 2^{N^d}

(

d < 1

), we design an algorithm whose query complexity is

O(\sqrt{N\log{M}/\log{N}})

, matching the lower bound proved in \cite{AIKMRY04}. (

ii

) Our algorithm also works for the range between

2^{N^d}

and

2^{N/\log{N}}

(where the bound becomes O(N)), but the gap between the upper and lower bounds worsens gradually. (

iii

) Our algorithm is robust, namely, it exhibits the same performance (up to a constant factor) against the noisy oracles as also shown in the literatures \cite{AC02,BNRW03,HMW03} for special cases of OIP.