跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.09744 · v1

QAOA for Layered Architecture Recovery: Feasibility, Limits, and the Role of Decomposition

面向分层架构恢复的QAOA:可行性、局限与分解的作用

首次提交 2026-11-07 01:16
版本更新 2026-11-07 01:16
雷达观测 2026-11-09 13:22
arXiv ↗PDF ↗

摘要

Layered architecture recovery (LAR) reconstructs a system's architectural layers from its package dependencies, and is defined as a combinatorial optimisation problem solved with classical search. We investigate whether the Quantum Approximate Optimization Algorithm (QAOA) can be applied to LAR, and with what practical limitations. We formulate LAR as a Quadratic Semi-Assignment Problem, transform it into a Quadratic Unconstrained Binary Optimisation (QUBO) problem in which each package is penalised unless it is assigned to exactly one layer, and encode it as an Ising Hamiltonian solved by QAOA. To reach instances beyond the qubit budget of a single circuit, we also apply an impact-guided decomposition that solves the problem as a sequence of smaller sub-problems. We evaluate the approach on three real Java systems (1515, 1818, and 2424 qubits), studying the effect of circuit depth and sampling budget (RQ1), a comparison with a classical Tabu Search baseline (RQ2), robustness to simulated quantum noise (RQ3), and the decomposition (RQ4). We find that monolithic QAOA is feasible and accurate on the two smaller systems but fails on the 2424-qubit instance, that the sampling budget rather than circuit depth governs its accuracy, and that it is competitive with but does not outperform Tabu Search. Decomposition restores reliable recovery on the 2424-qubit instance, raising the optimal rate from 6.7%6.7\% to 93.3%93.3\%; its accuracy is governed by the size of each sub-problem and, unlike the monolithic pipeline, improves as the sampling budget is reduced. Our results indicate that, in the current noisy intermediate-scale regime, problem decomposition, rather than larger circuits or more sampling, is the key to applying QAOA to software architecture recovery.

AI 论文解读

基于摘要 · 非全文审阅

该研究将分层架构恢复(LAR)建模为QUBO并用QAOA求解,发现分解比增大电路或采样预算更关键。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-07 01:16 · 最新观测版本

QAOA for Layered Architecture Recovery: Feasibility, Limits, and the Role of Decomposition

Layered architecture recovery (LAR) reconstructs a system's architectural layers from its package dependencies, and is defined as a combinatorial optimisation problem solved with classical search. We investigate whether the Quantum Approximate Optimization Algorithm (QAOA) can be applied to LAR, and with what practical limitations. We formulate LAR as a Quadratic Semi-Assignment Problem, transform it into a Quadratic Unconstrained Binary Optimisation (QUBO) problem in which each package is penalised unless it is assigned to exactly one layer, and encode it as an Ising Hamiltonian solved by QAOA. To reach instances beyond the qubit budget of a single circuit, we also apply an impact-guided decomposition that solves the problem as a sequence of smaller sub-problems. We evaluate the approach on three real Java systems (1515, 1818, and 2424 qubits), studying the effect of circuit depth and sampling budget (RQ1), a comparison with a classical Tabu Search baseline (RQ2), robustness to simulated quantum noise (RQ3), and the decomposition (RQ4). We find that monolithic QAOA is feasible and accurate on the two smaller systems but fails on the 2424-qubit instance, that the sampling budget rather than circuit depth governs its accuracy, and that it is competitive with but does not outperform Tabu Search. Decomposition restores reliable recovery on the 2424-qubit instance, raising the optimal rate from 6.7%6.7\% to 93.3%93.3\%; its accuracy is governed by the size of each sub-problem and, unlike the monolithic pipeline, improves as the sampling budget is reduced. Our results indicate that, in the current noisy intermediate-scale regime, problem decomposition, rather than larger circuits or more sampling, is the key to applying QAOA to software architecture recovery.

查看此版本解读 →查看此版本原文 ↗