论文标题
Grover的搜索算法$ n $ Qubits具有最佳迭代次数
Grover's search algorithm for $n$ qubits with optimal number of iterations
论文作者
论文摘要
使用Grover的搜索算法，从尺寸$ n $数据库中搜索$ m $目标的成功概率取决于Oracle的复合操作的迭代次数，然后是Grover的扩散操作。尽管所需数量的迭代量表缩放为$ \ MATHCAL {o}（\ sqrt {n}）$对于大$ n $，但是当$ \ sqrt {m/n} $不小时，渐近线不是最佳迭代的好指标。确定确切迭代次数的方案，要遵守搜索成功概率的阈值（检测目标状态），这对于算法的功效至关重要。在这项工作中，提出了一个通用计划，用于构建$ n $ qubit的Grover的搜索算法，并提出了$ 1 \ leq m \ leq n $目标状态，以及找到成功搜索的最佳迭代次数。还表明，对于给定的$ n $和$ m $，该算法的成功概率有上限。
The success probability of a search of $M$ targets from a database of size $N$, using Grover's search algorithm depends critically on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. Although the required number of iterations scales as $\mathcal{O}(\sqrt{N})$ for large $N$, the asymptote is not a good indicator of the optimal number of iterations when $\sqrt{M/N}$ is not small. A scheme for the determination of the exact number of iterations, subject to a threshold set for the success probability of the search (probability of detecting the target state(s)), is crucial for the efficacy of the algorithm. In this work, a general scheme for the construction of $n$-qubit Grover's search algorithm with $1 \leq M \leq N$ target states is presented, along with the procedure to find the optimal number of iterations for a successful search. It is also shown that for given $N$ and $M$, there is an upper-bound on the success probability of the algorithm.
