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

Vivek Katial (), Kate Smith-Miles (), Charles Hill () and Lloyd Hollenberg ()
Additional contact information
Vivek Katial: School of Mathematics and Statistics, The University of Melbourne, Parkville, Victoria 3010, Australia
Kate Smith-Miles: School of Mathematics and Statistics, The University of Melbourne, Parkville, Victoria 3010, Australia
Charles Hill: School of Mathematics and Statistics, The University of Melbourne, Parkville, Victoria 3010, Australia; and School of Physics, The University of Melbourne, Parkville, Victoria 3010, Australia; and School of Physics, University of New South Wales, Sydney, New South Wales 2052, Australia
Lloyd Hollenberg: School of Physics, The University of Melbourne, Parkville, Victoria 3010, Australia

INFORMS Journal on Computing, 2025, vol. 37, issue 1, 146-171

Abstract: 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.

Keywords: algorithm selection; instance space; quantum computing; optimization; MaxCut (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2024.0564 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:1:p:146-171

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().