Generalized quantum search with parallelism
Generalized quantum search with parallelism
复制标题
DOI：
10.1103/physreva.61.052313
复制
发表时间：
1999-04
影响因子：
2.9
通讯作者：
R. Gingrich;Colin P. Williams;Nicolas Cerf Caltech;J. P. Laboratory;Universit́e Libre de Bruxelles
中科院分区：
文献类型：
--
作者：
R. Gingrich;Colin P. Williams;Nicolas Cerf Caltech;J. P. Laboratory;Universit́e Libre de Bruxelles
我们推广Grover的非结构化量子搜索算法，使其能够与任意起始叠加和任意酉算子。我们表明，广义量子搜索算法，当投在一个特殊的正交基，可以理解为执行一个精确的旋转的起始叠加到一个目标叠加。我们推导了广义量子搜索算法在n轮振幅放大后的成功概率公式。然后，我们使用这个公式来确定间断量子搜索算法的最佳策略，即，其中在最大成功概率点之前观察到幅度放大状态。平均而言，最优策略比Grover算法的朴素使用好约12%。获得的加速并不显着，但它说明了量子计算和经典计算技术的混合使用可以产生比单独使用更好的性能。此外，我们表明，间断的量子算法，需要相同的平均计算时间Grover的标准算法只需要一半的相干时间。然后，我们将分析扩展到k个量子搜索并行作用的社会的情况。我们推导出一个解析公式，连接的并行度与预期的计算时间k-并行量子搜索。由此产生的并行加速的规模为O（\sqrt{k}），而需要确保成功的代理的最小数量，k，减少作为可实现的相干时间的平方的倒数。这一结果对于设计可能具有有限相干时间的初级量子计算机具有实际意义。
We generalize Grover's unstructured quantum search algorithm to enable it to work with arbitrary starting superpositions and arbitrary unitary operators. We show that the generalized quantum search algorithm, when cast in a special orthonormal basis, can be understood as performing an exact rotation of a starting superposition into a target superposition. We derive a formula for the success probability of the generalized quantum search algorithm after n rounds of amplitude amplification. We then use this formula to determine the optimal strategy for a punctuated quantum search algorithm, i.e., one in which the amplitude amplified state is observed before the point of maximum success probability. On average, the optimal strategy is about 12% better than the naive use of Grover's algorithm. The speedup obtained is not dramatic but it illustrates that a hybrid use of quantum computing and classical computing techniques can yield a performance that is better than either alone. In addition, we show that a punctuated quantum algorithm that takes the same average computation time as Grover's standard algorithm only requires half the coherence time. We then extend the analysis to the case of a society of k quantum searches acting in parallel. We derive an analytic formula that connects the degree of parallelism with the expected computation time for k-parallel quantum search. The resulting parallel speedup scales as $O(\sqrt{k}),$ while the minimum number of agents needed to ensure success, k, decreases as the inverse of the square of the achievable coherence time. This result has practical significance for the design of rudimentary quantum computers that are likely to have a limited coherence time.