论文标题
混合量子古典搜索算法
Hybrid Quantum-Classical Search Algorithms
论文作者
论文摘要
搜索是量子算法设计中最常用的原始图之一。众所周知，格罗弗（Grover）算法提供的二次加速度是最佳的，并且不存在更快的量子算法。众所周知，至少需要一些量子计算来实现这些加速，但现有界限并不排除大多数计算都是经典的同样快速混合量子量子算法的可能性。在这项工作中，我们研究了这种混合算法，我们表明经典计算本身可以解决搜索问题，不能帮助量子计算。此外，我们将此结果推广到具有子结构成功概率的算法。
Search is one of the most commonly used primitives in quantum algorithm design. It is known that quadratic speedups provided by Grover's algorithm are optimal, and no faster quantum algorithms for Search exist. While it is known that at least some quantum computation is required to achieve these speedups, the existing bounds do not rule out the possibility of an equally fast hybrid quantum-classical algorithm where most of the computation is classical. In this work, we study such hybrid algorithms and we show that classical computation, unless it by itself can solve the Search problem, cannot assist quantum computation. In addition, we generalize this result to algorithms with subconstant success probabilities.
