Daily News

Free-energy machine for combinatorial optimization

Abstract

Finding optimal solutions to combinatorial optimization problems (COPs) is pivotal in both scientific and industrial domains. Considerable efforts have been invested on developing accelerated methods utilizing sophisticated models and advanced computational hardware. However, the challenge remains to achieve both high efficiency and broad generality in problem-solving. Here we propose a general method, free-energy machine (FEM), based on the ideas of free-energy minimization in statistical physics, combined with automatic differentiation and gradient-based optimization in machine learning. FEM flexibly addresses various COPs within a unified framework and efficiently leverages parallel computational devices such as graphics processing units. We benchmark FEM on diverse COPs including maximum cut, balanced minimum cut and maximum k-satisfiability, scaled to millions of variables, across synthetic and real-world instances. The findings indicate that FEM remarkably outperforms state-of-the-art algorithms tailored for individual COP in both efficiency and efficacy, demonstrating the potential of combining statistical physics and machine learning for broad applications.

This is a preview of subscription content, access via your institution

Access options

/* style specs start */

/* style specs end */

Buy this article

  • Purchase on SpringerLink
  • Instant access to full article PDF
Buy now

Prices may be subject to local taxes which are calculated during checkout

/* style specs start */
style {
display: none !important;
}
.LiveAreaSection * {
align-content: stretch;
align-items: stretch;
align-self: auto;
animation-delay: 0s;
animation-direction: normal;
animation-duration: 0s;
animation-fill-mode: none;
animation-iteration-count: 1;
animation-name: none;
animation-play-state: running;
animation-timing-function: ease;
azimuth: center;
backface-visibility: visible;
background-attachment: scroll;
background-blend-mode: normal;
background-clip: borderBox;
background-color: transparent;
background-image: none;
background-origin: paddingBox;
background-position: 0 0;
background-repeat: repeat;
background-size: auto auto;
block-size: auto;
border-block-end-color: currentcolor;
border-block-end-style: none;
border-block-end-width: medium;
border-block-start-color: currentcolor;
border-block-start-style: none;
border-block-start-width: medium;
border-bottom-color: currentcolor;
border-bottom-left-radius: 0;
border-bottom-right-radius: 0;
border-bottom-style: none;
border-bottom-width: medium;
border-collapse: separate;
border-image-outset: 0s;
border-image-repeat: stretch;
border-image-slice: 100%;
border-image-source: none;
border-image-width: 1;
border-inline-end-color: currentcolor;
border-inline-end-style: none;
border-inline-end-width: medium;
border-inline-start-color: currentcolor;
border-inline-start-style: none;
border-inline-start-width: medium;
border-left-color: currentcolor;
border-left-style: none;
border-left-width: medium;
border-right-color: currentcolor;
border-right-style: none;
border-right-width: medium;
border-spacing: 0;
border-top-color: currentcolor;
border-top-left-radius: 0;
border-top-right-radius: 0;
border-top-style: none;
border-top-width: medium;
bottom: auto;
box-decoration-break: slice;
box-shadow: none;
box-sizing: border-box;
break-after: auto;
break-before: auto;
break-inside: auto;
caption-side: top;
caret-color: auto;
clear: none;
clip: auto;
clip-path: none;
color: initial;
column-count: auto;
column-fill: balance;
column-gap: normal;
column-rule-color: currentcolor;
column-rule-style: none;
column-rule-width: medium;
column-span: none;
column-width: auto;
content: normal;
counter-increment: none;
counter-reset: none;
cursor: auto;
display: inline;
empty-cells: show;
filter: none;
flex-basis: auto;
flex-direction: row;
flex-grow: 0;
flex-shrink: 1;
flex-wrap: nowrap;
float: none;
font-family: initial;
font-feature-settings: normal;
font-kerning: auto;
font-language-override: normal;
font-size: medium;
font-size-adjust: none;
font-stretch: normal;
font-style: normal;
font-synthesis: weight style;
font-variant: normal;
font-variant-alternates: normal;
font-variant-caps: normal;
font-variant-east-asian: normal;
font-variant-ligatures: normal;
font-variant-numeric: normal;
font-variant-position: normal;
font-weight: 400;
grid-auto-columns: auto;
grid-auto-flow: row;
grid-auto-rows: auto;
grid-column-end: auto;
grid-column-gap: 0;
grid-column-start: auto;
grid-row-end: auto;
grid-row-gap: 0;
grid-row-start: auto;
grid-template-areas: none;
grid-template-columns: none;
grid-template-rows: none;
height: auto;
hyphens: manual;
image-orientation: 0deg;
image-rendering: auto;
image-resolution: 1dppx;
ime-mode: auto;
inline-size: auto;
isolation: auto;
justify-content: flexStart;
left: auto;
letter-spacing: normal;
line-break: auto;
line-height: normal;
list-style-image: none;
list-style-position: outside;
list-style-type: disc;
margin-block-end: 0;
margin-block-start: 0;
margin-bottom: 0;
margin-inline-end: 0;
margin-inline-start: 0;
margin-left: 0;
margin-right: 0;
margin-top: 0;
mask-clip: borderBox;
mask-composite: add;
mask-image: none;
mask-mode: matchSource;
mask-origin: borderBox;
mask-position: 0 0;
mask-repeat: repeat;
mask-size: auto;
mask-type: luminance;
max-height: none;
max-width: none;
min-block-size: 0;
min-height: 0;
min-inline-size: 0;
min-width: 0;
mix-blend-mode: normal;
object-fit: fill;
object-position: 50% 50%;
offset-block-end: auto;
offset-block-start: auto;
offset-inline-end: auto;
offset-inline-start: auto;
opacity: 1;
order: 0;
orphans: 2;
outline-color: initial;
outline-offset: 0;
outline-style: none;
outline-width: medium;
overflow: visible;
overflow-wrap: normal;
overflow-x: visible;
overflow-y: visible;
padding-block-end: 0;
padding-block-start: 0;
padding-bottom: 0;
padding-inline-end: 0;
padding-inline-start: 0;
padding-left: 0;
padding-right: 0;
padding-top: 0;
page-break-after: auto;
page-break-before: auto;
page-break-inside: auto;
perspective: none;
perspective-origin: 50% 50%;
pointer-events: auto;
position: static;
quotes: initial;
resize: none;
right: auto;
ruby-align: spaceAround;
ruby-merge: separate;
ruby-position: over;
scroll-behavior: auto;
scroll-snap-coordinate: none;
scroll-snap-destination: 0 0;
scroll-snap-points-x: none;
scroll-snap-points-y: none;
scroll-snap-type: none;
shape-image-threshold: 0;
shape-margin: 0;
shape-outside: none;
tab-size: 8;
table-layout: auto;
text-align: initial;
text-align-last: auto;
text-combine-upright: none;
text-decoration-color: currentcolor;
text-decoration-line: none;
text-decoration-style: solid;
text-emphasis-color: currentcolor;
text-emphasis-position: over right;
text-emphasis-style: none;
text-indent: 0;
text-justify: auto;
text-orientation: mixed;
text-overflow: clip;
text-rendering: auto;
text-shadow: none;
text-transform: none;
text-underline-position: auto;
top: auto;
touch-action: auto;
transform: none;
transform-box: borderBox;
transform-origin: 50% 50%0;
transform-style: flat;
transition-delay: 0s;
transition-duration: 0s;
transition-property: all;
transition-timing-function: ease;
vertical-align: baseline;
visibility: visible;
white-space: normal;
widows: 2;
width: auto;
will-change: auto;
word-break: normal;
word-spacing: normal;
word-wrap: normal;
writing-mode: horizontalTb;
z-index: auto;
-webkit-appearance: none;
-moz-appearance: none;
-ms-appearance: none;
appearance: none;
margin: 0;
}
.LiveAreaSection {
width: 100%;
}
.LiveAreaSection .login-option-buybox {
display: block;
width: 100%;
font-size: 17px;
line-height: 30px;
color: #222;
padding-top: 30px;
font-family: Harding, Palatino, serif;
}
.LiveAreaSection .additional-access-options {
display: block;
font-weight: 700;
font-size: 17px;
line-height: 30px;
color: #222;
font-family: Harding, Palatino, serif;
}
.LiveAreaSection .additional-login > li:not(:first-child)::before {
transform: translateY(-50%);
content: “”;
height: 1rem;
position: absolute;
top: 50%;
left: 0;
border-left: 2px solid #999;
}
.LiveAreaSection .additional-login > li:not(:first-child) {
padding-left: 10px;
}
.LiveAreaSection .additional-login > li {
display: inline-block;
position: relative;
vertical-align: middle;
padding-right: 10px;
}
.BuyBoxSection {
display: flex;
flex-wrap: wrap;
flex: 1;
flex-direction: row-reverse;
margin: -30px -15px 0;
}
.BuyBoxSection .box-inner {
width: 100%;
height: 100%;
padding: 30px 5px;
display: flex;
flex-direction: column;
justify-content: space-between;
}
.BuyBoxSection p {
margin: 0;
}
.BuyBoxSection .readcube-buybox {
background-color: #f3f3f3;
flex-shrink: 1;
flex-grow: 1;
flex-basis: 255px;
background-clip: content-box;
padding: 0 15px;
margin-top: 30px;
}
.BuyBoxSection .subscribe-buybox {
background-color: #f3f3f3;
flex-shrink: 1;
flex-grow: 4;
flex-basis: 300px;
background-clip: content-box;
padding: 0 15px;
margin-top: 30px;
}
.BuyBoxSection .subscribe-buybox-nature-plus {
background-color: #f3f3f3;
flex-shrink: 1;
flex-grow: 4;
flex-basis: 100%;
background-clip: content-box;
padding: 0 15px;
margin-top: 30px;
}
.BuyBoxSection .title-readcube,
.BuyBoxSection .title-buybox {
display: block;
margin: 0;
margin-right: 10%;
margin-left: 10%;
font-size: 24px;
line-height: 32px;
color: #222;
text-align: center;
font-family: Harding, Palatino, serif;
}
.BuyBoxSection .title-asia-buybox {
display: block;
margin: 0;
margin-right: 5%;
margin-left: 5%;
font-size: 24px;
line-height: 32px;
color: #222;
text-align: center;
font-family: Harding, Palatino, serif;
}
.BuyBoxSection .asia-link,
.Link-328123652,
.Link-2926870917,
.Link-2291679238,
.Link-595459207 {
color: #069;
cursor: pointer;
text-decoration: none;
font-size: 1.05em;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
line-height: 1.05em6;
}
.BuyBoxSection .access-readcube {
display: block;
margin: 0;
margin-right: 10%;
margin-left: 10%;
font-size: 14px;
color: #222;
padding-top: 10px;
text-align: center;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
line-height: 20px;
}
.BuyBoxSection ul {
margin: 0;
}
.BuyBoxSection .link-usp {
display: list-item;
margin: 0;
margin-left: 20px;
padding-top: 6px;
list-style-position: inside;
}
.BuyBoxSection .link-usp span {
font-size: 14px;
color: #222;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
line-height: 20px;
}
.BuyBoxSection .access-asia-buybox {
display: block;
margin: 0;
margin-right: 5%;
margin-left: 5%;
font-size: 14px;
color: #222;
padding-top: 10px;
text-align: center;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
line-height: 20px;
}
.BuyBoxSection .access-buybox {
display: block;
margin: 0;
margin-right: 10%;
margin-left: 10%;
font-size: 14px;
color: #222;
opacity: 0.8px;
padding-top: 10px;
text-align: center;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
line-height: 20px;
}
.BuyBoxSection .price-buybox {
display: block;
font-size: 30px;
color: #222;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
padding-top: 30px;
text-align: center;
}
.BuyBoxSection .price-buybox-to {
display: block;
font-size: 30px;
color: #222;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
text-align: center;
}
.BuyBoxSection .price-info-text {
font-size: 16px;
padding-right: 10px;
color: #222;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
}
.BuyBoxSection .price-value {
font-size: 30px;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
}
.BuyBoxSection .price-per-period {
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
}
.BuyBoxSection .price-from {
font-size: 14px;
padding-right: 10px;
color: #222;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
line-height: 20px;
}
.BuyBoxSection .issue-buybox {
display: block;
font-size: 13px;
text-align: center;
color: #222;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
line-height: 19px;
}
.BuyBoxSection .no-price-buybox {
display: block;
font-size: 13px;
line-height: 18px;
text-align: center;
padding-right: 10%;
padding-left: 10%;
padding-bottom: 20px;
padding-top: 30px;
color: #222;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
}
.BuyBoxSection .vat-buybox {
display: block;
margin-top: 5px;
margin-right: 20%;
margin-left: 20%;
font-size: 11px;
color: #222;
padding-top: 10px;
padding-bottom: 15px;
text-align: center;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
line-height: 17px;
}
.BuyBoxSection .tax-buybox {
display: block;
width: 100%;
color: #222;
padding: 20px 16px;
text-align: center;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
line-height: NaNpx;
}
.BuyBoxSection .button-container {
display: flex;
padding-right: 20px;
padding-left: 20px;
justify-content: center;
}
.BuyBoxSection .button-container > * {
flex: 1px;
}
.BuyBoxSection .button-container > a:hover,
.Button-505204839:hover,
.Button-1078489254:hover,
.Button-2737859108:hover {
text-decoration: none;
}
.BuyBoxSection .btn-secondary {
background: #fff;
}
.BuyBoxSection .button-asia {
background: #069;
border: 1px solid #069;
border-radius: 0;
cursor: pointer;
display: block;
padding: 9px;
outline: 0;
text-align: center;
text-decoration: none;
min-width: 80px;
margin-top: 75px;
}
.BuyBoxSection .button-label-asia,
.ButtonLabel-3869432492,
.ButtonLabel-3296148077,
.ButtonLabel-1636778223 {
display: block;
color: #fff;
font-size: 17px;
line-height: 20px;
font-family: -apple-system, BlinkMacSystemFont, “Segoe UI”, Roboto,
Oxygen-Sans, Ubuntu, Cantarell, “Helvetica Neue”, sans-serif;
text-align: center;
text-decoration: none;
cursor: pointer;
}
.Button-505204839,
.Button-1078489254,
.Button-2737859108 {
background: #069;
border: 1px solid #069;
border-radius: 0;
cursor: pointer;
display: block;
padding: 9px;
outline: 0;
text-align: center;
text-decoration: none;
min-width: 80px;
max-width: 320px;
margin-top: 20px;
}
.Button-505204839 .btn-secondary-label,
.Button-1078489254 .btn-secondary-label,
.Button-2737859108 .btn-secondary-label {
color: #069;
}
.uList-2102244549 {
list-style: none;
padding: 0;
margin: 0;
}
/* style specs end */

Fig. 1: The principle and framework of FEM in solving COPs.
Fig. 2: Benchmarking results for the MaxCut problem.
Fig. 3: The scalability test of FEM in the q-way bMinCut problems on the Erdös–Rényi random graphs.
Fig. 4: The application of FEM in large-scale FPGA-chip verification tasks.
Fig. 5: Benchmarking results on the MaxSAT 2016 competition problems.

Data availability

The datasets utilized in this study for benchmarking the MaxCut (K2,000 and G-set), bMinCut (four real-world graphs from C. Walshaw’s archive and four generated Erdös–Rényi random graphs) and MaxSAT (454 MaxSAT 2016 competition instances) problems are publicly available via Zenodo at https://doi.org/10.5281/zenodo.14874189 (ref. 49). We are unable to publish the dataset of the FPGA-chip operator graph as it is closely tied to the proprietary product information of Huawei Technologies Co., Ltd. Source data are provided with this paper.

Code availability

The source code for this Article is publicly available via GitHub at https://github.com/Fanerst/FEM and Zenodo at https://doi.org/10.5281/zenodo.14874189 (ref. 49).

References

  1. Du, D. & Pardalos, P. M. Handbook of Combinatorial Optimization vol. 4 (Springer Science & Business Media, 1998).

  2. Arora, S. & Barak, B. Computational Complexity: A Modern Approach (Cambridge Univ. Press, 2009).

  3. Kirkpatrick, S., Gelatt Jr, C. D. & Vecchi, M. P. Optimization by simulated annealing. Science 220, 671–680 (1983).

  4. Selman, B. et al. Noise strategies for improving local search. AAAI 94, 337–343 (1994).

    MATH 

    Google Scholar 

  5. Glover, F. & Laguna, M. Tabu Search (Springer, 1998).

  6. Boettcher, S. & Percus, A. G. Optimization with extremal dynamics. Phys. Rev. Lett. 86, 5211-5214 (2001).

  7. Barahona, F. On the computational complexity of Ising spin glass models. J. Phys. A 15, 3241 (1982).

    Article 
    MathSciNet 
    MATH 

    Google Scholar 

  8. Tiunov, E. S., Ulanov, A. E. & Lvovsky, A. Annealing by simulating the coherent Ising machine. Optics Express 27, 10288–10295 (2019).

  9. 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).

  10. Goto, H., Tatsumura, K. & Dixon, A. R. Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems. Sci. Adv. 5, eaav2372 (2019).

    Article 
    MATH 

    Google Scholar 

  11. Goto, H. et al. High-performance combinatorial optimization based on classical mechanics. Sci. Adv. 7, eabe7953 (2021).

    Article 
    MATH 

    Google Scholar 

  12. Johnson, M. W. et al. Quantum annealing with manufactured spins. Nature 473, 194–198 (2011).

    Article 
    MATH 

    Google Scholar 

  13. Inagaki, T. et al. Large-scale Ising spin network based on degenerate optical parametric oscillators. Nat. Photonics 10, 415–419 (2016).

    Article 
    MATH 

    Google Scholar 

  14. Honjo, T. et al. 100,000-spin coherent Ising machine. Sci. Adv. 7, eabh0952 (2021).

    Article 

    Google Scholar 

  15. Pierangeli, D., Marcucci, G. & Conti, C. Large-scale photonic Ising machine by spatial light modulation. Phys. Rev. Lett. 122, 213902 (2019).

    Article 

    Google Scholar 

  16. Cai, F. et al. Power-efficient combinatorial optimization using intrinsic noise in memristor Hopfield neural networks. Nat. Electron. 3, 409–418 (2020).

    Article 
    MATH 

    Google Scholar 

  17. Mohseni, N., McMahon, P. L. & Byrnes, T. Ising machines as hardware solvers of combinatorial optimization problems. Nat. Rev. Phys. 4, 363–379 (2022).

    Article 
    MATH 

    Google Scholar 

  18. Kochenberger, G. et al. The unconstrained binary quadratic programming problem: a survey. J. Combin. Optim. 28, 58–81 (2014).

    Article 
    MathSciNet 
    MATH 

    Google Scholar 

  19. Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014).

    Article 
    MATH 

    Google Scholar 

  20. Gardner, E. Spin glasses with p-spin interactions. Nucl. Phys. B 257, 747–765 (1985).

    Article 
    MathSciNet 
    MATH 

    Google Scholar 

  21. Karp, R. M. Reducibility among Combinatorial Problems (Springer, 2010).

  22. Wu, F.-Y. The Potts model. Rev. Mod. Phys. 54, 235–268 (1982).

    Article 
    MathSciNet 
    MATH 

    Google Scholar 

  23. Jensen, T. R. & Toft, B. Graph Coloring Problems (John Wiley & Sons, 2011).

  24. Newman, M. E. Modularity and community structure in networks. Proc. Natl Acad. Sci. USA 103, 8577–8582 (2006).

    Article 
    MATH 

    Google Scholar 

  25. Papadimitriou, C. & Steiglitz, K. Combinatorial Optimization: Algorithms and Complexity (Dover Publications, 1998).

  26. Mézard, M., Parisi, G. & Zecchina, R. Analytic and algorithmic solution of random satisfiability problems. Science 297, 812–815 (2002).

  27. Chermoshentsev, D. A. et al. Polynomial unconstrained binary optimisation inspired by optical simulation. Preprint at https://arxiv.org/abs/2106.13167 (2021).

  28. Bybee, C. et al. Efficient optimization with higher-order Ising machines. Nat. Commun. 14, 6033 (2023).

    Article 
    MATH 

    Google Scholar 

  29. Kanao, T. & Goto, H. Simulated bifurcation for higher-order cost functions. Appl. Phys. Express 16, 014501 (2022).

    Article 
    MATH 

    Google Scholar 

  30. Reifenstein, S. et al. Coherent SAT solvers: a tutorial. Adv. Opt. Photonics 15, 385–441 (2023).

    Article 
    MATH 

    Google Scholar 

  31. Böhm, 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).

    Article 

    Google Scholar 

  32. Inagaki, T. et al. A coherent Ising machine for 2000-node optimization problems. Science 354, 603606 (2016).

    Article 
    MATH 

    Google Scholar 

  33. Schuetz, M. J., Brubaker, J. K. & Katzgraber, H. G. Combinatorial optimization with physics-inspired graph neural networks. Nat. Mach. Intell. 4, 367–377 (2022).

    Article 
    MATH 

    Google Scholar 

  34. 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–29 (Association for Computing Machinery, 2017).

  35. Walshaw, C. The graph partitioning archive. https://chriswalshaw.co.uk/partition/ (2023).

  36. Karypis, G. & Kumar, V. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359–392 (1998).

    Article 
    MathSciNet 
    MATH 

    Google Scholar 

  37. 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–175 (Springer, 2013).

  38. Schulz, C. KaHIP. GitHub https://github.com/KaHIP/KaHIP (2025).

  39. Argelich, J., Li, C. M., Manya, F. & Planes, J. Max-SAT 2016. http://www.maxsat.udl.cat/16/benchmarks/index.html (2016).

  40. Molnár, B., Molnár, F., Varga, M., Toroczkai, Z. & Ercsey-Ravasz, M. A continuous-time MaxSAT solver with high analog performance. Nat. Commun. 9, 4864 (2018).

    Article 
    MATH 

    Google Scholar 

  41. Wu, D., Wang, L. & Zhang, P. Solving statistical mechanics using variational autoregressive networks. Phys. Rev. Lett. 122, 080602 (2019).

    Article 
    MATH 

    Google Scholar 

  42. Hibat-Allah, M., Inack, E. M., Wiersema, R., Melko, R. G. & Carrasquilla, J. Variational neural annealing. Nat. Mach. Intell. 3, 952–961 (2021).

    Article 
    MATH 

    Google Scholar 

  43. Holland, P. W., Laskey, K. B. & Leinhardt, S. Stochastic blockmodels: first steps. Soc. Netw. 5, 109–137 (1983).

    Article 
    MathSciNet 
    MATH 

    Google Scholar 

  44. Karrer, B. & Newman, M. E. Stochastic blockmodels and community structure in networks. Phys. Rev. E 83, 016107 (2011).

    Article 
    MathSciNet 
    MATH 

    Google Scholar 

  45. 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).

  46. Mézard, M. et al. Replica symmetry breaking and the nature of the spin glass phase. J. Phys. 45, 843–854 (1984).

    Article 
    MathSciNet 
    MATH 

    Google Scholar 

  47. Mézard, 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).

  48. Bilbro, G. et al. Optimization by mean field annealing. In Advances in Neural Information Processing Systems (ed Touretzky, D.) (Morgan Kaufmann, 1988).

  49. Shen, Z. ZisongShen/Free_Energy_Machine. Zenodo https://doi.org/10.5281/zenodo.14874189 (2025).

Download references

Acknowledgements

We thank Y. Tang for helpful discussions. This work is supported by projects 12325501, 12047503 and 12247104 of the National Natural Science Foundation of China and project ZDRW-XX-2022-3-02 of the Chinese Academy of Sciences. P.Z. is partially supported by the Innovation Program for Quantum Science and Technology project 2021ZD0301900.

Author information

Author notes

  1. These authors contributed equally: Zi-Song Shen, Feng Pan, Yao Wang.

Authors and Affiliations

  1. CAS Key Laboratory for Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing, China

    Zi-Song Shen, Feng Pan, Yi-Ding Men, Wen-Biao Xu & Pan Zhang

  2. School of Physical Sciences, University of Chinese Academy of Sciences, Beijing, China

    Zi-Song Shen, Yi-Ding Men & Wen-Biao Xu

  3. 2012 Lab, Huawei Technologies Co., Ltd., Shenzhen, China

    Yao Wang & Man-Hong Yung

  4. School of Fundamental Physics and Mathematical Sciences, Hangzhou Institute for Advanced Study, UCAS, Hangzhou, China

    Yi-Ding Men, Wen-Biao Xu & Pan Zhang

Authors

  1. Zi-Song Shen
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Feng Pan
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Yao Wang
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Yi-Ding Men
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Wen-Biao Xu
    View author publications

    You can also search for this author inPubMed Google Scholar

  6. Man-Hong Yung
    View author publications

    You can also search for this author inPubMed Google Scholar

  7. Pan Zhang
    View author publications

    You can also search for this author inPubMed Google Scholar

