首页|The quantum Ising model for perfect matching and solving it with variational quantum eigensolver
The quantum Ising model for perfect matching and solving it with variational quantum eigensolver
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
万方数据
Obtaining all perfect matchings of a graph is a tough problem in graph theory,and its complex-ity 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 per-fect matching.The experimental results on a superconducting quantum computer of the Origin Quantum Computing Technology Company show that our model can encode 2n 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.
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
Hefei National Laboratory,Hefei 230088,China
National Key R&D Program of ChinaInnovation Program for Quantum Science and Technology
万方数据
