Top

Natural Computing

09-04-2024

Scalable almost-linear dynamical Ising machines

Authors: Aditya Shukla, Mikhail Erementchouk, Pinaki Mazumder

Published in: Natural Computing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The past decade has seen the emergence of Ising machines targeting hard combinatorial optimization problems by minimizing the Ising Hamiltonian with spins represented by continuous dynamical variables. However, capabilities of these machines at larger scales are yet to be fully explored. We introduce and investigate an almost-linear Ising machine, a machine based on a network of analog spins with piece-wise linear coupling. We show that such networks leverage the computational resource similar to that of the semidefinite positive relaxation of the Ising model. We estimate the expected performance of the almost-linear machine and benchmark it on a set of \(\left\{ 0, 1\right\}\)-weighted graphs. We show that the running time of the investigated machine scales polynomially (linearly with the number of edges in the connectivity graph). As an example of the physical realization of the machine, we present a CMOS-compatible implementation comprising an array of vertices efficiently storing the continuous spins on charged capacitors and communicating externally via analog current.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Babbush R, Perdomo-Ortiz A, O’Gorman B, Macready W, Aspuru-Guzik A (2014) Construction of energy functions for lattice heteropolymer models: efficient encodings for constraint satisfaction programming and quantum annealing. 201–244. https://doi.org/10.1002/9781118755815.ch05

Fraenkel AS (1993) Complexity of protein folding. Bull Math Biol 55(6):1199–1210. https://doi.org/10.1007/BF02460704CrossRef

Wang J, MacKenzie JD, Ramachandran R, Zhang Y, Wang H, Chen DZ (2015) Segmenting subcellular structures in histology tissue images. In: 2015 IEEE 12th international symposium on biomedical imaging (ISBI), pp 556–559. https://doi.org/10.1109/ISBI.2015.7163934

Barahona F (1982) On the computational complexity of Ising spin glass models. J Phys A Math Gen 15(10):3241–3253. https://doi.org/10.1088/0305-4470/15/10/028MathSciNetCrossRef

Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations. Springer, Boston, pp 85–103. https://doi.org/10.1007/978-1-4684-2001-2_9CrossRef

Garey MR, Johnson DS, Stockmeyer L (1976) Some simplified NP-complete graph problems. Theoret Comput Sci 1(3):237–267. https://doi.org/10.1016/0304-3975(76)90059-1MathSciNetCrossRef

Lucas A (2014) Ising formulations of many NP problems. Front Phys 2:5. https://doi.org/10.3389/fphy.2014.00005CrossRef

Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220(4598):671–680. https://doi.org/10.1126/science.220.4598.671MathSciNetCrossRef

Yamaoka M, Yoshimura C, Hayashi M, Okuyama T, Aoki H, Mizuno H (2015) 20k-spin Ising chip for combinational optimization problem with CMOS annealing. In: Digest of technical papers—IEEE international solid-state circuits conference, vol 58, pp 432–433. https://doi.org/10.1109/ISSCC.2015.7063111

Takemoto T, Hayashi M, Yoshimura C, Yamaoka M (2020) A 2 x 30k-spin multi-chip scalable CMOS annealing processor based on a processing-in-memory approach for solving large-scale combinatorial optimization problems. IEEE J Solid-State Circuits 55(1):145–156. https://doi.org/10.1109/JSSC.2019.2949230CrossRef

Su Y, Kim H, Kim B (2020) 31.2 CIM-Spin: A 0.5-to-1.2V scalable annealing processor using digital compute-in-memory spin operators and register-based spins for combinatorial optimization problems. In: 2020 IEEE international solid-state circuits conference—(ISSCC), pp 480–482. https://doi.org/10.1109/ISSCC19947.2020.9062938

Takemoto T, Yamamoto K, Yoshimura C, Hayashi M, Tada M, Saito H, Mashimo M, Yamaoka M (2021) 4.6 A 144kb annealing system composed of \(9\times\)16Kb annealing processor chips with scalable chip-to-chip connections for large-scale combinatorial optimization problems. In: 2021 IEEE international solid-state circuits conference (ISSCC), vol 64, pp 64–66. https://doi.org/10.1109/ISSCC42613.2021.9365748

