数理解析研究所講究録

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

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi, Katsumasa Watanabe

Published May 1, 2006• 0 citations

Abstract

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.

Related papers

Robust Quantum Algorithms with $\eps$-Biased Oracles

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi +1 more

arXiv:quant-ph/0605077May 8, 20063 citations

General Bounds for Quantum Biased Oracles

Kazuo Iwama, Rudy Raymond, Shigeru Yamashita

IPSJ Digital CourierJan 1, 20056 citations

Quantum Approximate Counting with Bernoulli Oracles

Chengshen Gao, Yongzhen Xu, Lvzhou Li

quant-pharXiv:2609.07604Sep 8, 20260 citations

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

Quantum Search with Noisy Oracle

Ansis Rosmanis

arXiv:2309.14944Sep 26, 20231 citation

Tight bounds for hybrid quantum-classical query algorithms

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

quant-pharXiv:2610.06803Oct 6, 20260 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, Katsumasa Watanabe

Published May 1, 2006• 0 citations

OpenAlex

Abstract

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.

Related papers

Robust Quantum Algorithms with $\eps$-Biased Oracles

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi +1 more

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

arXiv:quant-ph/0605077May 8, 20063 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

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

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

Quantum Search with Noisy Oracle

Ansis Rosmanis

We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability $p>0$ completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum $\mathrm{O}(\sqrt{n})$ -query algorithms in this setting, even for constant $p$ . We show that, for all $p\le 0.99$ , the quantum noisy-query complexity of the unstructured search is $\tildeΘ(\max\{np,\sqrt{n}\})$ . The lower bound $Ω(\max\{np,\sqrt n\})$ holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.We consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability $p>0$ completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum $\mathrm{O}(\sqrt{n})$-query algorithms in this setting, even for constant $p$. We show that, for all $p\le 0.99$, the quantum noisy-query complexity of the unstructured search is $\tildeΘ(\max\{np,\sqrt{n}\})$. The lower bound $Ω(\max\{np,\sqrt n\})$ holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.

arXiv:2309.14944Sep 26, 20231 citation

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

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.

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

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 consider quantum search algorithms that have access to a noisy oracle that, for every oracle call, with probability

p>0

completely depolarizes the query registers, while otherwise working properly. Previous results had not ruled out quantum

\mathrm{O}(\sqrt{n})

-query algorithms in this setting, even for constant

p

. We show that, for all

p\le 0.99

, the quantum noisy-query complexity of the unstructured search is

\tildeΘ(\max\{np,\sqrt{n}\})

. The lower bound

Ω(\max\{np,\sqrt n\})

holds also for the dephasing noise and even when, for every oracle call, the algorithm is provided with a flag indicating whether the error has occurred.

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.