Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm
复制标题
Metropolis-Hastings 算法的高效量子行走电路
DOI：
10.22331/q-2020-06-29-287
复制
发表时间：
2019
期刊：
影响因子：
6.4
通讯作者：
M. Troyer
中科院分区：
文献类型：
--
作者：
J. Lemieux;B. Heim;D. Poulin;K. Svore;M. Troyer
我们提出了一个详细的电路实现Szegedy的量化的Metropolis-Hastings步行。这种量子行走通常是相对于预言机来定义的。我们发现，直接实现这个预言需要昂贵的算术运算。因此，我们重新制定的量子漫步，绕过其实施完全遵循经典的大都会黑斯廷斯步行。我们还提出了启发式量子算法，在离散优化问题的背景下使用量子行走，并数值研究其性能。我们的数值结果表明多项式量子加速启发式设置。
We present a detailed circuit implementation of Szegedy's quantization of the Metropolis-Hastings walk. This quantum walk is usually defined with respect to an oracle. We find that a direct implementation of this oracle requires costly arithmetic operations. We thus reformulate the quantum walk, circumventing its implementation altogether by closely following the classical Metropolis-Hastings walk. We also present heuristic quantum algorithms that use the quantum walk in the context of discrete optimization problems and numerically study their performances. Our numerical results indicate polynomial quantum speedups in heuristic settings.