A quantum computer in combination with a binary oracle of domain size N is considered. It is shown how N/2+sqrt(N) calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 85%. This contrasts the power of classical computers which would require N calls to achieve the same result. From this result it follows that any binary function with the N bits of the oracle as input, can be calculated with a small 2 sided error using N/2+sqrt(N) queries.
A quantum computer in combination with a binary oracle of domain size N is considered. It is shown how N/2+sqrt(N) calls to the oracle are sufficient to guess the whole content of the oracle (being an N bit string) with probability greater than 85%. This contrasts the power of classical computers which would require N calls to achieve the same result. From this result it follows that any binary function with the N bits of the oracle as input, can be calculated with a small 2 sided error using N/2+sqrt(N) queries.
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.
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.
Our problem is to evaluate a multi-valued Boolean function F through oracle calls. If F is one-to-one and the size of its domain and range is the same, then our problem can be formulated as follows: Given an oracle f(a,x):{0,1}n×{0,1}n→{0,1} and a fixed (but hidden) value a0, we wish to obtain the value of a0 by querying the oracle f(a0,x). Our goal is to minimize the number of such oracle calls (the query complexity) using a quantum mechanism. Two popular oracles are the EQ-oracle defined as f(a,x)=1 iff x=a and the IP-oracle defined as f(a,x)=a⋅xmod2. It is also well-known that the query complexity is Θ(N) (N=2n) for the EQ-oracle while only O(1) for the IP-oracle. The main purpose of this paper is to fill this gap or to investigate what causes this large difference. To do so, we introduce a parameter K as the maximum number of 1's in a single column of Tf where Tf is the N×N truth-table of the oracle f(a,x). Our main result shows that the (quantum) query complexity is heavily governed by this parameter K: (i) The query complexity is Ω(N/K). (ii) This lower bound is tight in the sense that we can construct an explicit oracle whose query complexity is O(N/K). (iii) The tight complexity, Θ(KN+logK), is also obtained for the classical case. Thus, the quantum algorithm needs a quadratically less number of oracle calls when K is small and this merit becomes larger when K is large, e.g., logK v.s. constant when K=cN.
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$.
We consider the following data compression problem. Given a string x∈{0,1}m of Hamming weight at most n, compress it into a shorter string y∈{0,1}s so that any bit xi of x can be retrieved without any error using at most t quantum queries to the standard oracle encoding of y. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on m except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on n.