Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems

Sami Khairy; Ruslan Shaydulin; Lukasz Cincio; Yuri Alexeev; Prasanna Balaprakash

Source-linked AI summary

Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems

Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, Prasanna Balaprakash

arXiv:1911.11071v1Nov 25, 2019cs.LGquant-phstat.ML

TL;DR

QAOA parameter optimization is difficult and expensive, motivating methods that transfer knowledge across problem instances. The paper learns RL and KDE-based parameter optimizers from small instances and applies them to larger unseen problems. In simulations, these approaches reduce the optimality gap by factors up to 30.15 versus off-the-shelf optimizers.

Problem
QAOA solution quality depends on finding effective variational parameters, while parameter optimization is difficult and quantum-circuit evaluations are expensive.
Method
The paper trains an RL policy network and a KDE generative model on small graph instances to optimize parameters for unseen test instances.
Results
The RL- and KDE-based approaches reduce the optimality gap by factors up to 30.15 compared with Nelder-Mead.
Takeaways & Limitations
Learning from representative instances can amortize QAOA parameter-optimization cost across graph instances and support optimization of unseen circuits.
Takeaways & Limitations
Future work is needed to study these machine-learning-based methods on constrained combinatorial problems such as maximum independent set and max κ colorable subgraphs.

Abstract

from arXiv · show

Quantum computing is a computational paradigm with the potential to outperform classical methods for a variety of problems. Proposed recently, the Quantum Approximate Optimization Algorithm (QAOA) is considered as one of the leading candidates for demonstrating quantum advantage in the near term. QAOA is a variational hybrid quantum-classical algorithm for approximately solving combinatorial optimization problems. The quality of the solution obtained by QAOA for a given problem instance depends on the performance of the classical optimizer used to optimize the variational parameters. In this paper, we formulate the problem of finding optimal QAOA parameters as a learning task in which the knowledge gained from solving training instances can be leveraged to find high-quality solutions for unseen test instances. To this end, we develop two machine-learning-based approaches. Our first approach adopts a reinforcement learning (RL) framework to learn a policy network to optimize QAOA circuits. Our second approach adopts a kernel density estimation (KDE) technique to learn a generative model of optimal QAOA parameters. In both approaches, the training procedure is performed on small-sized problem instances that can be simulated on a classical computer; yet the learned RL policy and the generative model can be used to efficiently solve larger problems. Extensive simulations using the IBM Qiskit Aer quantum circuit simulator demonstrate that our proposed RL- and KDE-based approaches reduce the optimality gap by factors up to 30.15 when compared with other commonly used off-the-shelf optimizers.

1 Introduction

QAOA is a hybrid quantum-classical candidate for near-term quantum advantage, but its solution quality depends on classical optimization of variational parameters. The paper therefore formulates QAOA parameter optimization as a learning task and proposes RL- and KDE-based approaches trained on small instances for larger unseen problems.

Motivation: QAOA combines parameterized quantum evolution on a NISQ device with classical optimization of variational parameters for combinatorial problems.Robust parameter optimization is presented as necessary for practical quantum advantage.
Motivation: QAOA parameter optimization is difficult because its objective is nonconvex and has low-quality nondegenerate local optima.Existing approaches include gradient-based and derivative-free optimizers.
Contributions: The paper formulates learning a QAOA parameter-optimization policy as a reinforcement-learning task that exploits geometrical regularities in training objectives.The learned policy is intended to optimize new circuits for unseen test instances.
Contributions: A kernel-density-estimation approach learns a generative model of optimal QAOA parameters for sampling on new circuits.Both approaches use small-sized training instances while targeting larger test instances.
Contributions: The proposed approaches reduce the optimality gap by factors up to 30.15 versus commonly used off-the-shelf optimizers.The evaluation uses simulations with the IBM Qiskit Aer quantum circuit simulator.

2 The Quantum Approximate Optimization Algorithm

QAOA encodes combinatorial objectives in a cost Hamiltonian and alternates cost and mixer evolutions to prepare parameterized quantum states. Classical optimization varies the parameters to maximize expected cost energy, while circuit depth trades approximation quality against optimization complexity and hardware errors.

QAOA construction: QAOA encodes binary combinatorial assignments in a cost Hamiltonian and prepares a variational state using alternating cost and mixer operators.For unconstrained problems, the initial state is a uniform superposition.
Parameter optimization: The classical optimizer varies β and γ to maximize the expected energy of the cost Hamiltonian.In the ideal p →∞ limit, suitable parameters can encode the optimal classical solution.
Depth trade-offs: QAOA depth p balances approximation ratio, parameter-optimization complexity, and accumulated errors.Higher depth can improve approximation ratios, but hardware errors can dominate on near-term devices.
Applications: QAOA has been applied to Max-Cut, network community detection, and portfolio optimization, among other problems.For Max-Cut, prior work reported approximation ratios exceeding the classical Goemans-Williamson algorithm in some settings.
Max-Cut: For Max-Cut, QAOA partitions graph vertices into two disjoint subsets while maximizing the total weight of crossing edges.Max-Cut is used because it is equivalent to quadratic unconstrained binary optimization.
Linear-algebraic interpretation: The linear-algebraic view treats quantum states as superpositions in C2^n and QAOA operators as 2^n × 2^n linear transformations.The target is a unit-length eigenvector corresponding to the maximum eigenvalue of the cost Hamiltonian.

