QAOA algorithms creates pseudo-Boltzmann pure states

In this talk I will discuss the nature of the pure states created by single-layer and multi-layer Quantum Approximate Optimization Algorithm (QAOA) on universal Ising spin models. I will show that already a single layer produces thermal-like states with Gaussian perturbations [1]. We find that these pseudo-Boltzmann states can not be efficiently simulated on classical computers according to state-of-art techniques, and we relate this distribution to the optimization potential of QAOA. Moreover, we observe that the temperature depends on a hidden universal correlation between the energy of a state and the covariance of other energy levels and the Hamming distances of the state to those energies. As outlook, this work may help develop a better understanding of multi-layer QAOA and adiabatic quantum computation. To be precise, our study has revealed that a single-step QAOA with very small angles approximates well a thermal distribution. Given that single-layer QAOA approximates a short-time step in adiabatic quantum evolution, it is natural to expect that one may relate a full adiabatic quantum protocol to a process that creates pseudo-Boltzmann states—with temperatures that now also will depend on the speed of the passage.

[1] P. Diez, D. Porras, J.J. Garcia-Ripoll, arXiv:2201.03358