论文标题
量子算法和忘记的力量
Quantum algorithms and the power of forgetting
论文作者
论文摘要
所谓的焊接树问题提供了一个黑盒问题的示例，该示例可以通过量子步行速度更快地求解，而量子步行比通过任何经典算法更快地求解。鉴于特殊入口顶点的名称，量子步行可以使用多个问题上的许多查询找到另一个区别的出口顶点，尽管没有找到从入口到退出的任何特定路径。二十年来，这是一个空旷的问题，无论是否有有效的量子算法来找到这样的路径，还是对于量子计算机而言，连接问题也很难。我们表明，一种自然的有效量子算法证明无法找到从入口到退出的路径。具体来说，我们考虑算法，这些算法在其叠加的每个分支中始终存储一组顶点标签，这些标签形成包括入口在内的连接子图，并且仅提供这些顶点标签作为Oracle的输入。尽管这并不排除有效找到路径的量子算法的可能性，但尚不清楚算法如何通过偏离这种行为而受益。我们的无关结果表明，对于某些问题，量子算法必须忘记他们到达解决方案以超越经典计算的道路。
The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find another distinguished EXIT vertex using polynomially many queries, though without finding any particular path from ENTRANCE to EXIT. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the ENTRANCE, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation.
