{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,5]],"date-time":"2026-11-05T03:24:10Z","timestamp":1793849050508,"version":"4.6.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T00:00:00Z","timestamp":1729123200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T00:00:00Z","timestamp":1729123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000006","name":"United States Department of Defense | United States Navy | Office of Naval Research","doi-asserted-by":"publisher","award":["N000142312708"],"award-info":[{"award-number":["N000142312708"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000028","name":"Semiconductor Research Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000028","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Commun"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Domain-specific hardware to solve computationally hard optimization problems has generated tremendous excitement. Here, we evaluate probabilistic bit (p-bit) based Ising Machines (IM) on the 3-Regular 3-Exclusive OR Satisfiability (3R3X), as a representative hard optimization problem. We first introduce a multiplexed architecture that emulates all-to-all network functionality while maintaining highly parallelized chromatic Gibbs sampling. We implement this architecture in a\u00a0single Field-Programmable Gate Array (FPGA) and show that running the adaptive parallel tempering algorithm demonstrates competitive algorithmic and prefactor advantages over alternative IMs by D-Wave, Toshiba, and Fujitsu. We also implement higher-order interactions that lead to better prefactors without changing algorithmic scaling for the XORSAT problem. Even though FPGA implementations of p-bits are still not quite as fast as the best possible greedy algorithms accelerated on Graphics Processing Units (GPU), scaled magnetic versions of p-bit IMs could lead to orders of magnitude improvements over the state of the art for generic optimization.<\/jats:p>","DOI":"10.1038\/s41467-024-53270-w","type":"journal-article","created":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T14:02:52Z","timestamp":1729173772000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":38,"title":["All-to-all reconfigurability with sparse and higher-order Ising machines"],"prefix":"10.1038","volume":"15","author":[{"given":"Srijan","family":"Nikhar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sidharth","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9933-0728","authenticated-orcid":false,"given":"Navid Anjum","family":"Aadit","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6325-0790","authenticated-orcid":false,"given":"Shuvro","family":"Chowdhury","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6876-8812","authenticated-orcid":false,"given":"Kerem Y.","family":"Camsari","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,10,17]]},"reference":[{"key":"53270_CR1","doi-asserted-by":"publisher","first-page":"363","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":"53270_CR2","doi-asserted-by":"crossref","unstructured":"Lo, H., Moy, W., Yu, H., Sapatnekar, S. & Kim, C. H. An Ising solver chip based on coupled ring oscillators with a 48-node all-to-all connected array architecture. Nat. Electron. 6, 771\u2013778 (2023).","DOI":"10.1038\/s41928-023-01021-y"},{"key":"53270_CR3","first-page":"a2","volume":"1","author":"R Hamerly","year":"2018","unstructured":"Hamerly, R. et al. Scaling advantages of all-to-all connectivity in physical annealers: the coherent Ising machine vs D-wave 2000Q. Feedback 1, a2 (2018).","journal-title":"Feedback"},{"key":"53270_CR4","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":"53270_CR5","doi-asserted-by":"publisher","first-page":"48","DOI":"10.3389\/fphy.2019.00048","volume":"7","author":"M Aramon","year":"2019","unstructured":"Aramon, M. et al. Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Front. Phys. 7, 48 (2019).","journal-title":"Front. Phys."},{"key":"53270_CR6","doi-asserted-by":"crossref","unstructured":"Wang, T. Oscillators do the hard bits. Nat. Electron. 6, 728\u2013729 (2023).","DOI":"10.1038\/s41928-023-01046-3"},{"key":"53270_CR7","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1038\/s41928-022-00774-2","volume":"5","author":"NavidAnjum Aadit","year":"2022","unstructured":"Aadit, NavidAnjum et al. Massively parallel probabilistic computing with sparse Ising machines. Nat. Electron. 5, 460\u2013468 (2022).","journal-title":"Nat. Electron."},{"key":"53270_CR8","unstructured":"Aarts, E. and Korst, J. Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. (John Wiley & Sons, Inc., 1989)."},{"key":"53270_CR9","doi-asserted-by":"publisher","first-page":"011003","DOI":"10.1103\/PhysRevApplied.12.011003","volume":"12","author":"I Hen","year":"2019","unstructured":"Hen, I. Equation planting: a tool for benchmarking Ising machines. Phys. Rev. Appl. 12, 011003 (2019).","journal-title":"Phys. Rev. Appl."},{"key":"53270_CR10","doi-asserted-by":"publisher","first-page":"025008","DOI":"10.1088\/2058-9565\/ac4d1b","volume":"7","author":"M Kowalsky","year":"2022","unstructured":"Kowalsky, M., Albash, T., Hen, I. & Lidar, D. A. 3-regular three-XORSAT planted solutions benchmark of classical and quantum heuristic optimizers. Quantum Sci. Technol. 7, 025008 (2022).","journal-title":"Quantum Sci. Technol."},{"key":"53270_CR11","doi-asserted-by":"crossref","unstructured":"Aadit, Navid Anjum, Mohseni, M. & Camsari, K. Y. Accelerating adaptive parallel tempering with FPGA-based p-bits. In 2023 IEEE Symposium on VLSI Technology and Circuits (VLSI Technology and Circuits), pp. 1\u20132. (IEEE, 2023).","DOI":"10.23919\/VLSITechnologyandCir57934.2023.10185207"},{"key":"53270_CR12","doi-asserted-by":"publisher","unstructured":"Mohseni, M. et al. Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization. Preprint at arXiv https:\/\/doi.org\/10.48550\/arXiv.2111.13628 (2021).","DOI":"10.48550\/arXiv.2111.13628"},{"key":"53270_CR13","doi-asserted-by":"publisher","unstructured":"Bauza, Humberto Munoz & Lidar, D. A. Scaling advantage in approximate optimization with quantum annealing. Preprint at arXiv https:\/\/doi.org\/10.48550\/arXiv.2401.07184 (2024).","DOI":"10.48550\/arXiv.2401.07184"},{"key":"53270_CR14","doi-asserted-by":"publisher","unstructured":"Aiken, J. & Traversa, F. L. Memcomputing for accelerated optimization. Preprint at arXiv https:\/\/doi.org\/10.48550\/arXiv.2003.10644 (2020).","DOI":"10.48550\/arXiv.2003.10644"},{"key":"53270_CR15","doi-asserted-by":"crossref","unstructured":"Matsubara, S. et al. Digital annealer for high-speed solving of combinatorial optimization problems and its applications. In 2020 25th Asia and South Pacific Design Automation Conference (ASP-DAC), pp. 667\u2013672. (IEEE, 2020).","DOI":"10.1109\/ASP-DAC47756.2020.9045100"},{"key":"53270_CR16","doi-asserted-by":"publisher","unstructured":"Boothby, K., Bunyk, P., Raymond, J. & Roy, A. Next-generation topology of d-wave quantum processors. Preprint at arXiv https:\/\/doi.org\/10.48550\/arXiv.2003.00133 (2020).","DOI":"10.48550\/arXiv.2003.00133"},{"key":"53270_CR17","doi-asserted-by":"publisher","first-page":"60005","DOI":"10.1209\/0295-5075\/133\/60005","volume":"133","author":"M Bernaschi","year":"2021","unstructured":"Bernaschi, M. et al. How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs (a). Europhys. Lett. 133, 60005 (2021).","journal-title":"Europhys. Lett."},{"key":"53270_CR18","unstructured":"Carlson, C., Frishberg, D. & Vigoda, E. Improved distributed algorithms for random colorings. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023) (2023)."},{"key":"53270_CR19","doi-asserted-by":"crossref","unstructured":"Borders, W. A. et al. Integer factorization using stochastic magnetic tunnel junctions. Nature 573, 390\u2013393 (2019).","DOI":"10.1038\/s41586-019-1557-9"},{"key":"53270_CR20","doi-asserted-by":"crossref","unstructured":"He, Y., Fang, C., Luo, S. & Liang, G. Many-body effects-based invertible logic with a simple energy landscape and high accuracy. IEEE J. Explor. Solid-State Comput. Devices Circuits 9, 83\u201391 (2023).","DOI":"10.1109\/JXCDC.2023.3320230"},{"key":"53270_CR21","doi-asserted-by":"crossref","unstructured":"Bybee, C. et al. Efficient optimization with higher-order ising machines. Nat. Commun. 14, 6033 (2023).","DOI":"10.1038\/s41467-023-41214-9"},{"key":"53270_CR22","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":"53270_CR23","doi-asserted-by":"crossref","unstructured":"Hizzani, M. et al. Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines. In 2024 IEEE International Symposium on Circuits and Systems (ISCAS) (2024).","DOI":"10.1109\/ISCAS58744.2024.10558658"},{"key":"53270_CR24","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1109\/LSSC.2023.3303332","volume":"6","author":"Y Su","year":"2023","unstructured":"Su, Y., Tae-Hyoung Kim, T. & Kim, B. A reconfigurable CMOS ising machine with three-body spin interactions for solving boolean satisfiability with direct mapping. IEEE Solid-State Circuits Lett. 6, 221\u2013224 (2023).","journal-title":"IEEE Solid-State Circuits Lett."},{"key":"53270_CR25","doi-asserted-by":"publisher","unstructured":"He, Y., Fang, C., Luo, S. & Liang, G. Logically synthesized invertible logic based on many-body effects with probabilistic-bit implementation. In 2023 Silicon Nanoelectronics Workshop (SNW), pp. 39\u201340. https:\/\/doi.org\/10.23919\/SNW57900.2023.10183978 (2023b).","DOI":"10.23919\/SNW57900.2023.10183978"},{"key":"53270_CR26","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-024-52488-y","volume":"15","author":"T Bhattacharya","year":"2024","unstructured":"Bhattacharya, T. et al. Computing high-degree polynomial gradients in memory. Nat. Commun. 15, 8211 (2024).","journal-title":"Nat. Commun."},{"key":"53270_CR27","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1038\/s42005-023-01202-3","volume":"6","author":"S Chowdhury","year":"2023","unstructured":"Chowdhury, S., Camsari, K. Y. & Datta, S. Accelerated quantum Monte Carlo with probabilistic computers. Commun. Phys. 6, 85 (2023).","journal-title":"Commun. Phys."},{"key":"53270_CR28","doi-asserted-by":"crossref","unstructured":"Chowdhury, S. et al. A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms. IEEE J. Explor. Solid-State Comput. Devices Circuits 9, 1\u201311 (2023).","DOI":"10.1109\/JXCDC.2023.3256981"},{"key":"53270_CR29","doi-asserted-by":"publisher","first-page":"1639","DOI":"10.1126\/science.1189804","volume":"330","author":"F Ricci-Tersenghi","year":"2010","unstructured":"Ricci-Tersenghi, F. Being glassy without being hard to solve. Science 330, 1639\u20131640 (2010).","journal-title":"Science"},{"key":"53270_CR30","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D Br\u00e9laz","year":"1979","unstructured":"Br\u00e9laz, D. New methods to color the vertices of a graph. Commun. ACM 22, 251\u2013256 (1979).","journal-title":"Commun. ACM"},{"key":"53270_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3460772","volume":"47","author":"D Blackman","year":"2021","unstructured":"Blackman, D. & Vigna, S. Scrambled linear pseudorandom number generators. ACM Trans. Math. Softw. (TOMS) 47, 1\u201332 (2021).","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"key":"53270_CR32","doi-asserted-by":"publisher","first-page":"157238","DOI":"10.1109\/ACCESS.2020.3018682","volume":"8","author":"B Sutton","year":"2020","unstructured":"Sutton, B. et al. Autonomous probabilistic coprocessing with petaflips per second. IEEE Access 8, 157238\u2013157252 (2020).","journal-title":"IEEE Access"},{"key":"53270_CR33","doi-asserted-by":"publisher","first-page":"1407","DOI":"10.1109\/TED.2020.2965403","volume":"67","author":"S Ikegawa","year":"2020","unstructured":"Ikegawa, S., Mancoff, F. B., Janesky, J. & Aggarwal, S. Magnetoresistive random access memory: present and future. IEEE Trans. Electron Devices 67, 1407\u20131419 (2020).","journal-title":"IEEE Trans. Electron Devices"},{"key":"53270_CR34","doi-asserted-by":"publisher","first-page":"117202","DOI":"10.1103\/PhysRevLett.126.117202","volume":"126","author":"K Hayakawa","year":"2021","unstructured":"Hayakawa, K. et al. Nanosecond random telegraph noise in in-plane magnetic tunnel junctions. Phys. Rev. Lett. 126, 117202 (2021).","journal-title":"Phys. Rev. Lett."},{"key":"53270_CR35","doi-asserted-by":"publisher","unstructured":"Neira, David E. Bernal et al. Benchmarking the operation of quantum heuristics and ising machines: scoring parameter setting strategies on optimization applications. Preprint at arXiv https:\/\/doi.org\/10.48550\/arXiv.2402.10255 (2024).","DOI":"10.48550\/arXiv.2402.10255"},{"key":"53270_CR36","doi-asserted-by":"publisher","unstructured":"Nikhar, S., Kannan, S., Aadit, Navid Anjum, Chowdhury, S. & Camsari, K. Y. Code and data for the 3R3X (XORSAT) problem with probabilistic bits. GitHub Repository https:\/\/doi.org\/10.5281\/zenodo.13839752 (2024).","DOI":"10.5281\/zenodo.13839752"}],"container-title":["Nature Communications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.nature.com\/articles\/s41467-024-53270-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41467-024-53270-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.nature.com\/articles\/s41467-024-53270-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,17]],"date-time":"2024-10-17T14:06:04Z","timestamp":1729173964000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.nature.com\/articles\/s41467-024-53270-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,17]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,12]]}},"alternative-id":["53270"],"URL":"https:\/\/doi.org\/10.1038\/s41467-024-53270-w","relation":{},"ISSN":["2041-1723"],"issn-type":[{"value":"2041-1723","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,17]]},"assertion":[{"value":"22 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2024","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"}}],"article-number":"8977"}}