Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond
share
Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019], we study the limitations of the Quantum Approximate Optimization Algorithm (QAOA) and show that there exists ϵ > 0, such that ϵlog(n) depth QAOA cannot arbitrarily-well approximate boolean constraint satisfaction problems as long as the problem satisfies a combinatorial property from statistical physics called the coupled overlap-gap property (OGP) [Chen et al., Annals of Probability, 47(3), 2019]. We show that the random problem has this property when k≥4 is even by extending the corresponding result for diluted k-spin glasses. As a consequence of our techniques, we confirm a conjecture of Brandao et al. [arXiv:1812.04170, 2018] asserting that the landscape independence of QAOA extends to logarithmic depth – in other words, for every fixed choice of QAOA angle parameters, the algorithm at logarithmic depth performs almost equally well on almost all instances. Our results provide a new way to study the power and limit of QAOA through statistical physics methods and combinatorial properties.
READ FULL TEXT