论文标题
多维量子步行，应用于$ k $ stristness
Multidimensional Quantum Walks, with Application to $k$-Distinctness
论文作者
论文摘要
对于任何常量的$ k \ geq 4 $，$ k $ distinctence的量子查询复杂性的$ k $ distinctence是$ o \ weft（n^{3/4-1/4（2^k-1）} \ right）$ $，而$ k \ geq 4 $，$ k \ geq 4 $，是时间复杂性上最佳的上限是$ \ widetilde {o} {o} \ weft（n^of（n^n^^{1-1-1-1/k}）。我们在时间复杂性上给出了$ \ widetilde {o} \ left（n^{3/4-1/4（2^k-1）} \ right）$的新上限（n^{3/4-1/4（2^k-1）}。为了实现这一上限，我们提供了一种设计量子步行搜索算法的新技术，该算法是电动网络框架的扩展。我们还展示了如何在$ o（n）$ Queries和$ o（n^2）$使用此新技术中解决焊接的树问题，这表明新的量子步行框架可以实现指数加速。
While the quantum query complexity of $k$-distinctness is known to be $O\left(n^{3/4-1/4(2^k-1)}\right)$ for any constant $k \geq 4$, the best previous upper bound on the time complexity was $\widetilde{O}\left(n^{1-1/k}\right)$. We give a new upper bound of $\widetilde{O}\left(n^{3/4-1/4(2^k-1)}\right)$ on the time complexity, matching the query complexity up to polylogarithmic factors. In order to achieve this upper bound, we give a new technique for designing quantum walk search algorithms, which is an extension of the electric network framework. We also show how to solve the welded trees problem in $O(n)$ queries and $O(n^2)$ time using this new technique, showing that the new quantum walk framework can achieve exponential speedups.
