- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review A

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Efficient algorithms for weakly interacting quantum spin systems

Ryan L. Mann* and Gabriel Waite†

  • 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, Ultimo, New South Wales 2007, Australia

PDF

Phys. Rev. A 114, 012432 – Published 13 July, 2026

DOI: https://doi.org/10.1103/45rz-42gr

Abstract

We establish efficient algorithms for weakly interacting quantum spin systems at arbitrary temperature. In particular, we obtain a fully polynomial-time approximation scheme for the partition function and an efficient approximate sampling scheme for the thermal distribution over a classical spin space. Our approach is based on the cluster expansion method and a standard reduction from approximate sampling to approximate counting.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (28)

  1. T. Helmuth, W. Perkins, and G. Regts, Algorithmic Pirogov–Sinai theory, Probab. Theory Relat. Fields 176, 851 (2020).
  2. M. Jenssen, P. Keevash, and W. Perkins, Algorithms for #BIS-hard problems on expander graphs, SIAM J. Comput. 49, 681 (2020).
  3. Z. Chen, A. Galanis, L. A. Goldberg, W. Perkins, J. Stewart, and E. Vigoda, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019), Leibniz International Proceedings in Informatics (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Saarbrücken, 2019), Vol. 145, pp. 41:1–41:14.
  4. S. Cannon and W. Perkins, in Proceedings of the Fourteeth Annual ACM-SIAM Symposium on Discrete Algorithms, edited by S. Chawla (SIAM, Philadelphia, 2020), pp. 1456–1466.
  5. M. Jenssen and W. Perkins, Independent sets in the hypercube revisited, J. London Math. Soc. 102, 645 (2020).
  6. M. Jenssen, W. Perkins, and A. Potukuchi, Approximately counting independent sets in bipartite graphs via graph containers, Random Struct. Algorithms 63, 215 (2023).
  7. D. Galvin, G. McKinley, W. Perkins, M. Sarantis, and P. Tetali, On the zeroes of hypergraph independence polynomials, Comb. Probab. Comput. 33, 65 (2024).
  8. M. Collares, J. Erde, A. Geisler, and M. Kang, Counting independent sets in expanding bipartite regular graphs, arXiv:2503.22255.
  9. C. Borgs, J. Chayes, T. Helmuth, W. Perkins, and P. Tetali, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Chicago, 2020 (ACM, New York, 2020), pp. 738–751.
  10. T. Helmuth, M. Jenssen, and W. Perkins, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Ann. Inst. H. Poincaré Probab. Statist. 59, 817 (2023).
  11. C. Carlson, E. Davies, N. Fraiman, A. Kolla, A. Potukuchi, and C. Yap, Algorithms for the ferromagnetic Potts model on expanders, Comb. Probab. Comput. 33, 487 (2024).
  12. R. L. Mann and T. Helmuth, Efficient algorithms for approximating quantum partition functions, J. Math. Phys. 62, 022201 (2021).
  13. T. Helmuth and R. L. Mann, Efficient algorithms for approximating quantum partition functions at low temperature, Quantum 7, 1155 (2023).
  14. R. L. Mann and R. M. Minko, Algorithmic cluster expansions for quantum problems, PRX Quantum 5, 010305 (2024).
  15. R. Kotecký and D. Preiss, Cluster expansion for abstract polymer models, Commun. Math. Phys. 103, 491 (1986).
  16. S. Bravyi, D. DiVincenzo, and D. Loss, Polynomial-time algorithm for simulation of weakly interacting quantum spin systems, Commun. Math. Phys. 284, 481 (2008).
  17. H. Chen, C. Rouzé, J. Chen, J. Jiang, S. O. Scalet, Y. Zhan, G. K.-L. Chan, L. Ying, and Y. Tong, Convergence of the cumulant expansion and polynomial-time algorithm for weakly interacting fermions, arXiv:2512.12010.
  18. Y. Tong and Y. Zhan, Fast mixing of weakly interacting fermionic systems at any temperature, PRX Quantum 6, 030301 (2025).
  19. Š. Šmíd, R. Meister, M. Berta, and R. Bondesan, Polynomial-time quantum Gibbs sampling for the weak and strong coupling regime of the Fermi-Hubbard model at any temperature, Nat. Commun. 16, 10736 (2025).
  20. Y. Zhan, Z. Ding, J. Huhn, J. Gray, J. Preskill, G. K.-L. Chan, and L. Lin, Rapid quantum ground state preparation via dissipative dynamics, Phys. Rev. X 16, 011004 (2026).
  21. Š. Šmíd, R. Meister, M. Berta, and R. Bondesan, Rapid mixing of quantum Gibbs samplers for weakly-interacting quantum systems, arXiv:2510.04954.
  22. S. Friedli and Y. Velenik, Statistical Mechanics of Lattice Systems: A Concrete Mathematical Introduction (Cambridge University Press, Cambridge, 2017).
  23. M. R. Jerrum, L. G. Valiant, and V. V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theor. Comput. Sci. 43, 169 (1986).
  24. A. Sinclair and M. Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Inf. Comput. 82, 93 (1989).
  25. C. Yin and A. Lucas, Polynomial-time classical sampling of high-temperature quantum Gibbs states, arXiv:2305.18514.
  26. A. Bakshi, A. Liu, A. Moitra, and E. Tang, in Proceedings of the 2024 IEEE 65th Annual Symposium on Foundations of Computer Science, Chicago, 2024 (IEEE, Piscataway, 2024), pp. 1027–1036.
  27. A. Ramkumar, Y. Cai, Y. Tong, and J. Jiang, High-temperature fermionic Gibbs states are mixtures of Gaussian states, arXiv:2505.09730.
  28. Handbook of Combinatorics, edited by R. L. Graham, M. Grötschel, and L. Lovász (Elsevier, Amsterdam, 1995), Vol. 2.

Outline

Information

Phys. Rev. A 114, 012432– Published 13 July, 2026
  • Received 12 February 2026
  • Accepted 25 June 2026
Crossmark - Check for updates button

©2026 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation