Studies on quantum query complexity for oracle identification problems

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

Simplified quantum algorithm for the oracle identification problem

Leila Taghavi

arXiv:2109.03902Quantum Machine IntelligenceJul 9, 20223 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

Quantum query complexity of symmetric oracle problems

Daniel Copeland, Jamie Pommersheim

We study the query complexity of quantum learning problems in which the oracles form a group G of unitary matrices. In the simplest case, one wishes to identify the oracle, and we find a description of the optimal success probability of a t -query quantum algorithm in terms of group characters. As an application, we show that Ω(n) queries are required to identify a random permutation in Sn . More generally, suppose H is a fixed subgroup of the group G of oracles, and given access to an oracle sampled uniformly from G , we want to learn which coset of H the oracle belongs to. We call this problem coset identification and it generalizes a number of well-known quantum algorithms including the Bernstein-Vazirani problem, the van Dam problem and finite field polynomial interpolation. We provide character-theoretic formulas for the optimal success probability achieved by a t -query algorithm for this problem. One application involves the Heisenberg group and provides a family of problems depending on n which require n+1 queries classically and only 1 query quantumly.We study the query complexity of quantum learning problems in which the oracles form a group G of unitary matrices. In the simplest case, one wishes to identify the oracle, and we find a description of the optimal success probability of a t -query quantum algorithm in terms of group characters. As an application, we show that Ω(n) queries are required to identify a random permutation in Sn . More generally, suppose H is a fixed subgroup of the group G of oracles, and given access to an oracle sampled uniformly from G , we want to learn which coset of H the oracle belongs to. We call this problem coset identification and it generalizes a number of well-known quantum algorithms including the Bernstein-Vazirani problem, the van Dam problem and finite field polynomial interpolation. We provide character-theoretic formulas for the optimal success probability achieved by a t -query algorithm for this problem. One application involves the Heisenberg group and provides a family of problems depending on n which require n+1 queries classically and only 1 query quantumly.

arXiv:1812.09428QuantumMar 7, 20211 citation

Query Complexity of Quantum Biased Oracles

Kazuo Iwama, Rudy Raymond, Shigeru Yamashita

Springer eBooksJun 15, 20061 citation

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],

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.