{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T01:02:36Z","timestamp":1773363756311,"version":"3.50.1"},"reference-count":28,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T00:00:00Z","timestamp":1661990400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Army Research Office and Army Research Laboratory","award":["W911NF-20-1-0014"],"award-info":[{"award-number":["W911NF-20-1-0014"]}]},{"name":"European Research Council","award":["817581"],"award-info":[{"award-number":["817581"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. Our work has two main contributions: first, we modify the classical algorithm of Stefankovic, Vempala and Vigoda (J. ACM, 56(3), 2009) to improve its sample complexity; second, we quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei (SODA 2020).\nThe conventional approach to estimating partition functions requires approximating the means of Gibbs distributions at a set of inverse temperatures that form the so-called cooling schedule. The length of the cooling schedule directly affects the complexity of the algorithm. Combining our improved version of the algorithm of Stefankovic, Vempala and Vigoda with the paired-product estimator of Huber (Ann. Appl. Probab., 25(2), 2015), our new quantum algorithm uses a shorter cooling schedule than previously known. This length matches the optimal length conjectured by Stefankovic, Vempala and Vigoda. The quantum algorithm also achieves a quadratic advantage in the number of required quantum samples compared to the number of random samples drawn\nby the best classical algorithm, and its computational complexity has quadratically better dependence on the spectral gap of the Markov chains used to produce the quantum samples.<\/jats:p>","DOI":"10.22331\/q-2022-09-01-789","type":"journal-article","created":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T12:08:23Z","timestamp":1662034103000},"page":"789","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":12,"title":["Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions"],"prefix":"10.22331","volume":"6","author":[{"given":"Srinivasan","family":"Arunachalam","sequence":"first","affiliation":[{"name":"IBM Quantum, IBM T.J. Watson Research Center"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vojtech","family":"Havlicek","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM T.J. Watson Research Center"},{"name":"School of Mathematics, University of Bristol"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giacomo","family":"Nannicini","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM T.J. Watson Research Center"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kristan","family":"Temme","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM T.J. Watson Research Center"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pawel","family":"Wocjan","sequence":"additional","affiliation":[{"name":"IBM Quantum, IBM T.J. Watson Research Center"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2022,9,1]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Ivona Bez\u00e1kov\u00e1, Daniel \u0160tefankovi\u010d, Vijay V Vazirani, and Eric Vigoda. Accelerating simulated annealing for the permanent and combinatorial counting problems. SIAM Journal on Computing, 37(5):1429\u20131454, 2008. doi:10.1137\/050644033.","DOI":"10.1137\/050644033"},{"key":"1","doi-asserted-by":"crossref","unstructured":"Kurt Binder and Dieter W. Heermann. Monte Carlo Simulation in Statistical Physics: An Introduction (Graduate Texts in Physics). Springer, 2019.","DOI":"10.1007\/978-3-030-10758-1"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53\u201374, 2002.","DOI":"10.1090\/conm\/305\/05215"},{"key":"3","unstructured":"Shouvanik Chakrabarti, Andrew M Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu. Quantum algorithm for estimating volumes of convex bodies. arXiv:1908.03903, 2019."},{"key":"4","unstructured":"Guillaume Desjardins, Yoshua Bengio, and Aaron C Courville. On tracking the partition function. In Advances in neural information processing systems, pages 2501\u20132509. Citeseer, 2011."},{"key":"5","doi-asserted-by":"crossref","unstructured":"Martin Dyer and Alan Frieze. Computing the volume of convex bodies: a case where randomness provably helps. Probabilistic combinatorics and its applications, 44:123\u2013170, 1991.","DOI":"10.1090\/psapm\/044\/1141926"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM), 38(1):1\u201317, 1991. doi:10.1145\/102782.102783.","DOI":"10.1145\/102782.102783"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Andrew Gelman and Xiao-Li Meng. Simulating normalizing constants: From importance sampling to bridge sampling to path sampling. Statistical science, pages 163\u2013185, 1998. doi:10.1214\/ss\/1028905934.","DOI":"10.1214\/ss\/1028905934"},{"key":"8","unstructured":"Paul Glasserman. Monte Carlo methods in financial engineering, volume 53. Springer Science & Business Media, 2013."},{"key":"9","unstructured":"Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http:\/\/www.deeplearningbook.org."},{"key":"10","doi-asserted-by":"publisher","unstructured":"Yassine Hamoudi and Fr\u00e9d\u00e9ric Magniez. Quantum Chebyshev&apos;s Inequality and Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP), volume 132, pages 69:1\u201369:16, 2019. doi:10.4230\/LIPIcs.ICALP.2019.69.","DOI":"10.4230\/LIPIcs.ICALP.2019.69"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Aram W Harrow and Annie Y Wei. Adaptive quantum simulated annealing for bayesian inference and estimating partition functions. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 193\u2013212, 2020. doi:10.1137\/1.9781611975994.12.","DOI":"10.1137\/1.9781611975994.12"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Geoffrey E Hinton, Simon Osindero, and Yee-Whye Teh. A fast learning algorithm for deep belief nets. Neural computation, 18(7):1527\u20131554, 2006. doi:10.1162\/neco.2006.18.7.1527.","DOI":"10.1162\/neco.2006.18.7.1527"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Mark Huber. Approximation algorithms for the normalizing constant of Gibbs distributions. The Annals of Applied Probability, 25(2):974\u2013985, 2015. doi:10.1214\/14-AAP1015.","DOI":"10.1214\/14-AAP1015"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Mark Huber and Sarah Schott. Using TPA for Bayesian inference. Bayesian Statistics, 9:257\u2013282, 2010. doi:10.1093\/acprof:oso\/9780199694587.003.0009.","DOI":"10.1093\/acprof:oso\/9780199694587.003.0009"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM Journal On Computing, 18(6):1149\u20131178, 1989. doi:10.1137\/0218077.","DOI":"10.1137\/0218077"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169 \u2013 188, 1986. doi:10.1016\/0304-3975(86)90174-X.","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"17","unstructured":"Vladimir Kolmogorov. A faster approximation algorithm for the Gibbs partition function. In Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 228\u2013249. PMLR, 2018."},{"key":"18","unstructured":"Qiang Liu and Alexander T. Ihler. Bounding the partition function using holder&apos;s inequality. In Proceedings of the 28th International Conference on Machine Learning, ICML, pages 849\u2013856. Omnipress, 2011."},{"key":"19","doi-asserted-by":"publisher","unstructured":"F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk. SIAM Journal on Computing, 40(1):142\u2013164, 2011. doi:10.1137\/090745854.","DOI":"10.1137\/090745854"},{"key":"20","doi-asserted-by":"crossref","unstructured":"Ashley Montanaro. Quantum speedup of monte carlo methods. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 471(2181):20150301, 2015.","DOI":"10.1098\/rspa.2015.0301"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Elchanan Mossel and Allan Sly. Exact thresholds for ising\u2013gibbs samplers on general graphs. Ann. Probab., 41(1):294\u2013328, 01 2013. doi:10.1214\/11-AOP737.","DOI":"10.1214\/11-AOP737"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Daniel \u0160tefankovi\u010d, Santosh Vempala, and Eric Vigoda. Adaptive simulated annealing: A near-optimal connection between sampling and counting. Journal of the ACM (JACM), 56(3):1\u201336, 2009. doi:10.1145\/1516512.1516520.","DOI":"10.1145\/1516512.1516520"},{"key":"23","unstructured":"Mario Szegedy. Quantum speed-up of markov chain based algorithms. In 45th Annual IEEE symposium on foundations of computer science, pages 32\u201341. IEEE, 2004."},{"key":"24","doi-asserted-by":"crossref","unstructured":"J. P. Valleau and D. N. Card. Monte carlo estimation of the free energy by multistage sampling. The Journal of Chemical Physics, 57(12):5457\u20135462, 1972.","DOI":"10.1063\/1.1678245"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Eric Vigoda. Improved bounds for sampling colorings. Journal of Mathematical Physics, 41(3):1555\u20131569, 2000. doi:10.1063\/1.533196.","DOI":"10.1063\/1.533196"},{"key":"26","unstructured":"Marc Vuffray, Sidhant Misra, Andrey Lokhov, and Michael Chertkov. Interaction screening: Efficient and sample-optimal learning of ising models. In Advances in Neural Information Processing Systems, pages 2595\u20132603, 2016."},{"key":"27","doi-asserted-by":"publisher","unstructured":"Pawel Wocjan and Anura Abeyesinghe. Speedup via quantum sampling. Physical Review A, 78(4):042336, 2008. doi:10.1103\/PhysRevA.78.042336.","DOI":"10.1103\/PhysRevA.78.042336"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-09-01-789\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T12:08:45Z","timestamp":1662034125000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-09-01-789\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,1]]},"references-count":28,"URL":"https:\/\/doi.org\/10.22331\/q-2022-09-01-789","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,1]]},"article-number":"789"}}