论文标题
可逆的马尔可夫链的空间效率量化方法
Space-efficient Quantization Method for Reversible Markov Chains
论文作者
论文摘要
在一份开创性的论文中，Szegedy展示了如何为任何可逆的马尔可夫链$ p $构建量子步行$ W（p）$，以使其具有本征性的特征向量$ 0 $是随机步行的限制分布及其特征过相差距的量子样本，其特征性差距比$ p $ $ p $的频谱差异很大。 Szegedy量子步行的标准结构需要希尔伯特空间维度的Ancilla登记册，等于马尔可夫链的状态空间的大小。我们表明，有可能避免使用对称提案概率的某些马尔可夫链的状态空间加倍，并随后接受/拒绝从Gibbs分布中采样的概率。对于这样的马尔可夫链，我们提供了一种量化方法，该方法需要一个尺寸的Ancilla寄存器等于不同能量值的数量，该数值通常明显小于状态空间的大小。为了实现这一目标，我们开发了一种用于块编码Hadamard矩阵产品的技术，这可能引起更广泛的兴趣。
In a seminal paper, Szegedy showed how to construct a quantum walk $W(P)$ for any reversible Markov chain $P$ such that its eigenvector with eigenphase $0$ is a quantum sample of the limiting distribution of the random walk and its eigenphase gap is quadratically larger than the spectral gap of $P$. The standard construction of Szegedy's quantum walk requires an ancilla register of Hilbert-space dimension equal to the size of the state space of the Markov chain. We show that it is possible to avoid this doubling of state space for certain Markov chains that employ a symmetric proposal probability and a subsequent accept/reject probability to sample from the Gibbs distribution. For such Markov chains, we give a quantization method which requires an ancilla register of dimension equal to only the number of different energy values, which is often significantly smaller than the size of the state space. To accomplish this, we develop a technique for block encoding Hadamard products of matrices which may be of wider interest.
