Quantum approximate optimization algorithm: combinatorial problems and classical statistical models

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm for solving combinatorial optimization problems. Since most of combinatorial optimization problems may be thought as particular instances of Ising Hamiltonians, the study of the QAOA is very relevant from the physical point of view for its potential applications in describing physical systems. In the QAOA a quantum state is prepared and, through 2p parameterized quantum evolutions, a final state which represents an extreme of cost function and encodes the approximate solution of the problem is obtained. The 2p parameters are determined through a classical parameter optimization process. In this work we apply QAOA to two different problems, the Max Cut and the random bond Ising Model (RBIM). For both problems we perform an analysis of the optimization efficiency, verifying that the quality of the approximation increases with p. For the Max Cut we perform a further analysis of the p=1 case for which we obtain an analytical expression for the cost function and make observations regarding the choice of the initial parameters in the optimization procedure. For the RBIM, for different disordered configurations we obtain the ground states energies and magnetizations for different lattice sizes and different level p of the optimisation. We observe that, even if the magnetisation is obtained for small lattice sizes, its behaviour suggests the presence of a transition separating a ferromagnetic from a paramagnetic phase.