Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions
Adaptive Quantum Simulated Annealing for Bayesian Inference and Estimating Partition Functions
复制标题
用于贝叶斯推理和估计配分函数的自适应量子模拟退火
DOI：
10.1137/1.9781611975994.12
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Wei, A
中科院分区：
文献类型：
--
作者：
Harrow, Aram W.;Wei, A
马尔可夫链蒙特卡罗算法在计数问题和机器学习问题中具有重要的应用，这些问题涉及估计难以精确计算的数量。量子计算机可以将经典马尔可夫链算法加速多少？在这项工作中，我们考虑加速模拟退火算法的问题，其中马尔可夫链的平稳分布是根据退火计划指定的温度下的吉布斯分布。我们构建了一种量子算法，可以在每个温度下自适应地构建退火计划和量子样本。我们的自适应退火计划大致与最佳经典自适应退火计划的长度相匹配，并且对非自适应温度计划进行了大约二次因子的改进。我们对马尔可夫链间隙的依赖与其他量子算法相匹配，并且比经典马尔可夫链所实现的要好得多。我们的算法是第一个结合这两种二次改进的算法。与其他量子行走算法一样，它还通过生成“qsamples”而不是经典样本来改进经典算法。这意味着准备振幅为目标概率分布的平方根的量子态。在构建退火方案时，我们利用振幅估计，并且我们引入了一种几乎无需额外成本即可进行无损振幅估计的方法，这一结果可能具有独立的意义。最后，我们演示了如何将这种量子模拟退火算法应用于估计配分函数和贝叶斯推理的问题。
Markov chain Monte Carlo algorithms have important applications in counting problems and in machine learning problems, settings that involve estimating quantities that are difficult to compute exactly. How much can quantum computers speed up classical Markov chain algorithms? In this work we consider the problem of speeding up simulated annealing algorithms, where the stationary distributions of the Markov chains are Gibbs distributions at temperatures specified according to an annealing schedule.We construct a quantum algorithm that both adaptively constructs an annealing schedule and quantum samples at each temperature. Our adaptive annealing schedule roughly matches the length of the best classical adaptive annealing schedules and improves on nonadaptive temperature schedules by roughly a quadratic factor. Our dependence on the Markov chain gap matches other quantum algorithms and is quadratically better than what classical Markov chains achieve. Our algorithm is the first to combine both of these quadratic improvements. Like other quantum walk algorithms, it also improves on classical algorithms by producing “qsamples” instead of classical samples. This means preparing quantum states whose amplitudes are the square roots of the target probability distribution.In constructing the annealing schedule we make use of amplitude estimation, and we introduce a method for making amplitude estimation nondestructive at almost no additional cost, a result that may have independent interest. Finally we demonstrate how this quantum simulated annealing algorithm can be applied to the problems of estimating partition functions and Bayesian inference.
用于生成任意量子态的量子网络
DOI：
--
发表时间：
2001
期刊：
Optical Fiber Communications Conference and Exhibition
影响因子：
--
作者：
Phillip Kaye;M. Mosca
通讯作者：
M. Mosca
降低量子 Merlin-Arthur 证明系统的错误概率
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
井上雅隆;Sunmin KIM;萬和明;立川康人;椎葉充晴;野口賢二・諏訪義雄;Harumichi Nishimura
通讯作者：
Harumichi Nishimura