#
On the Power of Quantum Oracles

Kazuo Iwama (Kyoto Univ./ERATO,Kyoto)

## Abstract

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}
x {0, 1}^{n} -> {0, 1} and fixed (but hidden) value
a_{0}, we wish to obtain the value of a_{0}
by querying the oracle f(a_{0}, 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 \cdot x mod 2.
It is also well-known that the query complexity is \Theta(\sqrt{N})
(N = 2^{n}) 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 T_{f} where
T_{f} is the N x 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 \Omega(\sqrt{N/K}).
(ii) This lower bound is tight in the sense that we can construct several
explicit oracles whose complexity is O(\sqrt{N/K}).
(iii) The tight complexity, \Theta(N/K + log K), 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., log K v.s. constant when K = cN.

Joint work with Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra,
and Shigeru Yamashita.

ERATO QCI Project HOME |
EQIS'03 TOP |