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.
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$.
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.
We investigate the query complexity of quantum biased oracles.Supposϵ that the biased oracles answer queries correctly with probability at least 1/2+ϵ .Given such an oracle, we present an algorithm to simulate a single query to an oracle that answers queries COαecuy with probability at least 2/3, using 0(1/ϵ) 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 ϵ .We also consider the situation where no knowledge about ϵ is given.
Consider a quantum computer in combination with a binary oracle of domain size N. It is shown how N/2+/spl radic/N calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 95%. This contrasts the power of classical computers which would require N calls to achieve the same task. From this result it follows that any function with the N bits of the oracle as input can be calculated using N/2+/spl radic/N queries if we allow a small probability of error. It is also shown that this error probability can be made arbitrary small by using N/2+O(/spl radic/N) oracle queries. In the second part of the article 'approximate interrogation' is considered. This is when only a certain fraction of the N oracle bits are requested. Also for this scenario does the quantum algorithm outperform the classical protocols. An example is given where a quantum procedure with N/10 queries returns a string of which 80% of the bits are correct. Any classical protocol would need 6N/10 queries to establish such a correctness ratio.
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 p1,…,pm and a gap parameter Δ, the goal is to estimate the fraction ρ of \emph{positive} distributions (pi≥1/2+Δ) to within additive error ε. We prove an upper bound of O~(Δερ+Δε1) 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 Ω(ρ/(Δε)) 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 O~(ερ+ε1) and Ω(ερ), 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 Θ(qε21) queries;
(ii) (Unbiased) Amplitude estimation up to a precision ε requires Θ(qε2p(1−p)) queries;
(iii) Search among N items requires Θ(qN) queries;
(iv) Two level AND-OR tree (AND of m ORs, with n inputs to each OR) requires Θ(qnm) 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.