Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Efficient optimization with higher-order ising machines
University of California, USA.
RISE Research Institutes of Sweden, Digital Systems, Data Science. University of California, USA.ORCID iD: 0000-0002-6032-6155
Intel, USA.
University of California, USA; Intel, USA.
Show others and affiliations
2023 (English)In: Nature Communications, E-ISSN 2041-1723, Vol. 14, article id 6033Article in journal (Refereed) Published
Abstract [en]

A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Boolean k-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines. 

Place, publisher, year, edition, pages
Nature Research , 2023. Vol. 14, article id 6033
Keywords [en]
metal oxide, benchmarking; data set; hardware; optimization, Article; data availability; decomposition; machine; model; process optimization; satisfaction; simulated annealing
National Category
Physical Sciences
Identifiers
URN: urn:nbn:se:ri:diva-67762DOI: 10.1038/s41467-023-41214-9Scopus ID: 2-s2.0-85172783609OAI: oai:DiVA.org:ri-67762DiVA, id: diva2:1815666
Note

C.B. acknowledges support from the National Science Foundation (NSF) through an NSF Graduate Research Fellowships Program (GRFP) fellowship (DGE 1752814) and an Intel Corporation research grant. D.K. acknowledges support from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 839179. F.T.S. was supported by NSF Grant IIS1718991 and NIH Grant 1R01EB026955. B.A.O. was supported by NSF EAGER grant 2147640.

Available from: 2023-11-29 Created: 2023-11-29 Last updated: 2023-12-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Kleyko, Denis

Search in DiVA

By author/editor
Kleyko, Denis
By organisation
Data Science
In the same journal
Nature Communications
Physical Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 3 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf