1Center for Quantum Information and Control, University of New Mexico
2Center for Theoretical Physics, Massachusetts Institute of Technology
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
Path integral quantum Monte Carlo (PIMC) is a method for estimating thermal equilibrium properties of stoquastic quantum spin systems by sampling from a classical Gibbs distribution using Markov chain Monte Carlo. The PIMC method has been widely used to study the physics of materials and for simulated quantum annealing, but these successful applications are rarely accompanied by formal proofs that the Markov chains underlying PIMC rapidly converge to the desired equilibrium distribution.
In this work we analyze the mixing time of PIMC for 1D stoquastic Hamiltonians, including disordered transverse Ising models (TIM) with long-range algebraically decaying interactions as well as disordered XY spin chains with nearest-neighbor interactions. By bounding the convergence time to the equilibrium distribution we rigorously justify the use of PIMC to approximate partition functions and expectations of observables for these models at inverse temperatures that scale at most logarithmically with the number of qubits.
The mixing time analysis is based on the canonical paths method applied to the single-site Metropolis Markov chain for the Gibbs distribution of 2D classical spin models with couplings related to the interactions in the quantum Hamiltonian. Since the system has strongly nonisotropic couplings that grow with system size, it does not fall into the known cases where 2D classical spin models are known to mix rapidly.
► BibTeX data
► References
[1] Tameem Albash and Daniel A. Lidar. Adiabatic quantum computation. Rev. Mod. Phys., 90: 015002, Jan 2018. 10.1103/RevModPhys.90.015002.
https://doi.org/10.1103/RevModPhys.90.015002
[2] Tameem Albash, Gene Wagenbreth, and Itay Hen. Off-diagonal expansion quantum monte carlo. Physical Review E, 96 (6): 063309, 2017. 10.1103/PhysRevE.96.063309.
https://doi.org/10.1103/PhysRevE.96.063309
[3] Evgeny Andriyash and Mohammad H Amin. Can quantum Monte Carlo simulate quantum annealing?, 2017, arXiv:1703.09277.
arXiv:1703.09277
[4] Itai Arad, Zeph Landau, Umesh Vazirani, and Thomas Vidick. Rigorous RG algorithms and area laws for low energy eigenstates in 1D. Communications in Mathematical Physics, 356 (1): 65–105, 2017. 10.1007/s00220-017-2973-z.
https://doi.org/10.1007/s00220-017-2973-z
[5] Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, and Eric Vigoda. Accelerating simulated annealing for the permanent and combinatorial counting problems. SIAM Journal on Computing, 37 (5): 1429–1454, 2008. 10.1137/050644033.
https://doi.org/10.1137/050644033
[6] Lucas T Brady and Wim van Dam. Quantum Monte Carlo simulations of tunneling in quantum adiabatic optimization. Physical Review A, 93 (3): 032304, 2016a, arXiv:1509.02562. 10.1103/PhysRevA.93.032304.
https://doi.org/10.1103/PhysRevA.93.032304
arXiv:1509.02562
[7] Lucas T Brady and Wim van Dam. Spectral-gap analysis for efficient tunneling in quantum adiabatic optimization. Physical Review A, 94 (3): 032309, 2016b, arXiv:1601.01720. 10.1103/PhysRevA.94.032309.
https://doi.org/10.1103/PhysRevA.94.032309
arXiv:1601.01720
[8] Sergey Bravyi. Monte Carlo simulation of stoquastic Hamiltonians. Quantum Information & Computation, 15 (13-14): 1122–1140, 2015, arXiv:1402.2295. 10.5555/2871363.2871366.
https://doi.org/10.5555/2871363.2871366
arXiv:1402.2295
[9] Sergey Bravyi and David Gosset. Polynomial-time classical simulation of quantum ferromagnets. Physical review letters, 119 (10): 100503, 2017, arXiv:1612.05602. 10.1103/PhysRevLett.119.100503.
https://doi.org/10.1103/PhysRevLett.119.100503
arXiv:1612.05602
[10] Sergey Bravyi and Matthew Hastings. On complexity of the quantum Ising model. Communications in Mathematical Physics, 349 (1): 1–45, 2017, arXiv:1410.0703. 10.1007/s00220-016-2787-4.
https://doi.org/10.1007/s00220-016-2787-4
arXiv:1410.0703
[11] Sergey Bravyi and Barbara M. Terhal. Complexity of stoquastic frustration-free Hamiltonians. SIAM J. Comput., 39 (4): 1462–1485, 2009, arXiv:0806.1746. 10.1137/08072689X.
https://doi.org/10.1137/08072689X
arXiv:0806.1746
[12] Sergey Bravyi, David P. DiVincenzo, Roberto I. Oliveira, and Barbara M. Terhal. The complexity of stoquastic local Hamiltonian problems. Quant. Inf. Comp., 8 (5): 0361–0385, 2006, arXiv:quant-ph/0606140. 10.5555/2011772.2011773.
https://doi.org/10.5555/2011772.2011773
arXiv:quant-ph/0606140
[13] Jacob Bringewatt, William Dorland, Stephen P. Jordan, and Alan Mink. Diffusion monte carlo approach versus adiabatic computation for local hamiltonians. Phys. Rev. A, 97: 022323, Feb 2018. 10.1103/PhysRevA.97.022323.
https://doi.org/10.1103/PhysRevA.97.022323
[14] Alessandra Cipriani and Paolo Dai Pra. Decay of correlations for quantum spin systems with a transverse field: A dynamic approach, 2010, arXiv:1005.3547.
arXiv:1005.3547
[15] Elizabeth Crosson and Aram W Harrow. Simulated quantum annealing can be exponentially faster than classical simulated annealing. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 714–723. IEEE, 2016, arXiv:1601.03030. 10.1109/FOCS.2016.81.
https://doi.org/10.1109/FOCS.2016.81
arXiv:1601.03030
[16] Elizabeth Crosson, Edward Farhi, Cedric Yen-Yu Lin, Han-Hsuan Lin, and Peter Shor. Different strategies for optimization using the quantum adiabatic algorithm, 2014, arXiv:1401.7320.
arXiv:1401.7320
[17] Toby S. Cubitt, Ashley Montanaro, and Stephen Piddock. Universal quantum hamiltonians. Proceedings of the National Academy of Sciences, 115 (38): 9497–9502, 2018, arXiv:1701.05182. ISSN 0027-8424. 10.1073/pnas.1804949115. URL https://www.pnas.org/content/115/38/9497.
https://doi.org/10.1073/pnas.1804949115
arXiv:1701.05182
https://www.pnas.org/content/115/38/9497
[18] Ky Fan. Maximum properties and inequalities for the eigenvalues of completely continuous operators. Proceedings of the National Academy of Sciences, 37 (11): 760–766, 1951. ISSN 0027-8424. 10.1073/pnas.37.11.760.
https://doi.org/10.1073/pnas.37.11.760
[19] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science, 292 (5516): 472–475, 2001. 10.1126/science.1057726.
https://doi.org/10.1126/science.1057726
[20] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. Quantum adiabatic evolution algorithms versus simulated annealing, 2002, arXiv:quant-ph/0201031.
arXiv:quant-ph/0201031
[21] WMC Foulkes, L Mitas, RJ Needs, and G Rajagopal. Quantum monte carlo simulations of solids. Reviews of Modern Physics, 73 (1): 33, 2001. 10.1103/RevModPhys.73.33.
https://doi.org/10.1103/RevModPhys.73.33
[22] M. B. Hastings. Quantum adiabatic computation with a constant gap is not useful in one dimension. Phys. Rev. Lett., 103: 050502, 2009, arXiv:0902.2960. 10.1103/PhysRevLett.103.050502.
https://doi.org/10.1103/PhysRevLett.103.050502
arXiv:0902.2960
[23] Matthew B Hastings and MH Freedman. Obstructions to classically simulating the quantum adiabatic algorithm. Quantum Information & Computation, 13 (11-12): 1038–1076, 2013, arXiv:1302.5733. 10.5555/2535639.2535647.
https://doi.org/10.5555/2535639.2535647
arXiv:1302.5733
[24] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58 (301): 13–30, 1963. 10.1080/01621459.1963.10500830.
https://doi.org/10.1080/01621459.1963.10500830
[25] Layla Hormozi, Ethan W. Brown, Giuseppe Carleo, and Matthias Troyer. Nonstoquastic hamiltonians and quantum annealing of an ising spin glass. Phys. Rev. B, 95: 184416, May 2017. 10.1103/PhysRevB.95.184416.
https://doi.org/10.1103/PhysRevB.95.184416
[26] Michael Jarret and Brad Lackey. Substochastic Monte Carlo algorithms, 2017, arXiv:1704.09014.
arXiv:1704.09014
[27] Michael Jarret, Stephen P Jordan, and Brad Lackey. Adiabatic optimization versus diffusion monte carlo methods. Physical Review A, 94 (4), 2016, arXiv:1607.03389. 10.1103/PhysRevA.94.042318.
https://doi.org/10.1103/PhysRevA.94.042318
arXiv:1607.03389
[28] Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM Journal on Computing, 22: 1087–1116, 1993. 10.1137/0222066.
https://doi.org/10.1137/0222066
[29] Mark Jerrum and Alistair Sinclair. The Markov chain Monte Carlo method: An approach to approximate counting and integration. In Dorit S. Hochbaum, editor, Approximation Algorithms for NP-hard Problems, pages 482–520. PWS Publishing Co., Boston, MA, USA, 1997. ISBN 0-534-94968-1. 10.5555/241938.241950.
https://doi.org/10.5555/241938.241950
[30] Zhang Jiang, Vadim N Smelyanskiy, Sergei V Isakov, Sergio Boixo, Guglielmo Mazzola, Matthias Troyer, and Hartmut Neven. Scaling analysis and instantons for thermally assisted tunneling and quantum Monte Carlo simulations. Physical Review A, 95 (1): 012322, 2017, arXiv:1603.01293. 10.1103/PhysRevA.95.012322.
https://doi.org/10.1103/PhysRevA.95.012322
arXiv:1603.01293
[31] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse Ising model. Phys. Rev. E, 58: 5355–5363, Nov 1998, arXiv:cond-mat/9804280. 10.1103/PhysRevE.58.5355.
https://doi.org/10.1103/PhysRevE.58.5355
arXiv:cond-mat/9804280
[32] Linghang Kong and Elizabeth Crosson. The performance of the quantum adiabatic algorithm on spike Hamiltonians. Int. J. Quantum Inform., 15 (1750011), 2015, arXiv:1511.06991. 10.1142/S0219749917500113.
https://doi.org/10.1142/S0219749917500113
arXiv:1511.06991
[33] Zeph Landau, Umesh Vazirani, and Thomas Vidick. A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians. Nature Physics, 2013, arXiv:1307.5143. 10.1038/nphys3345.
https://doi.org/10.1038/nphys3345
arXiv:1307.5143
[34] D.A. Levin, Y. Peres, and E.L. Wilmer. Markov Chains and Mixing Times. American Mathematical Soc., 2008. ISBN 9780821886274. 10.1090/mbk/107.
https://doi.org/10.1090/mbk/107
[35] Fabio Martinelli and Marc Wouts. Glauber dynamics for the quantum Ising model in a transverse field on a regular tree. Journal of Statistical Physics, 146 (5): 1059–1088, 2012, arXiv:1105.5970. 10.1007/s10955-012-0436-7.
https://doi.org/10.1007/s10955-012-0436-7
arXiv:1105.5970
[36] Roman Martonák, Giuseppe E. Santoro, and Erio Tosatti. Quantum annealing by the path-integral monte carlo method: The two-dimensional random ising model. Phys. Rev. B, 66: 094203, Sep 2002. 10.1103/PhysRevB.66.094203.
https://doi.org/10.1103/PhysRevB.66.094203
[37] Siddharth Muthukrishnan, Tameem Albash, and Daniel A Lidar. Tunneling and speedup in quantum optimization for permutation-symmetric problems. Physical Review X, 6 (3): 031010, 2016. 10.1103/PhysRevX.6.031010.
https://doi.org/10.1103/PhysRevX.6.031010
[38] Ben W Reichardt. The quantum adiabatic optimization algorithm and local minima. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 502–510. ACM, 2004. 10.1145/1007352.1007428.
https://doi.org/10.1145/1007352.1007428
[39] Anders W Sandvik. Stochastic series expansion method with operator-loop update. Physical Review B, 59 (22): R14157, 1999. 10.1103/PhysRevB.59.R14157.
https://doi.org/10.1103/PhysRevB.59.R14157
[40] Lorenzo Stella and Giuseppe E Santoro. Quantum annealing of an Ising spin-glass by Green’s function Monte Carlo. Physical Review E, 75 (3): 036703, 2007, arXiv:cond-mat/0608420. 10.1103/PhysRevE.75.036703.
https://doi.org/10.1103/PhysRevE.75.036703
arXiv:cond-mat/0608420
[41] Yuki Susa, Yu Yamashiro, Masayuki Yamamoto, and Hidetoshi Nishimori. Exponential speedup of quantum annealing by inhomogeneous driving of the transverse field. Journal of the Physical Society of Japan, 87 (2): 023002, 2018. 10.7566/JPSJ.87.023002.
https://doi.org/10.7566/JPSJ.87.023002
[42] Masuo Suzuki. Quantum statistical Monte Carlo methods and applications to spin systems. Journal of Statistical Physics, 43 (5-6): 883–909, 1986. ISSN 0022-4715. 10.1007/BF02628318.
https://doi.org/10.1007/BF02628318
[43] Masuo Suzuki, Seiji Miyashita, and Akira Kuroda. Monte Carlo simulation of quantum spin systems. Prog. Theor. Phys., 58 (5): 1377–1387, 1977. 10.1143/PTP.58.1377.
https://doi.org/10.1143/PTP.58.1377
[44] S. Suzuki, J. Inoue, and B.K. Chakrabarti. Quantum Ising Phases and Transitions in Transverse Ising Models. Lecture notes in physics. Springer, 2013. ISBN 9783642330391. 10.1007/978-3-642-33039-1.
https://doi.org/10.1007/978-3-642-33039-1
[45] Frank Verstraete, Valentin Murg, and J Ignacio Cirac. Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems. Advances in Physics, 57 (2): 143–224, 2008, arXiv:0907.2796. 10.1080/14789940801912366.
https://doi.org/10.1080/14789940801912366
arXiv:0907.2796
[46] Walter Vinci and Daniel A Lidar. Non-stoquastic hamiltonians in quantum annealing via geometric phases. npj Quantum Information, 3 (1): 1–6, 2017. 10.1038/s41534-017-0037-z.
https://doi.org/10.1038/s41534-017-0037-z
Cited by
[1] Humberto Munoz-Bauza, Huo Chen, and Daniel Lidar, “A double-slit proposal for quantum annealing”, npj Quantum Information 5, 51 (2019).
[2] Elizabeth Crosson, Tameem Albash, Itay Hen, and A. P. Young, “De-Signing Hamiltonians for Quantum Adiabatic Optimization”, arXiv:2004.07681.
[3] Elizabeth Crosson and Samuel Slezak, “Classical Simulation of High Temperature Quantum Ising Models”, arXiv:2002.02232.
[4] Nicholas LaRacuente, “Quasi-factorization of Quantum Relative Entropy For Subalgebras with Scalar Intersection”, arXiv:1912.00983.
[5] Jacob Bringewatt and Michael Jarret, “Effective Gaps Are Not Effective: Quasipolynomial Classical Simulation of Obstructed Stoquastic Hamiltonians”, Physical Review Letters 125 17, 170504 (2020).
[6] Thiago Bergamaschi, “Simulated Quantum Annealing is Efficient on the Spike Hamiltonian”, arXiv:2011.15094.
The above citations are from SAO/NASA ADS (last updated successfully 2021-02-13 01:50:05). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2021-02-13 01:50:02).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
Source: https://quantum-journal.org/papers/q-2021-02-11-395/
