论文标题
分布式Grover的算法
Distributed Grover's algorithm
论文作者
论文摘要
让布尔函数$ f：\ {0,1 \}^n \ longrightArrow \ {0,1 \} $其中$ | \ {x \ in \ in \ {0,1 \}^n | f（x）= 1 \} | = a \ geq 1 $。要通过Grover's AlgorithM搜索\ {0,1 \}^n $的$ f（x）= 1 $，我们可以通过查询时间$ \ lfloor \fracπ{4} \ sqrt {\ sqrt {\ frac {\ frac {\ frac {2^n} {2^n} {a a} {a a}} {在本文中，我们提出了一种分布式的Grover的算法，用于计算$ f $的查询时间和较少的输入位。更确切地说，对于任何$ n> k \ geq 1 $的$ k $，我们可以将$ f $分解为$ 2^k $子函数，每个函数具有$ n-k $输入位，然后可以通过在最多的$ \ sum_ {i = 1}} r_i} {r_i} {r_i} {r_i}^{r lfolo中计算出这些子函数来找到目标。 \fracπ{4} \ sqrt {\ frac {2^{n-k}} {b_i}} {b_i}} \ rfloor+\ lceil+\ lceil \ sqrt \ sqrt {2^{n-k}} \ rceil+rceil+2t_a+1 $ for SON 2t_a+1 $，其中$ t_a = \ lceil2π\ sqrt {a} +11 \ rceil $。特别是，如果$ a = 1 $，则我们的分布式Grover的算法只需要$ \ lfloor \ lfloor \fracπ{4} \ sqrt {2^{n-k}} \ rfloor $ queries，vers $ \ lfloor \ lfloor \ lfloor \fracπ{4} {4} Grover的算法。 ％$ n $ Qubits属于中等规模，但在实践中仍然很难处理时，$ N-K $ Qubits可能对于适当的$ k $的物理可实现性可能是可行的。最后，我们提出了一种构造量子电路的有效算法，以实现与任何带有连接正常形式（CNF）的布尔函数相对应的甲骨文。
Let Boolean function $f:\{0,1\}^n\longrightarrow \{0,1\}$ where $|\{x\in\{0,1\}^n| f(x)=1\}|=a\geq 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π{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\geq 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π{4}\sqrt{\frac{2^{n-k}}{b_i}} \rfloor+\lceil\sqrt{2^{n-k}}\rceil+2t_a+1$ for some $1\leq b_i\leq a$ and $r_i\leq 2t_a+1$, where $t_a=\lceil 2π\sqrt{a}+11\rceil$. In particular, if $a=1$, then our distributed Grover's algorithm only needs $\lfloor \fracπ{4}\sqrt{2^{n-k}} \rfloor$ queries, versus $\lfloor \fracπ{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).
