IPSJ Digital Courier

Quantum Biased Oracles

Kazuo Iwama, Akinori Kawachi, Shigeru Yamashita

Published Jan 1, 2005• 0 citations

Abstract

This paper reviews researches on quantum oracle computations when oracles are not perfect, i.e., they may return wrong answers. We call such oracles biased oracles, and discuss the formal model of them. Then we provide an intuitive explanation how quantum search with biased oracles by Høyer, et al.(2003) works. We also review the method, by Buhrman, et al.(2005), to obtain all the answers of a quantum biased oracle without any overhead compared to the perfect oracle case. Moreover, we discuss two special cases of quantum biased oracles and their interesting properties, which are not found in the classical corresponding cases. Our discussion implies that the model of quantum biased oracle adopted by the existing researches is natural.

DOI: 10.2197/ipsjdc.1.461

Related papers

General Bounds for Quantum Biased Oracles

Kazuo Iwama, Rudy Raymond, Shigeru Yamashita

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

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

Robust Quantum Algorithms with $\eps$-Biased Oracles

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi +1 more

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

Comparative Computational Strength of Quantum Oracles

Alp Atıcı

arXiv:quant-ph/0312107Dec 11, 20032 citations

Robust Quantum Algorithms for Oracle Identification (Theoretical Computer Science and its Applications)

Kazuo Iwama, Akinori Kawachi, Rudy Raymond +1 more

数理解析研究所講究録Apr 1, 20050 citations

IPSJ Digital Courier

Quantum Biased Oracles

Kazuo Iwama, Akinori Kawachi, Shigeru Yamashita

Published Jan 1, 2005• 0 citations

Publisher

Abstract

DOI: 10.2197/ipsjdc.1.461

Related papers

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

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

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

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

Comparative Computational Strength of Quantum Oracles

Alp Atıcı

It is an established fact that for many of the interesting problems quantum algorithms based on queries of the standard oracle bring no significant improvement in comparison to known classical algorithms. It is conceivable that there are other oracles of algorithmic importance acting in a less intuitive fashion to which such limitations do not apply. Thus motivated this article suggests a broader understanding towards what a general quantum oracle is. We propose a general definition of a quantum oracle and give a classification of quantum oracles based on the behavior of the eigenvalues and eigenvectors of their queries. Our aim is to determine the computational characteristics of a quantum oracle in terms of these eigenvalues and eigenvectors. Within this framework we attempt to describe the class of quantum oracles that are efficiently simulated by the standard oracle and compare the computational strength of different kinds of quantum oracles by an adversary argument using trigonometric polynomials.It is an established fact that for many of the interesting problems quantum algorithms based on queries of the standard oracle bring no significant improvement in comparison to known classical algorithms. It is conceivable that there are other oracles of algorithmic importance acting in a less intuitive fashion to which such limitations do not apply. Thus motivated this article suggests a broader understanding towards what a general quantum oracle is. We propose a general definition of a quantum oracle and give a classification of quantum oracles based on the behavior of the eigenvalues and eigenvectors of their queries. Our aim is to determine the computational characteristics of a quantum oracle in terms of these eigenvalues and eigenvectors. Within this framework we attempt to describe the class of quantum oracles that are efficiently simulated by the standard oracle and compare the computational strength of different kinds of quantum oracles by an adversary argument using trigonometric polynomials.

arXiv:quant-ph/0312107Dec 11, 20032 citations

Robust Quantum Algorithms for Oracle Identification (Theoretical Computer Science and its Applications)

Kazuo Iwama, Akinori Kawachi, Rudy Raymond +1 more

The oracle identification problem (OIP) was introduced by Ambainis et.al. [4], which is given as a set $S$ of $M$ oracles and a hidden oracle $f$ .Our task is to figure out which oracle in $S$ is equal to the hidden $f$ by doing queries to $f$ .OIP includes several problems such as Grover Search as special cases.In this paper, we design robust algorithms, i.e., those which are tolerant against noisy oracles, for OIP.Our results include: (i) For any oracle set $S$ such that $|S|$ is polynomial in $N$ , $O(\sqrt{N})$ queries are enough to identify the hidden oracle, which is obviously optimal since this OIP includes Grover Search as a special case, (ii) For the case that $|S|\leq 2^{N^{d}}(d<1)$ , we design an algorithm whose query complexity is $O(\sqrt{N\log M/\log N})$ and matches the lower bound proved in [4].(Hi) We can furthermore design a robust algorithm whose complexity changes smoothly between the complexity of (ii) and the complexity of recovering all information about the hidden oracle whose complexity is $O(N)$ as showed by Buhrman et.al. in [11].Thus our new algorithms are not only robust but also their query complexities are even better than the previous noiseless case [4],The oracle identification problem (OIP) was introduced by Ambainis et.al. [4], which is given as a set $S$ of $M$ oracles and a hidden oracle $f$ .Our task is to figure out which oracle in $S$ is equal to the hidden $f$ by doing queries to $f$ .OIP includes several problems such as Grover Search as special cases.In this paper, we design robust algorithms, i.e., those which are tolerant against noisy oracles, for OIP.Our results include: (i) For any oracle set $S$ such that $|S|$ is polynomial in $N$ , $O(\sqrt{N})$ queries are enough to identify the hidden oracle, which is obviously optimal since this OIP includes Grover Search as a special case, (ii) For the case that $|S|\leq 2^{N^{d}}(d<1)$ , we design an algorithm whose query complexity is $O(\sqrt{N\log M/\log N})$ and matches the lower bound proved in [4].(Hi) We can furthermore design a robust algorithm whose complexity changes smoothly between the complexity of (ii) and the complexity of recovering all information about the hidden oracle whose complexity is $O(N)$ as showed by Buhrman et.al. in [11].Thus our new algorithms are not only robust but also their query complexities are even better than the previous noiseless case [4],

数理解析研究所講究録Apr 1, 20050 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$.

The oracle identification problem (OIP) was introduced by Ambainis et.al. [4], which is given as a set

S

M

oracles and a hidden oracle

f

.Our task is to figure out which oracle in

S

is equal to the hidden

f

by doing queries to

f

.OIP includes several problems such as Grover Search as special cases.In this paper, we design robust algorithms, i.e., those which are tolerant against noisy oracles, for OIP.Our results include: (i) For any oracle set

S

such that

|S|

is polynomial in

N

O(\sqrt{N})

queries are enough to identify the hidden oracle, which is obviously optimal since this OIP includes Grover Search as a special case, (ii) For the case that

|S|\leq 2^{N^{d}}(d<1)

, we design an algorithm whose query complexity is

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

and matches the lower bound proved in [4].(Hi) We can furthermore design a robust algorithm whose complexity changes smoothly between the complexity of (ii) and the complexity of recovering all information about the hidden oracle whose complexity is

O(N)

as showed by Buhrman et.al. in [11].Thus our new algorithms are not only robust but also their query complexities are even better than the previous noiseless case [4],