Physics – Quantum Physics
Scientific paper
2003-04-21
Physics
Quantum Physics
10 pages, 4 figures
Scientific paper
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$.
Iwama Kazuo
Kawachi Akinori
Masuda Hiroyuki
Putra Raymond H.
Yamashita Shigeru
No associations
LandOfFree
Quantum Evaluation of Multi-Valued Boolean Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Evaluation of Multi-Valued Boolean Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Evaluation of Multi-Valued Boolean Functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-218221