Okuyama T, Yoshimura C, Hayashi M, Yamaoka M (2016) Computing architecture to perform approximated simulated annealing for Ising models. In: 2016 IEEE international conference on rebooting computing (ICRC), pp 1–8. https://doi.org/10.1109/ICRC.2016.7738673

Yamamoto K, Huang W, Takamaeda-Yamazaki S, Ikebe M, Asai T, Motomura M (2017) A time-division multiplexing Ising machine on FPGAs. In: ACM international conference proceeding series. https://doi.org/10.1145/3120895.3120905

Ahmed I, Chiu PW, Moy W, Kim CH (2021) A probabilistic compute fabric based on coupled ring oscillators for solving combinatorial optimization problems. IEEE J Solid-State Circuits. https://doi.org/10.1109/JSSC.2021.3062821CrossRef

Bashar MK, Mallick A, Truesdell DS, Calhoun BH, Joshi S, Shukla N (2020) Experimental demonstration of a reconfigurable coupled oscillator platform to solve the max-cut problem. IEEE J Explor Solid-State Comput Devices Circuits 6(2):116–121. https://doi.org/10.1109/JXCDC.2020.3025994CrossRef

Parihar A, Shukla N, Jerry M, Datta S, Raychowdhury A (2017) Vertex coloring of graphs via phase dynamics of coupled oscillatory networks. Sci Rep 7(1):911. https://doi.org/10.1038/s41598-017-00825-1CrossRef

Raychowdhury A, Parihar A, Smith GH, Narayanan V, Csaba G, Jerry M, Porod W, Datta S (2019) Computing with networks of oscillatory dynamical systems. Proc IEEE 107(1):73–89. https://doi.org/10.1109/JPROC.2018.2878854CrossRef

Marandi A, Wang Z, Takata K, Byer RL, Yamamoto Y (2014) Network of time-multiplexed optical parametric oscillators as a coherent Ising machine. Nat Photonics 8(12):937–942. https://doi.org/10.1038/nphoton.2014.249CrossRef

McMahon PL, Marandi A, Haribara Y, Hamerly R, Langrock C, Tamate S, Inagaki T, Takesue H, Utsunomiya S, Aihara K, Byer RL, Fejer MM, Mabuchi H, Yamamoto Y (2016) A fully programmable 100-spin coherent Ising machine with all-to-all connections. Science 354(6312):614–617. https://doi.org/10.1126/science.aah5178CrossRef

Böhm F, Verschaffelt G, Van der Sande G (2019) A poor man’s coherent Ising machine based on opto-electronic feedback systems for solving optimization problems. Nat Commun 10(1):3538. https://doi.org/10.1038/s41467-019-11484-3CrossRef

Leleu T, Yamamoto Y, Utsunomiya S, Aihara K (2017) Combinatorial optimization using dynamical phase transitions in driven-dissipative systems. Phys Rev E 95(2):4–6. https://doi.org/10.1103/PhysRevE.95.022118MathSciNetCrossRef

Molnár B, Molnár F, Varga M, Toroczkai Z, Ercsey-Ravasz M (2018) A continuous-time MaxSAT solver with high analog performance. Nat Commun 9(1):1–12. https://doi.org/10.1038/s41467-018-07327-2CrossRef

Afoakwa R, Zhang Y, Vengalam UKR, Ignjatovic Z, Huang M (2021) BRIM: bistable resistively-coupled Ising machine. In: 2021 IEEE international symposium on high-performance computer architecture (HPCA). IEEE, Seoul, pp 749–760. https://doi.org/10.1109/HPCA51647.2021.00068

Gset: Group of Random Graphs. https://sparse.tamu.edu/Gset

Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. J Comput Syst Sci 43(3):425–440. https://doi.org/10.1016/0022-0000(91)90023-XMathSciNetCrossRef

Håstad J (2001) Some optimal inapproximability results. J ACM 48(4):798–859. https://doi.org/10.1145/502090.502098MathSciNetCrossRef

Khot S (2010) On the unique games conjecture (invited survey). In: 2010 IEEE 25th annual conference on computational complexity, pp 99–121. https://doi.org/10.1109/CCC.2010.19

Trevisan L (2012) On Khot’s unique games conjecture. Bull Am Math Soc 49(1):91–111. https://doi.org/10.1090/S0273-0979-2011-01361-1MathSciNetCrossRef

