MEMS Oscillators-Network-Based Ising Machine with Grouping Method

Deng, Yi1,2; Zhang, Yi1,2,3; Zhang, Xinyuan1,2; Jiang, Yang1,2,3; Chen, Xi1,2; Yang, Yansong4; Tong, Xin5; Cai, Yao5; Liu, Wenjuan5; Sun, Chengliang5; Shang, Dashan6; Wang, Qing3; Yu, Hongyu3; Wang, Zhongrui1,2

2024-05-01

10.1002/advs.202310096

ADVANCED SCIENCE   影响因子和分区

2198-3844

["Combinatorial optimization (CO) has a broad range of applications in various fields, including operations research, computer science, and artificial intelligence. However, many of these problems are classified as nondeterministic polynomial-time (NP)-complete or NP-hard problems, which are known for their computational complexity and cannot be solved in polynomial time on traditional digital computers. To address this challenge, continuous-time Ising machine solvers have been developed, utilizing different physical principles to map CO problems to ground state finding. However, most Ising machine prototypes operate at speeds comparable to digital hardware and rely on binarizing node states, resulting in increased system complexity and further limiting operating speed. To tackle these issues, a novel device-algorithm co-design method is proposed for fast sub-optimal solution finding with low hardware complexity. On the device side, a piezoelectric lithium niobate (LiNbO3) microelectromechanical system (MEMS) oscillator network-based Ising machine without second-harmonic injection locking (SHIL) is devised to solve Max-cut and graph coloring problems. The LiNbO3 oscillator operates at speeds greater than 9 GHz, making it one of the fastest oscillatory Ising machines. System-wise, an innovative grouping method is used that achieves a performance guarantee of 0.878 for Max-cut and 0.658 for graph coloring problems, which is comparable to Ising machines that utilize binarization.","A novel grouping method, which eliminates the need of second-harmonic injection locking (SHIL), is proposed for micro-electromechanical system (MEMS) oscillator network-based Ising machine. This grouping method achieves a performance guarantee of 0.878 for Max-cut and 0.658 for graph coloring problems. Besides, the MEMS oscillator operates at speeds greater than 9 GHz, making it one of the fastest oscillatory Ising machines. image"]

combinatorial optimization Ising machine Max-Cut MEMS oscillator semidefinite programming relaxation

SCI ; EI

英语

通讯

Hong Kong Research Grant Council["27206321","17205922","17212923"] ; National Natural Science Foundation of China["62122004","61874138","61888102","61771176","62171173","62274082"] ; Strategic Priority Research Program of the Chinese Academy of Sciences[XDB44000000] ; Research on the fabrication and mechanism of GaN power and RF devices["JCYJ20200109141233476","JCYJ20210324120409025","HZQB-KCZYZ-2021052"] ; null[2018YFA0701500]

Chemistry ; Science & Technology - Other Topics ; Materials Science

Chemistry, Multidisciplinary ; Nanoscience & Nanotechnology ; Materials Science, Multidisciplinary

WOS:001215923700001

WILEY

20241816024678

Combinatorial optimization ; Complex networks ; Computational complexity ; Computer hardware ; Continuous time systems ; Digital computers ; Graph theory ; Ground state ; Lithium compounds ; Oscillators (electronic) ; Polynomial approximation

Electric Equipment:704.2 ; Oscillators:713.2 ; Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Computer Systems and Equipment:722 ; Digital Computers and Systems:722.4 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4 ; Optimization Techniques:921.5 ; Numerical Methods:921.6 ; Systems Science:961

Web of Science

1.Univ Hong Kong, Dept Elect & Elect Engn, Pokfulam Rd, Hong Kong 999077, Peoples R China
2.AI Chip Ctr Emerging Smart Syst, InnoHK Ctr, ACCESS, Hong Kong Sci Pk, Hong Kong 999077, Peoples R China
3.Southern Univ Sci & Technol, Sch Microelect, Shenzhen 518055, Peoples R China
4.Hong Kong Univ Sci & Technol, Dept Elect & Comp Engn, Hong Kong 999077, Peoples R China
5.Wuhan Univ, Inst Technol Sci, Wuhan 430072, Peoples R China
6.Chinese Acad Sci, Inst Microelect, Beijing 100029, Peoples R China

Deng, Yi,Zhang, Yi,Zhang, Xinyuan,et al. MEMS Oscillators-Network-Based Ising Machine with Grouping Method[J]. ADVANCED SCIENCE,2024,11.

Deng, Yi.,Zhang, Yi.,Zhang, Xinyuan.,Jiang, Yang.,Chen, Xi.,...&Wang, Zhongrui.(2024).MEMS Oscillators-Network-Based Ising Machine with Grouping Method.ADVANCED SCIENCE,11.

Deng, Yi,et al."MEMS Oscillators-Network-Based Ising Machine with Grouping Method".ADVANCED SCIENCE 11(2024).