Graph neural network initialisation of quantum approximate optimisation
Preprint
Abstract
Approximate combinatorial optimisation has emerged as one of the most promising application areas for quantum computers, particularly those in the near term. In this work, we focus on the quantum approximate optimisation algorithm (QAOA) for solving the MaxCut problem. Specifically, we address two problems in the QAOA, how to initialise the algorithm, and how to subsequently train the parameters to find an optimal solution. For the former, we propose graph neural networks (GNNs) as a warm-starting technique for QAOA. We demonstrate that merging GNNs with QAOA can outperform both approaches individually. Furthermore, we demonstrate how graph neural networks enables warm-start generalisation across not only graph instances, but also to increasing graph sizes, a feature not straightforwardly available to other warm-starting methods. For training the QAOA, we test several optimisers for the MaxCut problem up to 16 qubits and benchmark against vanilla gradient descent. These include quantum aware/agnostic and machine learning based/neural optimisers. Examples of the latter include reinforcement and meta-learning. With the incorporation of these initialisation and optimisation toolkits, we demonstrate how the optimisation problems can be solved using QAOA in an end-to-end differentiable pipeline.Keywords
All Related Versions
This publication has 70 references indexed in Scilit:
- Mixer-phaser Ansätze for quantum optimization with hard constraintsQuantum Machine Intelligence, 2022
- Optimizing quantum heuristics with meta-learningQuantum Machine Intelligence, 2021
- Graph neural networks: A review of methods and applicationsAI Open, 2020
- Learning Heuristics for the TSP by Policy Gradient2018
- A variational eigenvalue solver on a photonic quantum processorNature Communications, 2014
- Quantum Computation and Quantum Information2012
- Clustering Pairwise Distances with Missing Data: Maximum Cuts Versus Normalized Cuts2006
- Semidefinite programmingMathematical Programming, 1997
- A Direct Search Optimization Method That Models the Objective and Constraint Functions by Linear Interpolation1994
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991