Optical experimental solution for the multiway number partitioning problem and its application to computing power scheduling  

作　　者：Jingwei Wen Zhenming Wang Zhiguo Huang Dunbo Cai Bingjie Jia Chongyu Cao Yin Ma Hai Wei Kai Wen Ling Qian 

机构地区：[1]China Mobile(Suzhou)Software Technology Company Limited,Suzhou 215163,China [2]Beijing QBoson Quantum Technology Co.,Ltd.,Beijing 100015,China

出　　处：《Science China(Physics,Mechanics & Astronomy)》2023年第9期15-22,共8页中国科学：物理学、力学、天文学（英文版）

基　　金：supported by the National Key R&D Plan (Grant No. 2021YFB2801800)。

摘　　要：Quantum computing is an emerging technology that is expected to realize an exponential increase in computing power. Recently,its theoretical foundation and application scenarios have been extensively researched and explored. In this work, we propose efficient quantum algorithms suitable for solving computing power scheduling problems in the cloud-rendering domain, which can be viewed mathematically as a generalized form of a typical NP-complete problem, i.e., a multiway number partitioning problem.In our algorithm, the matching pattern between tasks and computing resources with the shortest completion time or optimal load balancing is encoded into the ground state of the Hamiltonian;it is then solved using the optical coherent Ising machine, a practical quantum computing device with at least 100 qubits. The experimental results show that the proposed quantum scheme can achieve significant acceleration and save 97% of the time required to solve combinatorial optimization problems compared with classical algorithms. This demonstrates the computational advantages of optical quantum devices in solving combinatorial optimization problems. Our algorithmic and experimental work will advance the utilization of quantum computers to solve specific NP problems and will broaden the range of possible applications.

关 键 词：quantum algorithm coherent Ising machine multiway number partitioning problem 

分 类 号：O413[理学—理论物理]