Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature

Tyler Helmuth; Ryan L. Mann

doi:10.22331/q-2023-10-25-1155

Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature

Tyler Helmuth¹ and Ryan L. Mann^2,3

¹Department of Mathematical Sciences, Durham University, Durham, DH1 3LE, United Kingdom
²Centre for Quantum Computation and Communication Technology, Centre for Quantum Software and Information, School of Computer Science, Faculty of Engineering & Information Technology, University of Technology Sydney, NSW 2007, Australia
³School of Mathematics, University of Bristol, Bristol, BS8 1UG, United Kingdom

Published:	2023-10-25, volume 7, page 1155
Eprint:	arXiv:2201.06533v2
Doi:	https://doi.org/10.22331/q-2023-10-25-1155
Citation:	Quantum 7, 1155 (2023).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We establish an efficient approximation algorithm for the partition functions of a class of quantum spin systems at low temperature, which can be viewed as stable quantum perturbations of classical spin systems. Our algorithm is based on combining the contour representation of quantum spin systems of this type due to Borgs, Kotecký, and Ueltschi with the algorithmic framework developed by Helmuth, Perkins, and Regts, and Borgs et al.

► BibTeX data

@article{Helmuth2023efficientalgorithms,
  doi = {10.22331/q-2023-10-25-1155},
  url = {https://doi.org/10.22331/q-2023-10-25-1155},
  title = {Efficient {A}lgorithms for {A}pproximating {Q}uantum {P}artition {F}unctions at {L}ow {T}emperature},
  author = {Helmuth, Tyler and Mann, Ryan L.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {7},
  pages = {1155},
  month = oct,
  year = {2023}
}

► References

[1] D. Weitz, in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (ACM, 2006) pp. 140–149.
https://doi.org/10.1145/1132516.1132538

[2] A. Sly, in 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (IEEE, 2010) pp. 287–296, arXiv:1005.5584.
https://doi.org/10.1109/FOCS.2010.34
arXiv:1005.5584

[3] A. Sly and N. Sun, The Annals of Probability 42, 2383 (2014).
https://doi.org/10.1214/13-AOP888

[4] A. Galanis, D. Štefankovič, and E. Vigoda, Combinatorics, Probability and Computing 25, 500 (2016), arXiv:1203.2226.
https://doi.org/10.1017/s0963548315000401
arXiv:1203.2226

[5] M. Dyer, L. A. Goldberg, C. Greenhill, and M. Jerrum, Algorithmica 38, 471 (2004).
https://doi.org/10.1007/s00453-003-1073-y

[6] S. Bravyi, Quantum Information and Computation 15, 1122 (2015), arXiv:1402.2295.
arXiv:1402.2295

[7] R. L. Mann and M. J. Bremner, Quantum 3, 162 (2019), arXiv:1806.11282.
https://doi.org/10.22331/q-2019-07-11-162
arXiv:1806.11282

[8] A. W. Harrow, S. Mehraban, and M. Soleimanifar, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (ACM, 2020) pp. 378–386, arXiv:1910.09071.
https://doi.org/10.1145/3357713.3384322
arXiv:1910.09071

[9] T. Kuwahara, K. Kato, and F. G. Brandão, Physical Review Letters 124, 220601 (2020), arXiv:1910.09425.
https://doi.org/10.1103/physrevlett.124.220601
arXiv:1910.09425

[10] E. Crosson and S. Slezak, arXiv e-prints (2020), arXiv:2002.02232.
arXiv:2002.02232

[11] R. L. Mann and T. Helmuth, Journal of Mathematical Physics 62, 022201 (2021), arXiv:2004.11568.
https://doi.org/10.1063/5.0013689
arXiv:2004.11568

[12] A. Galanis, L. A. Goldberg, and A. Herrera-Poyatos, SIAM Journal on Discrete Mathematics 36, 2159 (2022), arXiv:2105.00287.
https://doi.org/10.1137/21M1454043
arXiv:2105.00287

[13] M. Jerrum and A. Sinclair, SIAM Journal on Computing 22, 1087 (1993).
https://doi.org/10.1137/0222066

[14] T. Helmuth, W. Perkins, and G. Regts, Probability Theory and Related Fields 176, 851 (2020), arXiv:1806.11548.
https://doi.org/10.1007/s00440-019-00928-y
arXiv:1806.11548

[15] M. Jenssen, P. Keevash, and W. Perkins, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, 2019) pp. 2235–2247, arXiv:1807.04804.
https://doi.org/10.1137/1.9781611975482.135
arXiv:1807.04804

[16] C. Liao, J. Lin, P. Lu, and Z. Mao, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019) arXiv:1903.07531.
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.34
arXiv:1903.07531

[17] C. Borgs, J. Chayes, T. Helmuth, W. Perkins, and P. Tetali, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (ACM, 2020) pp. 738–751, arXiv:1909.09298.
https://doi.org/10.1145/3357713.3384271
arXiv:1909.09298

[18] C. Carlson, E. Davies, and A. Kolla, arXiv e-prints (2020), arXiv:2003.01154.
arXiv:2003.01154

