{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:50:32Z","timestamp":1781077832768,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1452616,1729369,1818914"],"award-info":[{"award-number":["1452616,1729369,1818914"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-17-1-0433"],"award-info":[{"award-number":["W911NF-17-1-0433"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Samsung Advanced Institute of Technology"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384322","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"378-386","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Classical algorithms, correlation decay, and complex zeros of partition functions of Quantum many-body systems"],"prefix":"10.1145","author":[{"given":"Aram W.","family":"Harrow","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Saeed","family":"Mehraban","sequence":"additional","affiliation":[{"name":"California Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mehdi","family":"Soleimanifar","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-008-0710-3"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-017-2973-z"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01645134"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Barvinok A. Computing the partition function for cliques in a graph. Theory of Computing. An Open Access Journal 11 ( 2015 ) 339-355.  Barvinok A. Computing the partition function for cliques in a graph. Theory of Computing. An Open Access Journal 11 ( 2015 ) 339-355.","DOI":"10.4086\/toc.2015.v011a013"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-51829-9"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9243-7"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-016-3357-2"},{"key":"e_1_3_2_1_8_1","first-page":"871","volume-title":"Proceedings of the 2013 ACM Symposium on Theory of Computing-STOC 2013 ( 2013 ), ACM","author":"Brand\u00e3o F.","unstructured":"Brand\u00e3o , F. , and Harrow , A . Product-state approximations to quantum ground states . In Proceedings of the 2013 ACM Symposium on Theory of Computing-STOC 2013 ( 2013 ), ACM , New York , pp. 871 - 880 . Brand\u00e3o, F., and Harrow, A. Product-state approximations to quantum ground states. In Proceedings of the 2013 ACM Symposium on Theory of Computing-STOC 2013 ( 2013 ), ACM, New York, pp. 871-880."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Brand\u00e3o F. and Kastoryano M. J. Finite correlation length implies eficient preparation of quantum thermal states. Communications in Mathematical Physics ( 2016 ) 1-16.  Brand\u00e3o F. and Kastoryano M. J. Finite correlation length implies eficient preparation of quantum thermal states. Communications in Mathematical Physics ( 2016 ) 1-16.","DOI":"10.1007\/s00220-018-3150-8"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC15.13-14-3"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.119.100503"},{"key":"e_1_3_2_1_12_1","volume-title":"Classical algorithms for quantum mean values. arXiv preprint arXiv","author":"Bravyi S.","year":"1909","unstructured":"Bravyi , S. , Gosset , D. , and Movassagh , R . Classical algorithms for quantum mean values. arXiv preprint arXiv : 1909 . 11485 ( 2019 ). Bravyi, S., Gosset, D., and Movassagh, R. Classical algorithms for quantum mean values. arXiv preprint arXiv: 1909. 11485 ( 2019 )."},{"key":"e_1_3_2_1_13_1","first-page":"1456","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms ( 2020 ), SIAM","author":"Cannon S.","unstructured":"Cannon , S. , and Perkins , W . Counting independent sets in unbalanced bipartite graphs . In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms ( 2020 ), SIAM , pp. 1456 - 1466 . Cannon, S., and Perkins, W. Counting independent sets in unbalanced bipartite graphs. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms ( 2020 ), SIAM, pp. 1456-1466."},{"key":"e_1_3_2_1_14_1","first-page":"1","article-title":"Quantum algorithms for Gibbs sampling and hitting-time estimation","volume":"17","author":"Chowdhury A. N.","year":"2017","unstructured":"Chowdhury , A. N. , and Somma , R . Quantum algorithms for Gibbs sampling and hitting-time estimation . Quantum Information & Computation 17 , 1 - 2 ( 2017 ), 41-64. Chowdhury, A. N., and Somma, R. Quantum algorithms for Gibbs sampling and hitting-time estimation. Quantum Information & Computation 17, 1-2 ( 2017 ), 41-64.","journal-title":"Quantum Information & Computation"},{"key":"e_1_3_2_1_15_1","volume-title":"Rapid mixing of path integral Monte Carlo for 1d stoquastic Hamiltonians. arXiv preprint arXiv","author":"Crosson E.","year":"1812","unstructured":"Crosson , E. , and Harrow , A. W . Rapid mixing of path integral Monte Carlo for 1d stoquastic Hamiltonians. arXiv preprint arXiv : 1812 . 02144 ( 2018 ). Crosson, E., and Harrow, A. W. Rapid mixing of path integral Monte Carlo for 1d stoquastic Hamiltonians. arXiv preprint arXiv: 1812. 02144 ( 2018 )."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Cubitt T. S. Perez-Garcia D. and Wolf M. M. Undecidability of the spectral gap. Nature 528 7581 ( 2015 ) 207.  Cubitt T. S. Perez-Garcia D. and Wolf M. M. Undecidability of the spectral gap. Nature 528 7581 ( 2015 ) 207.","DOI":"10.1038\/nature16059"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01011153"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20004"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00012"},{"key":"e_1_3_2_1_20_1","unstructured":"Fisher M. The nature of critical points. Lecture notes in Theoretical Physics 7c ( 1965 ) 1-159.  Fisher M. The nature of critical points. Lecture notes in Theoretical Physics 7c ( 1965 ) 1-159."},{"key":"e_1_3_2_1_21_1","volume-title":"Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. arXiv preprint arXiv","author":"Harrow A.","year":"1910","unstructured":"Harrow , A. , Mehraban , S. , and Soleimanifar , M . Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. arXiv preprint arXiv : 1910 . 09071 ( 2019 ). Harrow, A., Mehraban, S., and Soleimanifar, M. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. arXiv preprint arXiv: 1910. 09071 ( 2019 )."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.73.085115"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.76.201102"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222066"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-016-2641-8"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-019-03485-6"},{"key":"e_1_3_2_1_27_1","unstructured":"Kim I. Markovian matrix product density operators: Eficient computation of global entropy. arXiv preprint arXiv:1709.07828 ( 2017 ).  Kim I. Markovian matrix product density operators: Eficient computation of global entropy. arXiv preprint arXiv:1709.07828 ( 2017 )."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.4.031019"},{"key":"e_1_3_2_1_29_1","volume-title":"Clustering of conditional mutual information for quantum gibbs states above a threshold temperature. arXiv preprint arXiv","author":"Kuwahara T.","year":"1910","unstructured":"Kuwahara , T. , Kato , K. , and Brand\u00e3o , F. G . Clustering of conditional mutual information for quantum gibbs states above a threshold temperature. arXiv preprint arXiv : 1910 . 09425 ( 2019 ). Kuwahara, T., Kato, K., and Brand\u00e3o, F. G. Clustering of conditional mutual information for quantum gibbs states above a threshold temperature. arXiv preprint arXiv: 1910. 09425 ( 2019 )."},{"key":"e_1_3_2_1_30_1","volume-title":"Polynomial-time classical simulation for onedimensional quantum gibbs states. arXiv preprint arXiv","author":"Kuwahara T.","year":"1807","unstructured":"Kuwahara , T. , and Saito , K . Polynomial-time classical simulation for onedimensional quantum gibbs states. arXiv preprint arXiv : 1807 . 08424 ( 2018 ). Kuwahara, T., and Saito, K. Polynomial-time classical simulation for onedimensional quantum gibbs states. arXiv preprint arXiv: 1807. 08424 ( 2018 )."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.87.410"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.71.045110"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.5082552"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-018-2199-2"},{"key":"e_1_3_2_1_35_1","volume-title":"Approximation algorithms for complex-valued Ising models on bounded degree graphs. arXiv preprint arXiv","author":"Mann R.","year":"1806","unstructured":"Mann , R. , and Bremner , M . Approximation algorithms for complex-valued Ising models on bounded degree graphs. arXiv preprint arXiv : 1806 . 11282 ( 2018 ). Mann, R., and Bremner, M. Approximation algorithms for complex-valued Ising models on bounded degree graphs. arXiv preprint arXiv: 1806. 11282 ( 2018 )."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.91.045138"},{"key":"e_1_3_2_1_37_1","volume-title":"Location of zeros for the partition function of the Ising model on bounded degree graphs. arXiv preprint arXiv","author":"Peters H.","year":"1810","unstructured":"Peters , H. , and Regts , G . Location of zeros for the partition function of the Ising model on bounded degree graphs. arXiv preprint arXiv : 1810 . 01699 ( 2018 ). Peters, H., and Regts, G. Location of zeros for the partition function of the Ising model on bounded degree graphs. arXiv preprint arXiv: 1810. 01699 ( 2018 )."},{"key":"e_1_3_2_1_38_1","first-page":"33","article-title":"On a conjecture of Sokal concerning roots of the independence polynomial","volume":"68","author":"Peters H.","unstructured":"Peters , H. , and Regts , G . On a conjecture of Sokal concerning roots of the independence polynomial . Michigan Math. J. 68 , 1 ( 2019 ), 33 - 55 . Peters, H., and Regts, G. On a conjecture of Sokal concerning roots of the independence polynomial. Michigan Math. J. 68, 1 ( 2019 ), 33-55.","journal-title":"Michigan Math. J."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.220502"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-014-0947-5"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.34"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.56"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1665583"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1048642"},{"key":"e_1_3_2_1_45_1","first-page":"140","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing-STOC 2006 ( 2006 ), ACM","author":"Weitz D.","unstructured":"Weitz , D. Counting independent sets up to the tree threshold . In Proceedings of the 38th Annual ACM Symposium on Theory of Computing-STOC 2006 ( 2006 ), ACM , New York , pp. 140 - 149 . Weitz, D. Counting independent sets up to the tree threshold. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing-STOC 2006 ( 2006 ), ACM, New York, pp. 140-149."},{"key":"e_1_3_2_1_46_1","first-page":"140","volume-title":"STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing ( 2006 ), ACM","author":"Weitz D.","unstructured":"Weitz , D. Counting independent sets up to the tree threshold . In STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing ( 2006 ), ACM , New York , pp. 140 - 149 . Weitz, D. Counting independent sets up to the tree threshold. In STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing ( 2006 ), ACM, New York, pp. 140-149."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384322","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384322","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:57Z","timestamp":1750199577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":46,"alternative-id":["10.1145\/3357713.3384322","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384322","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}