Original title: Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs
Bao Bach, Boris Tsvelikhovskiy, Jose Falla, Ilya Safro · September 2026
In computing, different ways of stating the same puzzle can change how a quantum computer solves it. For MaxCut, fixing one point removes a simple global symmetry. While this keeps the problem identical classically, it heavily changes the quantum dynamics of the Quantum Approximate Optimization Algorithm, or QAOAA quantum algorithm that uses layered quantum operations to approximate solutions to optimization problems.. These dynamics live in a mathematical structure called a dynamical Lie algebraA mathematical structure that captures the possible behaviors of a quantum algorithm's circuit., which is normally exponentially expensive to calculate directly. To fix this, researchers created a polynomial classical algorithm for trees, which are branch-like graphs without loops. The algorithm distinguishes graph points using shortest path structure and whether their connection count is odd or even. This approach efficiently reveals the algebra from the graph alone, showing how classical graph shapes can diagnose quantum behavior beforehand.
Imagine packing a suitcase for a trip where each item you add changes the suitcase's shape and capacity. Normally, you can plan based on fixed dimensions, but if the space shifts with every choice, your initial plan falls apart. In this paper, fixing one vertex in the quantum algorithm is like adding an item that reshapes the effective problem space. The classical algorithm predicts these dynamic changes by analyzing the graph structure alone, similar to foreseeing how packing affects capacity without opening the suitcase.
This helps quantum algorithm designers understand and optimize performance without expensive simulations or hardware runs. For optimization tasks like MaxCut, it shows how classical problem structure can influence quantum behavior, potentially making quantum computing more efficient.
The method is specifically for symmetry-reduced QAOA instances on acyclic graphs, like trees. It may not generalize to all quantum algorithms or graphs with loops. When full vertex resolution isn't achieved, it only provides lower bounds on the dynamical Lie algebra dimension rather than exact values.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs — Bao Bach, Boris Tsvelikhovskiy, Jose Falla et al.
Abstract licence: CC0
Explanation generated by Synthesis from the abstract — it is not the original paper. This is a preprint, so it hasn't necessarily been peer reviewed.