标题： 振幅放大和估计需要逆运算 显示英文标题

标题： Amplitude amplification and estimation require inverses

摘要： 我们证明，对于暴力搜索和计数的通用量子加速仅在我们对其应用的过程可以被高效逆时的情况下成立。 加速这些问题的算法，幅度放大和幅度估计，假设能够应用状态制备酉变换$U$及其逆变换$U^\dagger$; 我们基于迹估计给出了问题实例，其中没有任何仅使用$U$的算法能超越朴素的二次更慢的方法。 我们对此的证明很简单，通过了由Zhandry引入的压缩预言机方法。 由于这两个子例程负责量子算法中二次“Grover”加速的普遍性，我们的结果解释了为什么在量子学习、计量学和传感的设置中，这种加速要难得多。 在这些设置中， $U$模型实验系统的演化，因此实现$U^\dagger$可以更加困难——相当于在系统内逆转时间。 我们的结果表明一种二分法：没有逆访问，量子加速是稀少的；而有了它，量子加速则丰富。 显示英文摘要

摘要： We prove that the generic quantum speedups for brute-force search and counting only hold when the process we apply them to can be efficiently inverted. The algorithms speeding up these problems, amplitude amplification and amplitude estimation, assume the ability to apply a state preparation unitary $U$ and its inverse $U^\dagger$; we give problem instances based on trace estimation where no algorithm which uses only $U$ beats the naive, quadratically slower approach. Our proof of this is simple and goes through the compressed oracle method introduced by Zhandry. Since these two subroutines are responsible for the ubiquity of the quadratic "Grover" speedup in quantum algorithms, our result explains why such speedups are far harder to come by in the settings of quantum learning, metrology, and sensing. In these settings, $U$ models the evolution of an experimental system, so implementing $U^\dagger$ can be much harder -- tantamount to reversing time within the system. Our result suggests a dichotomy: without inverse access, quantum speedups are scarce; with it, quantum speedups abound.