Classical symmetries and the Quantum Approximate Optimization Algorithm

Abstract

We study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques towards predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize.

References in corpus (32)

• Scikit-learn: Machine Learning in Python
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Classification of topological quantum matter with symmetries
• A Quantum Approximate Optimization Algorithm
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• 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
• Graph Isomorphism in Quasipolynomial Time
• Improving Variational Quantum Optimization using CVaR
• On Automorphism Groups of Networks
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Near-optimal quantum circuit for Grover's unstructured search using a transverse field
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Multistart Methods for Quantum Approximate Optimization
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
• On the representation of Boolean and real functions as Hamiltonians for quantum computing
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• Learning to learn with quantum neural networks via classical neural networks
• Local Hamiltonians Whose Ground States are Hard to Approximate
• Classical and Quantum Bounded Depth Approximation Algorithms
• Evaluating Quantum Approximate Optimization Algorithm: A Case Study
• Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemes
• Quantum Algorithms for Scientific Computing and Approximate Optimization
• Tensor Network Quantum Simulator With Step-Dependent Parallelization
• Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design
• What do QAOA energies reveal about graphs?
• Symmetries, graph properties, and quantum speedups
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• ELRUNA: Elimination Rule-based Network Alignment

Cited by in corpus (31)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Building spatial symmetries into parameterized quantum circuits for faster training
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Analytical Framework for Quantum Alternating Operator Ansätze
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Fast Simulation of High-Depth QAOA Circuits
• Practical Verification of Quantum Properties in Quantum Approximate Optimization Runs
• Multi-Angle QAOA Does Not Always Need All Its Angles
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Quantum algorithms for scientific computing
• Characterizing Error Mitigation by Symmetry Verification in QAOA
• A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• Parameter Setting Heuristics Make the Quantum Approximate Optimization Algorithm Suitable for the Early Fault-Tolerant Era
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• MLQAOA: Graph Learning Accelerated Hybrid Quantum-Classical Multilevel QAOA
• Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions
• Quantum Approximate Optimization Algorithm with Sparsified Phase Operator
• Diagrammatic Analysis for Parameterized Quantum Circuits
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
• Dual Map Framework for Noise Characterization of Quantum Computers
• Quantum imaginary time evolution and UD-MIS problem