Quantum Evaluation of Multi-Valued Boolean Functions
Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita
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\times\{0,1\}^n \to \{0,1\}$ and a 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\times 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 an explicit oracle whose
query complexity is $O(\sqrt{N/K})$. ($iii$) The tight complexity,
$\Theta(\frac{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$.
- oai_identifier:
- oai:arXiv.org:quant-ph/0304131
- categories:
- quant-ph
- comments:
- 10 pages, 4 figures
- arxiv_id:
- quant-ph/0304131
- created:
- 2003-04-21
Full article ▸
|