The quantum Ising model for perfect matching and solving it with variational quantum eigensolver  

作　　者：Qilin ZHENG Pingyu ZHU Chao WU Miaomiao YU Weihong LUO Ping XU 

机构地区：[1]Institute for Quantum Information and State Key Laboratory of High Performance Computing,College of Computer Science and Technology,National University of Defense Technology,Changsha 410073,China [2]Hefei National Laboratory,Hefei 230088,China

出　　处：《Science China(Information Sciences)》2024年第9期302-316,共15页中国科学（信息科学）（英文版）

基　　金：supported by National Key R&D Program of China(Grant No.2019YFA0308700);Innovation Program for Quantum Science and Technology(Grant No.2021ZD0301500)。

摘　　要：Obtaining all perfect matchings of a graph is a tough problem in graph theory,and its complexity belongs to the #P-Complete class.The problem is closely related to combinatorics,marriage matching problems,dense subgraphs,the Gaussian boson sampling,chemical molecular structures,and dimer physics.In this paper,we propose a quadratic unconstrained binary optimization formula of the perfect matching problem and translate it into the quantum Ising model.We can obtain all perfect matchings by mapping them to the ground state of the quantum Ising Hamiltonian and solving it with the variational quantum eigensolver.Adjusting the model's parameters can also achieve the maximum or minimum weighted perfect matching.The experimental results on a superconducting quantum computer of the Origin Quantum Computing Technology Company show that our model can encode 2^(n) dimensional optimization space with only O(n)qubits consumption and achieve a high success probability of the ground state corresponding to all perfect matchings.In addition,the further simulation results show that the model can support a scale of more than 14 qubits,effectively resist the adverse effects of noise,and obtain a high success probability at a shallow variational depth.This method can be extended to other combinatorial optimization problems.

关 键 词：perfect matching Ising model quantum Hamiltonian variational quantum eigensolver quadratic unconstrained binary optimization 

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