Classical symmetries and the Quantum Approximate Optimization Algorithm
Authors:
- Ruslan ShaydulinRSRuslan Shaydulin
- Stuart HadfieldSHStuart Hadfield
- Tad HoggTHTad Hogg
- Ilya SafroISIlya Safro
Preprint
Abstract
We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques towards predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize.Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Optimizing quantum heuristics with meta-learningQuantum Machine Intelligence, 2021
- Engineering fast multilevel support vector machinesMachine Learning, 2019
- Asynchronously parallel optimization solver for finding multiple minimaMathematical Programming Computation, 2018
- A batch, derivative-free algorithm for finding multiple local minimaOptimization and Engineering, 2015
- Automorphism group and diameter of a graphJournal of Graph Theory, 2011
- Polynomial Time Approximation Schemes for Dense Instances of NP-Hard ProblemsJournal of Computer and System Sciences, 1999
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Isomorphism of graphs of bounded valence can be tested in polynomial timeJournal of Computer and System Sciences, 1982
- Entropy and the complexity of graphs: I. An index of the relative complexity of a graphBulletin of Mathematical Biology, 1968
- Asymmetric graphsActa Mathematica Hungarica, 1963