CSIC scientists obtain evidence for quantum advantage in quantum optimization
March 21, 2022
The quantum approximate optimization algorithm (QAOA) was originally proposed as a hybrid variational algorithm suitable for solving combinatorial optimization problems on near-term noisy intermediate-scale quantum (NISQ) devices. The Quantum Information and Foundations group at the Institute of Fundamental Physics has performed a very exhaustive study of the QAOA for a wide family of NP-hard problems not only from the optimization point of view, but also by understanding the types of states the algorithm prepares.
With a new theoretical approach, their research, available at arxiv:2201.03358, reveals that the shallowest QAOA on universal Ising spin models creates pure, but thermal-like states with Gaussian perturbations. Furthermore, they find that the amplitude probability of these states approaches a Boltzmann distribution at such a low temperature that it cannot be efficiently simulated on classical computers according to state-of-the-art techniques. This low temperature of the pseudo-Boltzmann distribution of QAOA states also implies an advantage with respect to optimization. The researchers show that the algorithm exhibits a quadratic advantage over classical sampling strategies, which include uniform sampling and classical Monte Carlo. The advantage is observed in an algebraic enhancement of the probability of finding the global optimum or ground-state of the system. These results are confirmed for variety of optimization problems such as QUBO, Max-Cut and random Ising models in arbitrary dimensions.
This work is the first one to illustrate a quantum advantage for QAOA in optimization. As future prospects, in addition to opening new avenues for proving quantum advantages, the tools in this manuscript may shed light on more complex circuits, as well as offer new methods to understand the behavior of adiabatic quantum computers and quantum simulators.
E-print: QAOA pseudo-Boltzmann states, P. Díez, D. Porras, J. J. García-Ripoll, https://arxiv.org/abs/2201.03358
