Quantum Evaluation of Multi-Valued Boolean Functions
| dc.creator | Iwama, Kazuo | |
| dc.creator | Kawachi, Akinori | |
| dc.creator | Masuda, Hiroyuki | |
| dc.creator | Putra, Raymond H. | |
| dc.creator | Yamashita, Shigeru | |
| dc.date | 2003-04-21 | |
| dc.date.accessioned | 2026-07-07T06:06:36Z | |
| dc.date.available | 2026-07-07T06:06:36Z | |
| dc.description | 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 $Θ(\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 $Ω(\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, $Θ(\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$. | |
| dc.description | 10 pages, 4 figures | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0304131 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0304131 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/91033 | |
| dc.subject | Quantum Physics | |
| dc.title | Quantum Evaluation of Multi-Valued Boolean Functions | |
| dc.type | text |