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

Abstract 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 ($15$, $18$, and $24$ 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 $24$-qubitinstance. 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 $24$-qubit instance, raising the optimal rate from $6.7\%$ to $93.3\%$; its accuracy is governed by the size of each sub-problem and, unlike the monolithic pipeline, improves as the samplingbudget 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

Authors

Institutions

Publication Details

Journal
Research Square
Published
2026-11-17
DOI
https://doi.org/10.21203/rs.3.rs-11571311/v1
Primary Topic
Quantum Computing Algorithms and Architecture
Type
preprint

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

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

Imen Benzarti, Christophe Père, Julien Cardinal, Jean-marc Robert et al.
1 links
Research Square
Quantum Computing Algorithms and Architecture
preprint

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

Imen Benzarti, Christophe Père, Julien Cardinal, Jean-marc Robert, Ghizlane El Boussaidi, Andrew Chedid
preprint en

Abstract

Abstract 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 ($15$, $18$, and $24$ 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 $24$-qubitinstance. 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 $24$-qubit instance, raising the optimal rate from $6.7\%$ to $93.3\%$; its accuracy is governed by the size of each sub-problem and, unlike the monolithic pipeline, improves as the samplingbudget 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

Research Square
École de Technologie Supérieure (CA)
Mitacs, Alliance de recherche numérique du Canada
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon