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 ex...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.展开更多
基金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.
