论文标题
量子步行中的平均混合可逆马尔可夫连锁店
Average Mixing in Quantum Walks of Reversible Markov Chains
论文作者
论文摘要
Szegedy量子步行是一个离散的时间量子步行模型，它定义了任何马尔可夫链的量子类似物。量子步行的长期行为可以用称为平均混合矩阵的矩阵编码，其列给定初始状态的行走的限制概率分布。我们定义了Szegedy量子步行的平均混合矩阵的一个版本，该版本使我们能够更容易地将限制行为与量化的链条的行为进行比较。我们证明了Markov链的光谱分解的混合矩阵的公式，并显示了与链上连续量子行走的混合矩阵的关系。特别是，我们证明连续步行中的平均均匀混合意味着在Szegedy Walk中平均均匀混合。最后，我们通过给出任意大尺寸的马尔可夫链的例子，这些链条在连续和szegedy量子步行中接受平均均匀混合。
The Szegedy quantum walk is a discrete time quantum walk model which defines a quantum analogue of any Markov chain. The long-term behavior of the quantum walk can be encoded in a matrix called the average mixing matrix, whose columns give the limiting probability distribution of the walk given an initial state. We define a version of the average mixing matrix of the Szegedy quantum walk which allows us to more readily compare the limiting behavior to that of the chain it quantizes. We prove a formula for our mixing matrix in terms of the spectral decomposition of the Markov chain and show a relationship with the mixing matrix of a continuous quantum walk on the chain. In particular, we prove that average uniform mixing in the continuous walk implies average uniform mixing in the Szegedy walk. We conclude by giving examples of Markov chains of arbitrarily large size which admit average uniform mixing in both the continuous and Szegedy quantum walk.
