机构名称：
¥ 2.0
所谓的焊接树问题是黑箱问题的一个例子，量子行走可以比任何经典算法 [3] 更快地解决该问题。给定一个特殊入口顶点的名称，量子行走可以使用多项式次数的查询找到另一个独特的出口顶点，尽管找不到从入口到出口的任何特定路径。二十年来，是否存在有效的量子算法来寻找这样的路径，或者路径寻找问题即使对于量子计算机来说是否也很难，这一直是一个悬而未决的问题。我们表明，一类自然的高效量子算法可以证明无法找到从入口到出口的路径。具体而言，我们考虑在算法叠加的每个分支中始终存储一组顶点标签，这些标签形成包含入口的连通子图，并且仅将这些顶点标签作为 oracle 的输入。虽然这并不排除量子算法能够有效找到路径的可能性，但尚不清楚算法如何通过偏离这种行为而受益。我们的无效结果表明，对于某些问题，量子算法必须忘记它们采取的解决问题的路径，才能胜过经典计算。
量子算法和遗忘的力量 - DROPS
主要关键词
相关文件推荐
