1Department of Mathematical Sciences, Durham University, Durham, DH1 3LE, United Kingdom
2Centre 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
3School of Mathematics, University of Bristol, Bristol, BS8 1UG, United Kingdom
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
► 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] Ryan L. Mann and Romy M. Minko, “Algorithmic Cluster Expansions for Quantum Problems”, arXiv:2306.08974, (2023).
[2] Álvaro M. Alhambra, “Quantum many-body systems in thermal equilibrium”, arXiv:2204.08349, (2022).
[3] Viresh Patel and Guus Regts, “Approximate counting using Taylor’s theorem: a survey”, arXiv:2212.08143, (2022).
The above citations are from SAO/NASA ADS (last updated successfully 2023-10-26 13:22:16). 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 2023-10-26 13:22:14).
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.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-10-25-1155/
