{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:34:03Z","timestamp":1787337243696,"version":"build-2736575974"},"reference-count":57,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"QuEra Computing Inc."},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["W911NF2010021"],"award-info":[{"award-number":["W911NF2010021"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014036","name":"Multidisciplinary University Research Initiative","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100014036","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["DE-SC0021013"],"award-info":[{"award-number":["DE-SC0021013"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"publisher","award":["7568717"],"award-info":[{"award-number":["7568717"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We introduce a unified framework to compute the solution space properties of a broad class of combinatorial optimization problems. These properties include finding one of the optimum solutions, counting the number of solutions of a given size, and enumeration and sampling of solutions of a given size. Using the independent set problem as an example, we show how all these solution space properties can be computed in the unified approach of generic tensor networks. We demonstrate the versatility of this computational tool by applying it to several examples, including computing the entropy constant for hardcore lattice gases, studying the overlap gap properties, and analyzing the performance of quantum and classical algorithms for finding maximum independent sets.<\/jats:p>","DOI":"10.1137\/22m1501787","type":"journal-article","created":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T05:54:10Z","timestamp":1686635650000},"page":"A1239-A1270","source":"Crossref","is-referenced-by-count":28,"title":["Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks"],"prefix":"10.1137","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1635-2679","authenticated-orcid":true,"given":"Jin-Guo","family":"Liu","sequence":"first","affiliation":[{"name":"Department of Physics, Harvard University, Cambridge, MA 02138 USA, and QuEra Computing, Boston, MA 02135 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xun","family":"Gao","sequence":"additional","affiliation":[{"name":"Department of Physics, Harvard University, Cambridge, MA 02138 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madelyn","family":"Cain","sequence":"additional","affiliation":[{"name":"Department of Physics, Harvard University, Cambridge, MA 02138 USA, and QuEra Computing, Boston, MA 02135 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mikhail D.","family":"Lukin","sequence":"additional","affiliation":[{"name":"Department of Physics, Harvard University, Cambridge, MA 02138 USA, and QuEra Computing, Boston, MA 02135 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sheng-Tao","family":"Wang","sequence":"additional","affiliation":[{"name":"QuEra Computing, Boston, MA 02135 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,6,13]]},"reference":[{"key":"ref1","unstructured":"Generic Tensor Networks, https:\/\/github.com\/QuEraComputing\/GenericTensorNetworks.jl."},{"key":"ref2","unstructured":"Tropical GEMM, https:\/\/github.com\/TensorBFS\/TropicalGEMM.jl."},{"key":"ref3","unstructured":"S. Alikhani  and \nY.H. Peng , Introduction to Domination Polynomial of a Graph, https:\/\/arxiv.org\/abs\/0905.2251, 2009."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1002116107"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01012867"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2018.2872064"},{"key":"ref7","unstructured":"J. Bezanson , \nS. Karpinski , \nV. B. Shah , and \nA. Edelman , Julia: A Fast Dynamic Language for Technical Computing, https:\/\/arxiv.org\/abs\/1209.5145, 2012."},{"key":"ref8","unstructured":"J. Biamonte  and \nV. Bergholm , Tensor Networks in a Nutshell, https:\/\/arxiv.org\/abs\/1708.00006, 2017."},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-015-1276-z"},{"key":"ref10","volume-title":"Pattern Recognition and Machine Learning","author":"Bishop C. M.","year":"2006"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-007-0096-x"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"ref13","unstructured":"S. Butenko  and \nP. M. Pardalos , Maximum Independent Set and Related Problems, with Applications, Ph.D. thesis, University of Florida, 2003, https:\/\/ufdc.ufl.edu\/UFE0001011\/00001."},{"key":"ref14","unstructured":"P. Butera  and \nM. Pernici , Sums of Permanental Minors Using Grassmann Algebra, https:\/\/arxiv.org\/abs\/1406.5337, 2014."},{"key":"ref15","unstructured":"A. Cichocki , Era of Big Data Processing: A New Approach via Tensor Networks and Tensor Decompositions, https:\/\/arxiv.org\/abs\/1403.2048, 2014."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.93.045003"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1088\/0953-8984\/28\/32\/323001"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1126\/science.abo6587"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1063\/1.2539141"},{"key":"ref22","unstructured":"G. M. Ferrin , Independence Polynomials, https:\/\/scholarcommons.sc.edu\/etd\/2609\/, 2014"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1145\/2428556.2428575"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2108492118"},{"key":"ref25","unstructured":"D. Gamarnik  and \nA. Jagannath , The Overlap Gap Property and Approximate Message Passing Algorithms for \\(p\\)-Spin Models, https:\/\/arxiv.org\/abs\/1911.06943, 2019."},{"key":"ref26","unstructured":"D. Gamarnik  and \nM. Sudan , Limits of Local Algorithms over Sparse Random Graphs, https:\/\/arxiv.org\/abs\/1304.1831, 2013."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1137\/0132071"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9474-1"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.56021\/9781421407944"},{"key":"ref30","first-page":"573","volume":"25","author":"Goodman J.","year":"1999","journal-title":"Comput. Linguist."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-03-15-410"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020-2649-2"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"N. J. Harvey , \nP. Srivastava , and \nJ. Vondr\u00e1k , Computing the independence polynomial: From the tree threshold down to the roots, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2018, pp. 1557\u20131576, https:\/\/doi.org\/10.1137\/1.9781611975031.102.","DOI":"10.1137\/1.9781611975031.102"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"J. Hastad , Clique is hard to approximate within \\(n^{1-\\epsilon }\\), in Proceedings of the 37th Conference on Foundations of Computer Science, IEEE, 1996, pp. 627\u2013636, https:\/\/doi.org\/10.1007\/BF02392825.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"ref36","unstructured":"G. Kalachev , \nP. Panteleev , and \nM.H. Yung , Multi-Tensor Contraction for XEB Verification of Quantum Circuits, https:\/\/arxiv.org\/abs\/2108.05665, 2021."},{"key":"ref37","unstructured":"L. R. Kerr , The Effect of Algebraic Structure on the Computational Complexity of Matrix Multiplication, Tech. report, Cornell University, 1970, https:\/\/ecommons.cornell.edu\/handle\/1813\/5934."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.21468\/SciPostPhys.7.5.060"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.87.410"},{"key":"ref40","unstructured":"V. E. Levit  and \nE. Mandrescu , The Independence Polynomial of a Graph at \u22121, https:\/\/arxiv.org\/abs\/0904.4819, 2009."},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.126.090506"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/161"},{"key":"ref43","doi-asserted-by":"crossref","unstructured":"F. Manne  and \nS. Sharmin , Efficient counting of maximal independent sets in sparse graphs, in International Symposium on Experimental Algorithms, Springer, New York, 2013, pp. 103\u2013114, https:\/\/doi.org\/10.1007\/978-3-642-38527-8_11.","DOI":"10.1007\/978-3-642-38527-8_11"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/050644756"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1016\/j.aop.2014.06.013"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1137\/090752286"},{"key":"ref48","unstructured":"F. Pan  and \nP. Zhang , Simulating the Sycamore Quantum Supremacy Circuits, https:\/\/arxiv.org\/abs\/2103.03074, 2021."},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1007\/BF01023857"},{"key":"ref50","unstructured":"H. Pichler , \nS.T. Wang , \nL. Zhou , \nS. Choi , and \nM. D. Lukin , Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays, https:\/\/arxiv.org\/abs\/1808.10816, 2018."},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOP1094"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242355"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2013.12.013"},{"key":"ref54","volume-title":"From Mathematics to Generic Programming","author":"Stepanov A. A.","year":"2014"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.09.064"},{"key":"ref56","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.121.210602"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.87.404"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1501787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:52:04Z","timestamp":1787334724000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1501787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1137\/22M1501787"],"URL":"https:\/\/doi.org\/10.1137\/22m1501787","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}