Contributions

P.Z. proposed the idea and helped to guide and interpret it. Z.-S.S., F.P. and P.Z. implemented the code, Z.-S.S., Y.-D.M., W.-B.X., Y.W. and M.-H.Y. contributed to the numerical experiments and the analysis of the experimental data. Z.-S.S., F.P. and P.Z. wrote and revised the manuscript.

Corresponding author

Correspondence to
Pan Zhang.

Ethics declarations

Competing interests

The authors declare no competing interests.

Peer review

Peer review information

Nature Computational Science thanks the anonymous reviewer(s) for their contribution to the peer review of this work. Primary Handling Editor: Jie Pan, in collaboration with the Nature Computational Science team.

Additional information

Publisher’s note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary information

Supplementary Information

Supplementary Notes 1–9.

Source data

Source Data Fig. 1

Statistical source data.

Source Data Fig. 2

Statistical source data.

Source Data Fig. 3

Statistical source data.

Source Data Fig. 4

Statistical source data.

Source Data Fig. 5

Statistical source data.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shen, ZS., Pan, F., Wang, Y. et al. Free-energy machine for combinatorial optimization.
Nat Comput Sci (2025). https://doi.org/10.1038/s43588-025-00782-0

Download citation

  • Received: 09 July 2024

  • Accepted: 19 February 2025

  • Published: 24 March 2025

  • DOI: https://doi.org/10.1038/s43588-025-00782-0

news

Leave a Reply

Your email address will not be published. Required fields are marked *