Graph neural network initialisation of quantum approximate optimisation

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.

arXiv comment12 pages, 8 Figures - publised version

References in corpus (63)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• TensorFlow: A system for large-scale machine learning
• Quantum Computing in the NISQ era and beyond
• ADADELTA: An Adaptive Learning Rate Method
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Quantum Annealing in the Transverse Ising Model
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum Circuit Learning
• Parameterized quantum circuits as machine learning models
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• Learning Combinatorial Optimization Algorithms over Graphs
• The power of quantum neural networks
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum optimization using variational algorithms on near-term quantum devices
• Spectral redemption: clustering sparse networks
• Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges
• Perspectives of quantum annealing: Methods and implementations
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Quantum Natural Gradient
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Warm-starting quantum optimization
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Exploring entanglement and optimization within the Hamiltonian Variational Ansatz
• PennyLane: Automatic differentiation of hybrid quantum-classical computations
• Improving Variational Quantum Optimization using CVaR
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Stochastic gradient descent for hybrid quantum-classical optimization
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Attention, Learn to Solve Routing Problems!
• Group-Invariant Quantum Machine Learning
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Reachability Deficits in Quantum Approximate Optimization
• Equivalence of quantum barren plateaus to cost concentration and narrow gorges
• Overview and Comparison of Gate Level Quantum Software Platforms
• Filtering variational quantum algorithms for combinatorial optimization
• An Adaptive Optimizer for Measurement-Frugal Variational Algorithms
• Supervised Community Detection with Line Graph Neural Networks
• Parameter Concentration in Quantum Approximate Optimization
• Hybrid quantum-classical algorithms for approximate graph coloring
• Practical optimization for hybrid quantum-classical algorithms
• Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information
• A case study of variational quantum algorithms for a job shop scheduling problem
• The Meta-Variational Quantum Eigensolver (Meta-VQE): Learning energy profiles of parameterized Hamiltonians for quantum simulation
• Using models to improve optimizers for variational quantum algorithms
• Quantum Graph Neural Networks
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• Characterizing local noise in QAOA circuits
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• An evolving objective function for improved variational quantum optimisation
• Avoiding local minima in Variational Quantum Algorithms with Neural Networks
• FLIP: A flexible initializer for arbitrarily-sized parametrized quantum circuits
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Progress towards analytically optimal angles in quantum approximate optimisation
• Exponentially Many Local Minima in Quantum Neural Networks
• Equivariant quantum circuits for learning on weighted graphs
• Improving the Quantum Approximate Optimization Algorithm with postselection

Cited by in corpus (18)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Barren Plateaus in Variational Quantum Computing
• Hamiltonian variational ansatz without barren plateaus
• A Hybrid Quantum Computing Pipeline for Real World Drug Discovery
• Quantum approximate optimization via learning-based adaptive optimization
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Neural network encoded variational quantum algorithms
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Quantum algorithms for scientific computing
• Variational Quantum Multi-Objective Optimization
• Bayesian Learning of Parameterised Quantum Circuits
• Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut Problems with QAOA
• Red-QAOA: Efficient Variational Optimization through Circuit Reduction
• Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Adiabatic quantum computing with parameterized quantum circuits
• Artificial intelligence for representing and characterizing quantum systems