Exploiting Symmetry Reduces the Cost of Training QAOA

Abstract

A promising approach to the practical application of the Quantum Approximate Optimization Algorithm (QAOA) is finding QAOA parameters classically in simulation and sampling the solutions from QAOA with optimized parameters on a quantum computer. Doing so requires repeated evaluations of QAOA energy in simulation. We propose a novel approach for accelerating the evaluation of QAOA energy by leveraging the symmetry of the problem. We show a connection between classical symmetries of the objective function and the symmetries of the terms of the cost Hamiltonian with respect to the QAOA energy. We show how by considering only the terms that are not connected by symmetry, we can significantly reduce the cost of evaluating the QAOA energy. Our approach is general and applies to any known subgroup of symmetries and is not limited to graph problems. Our results are directly applicable to nonlocal QAOA generalization RQAOA. We outline how available fast graph automorphism solvers can be leveraged for computing the symmetries of the problem in practice. We implement the proposed approach on the MaxCut problem using a state-of-the-art tensor network simulator and a graph automorphism solver on a benchmark of 48 graphs with up to 10,000 nodes. Our approach provides an improvement for $p=1$ on $71.7\%$ of the graphs considered, with a median speedup of $4.06$, on a benchmark where $62.5\%$ of the graphs are known to be hard for automorphism solvers.

minor revision

References in corpus (9)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Learning to learn with quantum neural networks via classical neural networks
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• Tensor Network Quantum Simulator With Step-Dependent Parallelization
• What do QAOA energies reveal about graphs?
• Planning for Compilation of a Quantum Algorithm for Graph Coloring

Cited by in corpus (21)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Empirical performance bounds for quantum approximate optimization
• Building spatial symmetries into parameterized quantum circuits for faster training
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Parameter Setting in Quantum Approximate Optimization of Weighted Problems
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Analytical Framework for Quantum Alternating Operator Ansätze
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• Fast Simulation of High-Depth QAOA Circuits
• Quantum algorithms for scientific computing
• Dynamic-ADAPT-QAOA: An algorithm with shallow and noise-resilient circuits
• Symmetry-informed transferability of optimal parameters in the Quantum Approximate Optimization Algorithm
• Characterization of variational quantum algorithms using free fermions
• Enabling High Performance Debugging for Variational Quantum Algorithms using Compressed Sensing
• Progress towards analytically optimal angles in quantum approximate optimisation
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
• Diagrammatic Analysis for Parameterized Quantum Circuits
• Non-Markovian Noise in Symmetry-Preserving Quantum Dynamics