Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems

Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, Prasanna BalaprakashAAAI 2020 · DOI

Abstract

Optimizing parameters for the Quantum Approximate Optimization Algorithm (QAOA) is traditionally a computationally expensive, instance-specific task. This paper proposes a paradigm shift, treating QAOA optimization as a learning problem. By employing Reinforcement Learning (RL) and Kernel Density Estimation (KDE), the authors demonstrate that models trained on small, classically simulatable circuits can generalize to larger problem instances. This approach reduces the optimality gap by up to 30x compared to standard classical optimizers.

Introduction

The Quantum Approximate Optimization Algorithm (QAOA) is a prominent candidate for achieving quantum advantage on Near-term Intermediate-Scale Quantum (NISQ) devices. However, its performance is heavily dependent on finding optimal variational parameters ($\beta$ and $\gamma$) via classical optimization. This process is often hindered by non-convex energy landscapes and numerous local optima, requiring extensive quantum device evaluations. Traditionally, each problem instance is treated in isolation, ignoring structural similarities between related problems. This work seeks to "amortize" these costs by learning optimization strategies that transfer across instances.

Methodology

The authors introduce two primary machine-learning-based frameworks to streamline QAOA parameter optimization:

  1. Deep Reinforcement Learning (RL): Optimization is modeled as a Markov Decision Process. Using the Proximal Policy Optimization (PPO) algorithm, an RL agent learns to navigate the parameter space by observing historical changes and objective values. This allows the agent to develop a specialized optimization policy tailored to the specific problem class.
  2. Kernel Density Estimation (KDE): This generative method leverages optimal parameters found in small training instances. By applying KDE to these points, a "meta-distribution" is formed. For new instances, high-quality starting points are sampled directly from this distribution, significantly reducing search time.

Experimental Setup and Datasets

The study evaluates these methods on the Max-Cut problem across four distinct graph topologies to ensure robustness:

  • Erdos-Renyi (Random): General random connectivity.
  • Ladder: Structured, grid-like connectivity.
  • Barbell: Two dense clusters connected by a single bridge.
  • Caveman: Multiple tight cliques with sparse inter-clique connections.
Graph topologies used for evaluation

Models were trained on small graphs (8 vertices) and tested on larger graphs (up to 20 vertices) to assess generalization capabilities.

Key Insights and Results

A central finding of this research is parameter concentration: optimal QAOA parameters for a specific problem class tend to cluster in specific regions of the parameter space, regardless of the system size. This phenomenon enables models trained on small-scale classical simulations to remain effective for larger systems.

KDE plot showing parameter concentration

The RL agent effectively learns the underlying geometry of the landscape, avoiding local traps that typically defeat standard optimizers like COBYLA or Nelder-Mead. Quantitatively, the proposed methods reduced the optimality gap by up to 30.15 times compared to Nelder-Mead. Furthermore, these learned models achieved high-quality solutions within a few hundred evaluations, a significant improvement over the thousands required by traditional methods.

Conclusion and Future Work

While these results are promising, the study was conducted in a noiseless simulation environment. Future research must address the impact of hardware noise on NISQ devices, which may distort the parameter landscape. Additionally, extending these techniques to other combinatorial problems, such as the Traveling Salesperson Problem, and testing on actual quantum hardware remain critical next steps for validating the scalability of learned optimization in quantum computing.

Summary updated

BibTeX
@inproceedings{khairy2020learning,
  author = {Sami Khairy and Ruslan Shaydulin and Lukasz Cincio and Yuri Alexeev and Prasanna Balaprakash},
  title = {{Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i03.5616},
}
Figure