QCover: QAOA-based Conbinational Optimization Solver*

We have entered the era of Noisy Intermedia-scale Quantum (NISQ), that is, quantum chips can contain tens to hundreds of qubits, but the large error rate of quantum logic gate operations affected by noise results in extremely limited circuit depth that can be effectively executed. Demonstrate quantum advantages in certain applications has become the most urgent thing at present. 

The Quantum Approximate Optimization Algorithm (QAOA) proposed by Edward Farhi et al. can solve the approximate solution of combinatorial optimization problems, and is widely believed to have the potential to show quantum advantages on NISQ computing chips.

The core of QAOA is to search the optimal parameters that minimize the expectation value of target Hamiltonian via variational method. It is thus very important to design an effective classical simulation method to quickly find the optimal parameters of the QAOA shallow quantum circuit, and the most important thing is to realize the effective classical simulation calculation of the expected value of the problem Hamiltonian. The Qcover present here, can efficiently simulate QAOA process to obtain the optimal parameters based on graph algorithm. It will accelerates the coming of quantum advantage with the assistant of NISQ hardware.