论文标题
关于一般量子马尔可夫过程的打击时间
On Hitting Times for General Quantum Markov Processes
论文作者
论文摘要
随机步行（或马尔可夫连锁店）是在理论计算机科学中广泛使用的模型。几种工具，包括分析诸如打击和混合时间之类的数量，有助于设计随机算法。一个值得注意的例子是Schönne的算法（SAT）问题。在这项工作中，我们使用密度 - 矩阵形式主义来定义一个量子马尔可夫链模型，该模型直接概括了古典步行，并且我们表明，可以使用与经典理论中的类似公式计算出的常见工具（如打击时间），然后我们将其应用于已知的量子设置，例如Grover的Algorithm's Algorithm。
Random walks (or Markov chains) are models extensively used in theoretical computer science. Several tools, including analysis of quantities such as hitting and mixing times, are helpful for devising randomized algorithms. A notable example is Schöning's algorithm for the satisfiability (SAT) problem. In this work, we use the density-matrix formalism to define a quantum Markov chain model which directly generalizes classical walks, and we show that a common tools such as hitting times can be computed with a similar formula as the one found in the classical theory, which we then apply to known quantum settings such as Grover's algorithm.
