Time-Efficient Quantum Walks for 3-Distinctness
Time-Efficient Quantum Walks for 3-Distinctness
复制标题
高效的量子行走实现 3 区别
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
F. Magniez
中科院分区：
文献类型：
--
作者：
Aleksandrs Belovs;Andrew M. Childs;S. Jeffery;Robin Kothari;F. Magniez
我们提出了两种用于 3-Distinctness 的量子行走算法。两种算法都具有时间复杂度 $\tilde{O}(n^{5/7})$，改进了之前的 $\tilde{O}(n^{3/4})$ 并将已知的查询复杂度上限（通过学习图获得）匹配到对数因子。第一个算法基于量子行走和电网之间的连接。第二种算法使用量子行走搜索框架的扩展，该框架有助于通过嵌套更新进行量子行走。
We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.