Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs
Abstract
Classically equivalent formulations of an optimization problem need not lead to equivalent quantum algorithms. For MaxCut, fixing the value of a single vertex removes a simple global symmetry without changing the underlying optimization problem, yet it can substantially alter the quantum dynamics generated by the Quantum Approximate Optimization Algorithm (QAOA). These dynamics are captured by the circuit's dynamical Lie algebra (DLA), whose direct construction can become exponentially expensive. Here we show that, for symmetry-reduced QAOA on trees, substantial information about the reduced DLA can instead be obtained efficiently from the graph alone. We introduce a polynomial classical algorithm that recursively distinguishes vertices using shortest path structure and degree parity. When all vertices are resolved individually, the method determines the complete reduced DLA and, under the corresponding graph conditions, certifies maximal expressibility of the reduced QAOA ansatz. Even when full resolution is not achieved, the algorithm identifies embedded subalgebras, provides rigorous lower bounds on DLA dimension, and certifies controllable subsystems. Our theoretical and experimental results show how classical graph structure can be used to diagnose and potentially guide the quantum dynamics of variational algorithms before running them on quantum hardware.
Related
- A Geometric Principle for Path Selection in Directed Acyclic Graphs
- An Efficient Error-Controlled POD Reduced-Order Collocation Spectral Method for Unsteady Incompressible Navier–Stokes Equations
- Efficient expectation value estimation for quantum circuits via extended stabilizer frameworks and adaptive variance estimation
- Real-Time Estimation of High-Resolution Flow Fields and Reduced-Order Coordinates from Event-Based Imaging Velocimetry
- Hamiltonian-Guided Leverage Embedding: Robust Subspace Compression for Efficient QAOA Parameter Estimation
BibTeX
@misc{bach2026efficient,
title = {{Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs}},
author = {Bao Bach and Boris Tsvelikhovskiy and Jose Falla and Ilya Safro},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03317},
eprint = {2609.03317},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03317},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs
AU - Bao Bach
AU - Boris Tsvelikhovskiy
AU - Jose Falla
AU - Ilya Safro
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03317
UR - https://arxiv.org/abs/2609.03317
AB - Classically equivalent formulations of an optimization problem need not lead to equivalent quantum algorithms. For MaxCut, fixing the value of a single vertex removes a simple global symmetry without changing the underlying optimization problem, yet it can substantially alter the quantum dynamics generated by the Quantum Approximate Optimization Algorithm (QAOA). These dynamics are captured by the circuit's dynamical Lie algebra (DLA), whose direct construction can become exponentially expensive. Here we show that, for symmetry-reduced QAOA on trees, substantial information about the reduced DLA can instead be obtained efficiently from the graph alone. We introduce a polynomial classical algorithm that recursively distinguishes vertices using shortest path structure and degree parity. When all vertices are resolved individually, the method determines the complete reduced DLA and, under the corresponding graph conditions, certifies maximal expressibility of the reduced QAOA ansatz. Even when full resolution is not achieved, the algorithm identifies embedded subalgebras, provides rigorous lower bounds on DLA dimension, and certifies controllable subsystems. Our theoretical and experimental results show how classical graph structure can be used to diagnose and potentially guide the quantum dynamics of variational algorithms before running them on quantum hardware.
ER -