Systematically Improving Quantum Approximate Optimization Algorithm with an Adaptive Ansatz

The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum eigensolver (VQE) algorithm that uses a variational ansatz of an alternating form to minimize a classical (‘problem’) Hamiltonian. The two alternating operators are given by exponentiation of the problem Hamiltonian and by the ‘mixing’ layer, which in the original formulation of QAOA is a rotation of all the qubits about the x axis. It has been discussed in the literature that by using more general mixers the performance of QAOA can be improved. However, determining how to choose these mixers is an open question. Here we provide a solution by employing the recently introduced ADAPT-VQE¹ algorithm, an iterative approach to creating ansatze for VQEs. We show that the performance of QAOA can be improved considerably by allowing more freedom in the single qubit gates and even further by allowing for entangling operations in the mixing layer.

[1] Grimsley, H.R., Economou, S.E., Barnes, E. and Mayhall, N.J., 2019. An adaptive variational algorithm for exact molecular simulations on a quantum computer. Nature communications, 10(1), pp.1-9.