On computational capabilities of Ising machines based on nonlinear oscillators. (English) Zbl 1492.68051
Summary: Dynamical Ising machines are actively investigated from the perspective of finding efficient heuristics for NP-hard optimization problems. However, the existing data demonstrate super-polynomial scaling of the running time with the system size, which is incompatible with large NP-hard problems. We show that oscillator networks implementing the Kuramoto model of synchronization are capable of demonstrating polynomial scaling. The dynamics of these networks is related to the semidefinite programming relaxation of the Ising model ground state problem. Consequently, such networks, as we numerically demonstrate, are capable of producing the best possible approximation in polynomial time. To reach such performance, however, the reconstruction of the binary Ising state (rounding) must be specially addressed. We demonstrate that commonly implemented forced collapse to a close-to-Ising state may diminish the computational capabilities up to their complete invalidation. Therefore, consistent treatment of rounding may cardinally improve various operation metrics of already existing and upcoming dynamical Ising machines.
MSC:
| 68Q09 | Other nonclassical models of computation |
| 82C20 | Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics |
| 90C27 | Combinatorial optimization |
| 90C59 | Approximation methods and heuristics in mathematical programming |
References:
| [1] | Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162 |
| [2] | Fu, Y.; Anderson, P. W., Application of statistical mechanics to NP-complete problems in combinatorial optimisation, J. Phys. A: Math. Gen., 19, 9, 1605-1620 (1986) · Zbl 0606.05064 |
| [3] | Barahona, F.; Grötschel, M.; Jünger, M.; Reinelt, G., An application of combinatorial optimization to statistical physics and circuit layout design, Oper. Res., 36, 3, 493-513 (1988) · Zbl 0646.90084 |
| [4] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W.; Bohlinger, J. D., Complexity of Computer Computations (1972), Springer US: Springer US Boston, MA), 85-103 · Zbl 1467.68065 |
| [5] | Garey, M.; Johnson, D.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 3, 237-267 (1976) · Zbl 0338.05120 |
| [6] | Lucas, A., Ising formulations of many NP problems, Front. Phys., 2, 5 (2014) |
| [7] | Wang, Z.; Marandi, A.; Wen, K.; Byer, R. L.; Yamamoto, Y., Coherent Ising machine based on degenerate optical parametric oscillators, Phys. Rev. A, 88, 6, Article 063853 pp. (2013) |
| [8] | Novikov, A. V.; Benderskaya, E. N., Oscillatory neural networks based on the Kuramoto model for cluster analysis, Pattern Recognit. Image Anal., 24, 3, 365-371 (2014) |
| [9] | Marandi, A.; Wang, Z.; Takata, K.; Byer, R. L.; Yamamoto, Y., Network of time-multiplexed optical parametric oscillators as a coherent Ising machine, Nat. Photonics, 8, 12, 937-942 (2014) |
| [10] | Mahboob, I.; Okamoto, H.; Yamaguchi, H., An electromechanical Ising Hamiltonian, Sci. Adv., 2, 6, Article e1600236 pp. (2016) |
| [11] | Inagaki, T.; Haribara, Y.; Igarashi, K.; Sonobe, T.; Tamate, S.; Honjo, T.; Marandi, A.; McMahon, P. L.; Umeki, T.; Enbutsu, K.; Tadanaga, O.; Takenouchi, H.; Aihara, K.; Kawarabayashi, K.-i.; Inoue, K.; Utsunomiya, S.; Takesue, H., A coherent Ising machine for 2000-node optimization problems, Science, 354, 6312, 603-606 (2016) |
| [12] | Parihar, A.; Shukla, N.; Jerry, M.; Datta, S.; Raychowdhury, A., Vertex coloring of graphs via phase dynamics of coupled oscillatory networks, Sci. Rep., 7, 1, 911 (2017) |
| [13] | Kalinin, K. P.; Berloff, N. G., Networks of non-equilibrium condensates for global optimization, New J. Phys., 20, 11, Article 113023 pp. (2018) |
| [14] | Pierangeli, D.; Marcucci, G.; Conti, C., Large-scale photonic ising machine by spatial light modulation, Phys. Rev. Lett., 122, 21, Article 213902 pp. (2019) |
| [15] | Chou, J.; Bramhavar, S.; Ghosh, S.; Herzog, W., Analog coupled oscillator based weighted ising machine, Sci. Rep., 9, 1, 14786 (2019) |
| [16] | Wang, T.; Roychowdhury, J., OIM: Oscillator-based ising machines for solving combinatorial optimisation problems, (McQuillan, I.; Seki, S., Unconventional Computation and Natural Computation. Vol. 11493 (2019), Springer International Publishing: Springer International Publishing Cham), 232-256 · Zbl 1525.68046 |
| [17] | Wang, T.; Wu, L.; Roychowdhury, J., New computational results and hardware prototypes for oscillator-based ising machines, (Proceedings of the 56th Annual Design Automation Conference 2019 (2019), ACM: ACM Las Vegas NV USA), 1-2 |
| [18] | Goto, H.; Tatsumura, K.; Dixon, A. R., Combinatorial optimization by simulating adiabatic bifurcations in nonlinear Hamiltonian systems, Sci. Adv., 5, 4, eaav2372 (2019) · Zbl 1411.90295 |
| [19] | Kalinin, K. P.; Amo, A.; Bloch, J.; Berloff, N. G., Polaritonic XY-Ising machine, Nanophotonics, 9, 13, 4127-4138 (2020) |
| [20] | Yamamoto, Y.; Leleu, T.; Ganguli, S.; Mabuchi, H., Coherent Ising machines—Quantum optics and neural network perspectives, Appl. Phys. Lett., 117, 16, Article 160501 pp. (2020) |
| [21] | Ahmed, I.; Chiu, P.-W.; Kim, C. H., A probabilistic self-annealing compute fabric based on 560 hexagonally coupled ring oscillators for solving combinatorial optimization problems, (2020 IEEE Symposium on VLSI Circuits (2020), IEEE: IEEE Honolulu, HI, USA), 1-2 |
| [22] | Mallick, A.; Bashar, M. K.; Truesdell, D. S.; Calhoun, B. H.; Joshi, S.; Shukla, N., Using synchronized oscillators to compute the maximum independent set, Nature Commun., 11, 1, 4689 (2020) |
| [23] | Dutta, S.; Khanna, A.; Datta, S., Understanding the continuous-time dynamics of phase-transition nano-oscillator-based ising Hamiltonian solver, IEEE J. Explor. Solid-State Comput. Devices Circuits, 6, 2, 155-163 (2020) |
| [24] | Afoakwa, R.; Zhang, Y.; Vengalam, U. K.R.; Ignjatovic, Z.; Huang, M., BRIM: Bistable resistively-coupled ising machine, (2021 IEEE International Symposium on High-Performance Computer Architecture. 2021 IEEE International Symposium on High-Performance Computer Architecture, HPCA (2021), IEEE: IEEE Seoul, Korea (South)), 749-760 |
| [25] | Goto, H.; Endo, K.; Suzuki, M.; Sakai, Y.; Kanao, T.; Hamakawa, Y.; Hidaka, R.; Yamasaki, M.; Tatsumura, K., High-performance combinatorial optimization based on classical mechanics, Sci. Adv., 7, 6, eabe7953 (2021) |
| [26] | Papadimitriou, C. H.; Yannakakis, M., Optimization, approximation, and complexity classes, J. Comput. System Sci., 43, 3, 425-440 (1991) · Zbl 0765.68036 |
| [27] | Khot, S.; Kindler, G.; Mossel, E.; O’Donnell, R., Optimal inapproximability results for max-cut and other 2-variable CSPs?, (45th Annual IEEE Symposium on Foundations of Computer Science (2004), IEEE: IEEE Rome, Italy), 146-154 |
| [28] | Håstad, J., Some optimal inapproximability results, J. ACM, 48, 4, 798-859 (2001) · Zbl 1127.68405 |
| [29] | Yurtsever, A.; Tropp, J. A.; Fercoq, O.; Udell, M.; Cevher, V., Scalable semidefinite programming, SIAM J. Math. Data Sci., 3, 1, 171-200 (2021) · Zbl 1470.90068 |
| [30] | Experimental investigation of performance differences between coherent ising machines and a quantum annealer, Sci. Adv., 5, 5, eaau0823 (2019) |
| [31] | Leleu, T.; Khoyratee, F.; Levi, T.; Hamerly, R.; Kohno, T.; Aihara, K., Scaling advantage of chaotic amplitude control for high-performance combinatorial optimization, Commun. Phys., 4, 1, 266 (2021) |
| [32] | Kuramoto, Y., Phase- and center-manifold reductions for large populations of coupled oscillators with application to non-locally coupled systems, Int. J. Bifurcation Chaos, 07, 04, 789-805 (1997) · Zbl 0901.92015 |
| [33] | Mori, H.; Kuramoto, Y., Dissipative Structures and Chaos (1998), Springer: Springer Berlin ; New York · Zbl 0904.58042 |
| [34] | Acebrón, J. A.; Bonilla, L. L.; Pérez Vicente, C. J.; Ritort, F.; Spigler, R., The Kuramoto model: A simple paradigm for synchronization phenomena, Rev. Modern Phys., 77, 1, 137-185 (2005) |
| [35] | Pietras, B.; Daffertshofer, A., Network dynamics of coupled oscillators and phase reduction techniques, Phys. Rep., 819, 1-105 (2019) |
| [36] | Bashar, M. K.; Mallick, A.; Truesdell, D. S.; Calhoun, B. H.; Joshi, S.; Shukla, N., 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 (2020) |
| [37] | Wang, T.; Wu, L.; Nobel, P.; Roychowdhury, J., Solving combinatorial optimisation problems using oscillator based Ising machines, Nat. Comput. (2021) · Zbl 1530.68119 |
| [38] | Gärtner, B.; Matousek, J., Approximation Algorithms and Semidefinite Programming (2012), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg · Zbl 1257.90001 |
| [39] | Raghavendra, P., Optimal algorithms and inapproximability results for every CSP?, (Proceedings of the 40th Annual ACM Symposium on Theory of Computing. Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC ’08 (2008), ACM: ACM New York, NY, USA), 245-254 · Zbl 1231.68142 |
| [40] | Trevisan, L., Max cut and the smallest eigenvalue, SIAM J. Comput., 41, 6, 1769-1786 (2012) · Zbl 1271.68245 |
| [41] | Soto, J. A., Improved analysis of a max-cut algorithm based on spectral partitioning, SIAM J. Discrete Math., 29, 1, 259-268 (2015) · Zbl 1331.68297 |
| [42] | Shinomoto, S.; Kuramoto, Y., Phase transitions in active rotator systems, Progr. Theoret. Phys., 75, 5, 1105-1110 (1986) |
| [43] | Adler, R., A study of locking phenomena in oscillators, Proc. IRE, 34, 6, 351-357 (1946) |
| [44] | Zhang, X.; Zhou, X.; Aliener, B.; Daryoush, A., A study of subharmonic injection locking for local oscillators, IEEE Microw. Guid. Wave Lett., 2, 3, 97-99 (1992) |
| [45] | Bhansali, P.; Roychowdhury, J., Gen-adler: The generalized adler’s equation for injection locking analysis in oscillators, (2009 Asia and South Pacific Design Automation Conference (2009), IEEE: IEEE Yokohama, Japan), 522-527 |
| [46] | Deza, M. M.; Laurent, M., (Geometry of Cuts and Metrics. Geometry of Cuts and Metrics, Algorithms and Combinatorics, vol. 15 (1997), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg) · Zbl 0885.52001 |
| [47] | Korte, B.; Vygen, J., (Combinatorial Optimization. Combinatorial Optimization, Algorithms and Combinatorics, vol. 21 (2018), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg) · Zbl 1390.90001 |
| [48] | Kalantari, B., Quadratic functions with exponential number of local maxima, Oper. Res. Lett., 5, 1, 47-49 (1986) · Zbl 0597.90067 |
| [49] | Laurent, M.; Poljak, S., On a positive semidefinite relaxation of the cut polytope, Linear Algebra Appl., 223-224, 439-461 (1995) · Zbl 0835.90078 |
| [50] | Delorme, C.; Poljak, S., Combinatorial properties and the complexity of a max-cut approximation, European J. Combin., 14, 4, 313-333 (1993) · Zbl 0780.05040 |
| [51] | Goemans, M. X.; Williamson, D. P., .879-Approximation algorithms for MAX CUT and MAX 2SAT, (Proceedings of the 26th Annual ACM Symposium on Theory of Computing - STOC ’94 (1994), ACM Press: ACM Press Montreal, Quebec, Canada), 422-431 · Zbl 1345.68274 |
| [52] | Goemans, M. X.; Williamson, D. P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM, 42, 6, 1115-1145 (1995) · Zbl 0885.68088 |
| [53] | Alon, N.; Sudakov, B., Bipartite subgraphs and the smallest eigenvalue, Combin. Probab. Comput., 9, 1, 1-12 (2000) · Zbl 0945.05041 |
| [54] | Raghavan, P.; Tompson, C. D., Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Combinatorica, 7, 4, 365-374 (1987) · Zbl 0651.90052 |
| [55] | Charikar, M.; Wirth, A., Maximizing quadratic programs: Extending Grothendieck’s inequality, (45th Annual IEEE Symposium on Foundations of Computer Science (2004), IEEE: IEEE Rome, Italy), 54-60 |
| [56] | Alon, N.; Naor, A., Approximating the cut-norm via Grothendieck’s inequality, (Proceedings of the 36th Annual ACM Symposium on Theory of Computing - STOC ’04 (2004), ACM Press: ACM Press Chicago, IL, USA), 72 · Zbl 1192.68866 |
| [57] | Anjos, M. F.; Wolkowicz, H., Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, Discrete Appl. Math., 119, 1-2, 79-106 (2002) · Zbl 1102.90369 |
| [58] | Trevisan, L., On Khot’s unique games conjecture, Bull. Amer. Math. Soc., 49, 1, 91-111 (2012) · Zbl 1280.68102 |
| [59] | Khot, S., On the unique games conjecture (invited survey), (2010 IEEE 25th Annual Conference on Computational Complexity (2010)), 99-121 |
| [60] | Burer, S.; Monteiro, R. D.C.; Zhang, Y., Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs, SIAM J. Optim., 12, 2, 503-521 (2002) · Zbl 1152.90532 |
| [61] | Dunning, I.; Gupta, S.; Silberholz, J., What works best when? A systematic evaluation of Heuristics for Max-Cut and QUBO, INFORMS J. Comput., 30, 3, 608-624 (2018) · Zbl 1528.90288 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
