Distributed Grover's algorithm

Abstract

Let Boolean function $f:\{0,1{\}}^n⟶\{0,1\}$ where $|\{x\in \{0,1{\}}^n|f(x)=1\}|=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$ for some $1\le b_i\le a$ and $r_i\le 2t_a+1$, where $t_a=\lceil 2\pi \sqrt{a}+11\rceil$. In particular, if $a=1$, then our distributed Grover's algorithm only needs $\lfloor \frac{\pi }{4}\sqrt{2^{n-k}}\rfloor$ queries, versus $\lfloor \frac{\pi }{4}\sqrt{2^n}\rfloor$ queries of Grover's algorithm. %When $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).

20pages, five figures, comments are welcome