We geometrically characterize the query complexity of the oracle identification prob- lem in this paper.By defining an inner product between two oracles, we construct a quantum algo- rithm, which generalizes Bemstein-Vazirani and Grover algorithms, for a certain class of the oracle identification problem characterized by the inner product.We also show the optimality of this quantum algorithm.
We geometrically characterize the query complexity of the oracle identification prob- lem in this paper.By defining an inner product between two oracles, we construct a quantum algo- rithm, which generalizes Bemstein-Vazirani and Grover algorithms, for a certain class of the oracle identification problem characterized by the inner product.We also show the optimality of this quantum algorithm.
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(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∣≤2Nd(d<1) , we design an algorithm whose query complexity is O(NlogM/logN) 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 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∣≤2Nd (d<1), we design an algorithm whose query complexity is O(NlogM/logN), matching the lower bound proved in \cite{AIKMRY04}. (ii) Our algorithm also works for the range between 2Nd and 2N/logN (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.
In the oracle identification problem, we are given oracle access to an unknown N-bit string x promised to belong to a known set C of size M and our task is to identify x. We present a quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm considerably simplifies and improves the previous best algorithm due to Ambainis et al. Our algorithm also has applications in quantum learning theory, where it improves the complexity of exact learning with membership queries, resolving a conjecture of Hunziker et al. The algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered γ2-norm semidefinite program, which characterizes quantum query complexity. Our composition theorem is quite general and allows us to compose quantum algorithms with input-dependent query complexities without incurring a logarithmic overhead for error reduction. As an application of the composition theorem, we remove all log factors from the best known quantum algorithm for Boolean matrix multiplication.
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.
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.
While powerful tools have been developed to analyze quantum query complexity, there are still many natural problems that do not fit neatly into the black box model of oracles. We create a new model that allows multiple oracles with differing costs. This model captures more of the difficulty of certain natural problems. We test this model on a simple problem, Search with Two Oracles, for which we create a quantum algorithm that we prove is asymptotically optimal. We further give some evidence, using a geometric picture of Grover's algorithm, that our algorithm is exactly optimal.