Deng Yi, Zhang Yi, Zhang Xinyuan, Jiang Yang, Chen Xi, Yang Yansong, Tong Xin, Cai Yao, Liu Wenjuan, Sun Chengliang, Shang Dashan, Wang Qing, Yu Hongyu, Wang Zhongrui
Department of Electrical and Electronic Engineering, The University of Hong Kong, Pokfulam Road, Hong Kong, 999077, China.
ACCESS - AI Chip Center for Emerging Smart Systems, InnoHK Centers, Hong Kong Science Park, Hong Kong, 999077, China.
Adv Sci (Weinh). 2024 Jul;11(26):e2310096. doi: 10.1002/advs.202310096. Epub 2024 May 2.
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 (LiNbO) 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 LiNbO 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.
组合优化（CO）在包括运筹学、计算机科学和人工智能在内的各个领域都有广泛应用。然而，这些问题中的许多都被归类为非确定性多项式时间（NP）完全或NP难问题，它们以计算复杂性著称，无法在传统数字计算机上以多项式时间求解。为应对这一挑战，人们开发了连续时间伊辛机求解器，利用不同物理原理将组合优化问题映射到基态寻找问题上。然而，大多数伊辛机原型的运行速度与数字硬件相当，并且依赖于对节点状态进行二值化，这导致系统复杂性增加，并进一步限制了运行速度。为解决这些问题，本文提出了一种新颖的器件 - 算法协同设计方法，用于以低硬件复杂度快速找到次优解。在器件方面，设计了一种基于压电铌酸锂（LiNbO）微机电系统（MEMS）振荡器网络且无二次谐波注入锁定（SHIL）的伊辛机，以解决最大割和图着色问题。铌酸锂振荡器的运行速度大于9 GHz，使其成为最快的振荡伊辛机之一。在系统层面，使用了一种创新的分组方法，对于最大割问题实现了0.878的性能保证，对于图着色问题实现了0.658的性能保证，这与利用二值化的伊辛机相当。
