Distributed Grover's algorithm

Let Boolean function $f:\{0,1{\}}^n⟶\{0,1\}$ where $\mathrm{\mid }\{x\in \{0,1{\}}^n\mathrm{\mid }f(x)=1\}\mathrm{\mid }=a\ge 1$. To search for an $x\in \{0,1{\}}^n$ with $f(x)=1$, by Grover’s algorithm we can get the objective with query times $\lfloor \frac{\pi }{4}\sqrt{\frac{2^n}{a}}\rfloor$. In this paper, we propose a distributed Grover’s algorithm for computing $f$ with lower query times and smaller number of input bits. More exactly, for any $k$ with $n>k\ge 1$, we can decompose $f$ into $2^k$ subfunctions, each which has $n-k$ input bits, and then the objective can be found out by computing these subfunctions with query times at most $\sum_{i=1}^{r_i} \lfloor \frac{\pi}{4}\sqrt{\frac{2^{n-k}}{b_i}} \rfloor+\lceil\sqrt{2^{n-k}}\rceil+2t_a+1$forsome$1\leq b_i\leq a$and$r_i\leq 2t_a+1$,where$t_a=\lceil 2\pi\sqrt{a}+11\rceil$\mathrm{.}Inparticular,if$a=1$,thenourdistributedGrove{r}^{\mathrm{\prime }}salgorithmonlyneeds$\lfloor \frac{\pi}{4}\sqrt{2^{n-k}} \rfloor$queries,versus$\lfloor \frac{\pi}{4}\sqrt{2^{n}} \rfloor$queriesofGrove{r}^{\mathrm{\prime }}salgorithm\mathrm{.}$n$ qubits belong to middle scale but still are a bit difficult to be processed in practice, $n-k$ qubits are likely feasible for appropriate $k$ in physical realizability. Finally, we propose an efficient algorithm of constructing quantum circuits for realizing the oracle corresponding to any Boolean function with conjunctive normal form (CNF).