3 Related Works

Prior work documents that QAOA parameter optimization is difficult for off-the-shelf methods because its landscapes are nonconvex. This paper responds by learning optimization structure across instances through RL and KDE methods, amortizing parameter-search cost.

Existing optimization methods: Off-the-shelf QAOA parameter optimization is difficult because energy landscapes are nonconvex with low-quality nondegenerate local optima.Prior work includes both gradient-based and derivative-free methods.
Learned optimization: For graph instances from reasonable distributions, QAOA energy landscapes are described as graph-instance-independent, motivating learned optimization methods.The proposed methods exploit geometrical structure and concentration of optimal parameters.
Learned optimization: The paper frames QAOA parameter optimization as analogous to learning an optimizer that exploits structure within a class of problems.This perspective parallels learned optimization work using LSTMs and reinforcement-learning policy networks.

4 Learning Optimal QAOA Parameters

The paper amortizes QAOA parameter optimization across graph instances using reinforcement learning and kernel density estimation. Both approaches learn from training instances to optimize unseen test instances, including larger graphs.

Learning framework: The framework learns QAOA optimization from representative training instances, then applies the learned models to high-quality optimization on unseen test instances.Quantum-circuit evaluations are expensive, so the approach aims to amortize optimization cost across graph instances.
Reinforcement learning: The RL approach learns a policy that maps finite-difference histories of objectives and parameters to iterative parameter-update actions.States contain L history iterations of objective and parameter differences, while actions are step vectors for updating β and γ.
Reinforcement learning: The RL reward is the change in the QAOA objective after applying the proposed parameter update.The policy is trained with PPO, whose clipping regularizes policy updates by limiting deviation from the previous policy.
Kernel density estimation: The KDE approach learns a meta-distribution of optimal QAOA parameters across diverse graph classes and samples new parameters from that distribution.It retains parameters achieving at least 99% optimality for training instances and uses Gaussian-kernel smoothing for the density estimate.
Graph instances: The experiments use Erdős–Rényi, ladder, barbell, and Caveman graph classes, with training instances smaller than the unseen test instances.The train and test sets are disjoint, and the test set contains 94 instances with varying numbers of vertices.

5 Results and Discussion

Training improves the RL optimization policy, while KDE learns regions where optimal QAOA parameters concentrate. Across graph classes and circuit depths, KDE maintains the strongest optimality ratios, and the proposed approaches reduce the optimality gap versus Nelder-Mead by up to 30.15.

RL and KDE training: The RL agent’s expected total discounted reward improves during training, and the epoch-750 policy reaches higher objective values more quickly than earlier policies.At the beginning, performance is comparable to random sampling; later training produces faster-rising trajectories.
RL and KDE training: KDE training shows that optimal QAOA parameters for p = 1 training instances concentrate in specific regions of parameter space.The learned bivariate density is visualized with contour lines.
Benchmark setup: The benchmark compares RL and sampling-KDE strategies with BOBYQA, COBYLA, Nelder-Mead, and random sampling using ten attempts from ten random parameter initializations.The comparison is designed around derivative-free optimization under a fixed evaluation budget.
Test performance: The KDE-based approach maintains high optimality ratios as parameter dimension increases from p = 1 to p = 4 and is superior across graph classes.RL, random sampling, and derivative-free optimizers degrade more as dimension increases; graph classes include random, community, and ladder graphs.
Gap reduction: 30.15 is the maximum optimality-gap reduction factor achieved by the proposed RL- and KDE-based approaches relative to Nelder-Mead.The reported gap reduction factor is consistently larger than 1.
Test performance: Increasing QAOA circuit depth improves the expected approximation ratio, especially for community and ladder graph instances.The ratio is measured relative to the classical optimum found by brute force.

6 Conclusion

The paper presents RL- and KDE-based approaches for learning QAOA parameters, trained on small instances and applied to larger ones. Results compare these methods with other optimizers and examine how circuit depth affects approximation ratios.

Contributions: RL learns a policy network and KDE learns a generative model of optimal QAOA parameters for new circuits.The approaches use learned structure from training instances to optimize unseen QAOA circuits.
Results: RL and KDE outperform derivative-free optimizers including COBYLA, BOBYQA, and Nelder-Mead on the reported graph-instance comparisons.Figure 4 evaluates expected optimality ratios for random, community, and ladder graphs at depths p ∈{1, 2, 4}.
Results: Higher-depth QAOA circuits improve the attained approximation ratio, especially for community and ladder graph instances.Figure 5 reports expected approximation ratios relative to classical optima found by brute force.
Contributions: Training on small-sized instances nevertheless supports efficient solution of larger problem instances.The paper frames this transfer as amortizing QAOA optimization cost across combinatorial instances.
Future work: Future work will extend the machine-learning-based methods to constrained combinatorial problems such as maximum independent set and max κ colorable subgraphs.These target problems are identified as having applications in many disciplines.