[19] A. Barvinok and G. Regts, Combinatorics, Probability and Computing 28, 696 (2019), arXiv:1706.05423.
https://doi.org/10.1017/S0963548319000105
arXiv:1706.05423

[20] J. Huijben, V. Patel, and G. Regts, Random Structures & Algorithms 62, 219 (2023), arXiv:2103.07360.
https://doi.org/10.1002/rsa.21089
arXiv:2103.07360

[21] J. Ginibre, Communications in Mathematical Physics 14, 205 (1969).
https://doi.org/10.1007/BF01645421

[22] T. Kennedy, Communications in Mathematical Physics 100, 447 (1985).
https://doi.org/10.1007/BF01206139

[23] C. Borgs, R. Kotecký, and D. Ueltschi, Communications in Mathematical Physics 181, 409 (1996).
https://doi.org/10.1007/bf02101010

[24] N. Datta, R. Fernández, and J. Fröhlich, Journal of Statistical Physics 84, 455 (1996a).
https://doi.org/10.1007/bf02179651

[25] N. Datta, J. Fröhlich, L. Rey-Bellet, and R. Fernández, Helvetica Physica Acta 69, 752 (1996b).
https://doi.org/10.5169/seals-116979

[26] C. Borgs, J. T. Chayes, and P. Tetali, Probability Theory and Related Fields 152, 509 (2012), arXiv:1011.3058.
https://doi.org/10.1007/s00440-010-0329-0
arXiv:1011.3058

[27] R. Kotecký and D. Preiss, Communications in Mathematical Physics 103, 491 (1986).
https://doi.org/10.1007/bf01211762

[28] S. Friedli and Y. Velenik, Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction (Cambridge University Press, 2017).
https://doi.org/10.1017/9781316882603

[29] D. Ueltschi, Discontinuous Phase Transitions in Quantum Lattice Systems, Ph.D. thesis, Verlag nicht ermittelbar (1998).

[30] C. Borgs and J. Z. Imbrie, Communications in Mathematical Physics 123, 305 (1989).
https://doi.org/10.1007/BF01238860

[31] M. Zahradník, Communications in Mathematical Physics 93, 559 (1984).
https://doi.org/10.1007/BF01212295

[32] A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto, in 49th Annual IEEE Symposium on Foundations of Computer Science (IEEE, 2008) pp. 677–686, arXiv:0711.2585.
https://doi.org/10.1109/FOCS.2008.40
arXiv:0711.2585

[33] R. Bauerschmidt, N. Crawford, and T. Helmuth, arXiv e-prints (2021), arXiv:2107.01878.
arXiv:2107.01878

[34] N. Anari, K. Liu, S. O. Gharan, C. Vinzant, and T.-D. Vuong, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (ACM, 2021) pp. 408–420, arXiv:2004.07220.
https://doi.org/10.1145/3406325.3451091
arXiv:2004.07220

[35] R. L. Graham, M. Grötschel, and L. Lovász, Handbook of Combinatorics, Vol. 2 (Elsevier, 1995).

Cited by

[1] Jorge Sánchez-Segovia, Jan T. Schneider, and Álvaro M. Alhambra, "High-Temperature Partition Functions and Classical Simulatability of Long-Range Quantum Systems", PRX Quantum 6 4, 040366 (2025).

[2] Joel Rajakumar and James D. Watson, "Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians", Quantum 10, 1981 (2026).

[3] Ryan L. Mann and Romy M. Minko, "Algorithmic Cluster Expansions for Quantum Problems", PRX Quantum 5 1, 010305 (2024).

[4] Štěpán Šmíd, Richard Meister, Mario Berta, and Roberto Bondesan, "Polynomial-time quantum Gibbs sampling for the weak and strong coupling regime of the Fermi-Hubbard model at any temperature", Nature Communications 16 1, 10736 (2025).

[5] Ryan L. Mann and Gabriel Waite, "Efficient algorithms for weakly interacting quantum spin systems", Physical Review A 114 1, 012432 (2026).

[6] Rakesh Achutha, Donghoon Kim, Yusuke Kimura, and Tomotaka Kuwahara, "Provably Efficient Simulation of 1D Long-Range Interacting Systems at Any Temperature", Physical Review Letters 134 19, 190404 (2025).

[7] Álvaro M. Alhambra, "Quantum Many-Body Systems in Thermal Equilibrium", PRX Quantum 4 4, 040201 (2023).

[8] Štěpán Šmíd, Richard Meister, Mario Berta, and Roberto Bondesan, "Rapid Mixing of Quantum Gibbs Samplers for Weakly-Interacting Quantum Systems", arXiv:2510.04954, (2025).

[9] Viresh Patel and Guus Regts, "Approximate counting using Taylor's theorem: a survey", arXiv:2212.08143, (2022).

[10] Ryan L. Mann and Gabriel Waite, "Approximate Counting in Local Lemma Regimes", arXiv:2512.10134, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-07 19:47:47) and SAO/NASA ADS (last updated successfully 2026-08-07 19:47:48). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.