dorsal/arxiv
View SchemaQuantum Evaluation of Multi-Valued Boolean Functions
| Authors | Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0304131 |
| URL | https://arxiv.org/abs/quant-ph/0304131 |
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$.
{
"annotation_id": "08736bfe-0188-4a36-88eb-d350a088d1d3",
"date_created": "2026-03-02T18:01:59.609000Z",
"date_modified": "2026-03-02T18:01:59.609000Z",
"file_hash": "642547af02c611075f536e18eae533f1c460daa6578b56c4294a4f9e0e1fbe29",
"private": false,
"record": {
"abstract": "Our problem is to evaluate a multi-valued Boolean function $F$ through oracle\ncalls. If $F$ is one-to-one and the size of its domain and range is the same,\nthen our problem can be formulated as follows: Given an oracle $f(a,x):\n\\{0,1\\}^n\\times\\{0,1\\}^n \\to \\{0,1\\}$ and a fixed (but hidden) value $a_0$, we\nwish to obtain the value of $a_0$ by querying the oracle $f(a_0,x)$. Our goal\nis to minimize the number of such oracle calls (the query complexity) using a\nquantum mechanism.\n Two popular oracles are the EQ-oracle defined as $f(a,x)=1$ iff $x=a$ and the\nIP-oracle defined as $f(a,x)= a\\cdot x \\mod 2$. It is also well-known that the\nquery complexity is $\\Theta(\\sqrt{N})$ ($N=2^n$) for the EQ-oracle while only\nO(1) for the IP-oracle. The main purpose of this paper is to fill this gap or\nto investigate what causes this large difference. To do so, we introduce a\nparameter $K$ as the maximum number of 1\u0027s in a single column of $T_f$ where\n$T_f$ is the $N\\times N$ truth-table of the oracle $f(a,x)$. Our main result\nshows that the (quantum) query complexity is heavily governed by this parameter\n$K$: ($i$) The query complexity is $\\Omega(\\sqrt{N/K})$. ($ii$) This lower\nbound is tight in the sense that we can construct an explicit oracle whose\nquery complexity is $O(\\sqrt{N/K})$. ($iii$) The tight complexity,\n$\\Theta(\\frac{N}{K}+\\log{K})$, is also obtained for the classical case. Thus,\nthe quantum algorithm needs a quadratically less number of oracle calls when\n$K$ is small and this merit becomes larger when $K$ is large, e.g., $\\log{K}$\nv.s. constant when $K = cN$.",
"arxiv_id": "quant-ph/0304131",
"authors": [
"Kazuo Iwama",
"Akinori Kawachi",
"Hiroyuki Masuda",
"Raymond H. Putra",
"Shigeru Yamashita"
],
"categories": [
"quant-ph"
],
"title": "Quantum Evaluation of Multi-Valued Boolean Functions",
"url": "https://arxiv.org/abs/quant-ph/0304131"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b337da29-ac44-40ea-ba1a-bfdde26e78ef",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}