Study on quantum adiabatic approximate solution of max-cut with different vertices

摘要

The max-cut is used to solve maximum partition for given undirected weighted graph, the sum of the weights of all sides between the subset of vertex and complementary subset obtains a maximum value. Quantum adiabatic approximation is used to design system Hamiltonian H_(sys), and the ground state of system Hamiltonian corresponds to the solution of max-cut problem. System Hamiltonian H_(sys) changes slowly along with initial Hamiltonian H_(ini) follow the evolution path of Hamiltonian H_(max), and then the ground state of Hamiltonian can be calculated. By analyzing the change of expected value with evolution time, one can judge whether the approximate solution is the optimal solution or not. In this paper, we test the adiabatic evolution of complete undirected graph with vertices from 6 to 14. Based on Python and Project Q package, we write a solver program that sets parameters according to the number of vertices and edges of undirected graph, and then obtain experimental results by measuring the state of qubits in quantum registers. It can be inferred from experimental results that for a complete undirected graph with less vertices, expected value can converge well, and then the optimal solution of max-cut problem can be obtained. When the number of vertices increase, the energy variation of Hamiltonian become more complex and the expected value is hard to converge.