论文标题
用于量子幅度估计的自适应算法
Adaptive Algorithm for Quantum Amplitude Estimation
论文作者
论文摘要
量子振幅估计是具有各种应用的许多量子算法的关键子仪。我们提出了一种自适应算法，用于振幅间隔估计。该算法的量子部分仅基于Grover的算法。关键成分是引入调整因子，该因素可以调整良好状态的幅度，以便可以在随后的步骤中估算调整后的振幅和原始振幅。我们通过数值研究表明，与最先进的算法相比，所提出的算法使用相似数量的量子查询来达到相同水平的精度$ε$，但是经典部分，即非量化部分，具有较低的计算复杂性。我们严格地证明，Oracle查询的数量可实现$ O（1/ε）$，即经典蒙特卡洛采样的二次加速度，经典部分的计算复杂性可实现$ o（\ log（1/ε））$，都可以达到双重元素。
Quantum amplitude estimation is a key sub-routine of a number of quantum algorithms with various applications. We propose an adaptive algorithm for interval estimation of amplitudes. The quantum part of the algorithm is based only on Grover's algorithm. The key ingredient is the introduction of an adjustment factor, which adjusts the amplitude of good states such that the amplitude after the adjustment, and the original amplitude, can be estimated without ambiguity in the subsequent step. We show with numerical studies that the proposed algorithm uses a similar number of quantum queries to achieve the same level of precision $ε$ compared to state-of-the-art algorithms, but the classical part, i.e., the non-quantum part, has substantially lower computational complexity. We rigorously prove that the number of oracle queries achieves $O(1/ε)$, i.e., a quadratic speedup over classical Monte Carlo sampling, and the computational complexity of the classical part achieves $O(\log(1/ε))$, both up to a double-logarithmic factor.
