On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA

Abstract

We investigate the Maximum Cut (MaxCut) problem on different graph classes with the Quantum Approximate Optimization Algorithm (QAOA) using symmetries. In particular, heuristics on the relationship between graph symmetries and the approximation ratio achieved by a QAOA simulation are considered. To do so, we first solve the MaxCut problem on well-known graphs, then we consider a simple and controllable perturbation of the graph and find again the approximate MaxCut with the QAOA. Through an analysis of the spectrum of the graphs and their perturbations, as well as a careful study of the associated automorphism groups, we aim to extract valuable insights into how symmetry impacts the performance of QAOA. These insights can then be leveraged to heuristically reduce the quantum circuit complexity, the number of training steps, or the number of parameters involved, thus enhancing the efficiency and effectiveness of QAOA-based solutions.

39 pages, 11 figures, 2 tables

References in corpus (19)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Classification of topological quantum matter with symmetries
• Parameterized quantum circuits as machine learning models
• Quantum algorithms: an overview
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Resource-Efficient Quantum Algorithm for Protein Folding
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• MAXCUT QAOA performance guarantees for p >1
• Benchmarking the performance of portfolio optimization with QAOA
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs