论文标题
使用多层次方法启用马尔可夫链的量子加速
Enabling Quantum Speedup of Markov Chains using a Multi-level Approach
论文作者
论文摘要
基于缓慢变化的$ r $ R $ Markov链的构建，可以轻松制备初始链，并且光谱间隙具有均匀的下限，可以实现用于混合Markov链的量子加速。总体复杂性与$ r $成正比。我们提出了一种多级方法，可以通过改变分辨率参数$h。$来构建$ R $ Markov链的序列，我们表明，低分辨率马尔可夫链的密度函数可用于温暖以高分辨率的启动马尔可夫链。我们证明，就链长而言，新算法具有$ o（1）$复杂性，而不是$ o（r）。
Quantum speedup for mixing a Markov chain can be achieved based on the construction of slowly-varying $r$ Markov chains where the initial chain can be easily prepared and the spectral gaps have uniform lower bound. The overall complexity is proportional to $r$. We present a multi-level approach to construct such a sequence of $r$ Markov chains by varying a resolution parameter $h.$ We show that the density function of a low-resolution Markov chain can be used to warm start the Markov chain with high resolution. We prove that in terms of the chain length the new algorithm has $O(1)$ complexity rather than $O(r).$
