On the Instance Dependence of Parameter Initialization for the Quantum Approximate Optimization Algorithm: Insights via Instance Space Analysis

The quantum approximate optimization algorithm (QAOA) tackles combinatorial optimization problems in a quantum computing context, where achieving globally optimal and exact solutions is not always feasible because of classical computational constraints or problem complexity. The performance of QAOA generally depends on finding sufficiently good parameters that facilitate competitive approximate solutions. However, this is fraught with challenges, such as “barren plateaus,” making the search for effective parameters a nontrivial endeavor. More recently, the question of whether such an optimal parameter search is even necessary has been posed, with some studies showing that optimal parameters tend to be concentrated on certain values for specific types of problem instances. However, these existing studies have only examined specific instance classes of Maximum Cut, so it is uncertain if the claims of instance independence apply to a diverse range of instances. In this paper, we use instance space analysis to study QAOA parameter initialization strategies for the first time, providing a comprehensive study of how instance characteristics affect the performance of initialization strategies across a diverse set of graph types and weight distributions. Unlike previous studies that focused on specific graph classes (e.g., d-regular or Erdős–Rényi), our work examines a much broader range of instance types, revealing insights about parameter transfer between different graph classes. We introduce and evaluate a new initialization strategy, quantum instance-based parameter initialization, that leverages instance-specific information, demonstrating its effectiveness across various instance types. Our analysis at higher QAOA depths (p = 15) provides insights into the effectiveness of different initialization strategies beyond the low-depth circuits typically studied. History: Accepted by Giacomo Nannicini, Area Editor for Quantum Computing and Operations Research. This article is accepted for Special Issue. Funding: This research was supported by the Australian Research Council [Grant IC200100009 for the Australian Research Council Training Centre in Optimization Technologies, Integrated Methodologies and Applications]. V. Katial is supported by The University of Melbourne [Research Training Program Scholarship]. The authors gratefully acknowledge the information technology infrastructure support provided by The University of Melbourne’s Research Computing Services and the Petascale Campus Initiative. This research was also supported by The University of Melbourne through the establishment of the IBM Quantum Network Hub at the university. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0564 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0564 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .