{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T13:24:05Z","timestamp":1770297845158,"version":"3.49.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T00:00:00Z","timestamp":1742774400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T00:00:00Z","timestamp":1742774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12047503"],"award-info":[{"award-number":["12047503"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12247104"],"award-info":[{"award-number":["12247104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput Sci"],"DOI":"10.1038\/s43588-025-00782-0","type":"journal-article","created":{"date-parts":[[2025,3,24]],"date-time":"2025-03-24T11:47:17Z","timestamp":1742816837000},"page":"322-332","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Free-energy machine for combinatorial optimization"],"prefix":"10.1038","volume":"5","author":[{"given":"Zi-Song","family":"Shen","sequence":"first","affiliation":[]},{"given":"Feng","family":"Pan","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7674-7002","authenticated-orcid":false,"given":"Yao","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Yi-Ding","family":"Men","sequence":"additional","affiliation":[]},{"given":"Wen-Biao","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Man-Hong","family":"Yung","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8496-2730","authenticated-orcid":false,"given":"Pan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,24]]},"reference":[{"key":"782_CR1","doi-asserted-by":"crossref","unstructured":"Du, D. & Pardalos, P. M. Handbook of Combinatorial Optimization vol. 4 (Springer Science & Business Media, 1998).","DOI":"10.1007\/978-1-4613-0303-9"},{"key":"782_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S. & Barak, B. Computational Complexity: A Modern Approach (Cambridge Univ. Press, 2009).","DOI":"10.1017\/CBO9780511804090"},{"key":"782_CR3","doi-asserted-by":"crossref","unstructured":"Kirkpatrick, S., Gelatt Jr, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671\u2013680 (1983).","DOI":"10.1126\/science.220.4598.671"},{"key":"782_CR4","first-page":"337","volume":"94","author":"B Selman","year":"1994","unstructured":"Selman, B. et al. Noise strategies for improving local search. AAAI 94, 337\u2013343 (1994).","journal-title":"AAAI"},{"key":"782_CR5","doi-asserted-by":"crossref","unstructured":"Glover, F. & Laguna, M. Tabu Search (Springer, 1998).","DOI":"10.1007\/978-1-4615-6089-0"},{"key":"782_CR6","doi-asserted-by":"crossref","unstructured":"Boettcher, S. & Percus, A. G. Optimization with extremal dynamics. Phys. Rev. Lett. 86, 5211-5214 (2001).","DOI":"10.1103\/PhysRevLett.86.5211"},{"key":"782_CR7","doi-asserted-by":"publisher","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","volume":"15","author":"F Barahona","year":"1982","unstructured":"Barahona, F. On the computational complexity of Ising spin glass models. J. Phys. A 15, 3241 (1982).","journal-title":"J. Phys. A"},{"key":"782_CR8","doi-asserted-by":"crossref","unstructured":"Tiunov, E. S., Ulanov, A. E. & Lvovsky, A. Annealing by simulating the coherent Ising machine. Optics Express 27, 10288\u201310295 (2019).","DOI":"10.1364\/OE.27.010288"},{"key":"782_CR9","unstructured":"King, A. D., Bernoudy, W., King, J., Berkley, A. J. & Lanting, T. Emulating the coherent Ising machine with a mean-field algorithm. Preprint at https:\/\/arxiv.org\/abs\/1806.08422 (2018)."},{"key":"782_CR10","doi-asserted-by":"publisher","first-page":"eaav2372","DOI":"10.1126\/sciadv.aav2372","volume":"5","author":"H Goto","year":"2019","unstructured":"Goto, H., Tatsumura, K. & Dixon, A. R. Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems. Sci. Adv. 5, eaav2372 (2019).","journal-title":"Sci. Adv."},{"key":"782_CR11","doi-asserted-by":"publisher","first-page":"eabe7953","DOI":"10.1126\/sciadv.abe7953","volume":"7","author":"H Goto","year":"2021","unstructured":"Goto, H. et al. High-performance combinatorial optimization based on classical mechanics. Sci. Adv. 7, eabe7953 (2021).","journal-title":"Sci. Adv."},{"key":"782_CR12","doi-asserted-by":"publisher","first-page":"194\u2013198","DOI":"10.1038\/nature10012","volume":"473","author":"MW Johnson","year":"2011","unstructured":"Johnson, M. W. et al. Quantum annealing with manufactured spins. Nature 473, 194\u2013198 (2011).","journal-title":"Nature"},{"key":"782_CR13","doi-asserted-by":"publisher","first-page":"415\u2013419","DOI":"10.1038\/nphoton.2016.68","volume":"10","author":"T Inagaki","year":"2016","unstructured":"Inagaki, T. et al. Large-scale Ising spin network based on degenerate optical parametric oscillators. Nat. Photonics 10, 415\u2013419 (2016).","journal-title":"Nat. Photonics"},{"key":"782_CR14","doi-asserted-by":"publisher","first-page":"eabh0952","DOI":"10.1126\/sciadv.abh0952","volume":"7","author":"T Honjo","year":"2021","unstructured":"Honjo, T. et al. 100,000-spin coherent Ising machine. Sci. Adv. 7, eabh0952 (2021).","journal-title":"Sci. Adv."},{"key":"782_CR15","doi-asserted-by":"publisher","first-page":"213902","DOI":"10.1103\/PhysRevLett.122.213902","volume":"122","author":"D Pierangeli","year":"2019","unstructured":"Pierangeli, D., Marcucci, G. & Conti, C. Large-scale photonic Ising machine by spatial light modulation. Phys. Rev. Lett. 122, 213902 (2019).","journal-title":"Phys. Rev. Lett."},{"key":"782_CR16","doi-asserted-by":"publisher","first-page":"409\u2013418","DOI":"10.1038\/s41928-020-0436-6","volume":"3","author":"F Cai","year":"2020","unstructured":"Cai, F. et al. Power-efficient combinatorial optimization using intrinsic noise in memristor Hopfield neural networks. Nat. Electron. 3, 409\u2013418 (2020).","journal-title":"Nat. Electron."},{"key":"782_CR17","doi-asserted-by":"publisher","first-page":"363\u2013379","DOI":"10.1038\/s42254-022-00440-8","volume":"4","author":"N Mohseni","year":"2022","unstructured":"Mohseni, N., McMahon, P. L. & Byrnes, T. Ising machines as hardware solvers of combinatorial optimization problems. Nat. Rev. Phys. 4, 363\u2013379 (2022).","journal-title":"Nat. Rev. Phys."},{"key":"782_CR18","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/s10878-014-9734-0","volume":"28","author":"G Kochenberger","year":"2014","unstructured":"Kochenberger, G. et al. The unconstrained binary quadratic programming problem: a survey. J. Combin. Optim. 28, 58\u201381 (2014).","journal-title":"J. Combin. Optim."},{"key":"782_CR19","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"A Lucas","year":"2014","unstructured":"Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014).","journal-title":"Front. Phys."},{"key":"782_CR20","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1016\/0550-3213(85)90374-8","volume":"257","author":"E Gardner","year":"1985","unstructured":"Gardner, E. Spin glasses with p-spin interactions. Nucl. Phys. B 257, 747\u2013765 (1985).","journal-title":"Nucl. Phys. B"},{"key":"782_CR21","unstructured":"Karp, R. M. Reducibility among Combinatorial Problems (Springer, 2010)."},{"key":"782_CR22","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1103\/RevModPhys.54.235","volume":"54","author":"F-Y Wu","year":"1982","unstructured":"Wu, F.-Y. The Potts model. Rev. Mod. Phys. 54, 235\u2013268 (1982).","journal-title":"Rev. Mod. Phys."},{"key":"782_CR23","unstructured":"Jensen, T. R. & Toft, B. Graph Coloring Problems (John Wiley & Sons, 2011)."},{"key":"782_CR24","doi-asserted-by":"publisher","first-page":"8577","DOI":"10.1073\/pnas.0601602103","volume":"103","author":"ME Newman","year":"2006","unstructured":"Newman, M. E. Modularity and community structure in networks. Proc. Natl Acad. Sci. USA 103, 8577\u20138582 (2006).","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"782_CR25","unstructured":"Papadimitriou, C. & Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity (Dover Publications, 1998)."},{"key":"782_CR26","doi-asserted-by":"crossref","unstructured":"M\u00e9zard, M., Parisi, G. & Zecchina, R. Analytic and algorithmic solution of random satisfiability problems. Science 297, 812\u2013815 (2002).","DOI":"10.1126\/science.1073287"},{"key":"782_CR27","unstructured":"Chermoshentsev, D. A. et al. Polynomial unconstrained binary optimisation inspired by optical simulation. Preprint at https:\/\/arxiv.org\/abs\/2106.13167 (2021)."},{"key":"782_CR28","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-023-41214-9","volume":"14","author":"C Bybee","year":"2023","unstructured":"Bybee, C. et al. Efficient optimization with higher-order Ising machines. Nat. Commun. 14, 6033 (2023).","journal-title":"Nat. Commun."},{"key":"782_CR29","doi-asserted-by":"publisher","first-page":"014501","DOI":"10.35848\/1882-0786\/acaba9","volume":"16","author":"T Kanao","year":"2022","unstructured":"Kanao, T. & Goto, H. Simulated bifurcation for higher-order cost functions. Appl. Phys. Express 16, 014501 (2022).","journal-title":"Appl. Phys. Express"},{"key":"782_CR30","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1364\/AOP.475823","volume":"15","author":"S Reifenstein","year":"2023","unstructured":"Reifenstein, S. et al. Coherent SAT solvers: a tutorial. Adv. Opt. Photonics 15, 385\u2013441 (2023).","journal-title":"Adv. Opt. Photonics"},{"key":"782_CR31","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1038\/s42005-021-00655-8","volume":"4","author":"F B\u00f6hm","year":"2021","unstructured":"B\u00f6hm, F., Vaerenbergh, T. V., Verschaffelt, G. & Van der Sande, G. Order-of-magnitude differences in computational performance of analog Ising machines induced by the choice of nonlinearity. Commun. Phys. 4, 149 (2021).","journal-title":"Commun. Phys."},{"key":"782_CR32","doi-asserted-by":"publisher","first-page":"603606","DOI":"10.1126\/science.aah4243","volume":"354","author":"T Inagaki","year":"2016","unstructured":"Inagaki, T. et al. A coherent Ising machine for 2000-node optimization problems. Science 354, 603606 (2016).","journal-title":"Science"},{"key":"782_CR33","doi-asserted-by":"publisher","first-page":"367\u2013377","DOI":"10.1038\/s42256-022-00468-6","volume":"4","author":"MJ Schuetz","year":"2022","unstructured":"Schuetz, M. J., Brubaker, J. K. & Katzgraber, H. G. Combinatorial optimization with physics-inspired graph neural networks. Nat. Mach. Intell. 4, 367\u2013377 (2022).","journal-title":"Nat. Mach. Intell."},{"key":"782_CR34","doi-asserted-by":"crossref","unstructured":"Ushijima-Mwesigwa, H., Negre, C. F. & Mniszewski, S. M. Graph partitioning using quantum annealing on the D-wave system. In Proc. Second International Workshop on Post Moores Era Supercomputing 22\u201329 (Association for Computing Machinery, 2017).","DOI":"10.1145\/3149526.3149531"},{"key":"782_CR35","unstructured":"Walshaw, C. The graph partitioning archive. https:\/\/chriswalshaw.co.uk\/partition\/ (2023)."},{"key":"782_CR36","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis, G. & Kumar, V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359\u2013392 (1998).","journal-title":"SIAM J. Sci. Comput."},{"key":"782_CR37","doi-asserted-by":"crossref","unstructured":"Sanders, P. & Schulz, C. Think locally, act globally: highly balanced graph partitioning. In Experimental Algorithms. SEA 2013. Lecture Notes in Computer Science (eds Bonifaci, V., Demetrescu, C. & Marchetti-Spaccamela, A.) 164\u2013175 (Springer, 2013).","DOI":"10.1007\/978-3-642-38527-8_16"},{"key":"782_CR38","unstructured":"Schulz, C. KaHIP. GitHub https:\/\/github.com\/KaHIP\/KaHIP (2025)."},{"key":"782_CR39","unstructured":"Argelich, J., Li, C. M., Manya, F. & Planes, J. Max-SAT 2016. http:\/\/www.maxsat.udl.cat\/16\/benchmarks\/index.html (2016)."},{"key":"782_CR40","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-018-07327-2","volume":"9","author":"B Moln\u00e1r","year":"2018","unstructured":"Moln\u00e1r, B., Moln\u00e1r, F., Varga, M., Toroczkai, Z. & Ercsey-Ravasz, M. A continuous-time MaxSAT solver with high analog performance. Nat. Commun. 9, 4864 (2018).","journal-title":"Nat. Commun."},{"key":"782_CR41","doi-asserted-by":"publisher","first-page":"080602","DOI":"10.1103\/PhysRevLett.122.080602","volume":"122","author":"D Wu","year":"2019","unstructured":"Wu, D., Wang, L. & Zhang, P. Solving statistical mechanics using variational autoregressive networks. Phys. Rev. Lett. 122, 080602 (2019).","journal-title":"Phys. Rev. Lett."},{"key":"782_CR42","doi-asserted-by":"publisher","first-page":"952\u2013961","DOI":"10.1038\/s42256-021-00401-3","volume":"3","author":"M Hibat-Allah","year":"2021","unstructured":"Hibat-Allah, M., Inack, E. M., Wiersema, R., Melko, R. G. & Carrasquilla, J. Variational neural annealing. Nat. Mach. Intell. 3, 952\u2013961 (2021).","journal-title":"Nat. Mach. Intell."},{"key":"782_CR43","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","volume":"5","author":"PW Holland","year":"1983","unstructured":"Holland, P. W., Laskey, K. B. & Leinhardt, S. Stochastic blockmodels: first steps. Soc. Netw. 5, 109\u2013137 (1983).","journal-title":"Soc. Netw."},{"key":"782_CR44","doi-asserted-by":"publisher","first-page":"016107","DOI":"10.1103\/PhysRevE.83.016107","volume":"83","author":"B Karrer","year":"2011","unstructured":"Karrer, B. & Newman, M. E. Stochastic blockmodels and community structure in networks. Phys. Rev. E 83, 016107 (2011).","journal-title":"Phys. Rev. E"},{"key":"782_CR45","unstructured":"Cook, S. A. The complexity of theorem-proving procedures. In Logic, Automata, and Computational Complexity: The Works of Stephen A. Cook (ed Kapron, B. M.) 143-152 (Association for Computing Machinery, 2023)."},{"key":"782_CR46","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1051\/jphys:01984004505084300","volume":"45","author":"M M\u00e9zard","year":"1984","unstructured":"M\u00e9zard, M. et al. Replica symmetry breaking and the nature of the spin glass phase. J. Phys. 45, 843\u2013854 (1984).","journal-title":"J. Phys."},{"key":"782_CR47","doi-asserted-by":"crossref","unstructured":"M\u00e9zard, M., Parisi, G. & Virasoro, M. A. Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications Vol. 9 (World Scientific, 1987).","DOI":"10.1142\/0271"},{"key":"782_CR48","unstructured":"Bilbro, G. et al. Optimization by mean field annealing. In Advances in Neural Information Processing Systems (ed Touretzky, D.) (Morgan Kaufmann, 1988)."},{"key":"782_CR49","doi-asserted-by":"publisher","unstructured":"Shen, Z. ZisongShen\/Free_Energy_Machine. Zenodo https:\/\/doi.org\/10.5281\/zenodo.14874189 (2025).","DOI":"10.5281\/zenodo.14874189"}],"container-title":["Nature Computational Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/s43588-025-00782-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s43588-025-00782-0","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s43588-025-00782-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T22:02:11Z","timestamp":1745532131000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/s43588-025-00782-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,24]]},"references-count":49,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2025,4]]}},"alternative-id":["782"],"URL":"https:\/\/doi.org\/10.1038\/s43588-025-00782-0","relation":{},"ISSN":["2662-8457"],"issn-type":[{"value":"2662-8457","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,24]]},"assertion":[{"value":"9 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}