{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T07:15:26Z","timestamp":1725434126675},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,5,5]],"date-time":"2021-05-05T00:00:00Z","timestamp":1620172800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,5,5]],"date-time":"2021-05-05T00:00:00Z","timestamp":1620172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s11047-021-09845-3","type":"journal-article","created":{"date-parts":[[2021,5,5]],"date-time":"2021-05-05T09:03:54Z","timestamp":1620205434000},"page":"287-306","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":42,"title":["Solving combinatorial optimisation problems using oscillator based Ising machines"],"prefix":"10.1007","volume":"20","author":[{"given":"Tianshi","family":"Wang","sequence":"first","affiliation":[]},{"given":"Leon","family":"Wu","sequence":"additional","affiliation":[]},{"given":"Parth","family":"Nobel","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-2684-2279","authenticated-orcid":false,"given":"Jaijeet","family":"Roychowdhury","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,5,5]]},"reference":[{"issue":"1","key":"9845_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1103\/RevModPhys.77.137","volume":"77","author":"JA Acebr\u00f3n","year":"2005","unstructured":"Acebr\u00f3n JA, Bonilla LL, Vicente CJP, Ritort F, Spigler R (2005) The Kuramoto model: a simple paradigm for synchronization phenomena. Rev Mod Phys 77(1):137","journal-title":"Rev Mod Phys"},{"key":"9845_CR2","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 (2019) Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Front Phys 7:48","journal-title":"Front Phys"},{"issue":"10","key":"9845_CR3","doi-asserted-by":"publisher","first-page":"3241","DOI":"10.1088\/0305-4470\/15\/10\/028","volume":"15","author":"Francisco Barahona","year":"1982","unstructured":"Barahona Francisco (1982) On the computational complexity of Ising spin glass models. J Phys A Math Gen 15(10):3241","journal-title":"J Phys A Math Gen"},{"key":"9845_CR4","doi-asserted-by":"crossref","unstructured":"Bhansali P, Roychowdhury J (2009) Gen-Adler: the generalized Adler\u2019s equation for injection locking analysis in oscillators. In: Proceedings of IEEE ASP-DAC, pp 227\u2013522","DOI":"10.1109\/ASPDAC.2009.4796533"},{"key":"9845_CR5","doi-asserted-by":"publisher","first-page":"56","DOI":"10.3389\/fphy.2014.00056","volume":"2","author":"Z Bian","year":"2014","unstructured":"Bian Z, Chudak F, Israel R, Lackey B, Macready WG, Roy A (2014) Discrete optimization using quantum annealing on sparse Ising models. Front Phys 2:56","journal-title":"Front Phys"},{"key":"9845_CR6","unstructured":"Bian Z, Chudak F, Macready WG, Rose G (2010) The Ising model: teaching an old problem new tricks. D-Wave Syst, 2"},{"issue":"4","key":"9845_CR7","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1103\/RevModPhys.39.883","volume":"39","author":"Stephen G Brush","year":"1967","unstructured":"Brush Stephen G (1967) History of the Lenz-Ising model. Rev Mod Phys 39(4):883\u2013893","journal-title":"Rev Mod Phys"},{"issue":"2","key":"9845_CR8","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1137\/S1052623400382467","volume":"12","author":"S Burer","year":"2002","unstructured":"Burer S, Monteiro R, Zhang Y (2002) Rank-two relaxation heuristics for max-cut and other binary quadratic programs. SIAM J Optim 12(2):503\u2013521","journal-title":"SIAM J Optim"},{"issue":"3","key":"9845_CR9","first-page":"031014","volume":"7","author":"KY Camsari","year":"2017","unstructured":"Camsari KY, Faria R, Sutton BM, Datta S (2017) Stochastic p-bits for invertible logic. Phys Rev X 7(3):031014","journal-title":"Phys Rev X"},{"issue":"5","key":"9845_CR10","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1109\/81.847872","volume":"47","author":"A Demir","year":"2000","unstructured":"Demir A, Mehrotra A, Roychowdhury J (2000) Phase noise in oscillators: a unifying theory and numerical methods for characterization. IEEE Trans Circ Syst I Fund Theory Appl 47(5):655\u2013674","journal-title":"IEEE Trans Circ Syst I Fund Theory Appl"},{"issue":"3","key":"9845_CR11","first-page":"031015","volume":"6","author":"VS Denchev","year":"2016","unstructured":"Denchev VS, Boixo S, Isakov SV, Ding N, Babbush R, Smelyanskiy V, Martinis J, Neven H (2016) What is the computational value of finite-range tunneling? Phys Rev X 6(3):031015","journal-title":"Phys Rev X"},{"issue":"12","key":"9845_CR12","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1038\/nphys2105","volume":"7","author":"M Ercsey-Ravasz","year":"2011","unstructured":"Ercsey-Ravasz M, Toroczkai Z (2011) Optimization hardness as transient chaos in an analog approach to constraint satisfaction. Nat Phys 7(12):966","journal-title":"Nat Phys"},{"issue":"6","key":"9845_CR13","doi-asserted-by":"publisher","first-page":"1033","DOI":"10.1080\/1055678021000090033","volume":"17","author":"P Festa","year":"2002","unstructured":"Festa P, Pardalos PM, Resende MGC, Ribeiro CC (2002) Randomized heuristics for the MAX-CUT problem. Optim Methods softw 17(6):1033\u20131058","journal-title":"Optim Methods softw"},{"issue":"2","key":"9845_CR14","doi-asserted-by":"publisher","first-page":"314","DOI":"10.1587\/transinf.2017RCP0015","volume":"E101.D","author":"H Gyoten","year":"2018","unstructured":"Gyoten H, Hiromoto M, Sato T (2018) Area efficient annealing processor for Ising model without random number generator. IEICE Trans Inform Syst E101.D(2):314\u2013323","journal-title":"IEICE Trans Inform Syst"},{"key":"9845_CR15","doi-asserted-by":"crossref","unstructured":"Gyoten H, Hiromoto M, Sato T (2018) Enhancing the solution quality of hardware Ising-model solver via parallel tempering. In: Proceedings of ICCAD\u201918, pp 70:1\u201370:8, New York, NY, USA, ACM","DOI":"10.1145\/3240765.3240806"},{"issue":"5","key":"9845_CR16","doi-asserted-by":"publisher","first-page":"eaau0823","DOI":"10.1126\/sciadv.aau0823","volume":"5","author":"R Hamerly","year":"2019","unstructured":"Hamerly R et al (2019) Experimental investigation of performance differences between coherent Ising machines and a quantum annealer. Sci Adv 5(5):eaau0823","journal-title":"Sci Adv"},{"issue":"13","key":"9845_CR17","doi-asserted-by":"publisher","first-page":"134510","DOI":"10.1103\/PhysRevB.81.134510","volume":"81","author":"R Harris","year":"2010","unstructured":"Harris R, Johansson J, Berkley AJ, Johnson MW, Lanting T, Han S, Bunyk P, Ladizinsky E, Oh T, Perminov I et al (2010) Experimental demonstration of a robust and scalable flux qubit. Phys Rev B 81(13):134510","journal-title":"Phys Rev B"},{"issue":"3","key":"9845_CR18","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"C Helmberg","year":"2000","unstructured":"Helmberg C, Rendl F (2000) A spectral bundle method for semidefinite programming. SIAM J Optim 10(3):673\u2013696","journal-title":"SIAM J Optim"},{"issue":"4","key":"9845_CR19","doi-asserted-by":"publisher","first-page":"042325","DOI":"10.1103\/PhysRevA.92.042325","volume":"92","author":"I Hen","year":"2015","unstructured":"Hen I, Job J, Albash T, R\u00f8nnow TF, Troyer M, Lidar DA (2015) Probing for quantum speedup in spin-glass problems with planted solutions. Phys Rev A 92(4):042325","journal-title":"Phys Rev A"},{"issue":"3","key":"9845_CR20","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00339943","volume":"52","author":"JJ Hopfield","year":"1985","unstructured":"Hopfield JJ, Tank DW (1985) \u201cNeural\u201d computation of decisions in optimization problems. Biol Cybern 52(3):141\u2013152","journal-title":"Biol Cybern"},{"issue":"6312","key":"9845_CR21","doi-asserted-by":"publisher","first-page":"603","DOI":"10.1126\/science.aah4243","volume":"354","author":"T Inagaki","year":"2016","unstructured":"Inagaki T, Haribara Y, Igarashi K, Sonobe T, Tamate S, Honjo T, Marandi A, McMahon PL, Umeki T, Enbutsu K et al (2016) A coherent Ising machine for 2000-node optimization problems. Science 354(6312):603\u2013606","journal-title":"Science"},{"issue":"1","key":"9845_CR22","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF02980577","volume":"31","author":"E Ising","year":"1925","unstructured":"Ising E (1925) Beitrag zur Theorie des Ferromagnetismus. Zeitschrift f\u00fcr Physik 31(1):253\u2013258","journal-title":"Zeitschrift f\u00fcr Physik"},{"key":"9845_CR23","volume-title":"Graph coloring problems","author":"Tommy\u00a0R Jensen","year":"1995","unstructured":"Jensen Tommy\u00a0R, Toft Bjarne (1995) Graph coloring problems. Wiley, New Jersey"},{"issue":"7346","key":"9845_CR24","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1038\/nature10012","volume":"473","author":"MW Johnson","year":"2011","unstructured":"Johnson MW, Amin MHS, Gildert S, Lanting T, Hamze F, Dickson N, Harris R, Berkley AJ, Johansson J, Bunyk P et al (2011) Quantum annealing with manufactured spins. Nature 473(7346):194","journal-title":"Nature"},{"key":"9845_CR25","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibility among combinatorial problems. Complexity of computer computations","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. Complexity of computer computations. Springer, Berlin, pp 85\u2013103"},{"key":"9845_CR26","unstructured":"King AD, Lanting T, Harris R (2015) Performance of a quantum annealer on range-limited constraint satisfaction problems. arXiv:1502.02098"},{"key":"9845_CR27","volume-title":"Chemical oscillations, waves and turbulence","author":"Y Kuramoto","year":"2003","unstructured":"Kuramoto Y (2003) Chemical oscillations, waves and turbulence. Dover, New York"},{"key":"9845_CR28","doi-asserted-by":"crossref","unstructured":"Kuramoto Y (1975) Self-entrainment of a population of coupled non-linear oscillators. In: International symposium on mathematical problems in theoretical physics, pp 420\u2013422. Springer","DOI":"10.1007\/BFb0013365"},{"key":"9845_CR29","doi-asserted-by":"publisher","first-page":"5","DOI":"10.3389\/fphy.2014.00005","volume":"2","author":"Andrew Lucas","year":"2014","unstructured":"Lucas Andrew (2014) Ising formulations of many NP problems. Front Phys 2:5","journal-title":"Front Phys"},{"key":"9845_CR30","doi-asserted-by":"crossref","unstructured":"Lucas A (2013) Ising formulations of many NP problems. arXiv:1302.5843","DOI":"10.3389\/fphy.2014.00005"},{"issue":"3","key":"9845_CR31","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1080\/00207179208934253","volume":"55","author":"AM Lyapunov","year":"1992","unstructured":"Lyapunov AM (1992) The general problem of the stability of motion. Int J Control 55(3):531\u2013534","journal-title":"Int J Control"},{"issue":"6","key":"9845_CR32","doi-asserted-by":"publisher","first-page":"e1600236","DOI":"10.1126\/sciadv.1600236","volume":"2","author":"I Mahboob","year":"2016","unstructured":"Mahboob I, Okamoto H, Yamaguchi H (2016) An electromechanical Ising Hamiltonian. Sci Adv 2(6):e1600236","journal-title":"Sci Adv"},{"issue":"12","key":"9845_CR33","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1038\/nphoton.2014.249","volume":"8","author":"A Marandi","year":"2014","unstructured":"Marandi A, Wang Z, Takata K, Byer RL, Yamamoto Y (2014) Network of time-multiplexed optical parametric oscillators as a coherent Ising machine. Nat Photon 8(12):937\u2013942","journal-title":"Nat Photon"},{"issue":"1","key":"9845_CR34","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1287\/ijoc.1080.0275","volume":"21","author":"R Mart\u00ed","year":"2009","unstructured":"Mart\u00ed R, Duarte A, Laguna M (2009) Advanced scatter search for the max-cut problem. INFORMS J Comput 21(1):26\u201338","journal-title":"INFORMS J Comput"},{"key":"9845_CR35","doi-asserted-by":"publisher","first-page":"5178","DOI":"10.1126\/science.aah5178","volume":"354","author":"PL McMahon","year":"2016","unstructured":"McMahon PL, Marandi A, Haribara Y, Hamerly R, Langrock C, Tamate S, Inagaki T, Takesue H, Utsunomiya S, Aihara K et al (2016) A fully-programmable 100-spin coherent Ising machine with all-to-all connections. Science 354:5178","journal-title":"Science"},{"key":"9845_CR36","unstructured":"Myklebust T (2015) Solving maximum cut problems by simulated annealing. arXiv:1505.03068"},{"key":"9845_CR37","doi-asserted-by":"crossref","unstructured":"Neogy A, Roychowdhury J (2012) Analysis and design of sub-harmonically injection locked oscillators. In: Proceedings of IEEE DATE","DOI":"10.1109\/DATE.2012.6176677"},{"key":"9845_CR38","unstructured":"Rinaldi G. Rudy graph generator code. https:\/\/www-user.tu-chemnitz.de\/~helmberg\/rudy.tar.gz. Website: https:\/\/www-user.tu-chemnitz.de\/~helmberg\/sdp_software.html"},{"key":"9845_CR39","doi-asserted-by":"crossref","unstructured":"Robertson N, Sanders DP, Seymour P, Thomas R (1996) Efficiently four-coloring planar graphs. In: STOC \u201996: Proceedings of the 28th annual ACM symposium on theory of computing, pp 571\u2013575. ACM","DOI":"10.1145\/237814.238005"},{"issue":"6195","key":"9845_CR40","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1126\/science.1252319","volume":"345","author":"TF R\u00f8nnow","year":"2014","unstructured":"R\u00f8nnow TF, Wang Z, Job J, Boixo S, Isakov SV, Wecker D, Martinis JM, Lidar DA, Troyer M (2014) Defining and detecting quantum speedup. Science 345(6195):420\u2013424","journal-title":"Science"},{"issue":"5","key":"9845_CR41","doi-asserted-by":"publisher","first-page":"053311","DOI":"10.1103\/PhysRevE.100.053311","volume":"100","author":"F Sheldon","year":"2019","unstructured":"Sheldon F, Traversa FL, Di Ventra M (2019) Taming a nonconvex landscape with dynamical long-range order: memcomputing Ising benchmarks. Phys Rev E 100(5):053311","journal-title":"Phys Rev E"},{"issue":"5","key":"9845_CR42","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.1143\/PTP.75.1105","volume":"75","author":"S Shinomoto","year":"1986","unstructured":"Shinomoto S, Kuramoto Y (1986) Phase transitions in active rotator systems. Prog Theor Phys 75(5):1105\u20131110","journal-title":"Prog Theor Phys"},{"key":"9845_CR43","unstructured":"The G-set benchmarks for MAX-CUT. http:\/\/grafo.etsii.urjc.es\/optsicom\/maxcut"},{"key":"9845_CR44","unstructured":"Wang T, Roychowdhury J (2017) Oscillator-based Ising machine. In arXiv:1709.08102"},{"key":"9845_CR45","doi-asserted-by":"crossref","unstructured":"Wang T, Roychowdhury J (2014) PHLOGON: PHase-based logic using oscillatory nanosystems. In: Proceedings of Unconventional Computation and Natural Computation, LNCS sublibrary: Theoretical Computer Science and General Issues. Springer","DOI":"10.1007\/978-3-319-08123-6_29"},{"key":"9845_CR46","unstructured":"Wang T (2017) Sub-harmonic injection locking in metronomes. arXiv:1709.03886"},{"key":"9845_CR47","unstructured":"Wang T (2017) Achieving phase-based logic bit storage in mechanical metronomes. arXiv:1710.01056"},{"key":"9845_CR48","doi-asserted-by":"crossref","unstructured":"Wang T, Roychowdhury J (2019) OIM: Oscillator-based Ising Machines for solving Combinatorial Optimisation problems. arXiv:1903.07163","DOI":"10.1007\/978-3-030-19311-9_19"},{"key":"9845_CR49","doi-asserted-by":"crossref","unstructured":"Wang T, Roychowdhury J (2015) Design tools for oscillator-based computing systems. In: Proceedings of IEEE DAC, pp 188:1\u2013188:6","DOI":"10.1145\/2744769.2744818"},{"key":"9845_CR50","doi-asserted-by":"crossref","unstructured":"Wang T, Wu L, Roychowdhury J (2019) New Computational Results and Hardware Prototypes for Oscillator-based Ising Machines. In: Proceedings IEEE DAC, pp 239:1\u2013239:2","DOI":"10.1145\/3316781.3322473"},{"key":"9845_CR51","doi-asserted-by":"crossref","unstructured":"Wang T, Roychowdhury J (2019) OIM: Oscillator-based Ising Machines for Solving Combinatorial Optimisation Problems. In: Proceedings of International Conference on Unconventional Computation and Natural Computation","DOI":"10.1007\/978-3-030-19311-9_19"},{"key":"9845_CR52","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0022-5193(67)90051-3","volume":"16","author":"A Winfree","year":"1967","unstructured":"Winfree A (1967) Biological rhythms and the behavior of populations of coupled oscillators. Theor Biol 16:15\u201342","journal-title":"Theor Biol"},{"key":"9845_CR53","doi-asserted-by":"crossref","unstructured":"Yamamoto K, Huang W, Takamaeda-Yamazaki S, Ikebe M, Asai T, Motomura M (2017) A time-division multiplexing Ising machine on FPGAs. In: Proceedings of the 8th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies, p\u00a03. ACM","DOI":"10.1145\/3120895.3120905"},{"issue":"1","key":"9845_CR54","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1109\/JSSC.2015.2498601","volume":"51","author":"M Yamaoka","year":"2016","unstructured":"Yamaoka M, Yoshimura C, Hayashi M, Okuyama T, Aoki H, Mizuno H (2016) A 20k-spin Ising chip to solve combinatorial optimization problems with CMOS annealing. IEEE J Solid State Circ 51(1):303\u2013309","journal-title":"IEEE J Solid State Circ"},{"issue":"1","key":"9845_CR55","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1109\/TVLSI.2017.2754192","volume":"26","author":"X Yin","year":"2018","unstructured":"Yin X, Sedighi B, Varga M, Ercsey-Ravasz M, Toroczkai Z, Hu XS (2018) Efficient analog circuits for Boolean satisfiability. IEEE Trans Very Large Scale Integr (VLSI) Syst 26(1):155\u2013167","journal-title":"IEEE Trans Very Large Scale Integr (VLSI) Syst"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-021-09845-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11047-021-09845-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-021-09845-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,26]],"date-time":"2022-12-26T11:10:55Z","timestamp":1672053055000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11047-021-09845-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,5]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["9845"],"URL":"http:\/\/dx.doi.org\/10.1007\/s11047-021-09845-3","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,5]]},"assertion":[{"value":"16 January 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}
