Markov chain Monte Carlo enhanced variational quantum algorithms
Markov chain Monte Carlo enhanced variational quantum algorithms
复制标题
马尔可夫链蒙特卡罗增强变分量子算法
DOI：
10.1088/2058-9565/aca821
复制
发表时间：
2022
影响因子：
6.7
通讯作者：
Yelin, Susanne F
中科院分区：
文献类型：
--
作者：
Patti, Taylor L;Shehab, Omar;Najafi, Khadijeh;Yelin, Susanne F
变分量子算法在经典组合学、量子化学和凝聚态物质中的应用，可能对高维优化产生重大影响。然而，这些算法的优化环境通常是非凸的，导致算法收敛到局部最小值，而不是全局最小值，并产生次优解。在这项工作中，我们介绍了一种变分量子算法，它将经典的马尔可夫链蒙特卡罗技术与变分量子算法结合起来，使前者可证明地收敛到全局最小点，从而保证解的质量。由于我们方法的通用性，它适用于无数的量子最小化问题，包括优化和量子态准备。具体地说，我们设计了一种适用于变分量子器件的Metropolis-Hastings方法，并将其与量子优化结合起来，构造出收敛到Gibbs态的量子系综。这些性能保证源于算法状态空间的遍历性，并使我们能够对其时间复杂性进行分析。我们通过对MaxCut实例的量子电路模拟，以及高达50个量子比特的大规模量子伊辛和横场自旋模型，以确定性和完美的精度证明了我们技术的有效性和分析的有效性。我们的技术将广泛丰富变分量子算法的领域，改进和保证这些有希望但往往是启发式的方法的性能。
Variational quantum algorithms have the potential for significant impact on high-dimensional optimization, with applications in classical combinatorics, quantum chemistry, and condensed matter. Nevertheless, the optimization landscape of these algorithms is generally nonconvex, leading the algorithms to converge to local, rather than global, minima and the production of suboptimal solutions. In this work, we introduce a variational quantum algorithm that couples classical Markov chain Monte Carlo techniques with variational quantum algorithms, allowing the former to provably converge to global minima and thus assure solution quality. Due to the generality of our approach, it is suitable for a myriad of quantum minimization problems, including optimization and quantum state preparation. Specifically, we devise a Metropolis–Hastings method that is suitable for variational quantum devices and use it, in conjunction with quantum optimization, to construct quantum ensembles that converge to Gibbs states. These performance guarantees are derived from the ergodicity of our algorithm's state space and enable us to place analytic bounds on its time-complexity. We demonstrate both the effectiveness of our technique and the validity of our analysis through quantum circuit simulations for MaxCut instances, solving these problems deterministically and with perfect accuracy, as well as large-scale quantum Ising and transverse field spin models of up to 50 qubits. Our technique stands to broadly enrich the field of variational quantum algorithms, improving and guaranteeing the performance of these promising, yet often heuristic, methods.
登录
查看更多内容
DOI：
10.1002/9781118445112.stat07834
发表时间：
2015-04
期刊：
Proceedings of the 38th Annual Hawaii International Conference on System Sciences
影响因子：
--
作者：
C. Robert
通讯作者：
C. Robert
Metropolis-Hastings 算法的高效量子行走电路
影响因子：
6.4
作者：
J. Lemieux;B. Heim;D. Poulin;K. Svore;M. Troyer
通讯作者：
M. Troyer
关于最大割问题
DOI：
--
发表时间：
2006
期刊：
Algorithms and Complexity in Durham
影响因子：
--
作者：
W. Ben
通讯作者：
W. Ben
一种制备量子吉布斯态的变分量子算法
DOI：
--
发表时间：
2020
期刊：
影响因子：
--
作者：
Anirban Narayan Chowdhury;G. Low;N. Wiebe
通讯作者：
N. Wiebe
DOI：
10.1103/physrevapplied.16.054035
发表时间：
2020-05
期刊：
ArXiv
影响因子：
--
作者：
Youle Wang;Guangxi Li;Xin Wang
通讯作者：
Youle Wang;Guangxi Li;Xin Wang