Simpler quantum counting
Simpler quantum counting
复制标题
更简单的量子计数
DOI：
--
复制
发表时间：
2019
影响因子：
1
通讯作者：
Chu
中科院分区：
文献类型：
--
作者：
Chu
提出了一种基于振幅放大的量子计数算法。该算法是有界的O（sqrt（N/M））调用控制Grover操作，其中M是标记状态的数量和N是在搜索空间中的状态的总数。该算法在log（sqrt（N/M））连续测量步骤内终止，当测量状态的概率p1| 1>至少为0.5，并且来自最终步骤的结果用于通过经典后处理来估计M。受控Grover迭代的目的是增加概率p1。该算法在量子电路的宽度和深度方面需要更少的量子资源，产生对M的更准确的估计，并且当比率M/N小时，运行速度明显快于基于相位估计的量子计数算法。通过模拟不同M/N比的情况，如M/N > 0.125或M/N < 0.001，我们比较了两种量子计数算法。
A simpler quantum counting algorithm based on amplitude amplification is presented. This algorithm is bounded by O(sqrt(N/M)) calls to the controlled-Grover operator where M is the number of marked states and N is the total number of states in the search space. This algorithm terminates within log(sqrt(N/M)) consecutive measurement steps when the probability p1 of measuring the state |1> is at least 0.5, and the result from the final step is used in estimating M by a classical post processing. The purpose of controlled-Grover iteration is to increase the probability p1. This algorithm requires less quantum resources in terms of the width and depth of the quantum circuit, produces a more accurate estimate of M, and runs significantly faster than the phase estimation-based quantum counting algorithm when the ratio M/N is small. We compare the two quantum counting algorithms by simulating various cases with a different M/N ratio, such as M/N > 0.125 or M/N < 0.001.