Khot S, Kindler G, Mossel E, O’Donnell R (2004) Optimal inapproximability results for max-cut and other 2-variable CSPs? In: 45th annual IEEE symposium on foundations of computer science. IEEE, Rome, pp. 146–154. https://doi.org/10.1109/FOCS.2004.49

...Hamerly R, Inagaki T, McMahon PL, Venturelli D, Marandi A, Onodera T, Ng E, Langrock C, Inaba K, Honjo T, Enbutsu K, Umeki T, Kasahara R, Utsunomiya S, Kako S, Kawarabayashi K-I, Byer RL, Fejer MM, Mabuchi H, Englund D, Rieffel E, Takesue H, Yamamoto Y (2019) Experimental investigation of performance differences between coherent Ising machines and a quantum annealer. Sci Adv 5(5):0823. https://doi.org/10.1126/sciadv.aau0823CrossRef

Leleu T, Khoyratee F, Levi T, Hamerly R, Kohno T, Aihara K (2021) Scaling advantage of chaotic amplitude control for high-performance combinatorial optimization. Commun Phys 4(1):266. https://doi.org/10.1038/s42005-021-00768-0CrossRef

Erementchouk M, Shukla A, Mazumder P (2022) On computational capabilities of Ising machines based on nonlinear oscillators. Physica D 437:133334. https://doi.org/10.1016/j.physd.2022.133334MathSciNetCrossRef

Adler R (1946) A study of locking phenomena in oscillators. Proc IRE 34(6):351–357. https://doi.org/10.1109/JRPROC.1946.229930CrossRef

Bhansali P, Roychowdhury J (2009) Gen-Adler: the generalized Adler’s equation for injection locking analysis in oscillators. In: 2009 Asia and South Pacific design automation conference. IEEE, Yokohama, pp 522–527. https://doi.org/10.1109/ASPDAC.2009.4796533

Korte B, Vygen J (2018) Combinatorial optimization. Algorithms and Combinatorics. Springer, Berlin, Heidelberg, vol 21. https://doi.org/10.1007/978-3-662-56039-6

Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115–1145. https://doi.org/10.1145/227683.227684MathSciNetCrossRef

Alon N, Sudakov B (2000) Bipartite subgraphs and the smallest eigenvalue. Comb Probab Comput 9(1):1–12. https://doi.org/10.1017/S0963548399004071MathSciNetCrossRef

Deza MM, Laurent M (1997) Geometry of cuts and metrics. In: Algorithms and Combinatorics. Springer, Berlin, Heidelberg, vol 15. https://doi.org/10.1007/978-3-642-04295-9

Burer S, Monteiro RDC, Zhang Y (2002) Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs. SIAM J Optim 12(2):503–521. https://doi.org/10.1137/S1052623400382467MathSciNetCrossRef

Laurent M, Poljak S (1995) On a positive semidefinite relaxation of the cut polytope. Linear Algebra Appl 223–224:439–461. https://doi.org/10.1016/0024-3795(95)00271-RMathSciNetCrossRef

Charikar M, Wirth A (2004) Maximizing quadratic programs: extending grothendieck’s inequality. In: 45th annual IEEE symposium on foundations of computer science. IEEE, Rome, pp 54–60. https://doi.org/10.1109/FOCS.2004.39

Alon N, Naor A (2004) Approximating the cut-norm via Grothendieck’s inequality. In: Proceedings of the thirty-sixth annual acm symposium on theory of computing—STOC ’04. ACM Press, Chicago, p 72. https://doi.org/10.1145/1007352.1007371

Anjos MF, Wolkowicz H (2002) Strengthened semidefinite relaxations via a second lifting for the max-cut problem. Discret Appl Math 119(1–2):79–106. https://doi.org/10.1016/S0166-218X(01)00266-9MathSciNetCrossRef

Razavi B (2002) Design of analog CMOS integrated circuits. Tata McGraw-Hill, p 684

Title: Scalable almost-linear dynamical Ising machines
Authors: Aditya Shukla
Mikhail Erementchouk
Pinaki Mazumder
Publication date: 09-04-2024
Publisher: Springer Netherlands
Published in: Natural Computing
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-024-09983-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner