Argonne National Laboratory

Center for Nanoscale Materials

Improving performance of quantum optimization by leveraging problem structure

This project addresses crucial obstacles to using quantum computers to outperform classical algorithms in optimization problems. Our insights bring quantum systems closer to being useful for real-world applications.
Symmetries in the amplitudes of the quantum state of QAOA applied to a maximum cut problem on a three-node graph (left). The rotational symmetry of the graph corresponds to a permutation of qubits that preserves the quantum state.

The Quantum Approximate Optimization Algorithm (QAOA) is considered one of the leading candidate algorithms to achieve a quantum advantage in optimization problems, that is, to outperform the best known classical algorithms on some problem. This quantum algorithm is in principle capable of solving optimization problems that arise in scheduling, data analysis and machine learning. However, several known limitations must be overcome before this algorithm can achieve its goal. In this project, we have formalized a connection between the structure of the optimization problem and the quantum dynamics of the QAOA and show how this connection can be leveraged to overcome three challenges.

First, this connection can be used to predict QAOA performance [1], simplifying the task of selecting problem instances with the highest potential for quantum advantage. Second, the symmetry structure of the problem can be used to accelerate the QAOA parameter optimization in simulation [2], which is a crucial obstacle to the practical applicability of QAOA. Third, the verification of classical problem symmetries can be used to mitigate the quantum errors that occur during QAOA evolution on noisy hardware [3]. Our methods boost the quality of the solution and the success probability when executed on real quantum devices.

This project is led by Ruslan Shaydulin, who is a Maria Goeppert Mayer fellow in Argonne’s Mathematics and Computer Science (MCS) Division.

[1] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg and Ilya Safro, Classical symmetries and QAOA, arXiv:2012.04713 (2020).
[2] Ruslan Shaydulin and Stefan Wild, Exploiting symmetry reduces the cost of training QAOA, in IEEE Transactions on Quantum Engineering, 2: 1-9 (2021), doi: 10.1109/TQE.2021.3066275.
[3] Ruslan Shaydulin, Alexey Galda. Error mitigation for deep quantum optimization circuits by leveraging problem symmetries, arXiv:2106.04410 (2021).