论文标题
单个标记顶点图中基于量子步行的搜索算法的改进
Improvement of quantum walk-based search algorithms in single marked vertex graphs
论文作者
论文摘要
量子步行是用于构建量子搜索算法或量子采样算法的强大工具，称为量子固定状态的构造。 但是，这些算法的成功概率都远离1。振幅扩增通常用于扩大成功概率，但蛋soufflé问题随之而来。只有在正确的步骤停止，我们才能达到最大成功概率。否则，随着步骤数的增加，成功概率可能会降低，当未知的最佳步骤数时，将在算法的实际应用中引起麻烦。 在这项工作中，我们定义了广义的插值量子步行，这既可以提高搜索算法的成功概率，又可以避免蛋奶酥问题。 然后，我们将广义的插值量子步行与量子快进。两者的组合都将搜索算法的呼叫步行操作员的时间从$θ（（（\ varepsilon^{ - 1}）\ sqrt {\ heg}）$降低到$θ（\ log（\ varepsilon^{ - 1}}） $θ（\ log（\ varepsilon^{ - 1}）+\ log \ sqrt {\ heg}）$ to $θ（\ log log \ log \ log \ log \ varepsilon^{ - 1} { - 1}）+\ log \ \ \ \ \ \ \ sqrt {\ heg} $ \ varepsilon $表示精度，$ \ heg $表示经典的打击时间。 此外，我们表明我们的广义插值量子步道可用于改善与固定分布相对应的量子状态的构造。 最后，我们提供了一个应用程序，该应用可用于通过应用通用的插值量子步道来构建缓慢发展的马尔可夫链序列，这是绝热固定态制备中必要的前提。
Quantum walks are powerful tools for building quantum search algorithms or quantum sampling algorithms named the construction of quantum stationary state. However, the success probability of those algorithms are all far away from 1. Amplitude amplification is usually used to amplify success probability, but the soufflé problems follow. Only stop at the right step can we achieve a maximum success probability. Otherwise, as the number of steps increases, the success probability may decrease, which will cause troubles in practical application of the algorithm when the optimal number of steps is not known. In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the soufflé problems. Then we combine generalized interpolation quantum walks with quantum fast-forwarding. The combination both reduce the times of calling walk operator of searching algorithm from $Θ((\varepsilon^{-1})\sqrt{\Heg})$ to $Θ(\log(\varepsilon^{-1})\sqrt{\Heg})$ and reduces the number of ancilla qubits required from $Θ(\log(\varepsilon^{-1})+\log\sqrt{\Heg})$ to $Θ(\log\log(\varepsilon^{-1})+\log\sqrt{\Heg})$, and the souffle problem is avoided while the success probability is improved, where $\varepsilon$ denotes the precision and $\Heg$ denotes the classical hitting time. Besides, we show that our generalized interpolated quantum walks can be used to improve the construction of quantum states corresponding to stationary distributions as well. Finally, we give an application that can be used to construct a slowly evolving Markov chain sequence by applying generalized interpolated quantum walks, which is the necessary premise in adiabatic stationary state preparation.
