Metraipolis › archive › dc_f9198da23913
QAOA Inside ADMM: Subproblem Wins Do Not Become Decomposition Wins at Matched Budgets — arXiv:2611.10527
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.10527
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-10T18:45:55.072Z
- SHA-256 of the archived text
ce7bae6fcf21b533b187dd4f485f96066f13581090f1603f64c2c43a0dfb39a9- Stable URL of this page
https://metraipolis.com/documento/dc_f9198da23913
How to cite
QAOA Inside ADMM: Subproblem Wins Do Not Become Decomposition Wins at Matched Budgets — arXiv:2611.10527 — arXiv (en), https://arxiv.org/abs/2611.10527 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f9198da23913 (Metraipolis archive dc_f9198da23913, sha256 ce7bae6fcf21b533b187dd4f485f96066f13581090f1603f64c2c43a0dfb39a9)
BibTeX
@misc{dcf9198da23913,
title = {QAOA Inside ADMM: Subproblem Wins Do Not Become Decomposition Wins at Matched Budgets — arXiv:2611.10527},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.10527},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f9198da23913; sha256 ce7bae6fcf21b533b187dd4f485f96066f13581090f1603f64c2c43a0dfb39a9},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.10527. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We benchmark the quantum approximate optimization algorithm (QAOA) as the binary subproblem solver in a two-block alternating direction method of multipliers (ADMM) for mixed-binary problems against classical solvers under matched budgets. With 23 optimizer evaluations per subproblem, scoring determines the comparison: on its final readout, the optimized QAOA loses to random search at $n=12$ and 16 binary variables (inconclusive at 20; exploratory and post hoc tests). When credited with its best sample, it wins. In a noiseless 12-qubit simulation, transferred-angle depth-2 QAOA finds the exact optimum of 97.3\% of planted-family subproblems, against 50.6\%--67.4\% for the four strongest local heuristics (100\% against 90.4\%--94.4\% crediting the four best bitstrings) and a not significantly different 96.5\% for semidefinite rounding with local search (SDP+LS). Under our evaluation-counting convention, its time to solution there is a factor of three to five below the local heuristics' but grows with a larger exponent; it is ten times that of SDP+LS and, in seconds, 54 times that of tabu search with restarts. For the benchmark class, an unconstrained binary quadratic problem in disguise, ADMM's binary step is a proximal step on the reduced problem: at unit penalty ADMM re-solves it, and for larger penalties exact solutions increasingly stall. On two families that do not reduce to one, less accurate solvers found the problem optimum more often at unit and larger penalties. No family gave QAOA a better ADMM outcome than the best classical solver and penalty. The benchmark includes a correctness gate and a log of its hypothesis tests. Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno). Categorie arXiv: Quantum Physics (quant-ph) ; Distributed, Parallel, and Cluster Computing (cs.DC). Pagina del lavoro: https://arxiv.org/abs/2611.10527 — 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-11-10T18:38:07.450Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).