Exploring Connections Between Mutual Information Dynamics and the Performance of QAOA

Quantum algorithms have attracted the interest of the scientific community over the past few decades due to their potential to solve classically intractable problems. The design of these algorithms has been accompanied by investigations into the role quantum mechanical phenomena, such as entanglement play in achieving quantum advantage. Here, we build on this work and investigate entanglement dynamics in a quantum algorithm that potentially offers quantum advantage in near-term devices: the quantum approximate optimization algorithm (QAOA). We examine the relationship between entanglement and the performance of QAOA in solving a well-known combinatorial problem: the MAXCUT problem. We find a correlation between the algorithm’s performance and mutual information, a metric for quantifying entanglement, though evidence of causation remains unclear. Through our analysis of entanglement, we seek to identify relationships between entanglement dynamics and computational problem structure that can be leveraged to improve algorithmic performance and accelerate algorithm training.