Metraipolis › archive › dc_15c582ff3548
Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs — arXiv:2609.03317
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.03317
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T03:03:21.458Z
- SHA-256 of the archived text
4f60dd8bdd069a543f233687fc78df44ac0c4cc717653af5bab661887c734dbb- Stable URL of this page
https://metraipolis.com/documento/dc_15c582ff3548
How to cite
Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs — arXiv:2609.03317 — arXiv (en), https://arxiv.org/abs/2609.03317 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_15c582ff3548 (Metraipolis archive dc_15c582ff3548, sha256 4f60dd8bdd069a543f233687fc78df44ac0c4cc717653af5bab661887c734dbb)
BibTeX
@misc{dc15c582ff3548,
title = {Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs — arXiv:2609.03317},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.03317},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_15c582ff3548; sha256 4f60dd8bdd069a543f233687fc78df44ac0c4cc717653af5bab661887c734dbb},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.03317. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-09-04 in quant-ph). Categorie arXiv: Quantum Physics (quant-ph). Pagina del lavoro: https://arxiv.org/abs/2609.03317 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-17T02:49:19.487Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).