An Empirical Study on Clustering-based Quantum Approximate Optimization Algorithm for Regression Test Case Selection

Noname manuscript No. (will be inserted by the editor)

An Empirical Study on Clustering-based Quantum Approximate Optimization Algorithm for Regression Test Case Selection

arXiv:2611.09869v1 [cs.SE] 6 Nov 2026

Antonio Trovato · Martin Beseda · Dario Di Nucci

Received: date / Accepted: date

Abstract Regression testing assesses whether software components that have already been developed and tested continue to work correctly after modifications. Ideally, regression testing re-executes the entire test suite after each modification, but this is infeasible in real-world scenarios because of the computational burden; therefore, optimized approaches, such as Test Case Selection, have been developed. The state of the art in regression testing optimization includes both classical approaches, such as Additional Greedy and DIV-GA, and quantum approaches, such as SelectQA, BootQA, and IGDec-QAOA. However, while the former incur high computational costs, the latter are constrained by the physical limitations of currently available quantum machines. This paper extends the evaluation of QAOA-TCS, our quantum approach for the test case selection problem. We thoroughly evaluate its performance, compare it with state-of-the-art classical and quantum approaches, and assess its robustness to quantum noise. The results show that QAOA-TCS outperforms state-of-the-art multiobjective approaches in most cases and maintains stable performance even under high noise levels. In the single-objective formulation, QAOA-based methods perform comparably. In terms of efficiency, our previous method based on quantum annealing, namely SelectQA, is the most efficient for large problems in the multi-objective formulation, whereas QAOA-TCS offers the best trade-off between effectiveness and efficiency in the single-objective Antonio Trovato University of Salerno, Fisciano (SA), Italy E-mail: atrovato@unisa.it Martin Beseda University of L’Aquila, L’Aquila (AQ), Italy E-mail: martin.beseda@univaq.it Dario Di Nucci University of Salerno, Fisciano (SA), Italy E-mail: ddinucci@unisa.it

2

Trovato et al.

formulation when run on realistic noisy simulators. However, such analysis is constrained by the different computational environments used to run the algorithms. Keywords Regression Testing, Regression Test Case Selection, Quantum Computing, Search-based Software Engineering 1 Introduction In modern software development, software systems undergo continuous modifications and enhancements, particularly since the advent of Agile methodologies (Annosi et al., 2024; Meier and Kock, 2023). In this landscape, each modification could interfere with the proper behavior of already developed system components; hence, there is a strong need to continuously monitor software quality. To address this problem, regression testing (Yoo and Harman, 2012) verifies, after each developer modification, whether previously implemented and tested components still function as expected, and plays a key role. The ideal regression testing approach, also called retest-all, re-executes the entire regression test suite after each software modification; however, in real-world scenarios, it quickly becomes impractical (Rothermel and Harrold, 1998; Perrouin et al., 2012). Therefore, many Regression Test Suite Optimization (RTSO) methods have been proposed to drastically reduce the costs of regression testing, without losing its effectiveness in finding defects, either by reducing the size of the starting test suite according to specific strategies, or by finding an optimal execution order following some prioritization criteria (Yoo and Harman, 2007, 2010; Yoo et al., 2011; Wang et al., 2013; Panichella et al., 2014; Arrieta et al., 2019; Xue and Li, 2020). Above all, Test Case Selection (TCS) (Engström et al., 2010; Yoo and Harman, 2012) is one of the most adopted approaches, focusing on identifying a minimal subset of the initial regression suite to minimize overall regression testing cost while preserving effectiveness, as often measured by fault and statement coverage. Although state-of-the-art classical strategies, such as Additional Greedy (Yoo and Harman, 2007) and DIV-GA (Panichella et al., 2014), have proven effective for solving TCS, their practical use is limited by their computational burden. Therefore, research has focused on alternatives that leverage the potential of quantum computing, such as superposition and entanglement (Hoare and Milner, 2005; Knight, 2018), to overcome the limitations of classical strategies in execution costs without sacrificing solution quality. Currently, such proposed strategies are: SelectQA (Trovato et al., 2024), BootQA (Wang et al., 2024b), and IGDec-QAOA (Wang et al., 2024a). While SelectQA and BootQA address the TCS problem relying on Quantum Annealing (QA) (Kadowaki and Nishimori, 1998; Suzuki, 2009), IGDec-QAOA relies on the Quantum Approximate Optimization Algorithm (QAOA) (Farhi et al., 2014; Moll et al., 2018). The major limitation of the aforementioned approaches lies in their decomposition strategy; BootQA totally commits to random sampling to produce the sub-suites to optimize, resulting in unstable results; IGDec-QAOA

An Empirical Study on Clustering-based QAOA for TCS

3

relies on an impact-guided strategy, which does not take into account dependencies among the test cases; finally, SelectQA does not rely on a tailored decomposition strategy at all, thus worsening its efficiency. This paper extends Trovato et al. (2025), where we proposed Quantum Approximate Optimization Algorithm - Test Case Selection (QAOATCS), a clustering-based QAOA approach for TCS. The novelty of the method was twofold: (i) circumventing the limitations of currently available quantum computers by leveraging a clustering-based decomposition strategy; (ii) applying QAOA to solve the multi-objective TCS problem. Although our previous study showed that QAOA-TCS outperformed stateof-the-art methods in effectiveness and efficiency, it had several limitations. First, we did not consider the effect of quantum noise in the experiments, since all QAOA-TCS executions were performed on an ideal simulator. Although this choice yielded encouraging preliminary results, it was not sufficient to assess the QAOA-based approach’s performance in real environments. Second, although the study compared the proposed approach with well-established state-of-the-art strategies in the literature, it did not consider more recent solutions based on quantum algorithms. Therefore, this paper provides a more rigorous and comprehensive empirical analysis of QAOA-TCS compared with state-of-the-art TCS strategies. Specifically, we have: – Compared QAOA-TCS with state-of-the-art single-objective quantum approaches, which were not included in the original work on QAOA-TCS – Executed both multi- and single-objective versions of our approach over five different noisy backend simulators, namely Sampling-noise simulator, Fake Brisbane with sampling noise simulator, and 1%, 2%, and 5% depolarizing-noise models with sampling noise simulators, to exhaustively evaluate the robustness of QAOA-TCS in noisy quantum environments. – Compared the performance of both the multi-objective and single-objective versions of QAOA-TCS over each noisy environment with the aforementioned classical and quantum state-of-the-art approaches. – Developed an open and reproducible online appendix (Appendix, 2026). The empirical results show that QAOA-TCS outperforms state-of-the-art multi-objective approaches in most cases and maintains stable performance even under high noise levels. In the single-objective formulation, different quantumbased methods perform comparably. Our previous quantum annealing-based method, namely SelectQA, is the most efficient for large problems in the multi-objective formulation. In contrast, QAOA-TCS offers the best trade-off between effectiveness and efficiency in the single-objective formulation when executed on realistic noisy environments. However, such analysis could be hindered by the different computational environments and simulators used to run the algorithms. Paper Structure. Section 2 introduces quantum computing and its noise, details the TCS problem we aim to tackle, and describes the baseline algorithms

4

Trovato et al.

currently available to solve it, together with their main limitations motivating the need for this study. Section 3 introduces how QAOA-TCS operates, the mathematical formulations it adopts to represent the TCS problem, and the clustering algorithm used by QAOA-TCS to decompose it. Section 4 describes the design of the empirical evaluation that compares QAOA-TCS with stateof-the-art algorithms, while its threats to validity are provided in Section 6. Finally, Section 7 summarizes the contributions of this work and envisions future work.

2 Background and Related Work This section provides a more detailed introduction to TCS and how state-ofthe-art algorithms solve it.

2.1 Test Case Selection Test Case Selection (TCS) is a modification-aware optimization strategy that identifies a reduced subset of a regression test suite sufficient to validate whether components of software systems that have already been tested and were indirectly affected by a modification continue to function as expected after the modification (Rothermel and Harrold, 1996). Several techniques have been proposed to determine which tests are relevant for the selection, including integer programming (Fischer, 1977), symbolic execution (Yau and Kishimoto, 1987), data flow analysis (Rothermel and Harrold, 1993), dependence graphs (Bates and Horwitz, 1993), and control-flow graphs (Rothermel and Harrold, 1996). Once the candidates are identified, the problem naturally becomes one of optimization: selecting the smallest possible set of tests while still achieving adequate coverage and fault detection. The goal is to reduce regression testing costs without compromising its effectiveness. Although TCS can be treated as a single-objective problem, the natural interplay among its objectives has led researchers to adopt multi-objective formulations. In particular, let Γ = {τ1 , τ2 , . . . , τn } be the starting regression test suite which we aim to optimize; let F = {f1 , f2 , . . . , fm } be the set of objectives of our selection. Multi-objective TCS aims at finding a Paretooptimal set P , such that the ∀p ∈ P, p ⊆ Γ , given the objectives in functions in F , where the elements of P are sub-suites (solutions). A solution p belongs to P if it is non-dominated by any other solution in the search space; in other words, any other solution r that improves p in some objective function in F worsens it in at least 1 function. Finally, the Pareto-optimal set consists of all non-dominated solutions, which correspond to points in an N -dimensional space (N = |F |) that form the Pareto frontier. Leveraging this formulation of TCS, Yoo and Harman (2007) introduced a multi-objective version of the traditional single-objective greedy strategy, called Additional Greedy. This method produces a solution (i.e., a subsuite) by

An Empirical Study on Clustering-based QAOA for TCS

5

iteratively selecting test cases that maximize statement and fault coverage over a given time interval. Finally, a Pareto-optimal set is obtained by selecting all non-dominated incremental subsets of the solution set. Nevertheless, this strategy suffers from scalability issues, as its execution time becomes impractical on real-world systems (Harrold et al., 1993). Therefore, Panichella et al. (2014) proposed DIV-GA, an approach that improves the established usage of Non-dominated Sorting Genetic Algorithm (NSGA-II) (Deb et al., 2000) by injecting diversity during the evolutionary process. Although DIV-GA was empirically proven to outperform its counterparts NSGA-II, Additional Greedy, and even the NSGA-II variant called vNSGA-II (Yoo and Harman, 2007), it is limited in terms of execution cost because computing the individuals to inject into populations entails additional computational effort, making this approach impractical in many real-world scenarios.

2.2 The Impact of the Quantum Era on Test Case Selection One of the greatest promises of quantum computers is to efficiently solve practically unsolvable optimization problems. The core concept behind this potential is quantum parallelism, which exploits the superposition property of quantum bits (qubits), i.e., that a qubit can exist in a state that is a linear combination of 0 and 1, to compute multiple solutions simultaneously. Quantum Annealers are a special kind of quantum machine that execute the Quantum Annealing (QA) algorithm, formulated as a Quadratic Unconstrained Binary Optimization (QUBO), as in Eq. (10). In QA, a quantum system is initialized so that its ground state can be measured by an easy-to-compute initial Hamiltonian, e.g., a mathematical function modeling the energy of a system. QA relies on the adiabatic theorem (Kadowaki and Nishimori, 1998; Suzuki, 2009), which states that if a quantum system starts in its ground state and its Hamiltonian changes slowly, it remains in the ground state. The system then slowly evolves until its ground state matches the minimal (optimal) value of the problem Hamiltonian, i.e., the one encoding the optimization problem we aim to solve. Building on this paradigm, Wang et al. (2024b) introduced BootQA, the first approach to apply quantum annealing to test suite optimization. To cope with the limited qubit capacity of current quantum annealers, BootQA relies on bootstrap sampling: starting from the original test suite T S, it randomly draws m subsets of size n, where n is chosen to fit the hardware constraints. Each subset is independently formulated as a QUBO sub-problem and solved by the annealer; the resulting sub-solutions are then merged into a final solution by retaining all test cases selected across sub-problems. Despite its efficiency, BootQA has several limitations. First, random sampling does not guarantee that the sampled subsets represent the original suite, leading to unstable coverage and inconsistent solutions. Second, because BootQA samples randomly at each run, result quality depends heavily on the initial random

6

Trovato et al.

choice. Finally, selecting the optimal hyperparameter pair (n, m) requires repeated trial runs, incurring significant execution time. In Trovato et al. (2024), we proposed SelectQA to address the coverage instability of BootQA. Rather than decomposing the problem manually, SelectQA delegates both decomposition and solving to D-Wave’s Hybrid Solver Service1 , which internally combines classical and quantum resources to handle large-scale QUBO instances. We evaluated SelectQA in two variants: a single-objective version directly comparable to BootQA and a multi-objective version compared against classical baselines such as Additional Greedy and DIV-GA. Our experiments showed that SelectQA consistently outperformed all competitors in effectiveness. However, SelectQA also has limitations. The absence of an explicit decomposition strategy makes it less scalable than BootQA for very large test suites. Furthermore, D-Wave has discontinued the limited free access to its cloud services, making the operational costs of BootQA and SelectQA expensive. Therefore, we investigate an alternative to QA based on quantum gates that addresses the broader physical limitations of quantum computers leveraging problem-decomposition strategies. 2.3 Gate-based Approaches and Backends Before introducing the algorithm and the noisy environments, we briefly summarize the concepts underlying gate-based quantum computing. The fundamental unit of quantum information is a qubit. Unlike a classical bit, which can only assume the values 0 or 1, a qubit can exist in a superposition of basis states, |ψ⟩ = α|0⟩ + β|1⟩,

(1)

where α, β ∈ C are probability amplitudes satisfying |α|2 + |β|2 = 1,

(2)

as |α|2 and |β|2 denote the probability of measuring |0⟩ or |1⟩, respectively. Another important property is that an isolated quantum system is described by unitary transformations, represented by matrices U , thus satisfying U †U = I

(3)

and subsequently preserving the norm of the system, i.e., also the probability amplitudes of the normalized quantum state. When multiple qubits are considered jointly, the state space grows as the tensor product of the individual Hilbert spaces. Consequently, an n-qubit state can generally be expressed as |Ψ ⟩ =

n 2X −1

cx |x⟩,

(4)

x=0 1 (Accessed on: 10-06-2026) https://www.dwavesys.com/media/m2xbmlhs/14-1048a-a_ d-wave_hybrid_solver_service_plus_advantage_technology_update.pdf

An Empirical Study on Clustering-based QAOA for TCS

7

where n ∈ N represents the number of qubits, |x⟩ denotes the computational basis state corresponding to the binary representation of the x ∈ N, and cx ∈ C are probability amplitudes satisfying n 2X −1

|cx |2 = 1.

(5)

x=0

A multipartite state is called separable if it can be written as |Ψ ⟩ = |ψ1 ⟩ ⊗ |ψ2 ⟩ ⊗ · · · ⊗ |ψn ⟩,

(6)

where |ψi ⟩ denotes the state of the i-th qubit. Otherwise, the state is entangled. For example, since the Bell state |Φ+ ⟩ =

|00⟩ + |11⟩ √ 2

(7)

cannot be decomposed into a tensor product of two single-qubit states, it represents an entangled state. Quantum circuits, i.e., sequences of quantum gates that implement unitary or binary operations on qubits, allow quantum algorithms to exploit superposition and entanglement. A quantum circuit implementing a unitary operator U may be expressed as U = Up Up−1 · · · U2 U1 ,

(8)

where each layer may itself be decomposed as (1)

(2)

(md )

Ud = Ud ⊗ Ud ⊗ · · · ⊗ Ud

,

(9)

where md denotes the number of gate blocks that can be executed in parallel within the d-th layer. Gates acting on overlapping sets of qubits cannot belong to the same layer and therefore contribute to the circuit depth. The operators (j) Ud act on disjoint subsets of qubits and therefore can be executed in parallel. The quantity p ∈ N is the circuit depth and represents the number of sequential gate layers required to implement the algorithm. Circuit depth is an important practical consideration, since gate imperfections and decoherence generally accumulate with the number of sequential operations, making deeper circuits more susceptible to noise. More recently, these gate-based approaches have gained attention, particularly the Quantum Approximate Optimization Algorithm (QAOA) (Farhi et al., 2014), because gate-based computers are universal, in contrast to quantum annealers, and their universality has been formally proved in (Jeandel, 2004). The algorithm can be used to solve the problems of Quadratic Unconstrained Binary Optimization (QUBO), defined as min f (x) = xT Qx,

x∈{0,1}k

(10)

8

Trovato et al.

where x = (x1 , . . . , xk )T and xi ∈ {0, 1} and Q ∈ Rk×k is a symmetric or upper-triangular matrix, while k ∈ N. QAOA then relies on the construction of a variational quantum state called “ansatz” defined as

|ψ(γ, β)⟩ =

p Y

e−iβj B e−iγj C |+⟩⊗k

(11)

j=1

where i is an imaginary unit, p ∈ N denotes the depth of the ansatz according to Eqs. (8) and (9), γ, β ∈ Rp , 1 1 1 X 1 X X |+⟩⊗k = √ ... (|z1 ⟩ ⊗ |z2 ⟩ ⊗ · · · ⊗ |zk ⟩), 2k z1 =0 z2 =0 zk =0

|zi ⟩ ∈ {|0⟩, |1⟩} (12)

and B with C, representing the “mixer” Hamiltonian and the ”cost” Hamiltonian, respectively, are defined as

B=

k X

Xi

(13)

i=1 k X

(1 − Zi )(1 − Zj ) , 4

(14)

Zi = I ⊗(i−1) ⊗ Z ⊗ I ⊗(k−i) .

(15)

C=

i,j=1

Qij

with

The cost Hamiltonian C here encodes the QUBO objective function, favoring bitstrings corresponding to better solutions. In contrast, the “mixer” Hamiltonian B induces transitions between basis states, enabling exploration of the search space. Finally, QAOA proceeds by solving the optimization problem min Fp (γ, β) = ⟨ψ(γ, β)|C|ψ(γ, β)⟩ γ,β

(16)

via a classical optimizer. Sampling noise is an inherent quantum-mechanical property, tied to the finite number of measurements we perform. Its effect diminishes as the number of measurements increases due to the law of large numbers. Nevertheless, it does not disappear; therefore, we must account for the distortion of the measured probabilities. Assuming a circuit with n qubits, there are 2n possible outcomes following the multinomial distribution given by

An Empirical Study on Clustering-based QAOA for TCS

9

n

− P r(→ n) =

2Y −1 m! pni , n0 !n1 ! . . . n2n −1 i=0 i

(17)

P2n −1 − n = (n0 , n1 , . . . , n2n −1 ) denote the total number where m = i=0 ni and → of measurements and a specific output vector of measured “counts”. Defining the measured frequencies as fi = nmi , we can describe the standard deviation, i.e., the “fluctuations” caused by sampling noise as r

pi (1 − pi ) , m

(18)

I ε(ρ) = (1 − pd )ρ + pd . 2

(19)

σ(fi ) =

√ thus being of order O(1/ m). The sampling noise was implemented via Aer Simulator2 from the Qiskit framework. Because sampling noise is only part of the total noise in real quantum computational infrastructures, we also considered noisy simulators to approximate realistic execution environments. Specifically, the Fake Brisbane backend realistically simulates IBM’s Brisbane quantum processor, while depolarizing channels provide simplified, controllable noise models that enable systematic evaluation of QAOA-TCS sensitivity to increasing decoherence levels. The Fake Brisbane backend 3 is a complex simulation of quantum decoherence that closely replicates the Brisbane quantum computer environment, providing its coupling map, error channels, and data from the most recent calibration. The depolarizing channel denotes a simplified decoherence model in which, in addition to sampling noise, the qubit state is replaced by the maximally mixed state with probability pd , and it is usually helpful for representing gate errors when the simplification is acceptable. Its effect on the quantum state of one qubit represented via a density matrix ρ can be described as

This channel was implemented via depolarizing error()4 from Qiskit framework. In this work, we ran QAOA on an ideal backend and on all three aforementioned backends independently to understand which noise types may make it challenging to apply QAOA-TCS to real-world problems and to identify ways to address them. For the depolarizing channel, we adopted pd = {0.01, 0.02, 0.05}. 2

https://qiskit.github.io/qiskit-aer/stubs/qiskit_aer.AerSimulator.html https://quantum.cloud.ibm.com/docs/en/api/qiskit-ibm-runtime/ fake-provider-fake-brisbane 4 https://qiskit.github.io/qiskit-aer/stubs/qiskit_aer.noise.depolarizing_ error.html 3

10

Trovato et al.

2.4 Differences between IGDec-QAOA and QAOA-TCS

In the context of gate-based algorithms for TCS, Wang et al. (2024a) proposed IGDec-QAOA, the first hybrid classical-quantum approach that combines QAOA with an impact-guided decomposition strategy (IGDec) to tackle single-objective TCO problems. As in all the approaches introduced above, a solution is represented as a bitstring, where the i − th bit, or decision variable, is 1 if the i − th test case is selected, -1 otherwise. IGDec-QAOA randomly initializes a solution by assigning values to all decision variables and computing the corresponding fitness value f (x). Afterward, it orders test cases by impact: for each test case tk , the value of its decision variable zk is flipped while keeping the others fixed, yielding a new fitness f ′ (x); the impact of tk is then defined as f ′ (x) − f (x), and test cases are sorted in ascending order of impact. Finally, the sorted test cases are decomposed into fixed-size consecutive groups of N elements, where N depends on the total number of qubits supported by the available quantum hardware, each of which is solved independently by QAOA; the resulting sub-solutions are combined by keeping the optimized values from each group. This process iterates until a stopping criterion is met, and the best solution encountered across all iterations is returned as the final output. Despite its contribution, IGDec-QAOA suffers from two main limitations that QAOA-TCS is designed to address. On the one hand, its decomposition is order-driven but impact-blind to inter-test dependencies: by selecting consecutive groups of N test cases based on individual impact scores, the strategy does not account for structural relationships among test cases, such as shared statement coverage, which are crucial for TCS. As a consequence, test cases that jointly cover statements may end up in different sub-problems, potentially leading to suboptimal coverage in the merged solution. On the other hand, the quality of the final solution is heavily dependent on the initial random sampling: since the impact order is recomputed at each iteration starting from the current solution, a poor random initialization can steer the search towards a suboptimal region of the solution space, from which recovery across iterations is not guaranteed. QAOA-TCS addresses both limitations through its clustering-based decomposition strategy. By leveraging Ward’s hierarchical clustering (Ward, 1963) on test-case attributes, QAOA-TCS groups structurally similar test cases into the same sub-problem, preserving coverage dependencies throughout the decomposition. Moreover, because clustering is fully deterministic, QAOATCS produces stable, reproducible decompositions independent of random initialization, making its results robust across executions. Further details are given in the following section.

An Empirical Study on Clustering-based QAOA for TCS

11

3 QAOA-TCS: a Clustering-based Quantum Approximate Optimization Algorithm for Regression Test Case Selection QAOA-TCS applies the Quantum Approximate Optimization Algorithm (Farhi et al., 2014) to solve TCS in both a multi- and single-objective fashion. The core algorithmic pipeline — QUBO formulation, QAOA circuit, and solution merging — was introduced in Trovato et al. (2025). The present paper extends that contribution by: (i) comparing QAOA-TCS with single-objective quantum state-of-the-art approaches by introducing a single-objective version of QAOA-TCS, and (ii) conducting a comprehensive empirical evaluation of both versions under noisy quantum simulators, necessary to assess the QAOA-TCS performance in realistic environments.

3.1 Overview of the QAOA-TCS Pipeline The QAOA-TCS pipeline consists of three main steps, regardless of whether the multi- or single-objective version is used. Step 1 — Clustering-based decomposition. QAOA-TCS decomposes the initial regression test suite Γ = {τ1 , τ2 , . . . , τn } into smaller sub-suites. Such decomposition leverages Ward’s hierarchical agglomerative clustering method (Ward, 1963). Using a feature vector, we represent test-case attributes relevant to the optimization objectives, standardized via z-score normalization (e.g., execution cost, failure rate, and statement coverage). The resulting feature vector is a composite, heterogeneous representation of test cases that can be adapted to any combination of TCS objectives available in a given dataset. Ward’s method minimizes the total within-cluster variance at each merge step, grouping test cases similar across all considered attributes. Step 2 — QAOA optimization of sub-problems. Each cluster of test cases is independently formulated as a QUBO problem and directly solved by QAOA. Each sub-problem involves at most N binary decision variables xi ∈ {0, 1}, where xi = 1 indicates that test case τi is selected, 0 otherwise. The solution to each sub-problem is a bitstring of length equal to the cluster size, encoding the selection decisions for the test cases in that cluster. Step 3 — Solution merging. The sub-solutions produced in Step 2 are merged into a single final solution by taking their union: a test case τi is included in the final suite if and only if it was selected (xi = 1) in at least one sub-solution. In the multi-objective version, a Pareto frontier is then constructed from the final solution using the same strategy as Additional Greedy (Yoo and Harman, 2007).

3.2 Why Does Clustering Improve QAOA-TCS Beyond Hardware Constraints? Ward’s hierarchical clustering serves a dual purpose as a decomposition strategy in QAOA-TCS.

12

Trovato et al.

On the one hand, current quantum hardware makes the problem solvable only after partitioning the test suites into bounded-size subproblems. This constraint is shared by all existing quantum TCS approaches. On the other hand, grouping test cases with similar optimization-relevant attributes ensures that the test cases most likely to interact are co-located within the same sub-problem. In other words, when solving each sub-problem, the QAOA optimizer can reason jointly over test cases that share statement coverage, exhibit similar failure rates, or incur comparable execution costs. As a consequence, the selection decisions made within each cluster are locally coherent with respect to the TCS objectives, and the merged final solution inherits this coherence globally. This strategy contrasts with the decomposition strategies of BootQA and IGDec-QAOA, which assign test cases to sub-problems without analyzing attribute similarity. In BootQA, the assignment is purely random, and test cases sharing statement coverage may end up in different sub-problems, causing redundant selections in the merged solution. In IGDec-QAOA, the assignment is driven by individual impact scores, which capture each test case’s marginal contribution in isolation but ignore the joint interactions among test cases. By contrast, the clustering-based decomposition of QAOA-TCS aligns the subproblem boundaries with the natural structure of the TCS objective, enabling QAOA to exploit its quadratic optimization capacity on the most relevant groups of test cases. The following subsections present the mathematical formulations for both versions, inspired by Serrano et al. (2024), where TCS is formulated and solved as the Minimum Vertex Cover. Table 1 summarizes all definitions needed to understand such formulations.

Table 1 Definitions of Variables # i k Γ Tk xi cost(τi ) ei fi di pi ti α P

Definition index identifying a test case index identifying a statement the initial regression test suite list of test cases executing the k-th statement binary variable specifying whether the i-th test case has been selected (normalized) execution cost of the i-th test binary variable specifying whether the i-th test case detected faults in the past the failure rate, i.e., the percentage of times a test detected a fault in the past the i-th test case diversity (normalized) passenger count of the i-th test case (normalized) travel distance of the i-th test case weight factor modulating the contrast ratio between the objectives of the problem penalty coefficient modeling the importance of constraints of the problem when searching for the solution

An Empirical Study on Clustering-based QAOA for TCS

13

3.3 Multi-Objective QAOA-TCS The multi-objective formulation of QAOA-TCS follows the mathematical model introduced in the multi-objective version of SelectQA (Trovato et al., 2024), which selects the smallest subset of test cases that preserves statement and fault coverage. Specifically, we considered execution cost, statement coverage, and fault coverage, in line with the other baselines we considered: SelectQA (Trovato et al., 2024), Additional Greedy (Yoo and Harman, 2007), and DIV-GA (Panichella et al., 2014). As in SelectQA, each test case is represented by a binary decision variable xi ∈ {0, 1}, which indicates whether the test case τi is included in the selected sub-suite. The optimization problem is formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, where the linear terms represent the contributions of each test case to execution cost and fault coverage, and the off-diagonal quadratic terms capture interactions among test cases through overlapping statement coverage. The final QUBO integrates: (i) minimization of the total execution cost of selected tests, (ii) maximization of fault detection ability, and (iii) maximization of statement coverage. Formally, it is the same as that used by SelectQA, which is defined as

H=α

|Γ | X

xi · cost(τi ) − (1 − α)

i=1

|Γ | X i=1

(ei · xi ) +

X X

(−P xi + 2P xi xj ) (20)

k i,j∈Tk

where α is a weight factor regulating the trade-off between objectives, and P is a penalty coefficient enforcing statement coverage constraints. 3.4 Single-Objective QAOA-TCS We leveraged the TCS QUBO of SelectQA (Trovato et al., 2024), specifically its single-objective version in this case, also to compare QAOA-TCS with single-objective approaches such as SelectQA (Trovato et al., 2024), BootQA (Wang et al., 2024b), and IGDec-QAOA (Wang et al., 2024a). The general idea is to aggregate multiple criteria into a weighted linear function to minimize. The objective function is expressed as H=α

|Γ | X i=1

xi · cost(τi ) − (1 − α)

|Γ | X

(fi · xi ),

(21)

i=1

where cost(τi ) indicates the normalized execution cost of the test case τi , and fi is its failure rate, i.e., the rate τi has revealed faults in the past. Since IGDec-QAOA defines two additional formulations to optimize a test suite for an elevator system, we introduce the corresponding formulations for QAOA-TCS. The first one differs from the previous one by substituting the failure rate objective with test case diversity, denoted as di , thus describing the objective function as:

14

Trovato et al.

H=α

|Γ | X

xi · cost(τi ) − (1 − α)

i=1

|Γ | X

(di · xi ).

(22)

i=1

In the third formulation, the weighted sum combines the execution cost objective with passenger count pi and travel distance ti , as H=α

|Γ | X

xi · cost(τi ) − β

i=1

|Γ | |Γ | X X (pi · xi ) − γ (ti · xi ), i=1

(23)

i=1

where α, β, and γ are weight coefficients that balance the three objectives. 4 Experimental Design This section presents the experimental design of our empirical evaluation of QAOA-TCS against the considered baselines, including its goal and research questions. The first part focuses on the multi-objective formulation of QAOA-TCS, whereas the second focuses on the single-objective one. For each formulation, it introduces the test suite datasets used as the basis for the selection problem, the algorithm configurations used in the experiments, and the metrics and statistical tests used to quantitatively measure and reliably discuss the results. 4.1 Research Goals and Research Questions The main objective of this evaluation is to assess the performance of QAOATCS on ideal and noisy environment simulators, compared with both classical and quantum state-of-the-art methods, in terms of effectiveness and efficiency. Our results are expected to be of interest to both practitioners and researchers: the former seek a cost-effective strategy to reduce the time to market of their products by speeding up the testing activities; the latter, especially in the field of quantum computing for software engineering, are concerned with continuously enhancing the state-of-the-art. To this aim, we define the following research questions: RQ1 . To what extent does the circuit depth of QAOA impact the effectiveness of QAOA-TCS in its multi- and single- objective formulations? RQ2 . What is the effectiveness of QAOA-TCS compared with state-of-the-art approaches in its multi- and single- objective formulations when executed on an ideal simulator? RQ3 . How robust is QAOA-TCS to noisy quantum environments in its multiand single- objective formulations? RQ4 . How efficient is QAOA-TCS compared with state-of-the-art approaches in its multi- and single- objective formulations? Since we aim to evaluate both multi- and single-objective TCS formulations, we use distinct metrics and datasets for each.

An Empirical Study on Clustering-based QAOA for TCS

15

4.2 Evaluating the Multi-Objective QAOA-TCS Next, we present the experimental design to compare multi-objective QAOATCS with state-of-the-art multi-objective test case selection approaches. 4.2.1 Study Design Study Context. To select the systems under test (SUTs) for our evaluation of multi-objective QAOA-TCS, we relied on the Software-artifact Infrastructure Repository (SIR)5 . Specifically, we have chosen four systems, namely Flex, Grep, Gzip, and Sed. We chose SIR programs because they have been widely used in prior studies (Trovato et al., 2024; Yoo and Harman, 2007; Panichella et al., 2014) on this topic, particularly for evaluating our baselines. Table 2 summarizes the key characteristics of such programs.

Table 2 Characteristics of the chosen SIR programs (Trovato et al., 2025) Program

LOC

# TCs

Description

Flex Grep Gzip Sed

10,459 10,068 5,680 14,427

567 808 215 360

Fast lexical analyzer Regular expression utility Data compression program Non-interactive text editor

To collect the data required for the three objectives, we adopted the same methodology we previously employed for SelectQA and DIV-GA (Trovato et al., 2024; Panichella et al., 2014): – Statement Coverage. Through gcov, we could get the statements covered by each executed test case. – Execution Cost. Following Panichella et al. (2014), we used gcov, considering the execution cost to be the execution frequency of basic blocks, i.e., elementary instructions of the code, which provides a finer granularity than source lines. – Past Faults Coverage. The SIR repository provides multiple faulty versions for each program, together with a fault matrix indicating whether each test case revealed an injected fault, which we have converted into a bitstring, having the i − th bit corresponding to the i − th test case. Experiment Configurations. We compared the multi-objective QAOA-TCS with Additional Greedy (Yoo and Harman, 2007), DIV-GA (Panichella et al., 2014), and the multi-objective SelectQA (Trovato et al., 2024). To ensure robust empirical results, we ran all stochastic algorithms ten times, consistent with Wang et al. (2024b); Trovato et al. (2024), whereas Additional 5 (Accessed on: 12-17-2025) https://sir.csc.ncsu.edu/portal/index.php

16

Trovato et al.

Greedy, being fully deterministic, was run only once. To address RQ3, we ran QAOA-TCS ten times for each simulator. Before comparing QAOA-TCS with multi-objective state-of-the-art approaches, we tuned the circuit depth hyperparameter of QAOA by executing QAOA-TCS on the ideal simulator ten times for each SIR program, varying the circuit depth in the {1, 2, 4, 8, 16} range, following Wang et al. (2024a). We ran Additional Greedy and SelectQA under the same conditions as in Trovato et al. (2024); we implemented DIV-GA using the MATLAB R2024a Global Optimization Toolbox, following the setup in Panichella et al. (2014). QAOA-TCS was executed on six different backends provided by Qiskit 6 : (i) the ideal noiseless Statevector Simulator, which has been employed also by IGDec-QAOA (Wang et al., 2024a), (ii) the noisy simulator modeling sampling noise only, (iii) the “realistic” Fake Brisbane backend based on IBM’s Brisbane computer, chosen to be coherent with Wang et al. (2024a), and (iv–vi) three noisy simulators with depolarization error rates of 1%, 2%, and 5%, each combined with sampling noise. We used the Qiskit Aer framework to integrate QAOA with the aforementioned simulators. All implementations and configurations are available in our replication package (Appendix, 2026). Evaluation Metrics (Effectiveness). As in Trovato et al. (2024); Panichella et al. (2014), the quality of a multi-objective optimization approach was evaluated using a reference Pareto frontier. Since computing the actual frontier is impractical for large-scale problems, we constructed an a posteriori reference frontier by aggregating all non-dominated solutions produced across all algorithms and runs. Formally, given P = {P1 , . . . , Pl } as the set of l different Pareto frontiers generated by each algorithm during each run, the reference frontier Pref is defined as: Pref ⊆

l [

Pi

(24)

i=1

where ∀p ∈ Pref , ̸ ∃q ∈ Pref : q > p. To practically measure the effectiveness of the approaches, we computed the number of non-dominated solutions contributed by the Pareto frontier of each algorithm to the reference Pareto frontier, in line with Panichella et al. (2014) and Trovato et al. (2024). In other words, for each frontier built by an algorithm, we computed the number of solutions on that frontier that are non-dominated by any other solution produced by all the other approaches. To further analyze the effectiveness of the Pareto frontier, we have included the computation of two further metrics used in the context of multi-objective algorithms (Riquelme et al., 2015; Auger et al., 2009; Van Moffaert et al., 2016): Hypervolume (HV), measuring the volume of the objective space dominated by a Pareto frontier P and bounded by a reference point r, and Inverted Generational Distance (IGD), which measures how far a Pareto frontier approximation P 6 (Accessed On: 01-11-2026): https://www.ibm.com/quantum/qiskit

An Empirical Study on Clustering-based QAOA for TCS

17

is from a Reference one R. Specifically, by setting the reference point r as (1.1, 1.1, 1.1), chosen since it is slightly worse than the nadir point (Ishibuchi et al., 2018), and using the Pref frontier as the reference one, we have computed the two metrics for each Pareto frontier computed by each algorithm execution, resulting in ten HV and ten IGD values for each algorithm. Evaluation Metrics (Efficiency). To compare the efficiency of each adopted algorithm, we have computed their mean run time over ten executions for each considered program. All algorithms, except for SelectQA which, following Trovato et al. (2024), was executed on the D-Wave Leap Hybrid Solver hybrid binary quadratic model version27 , have been deployed on the same Windows 11 machine providing 32GB of RAM, Intel(R) Core(TM) Ultra 9 285K CPU of 3.70GHz, and a NVIDIA GeForce RTX 5090 GPU with 31.50GB. Since the decomposition time of QAOA-TCS was always under 0.01s, we excluded it from the evaluation. Statistical Analysis. To assess the reliability of the observed results, we statistically analyzed each metric: the number of non-dominated solutions, HV, and IGD. Since each approach, except Additional Greedy, was executed ten times per SIR program, we obtained ten values per metric per approach. We first applied the Shapiro-Wilk normality test (Shapiro and Wilk, 1965) to each group of ten values to determine the appropriate statistical test. Based on its outcome, for each program and metric, we followed one of two paths: – If at least one group was non-normally distributed, we applied the Kruskal–Wallis H test (Kruskal and Wallis, 1952) with null hypothesis H0 : “There is no statistically significant difference between the groups.” When significance was detected (p-value < 0.05), we performed post-hoc Dunn’s tests (Dunn, 1964) with Bonferroni correction (VanderWeele and Mathur, 2019), with null hypothesis H0 : “There is no statistically significant difference between the pair.” Effect size was quantified via the Vargha–Delaney Â12 statistic (Vargha and Delaney, 2000). – If all groups were normally distributed, we applied a one-way ANOVA (Sawyer, 2009) test with the same null hypothesis as the H test. When significance was detected, we performed post-hoc Tukey HSD (Tukey, 1962) pairwise comparisons with Bonferroni correction using the same null hypothesis as Dunn’s test, and quantified effect size via Cohen’s d (Conover, 1998). Following Trovato et al. (2024), Â12 values are labeled small if in (0.34,0.44] or [0.56, 0.64), medium if in (0.29,0.34] or [0.64,0.71), and large if in [0,0.29] or [0.71,1]. The labeling for Cohen’s d follows (Panichella et al., 2014) thresholds: small |d| ∈ (0.2, 0.5], medium |d| ∈ (0.5, 0.8], and large |d| > 0.8. All results and implementations are provided in our replication package (Appendix, 2026). 7 (Accessed on: 10-06-2026) https://www.dwavesys.com/media/m2xbmlhs/14-1048a-a_ d-wave_hybrid_solver_service_plus_advantage_technology_update.pdf

18

Trovato et al.

Table 3 Characteristics of the evaluated datasets Dataset GSDTSR Paint Control IOF/ROL Elevator

# TCs

Description

5,553 89 1,941 1,925

Google shared dataset of test suite results Painting robot test suite Robot test suite Test elevator scheduler

4.3 Evaluating the Single-Objective QAOA-TCS Next, we present the experimental design to compare single-objective QAOATCS with state-of-the-art single-objective test case selection approaches. 4.3.1 Study Design Study Context. The context of this part of the study, depicted by Table 3, extends the experimental setup used in (Trovato et al., 2024) and (Wang et al., 2024b). In addition to the datasets we previously considered in (Trovato et al., 2024), namely Paint Control from ABB Robotics Norway and GSDTSR from Google, whose test cases are characterized by execution cost and failure rate, we included two further datasets used in the evaluation of IGDec-QAOA (Wang et al., 2024a). The IOF/ROL dataset provided by ABB Robotics Norway contains 1,941 tests characterized by execution time and failure rate. The ELEVATOR dataset, from Orona5, comprises a test suite of 1,925 elements that test an elevatorscheduling dispatcher. Since this dataset comes with different attributes for its test cases, it also enables the formalization of two different optimization scenarios: (i) ELEVATORo2 , in which the test cases are characterized by execution cost and input diversity; (ii) ELEVATORo3 , characterizing test cases with execution cost, passenger counts, and travel distance. Following Wang et al. (2024b); Trovato et al. (2024); Wang et al. (2024a), we filtered out all test cases with a zero failure rate from Paint Control, GSDTSR, and IOF/ROL. Experiment Configuration. To account for the stochastic nature of quantum algorithms and obtain statistically reliable results, we executed each singleobjective approach ten times, in line with Wang et al. (2024b); Trovato et al. (2024). BootQA was cloned from its GitHub page8 and executed in its optimal configurations of (n, m) parameters, as empirically determined in Wang et al. (2024b). Similarly, we ran SelectQA using the same procedure described in Trovato et al. (2024) to ensure full comparability with the reported results. New time limits for experimenting with D-Wave quantum annealers prevented us from running BootQA and SelectQA on the IOF/ROL and ELEVATOR datasets; therefore, we compared these approaches only against the QAOA approaches on the GSDTSR and Paint Control datasets. 8 (Accessed on: 12-17-2025) https://github.com/AsmarMuqeet/BootQA

An Empirical Study on Clustering-based QAOA for TCS

19

We executed IGDec-QAOA as described in Wang et al. (2024a), using both the ideal simulator and the Fake Brisbane backends, with ten repetitions for each configuration and a QAOA depth of one. The problem decomposition size was fixed at seven, corresponding to the optimal setting identified in Wang et al. (2024a). The single-objective QAOA-TCS was also executed ten times using the same ideal and noisy simulators as in the multi-objective case. We also set the number of sub-problems obtained via clustering to 7, consistent with the sub-problem size of IGDec-QAOA. To compute the optimal QAOA circuit depth, we ran QAOA-TCS on the ideal simulator for each dataset ten times across depths {1, 2, 4, 8, 16}. Once the optimal value was determined, it was used to configure QAOA-TCS for comparisons with the other approaches. Because both IGDec-QAOA and QAOA-TCS let developers adjust the relative importance of individual selection criteria through objective-specific weights, we used the Optuna framework (Akiba et al., 2019) to examine how these weights affect the algorithms’ performance. With Optuna, we systematically explored the weights’ configuration space, treating them as hyperparameters of the test case selection process. All implementations and configurations are included in our replication package (Appendix, 2026). Evaluation Metrics (Effectiveness). Since none of the algorithms shared the same objective function, we could not directly compare the solutions produced by the approaches. For the Paint Control, GSDTSR, and IOF/ROL datasets, effectiveness was measured by the execution time and failure rate of the resulting suites, consistent with Wang et al. (2024b); Trovato et al. (2024). For the other two scenarios, we used execution time and input diversity for ELEVATORo2 , and execution time, passenger counts, and travel distance for ELEVATORo3 . Evaluation Metrics (Efficiency). To compare the approaches’ efficiency, we collected their mean run time for each experiment repetition over the considered datasets. We ran SelectQA and QAOA-TCS on the same hardwares used for them in the multi-objective setting, while IGDec-QAOA was executed on the same Windows 11 machine used for QAOA-TCS. Furthermore, BootQA was executed on the D-Wave Advanced Systems QPU 9 , following Wang et al. (2024b). Since the decomposition times of QAOA-TCS, IGDec-QAOA, and BootQA are all under the 0.01s, we excluded them from the evaluations. Statistical Analysis. Because we quantify the effectiveness of the approaches using different metrics across datasets (Section 4.3.1), we performed the statistical analysis separately for each dataset–metric pair. Specifically, for each dataset and each metric, we first assessed whether the available data could be treated as following a normal distribution; based on this first evaluation, we chose the appropriate parametric or non-parametric tests to assess whether our findings were statistically grounded. 9 (Accessed on: 10-06-2026): \url{https://www.dwavesys.com/media/s3qbjp3s/ 14-1049a-a_the_d-wave_advantage_system_an_overview.pdf}

20

Trovato et al.

To decide whether to use parametric or non-parametric tests, we applied the Shapiro-Wilk normality test to each data group. Finally, for each dataset, we applied the following strategy to the sets of ten results for each metric and approach. – To analyze the effect of QAOA circuit depth on QAOA-TCS, we used ANOVA with Tukey’s post-hoc test and Cohen’s d effect size with the null hypothesis H0 : “There is no statistically significant difference between the groups of data.” – We compared QAOA-TCS and IGDec-QAOA on IOF/ROL, ELEVATORo2 , and ELEVATORo3 using the Mann–Whitney U test and Â12 with the null hypothesis H0 : “There is no statistically significant difference between the groups of data.” – For the GSDTSR dataset, we used the Kruskal–Wallis H test with Bonferronicorrected Dunn’s test and Â12 with the null hypothesis H0 : “There is no statistically significant difference between the groups of data.” – For the Paint Control dataset, we used ANOVA with Tukey’s test and Cohen’s d and Kruskal–Wallis H test with Bonferroni-corrected Dunn’s test and Â12 for comparing the failure rates and the execution costs, respectively, with the null hypothesis H0 : “There is no statistically significant difference between the groups of data.” We interpreted the effect size values as we did in the analysis of the multi-objective QAOA-TCS version. The replication package (Appendix, 2026) includes the implementation of the statistical tests, along with tables showing the results of all statistical analyses.

5 Empirical Evaluations This section presents the experimental results, including comparisons between algorithms and key findings, and offers insights for practitioners and researchers. For the sake of space, all the tables depicting the results of the statistical tests have been left in the online appendix (Appendix, 2026).

5.1 Experimental Results of Multi-Objective Algorithms This section presents and discusses the results of the comparisons of the multi-objective algorithms for TCS. 5.1.1 RQ1.1 : To what extent does the circuit depth of QAOA impact the effectiveness of QAOA-TCS in its multi-objective formulation? The results of the Kruskal-Wallis H test show no significant differences between the values of non-dominated solutions among the results obtained by QAOATCS executed over the different configurations, with all p−values exceeding

An Empirical Study on Clustering-based QAOA for TCS

21

Table 4 Mean and standard deviation of non-dominated solutions, HV, and IGD for QAOATCS compared to state-of-the-art methods on the Ideal Simulator. Program Algorithm

Non-dom. sol. ↑

HV ↑

IGD ↓

Flex

Additional Greedy SelectQA DIV-GA QAOA-TCS

199.0 187.0 139.7 ± 0.67 229.1 ± 3.38

0.3995 0.3872 0.4622 0.3313 0.6668 ± 0.0103 0.2148 ± 0.0077 0.9599 ± 0.0075 0.0857 ± 0.0010

Grep

Additional Greedy SelectQA DIV-GA QAOA-TCS

167.0 9.5 ± 0.53 70.0 326.2 ± 3.08

0.3577 0.4082 0.3610 0.2553 0.5790 ± 0.0227 0.3309 ± 0.0131 0.7907 ± 0.0055 0.0758 ± 0.0013

Gzip

Additional Greedy SelectQA DIV-GA QAOA-TCS

72.0 38.3 ± 0.82 104.9 ± 0.32 89.5 ± 0.53

0.3348 0.3773 0.4380 0.2999 0.6103 ± 0.0257 0.2804 ± 0.0171 0.4828 ± 0.0031 0.2567 ± 0.0025

Sed

Additional Greedy SelectQA DIV-GA QAOA-TCS

83.0 83.0 99.2 ± 9.54 120.6 ± 3.10

0.4744 0.2359 0.3868 0.3011 0.5831 ± 0.0140 0.2495 ± 0.0103 0.7221 ± 0.0056 0.0582 ± 0.0016

the 0.05 threshold. This result indicates that, for each SIR program, increasing the depth of the QAOA circuit does not influence the quality of QAOA-TCS results; therefore, we tuned QAOA-TCS in the following analyses with a depth level of p = 1, as it minimizes the computational cost of QAOA without compromising the effectiveness of our approach. Takeaway #1. Circuit depth does not impact the performance of QAOA-TCS in a statistically significant manner. Configuring the circuit depth to p = 1 is the most appropriate choice, as it minimizes the computational cost of QAOA without compromising the effectiveness of our approach.

5.1.2 RQ2.1 . What is the effectiveness of multi-objective QAOA-TCS compared with state-of-the-art approaches when executed on an ideal simulator? This section reports results obtained by QAOA-TCS on the ideal simulator and compares them with the baseline approaches. We compared QAOA-TCS executed on the ideal simulator against the state-of-the-art multi-objective approaches. As shown in Table 4, QAOA-TCS achieves the best overall performance on Flex, Grep, and Sed, reporting the largest number of non-dominated solutions, the highest HV, and the lowest IGD. The statistical analysis mostly confirms this trend; in terms of non-dominated solutions, QAOA-TCS significantly outperforms DIV-GA and SelectQA on Flex and Grep, with large effect sizes, while on Sed, QAOA-TCS is significantly better than SelectQA and Additional Greedy, always with large effect sizes. For HV and IGD, improvements are statistically significant across all

22

Trovato et al.

baselines on Sed, while on Flex and Grep only the comparisons with Additional Greedy are significant. In Gzip, DIV-GA obtains a larger number of non-dominated solutions and a higher HV than QAOA-TCS; however, the difference in the number of non-dominated solutions is not statistically significant, while QAOA-TCS still obtains statistically significantly better results in terms of IGD values than DIV-GA. Takeaway #2. QAOA-TCS performs statistically better than the multi-objective baseline approaches in most cases; only in one case did DIV-GA obtain better results, but these findings are not statistically significant in terms of non-dominated solutions.

5.1.3 RQ3.1 . How robust is QAOA-TCS to noisy quantum environments in its multi-objective formulation? For each noisy configuration, Tables 5 to 9 report the absolute values of the three adopted metrics and include, in italics, the corresponding QAOA-TCS result obtained on the ideal simulator, allowing us to compare with state-ofthe-art approaches and assess the degradation or preservation of QAOA-TCS compared to its ideal execution.

Table 5 Mean and standard deviation of non-dominated solutions, HV, and IGD for QAOATCS compared to state-of-the-art methods on the simulator with sampling noise. The italic row reports the Ideal QAOA-TCS reference. Program Algorithm

Non-dom. sol. ↑

HV ↑

IGD ↓

Flex

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

1.0 187.0 139.4 ± 0.70 241.8 ± 63.90 229.1 ± 3.38

0.3995 0.4622 0.6668 ± 0.0103 0.6966 ± 0.1926 0.9599 ± 0.0075

0.3024 0.3686 0.2146 ± 0.0084 0.1372 ± 0.0116 0.0857 ± 0.0010

Grep

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

167.0 9.5 ± 0.53 70.0 419.2 ± 7.50 326.2 ± 3.08

0.3577 0.4021 0.3610 0.3079 0.5790 ± 0.0227 0.2980 ± 0.0135 0.9384 ± 0.0157 0.0700 ± 0.0131 0.7907 ± 0.0055 0.0758 ± 0.0013

Gzip

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

8.0 35.3 ± 0.82 96.9 ± 6.74 85.3 ± 19.59 89.5 ± 0.53

0.3332 0.4210 0.4360 0.2464 0.6071 ± 0.0255 0.1938 ± 0.0152 0.7186 ± 0.0813 0.0931 ± 0.0193 0.4828 ± 0.0031 0.2567 ± 0.0025

Sed

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

83.0 84.0 99.2 ± 9.54 115.8 ± 4.64 120.6 ± 3.10

0.4776 0.3907 0.5845 ± 0.0140 0.7143 ± 0.0075 0.7221 ± 0.0056

0.2323 0.3033 0.2485 ± 0.0103 0.0609 ± 0.0014 0.0582 ± 0.0016

Analyzing the results obtained on the sampling-noise-only simulator, as shown in Table 5, we observed that noise did not substantially alter the overall

An Empirical Study on Clustering-based QAOA for TCS

23

Table 6 Mean and standard deviation of non-dominated solutions, HV, and IGD for QAOATCS compared to state-of-the-art methods on the Fake Brisbane backend with sampling noise. The italic row reports the Ideal QAOA-TCS reference. Program Algorithm

Non-dom. sol. ↑

HV ↑

IGD ↓

Flex

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

10.0 187.0 136.9 ± 3.38 278.7 ± 70.19 229.1 ± 3.38

0.3996 0.4622 0.6668 ± 0.0103 0.8198 ± 0.2104 0.9599 ± 0.0075

0.3455 0.3237 0.2147 ± 0.0087 0.1336 ± 0.0294 0.0857 ± 0.0010

Grep

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

167.0 9.5 ± 0.53 70.0 419.8 ± 11.14 326.2 ± 3.08

0.3577 0.3991 0.3610 0.3097 0.5790 ± 0.0227 0.2939 ± 0.0136 0.9427 ± 0.0079 0.0589 ± 0.0029 0.7907 ± 0.0055 0.0758 ± 0.0013

Gzip

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

3.0 35.3 ± 0.82 104.0 ± 1.15 83.2 ± 16.73 89.5 ± 0.53

0.3332 0.4225 0.4360 0.2456 0.6071 ± 0.0255 0.1865 ± 0.0149 0.7090 ± 0.0685 0.0934 ± 0.0183 0.4828 ± 0.0031 0.2567 ± 0.0025

Sed

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

83.0 79.0 99.2 ± 9.54 118.2 ± 3.91 120.6 ± 3.10

0.4779 0.3909 0.5845 ± 0.0140 0.7196 ± 0.0104 0.7221 ± 0.0056

0.2332 0.3046 0.2469 ± 0.0103 0.0610 ± 0.0025 0.0582 ± 0.0016

Table 7 Mean and standard deviation of non-dominated solutions, HV, and IGD for QAOATCS compared with state-of-the-art methods under 1% depolarizing error with sampling noise. The italic row reports the Ideal QAOA-TCS reference. Program Algorithm

Non-dom. sol. ↑

HV ↑

IGD ↓

Flex

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

1.0 187.0 134.0 ± 7.26 254.8 ± 63.44 229.1 ± 3.38

0.3996 0.4622 0.6668 ± 0.0103 0.7412 ± 0.2061 0.9599 ± 0.0075

0.3183 0.3535 0.2154 ± 0.0084 0.1403 ± 0.0043 0.0857 ± 0.0010

Grep

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

167.0 9.5 ± 0.53 69.9 ± 0.32 424.0 ± 10.24 326.2 ± 3.08

0.3577 0.4002 0.3610 0.3147 0.5790 ± 0.0227 0.2905 ± 0.0136 0.9471 ± 0.0069 0.0541 ± 0.0014 0.7907 ± 0.0055 0.0758 ± 0.0013

Gzip

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

8.0 35.3 ± 0.82 101.0 ± 4.45 88.9 ± 14.64 89.5 ± 0.53

0.3325 0.4299 0.4360 0.2411 0.6071 ± 0.0255 0.1824 ± 0.0140 0.7357 ± 0.0658 0.0821 ± 0.0210 0.4828 ± 0.0031 0.2567 ± 0.0025

Sed

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

83.0 78.0 99.2 ± 9.54 117.1 ± 3.75 120.6 ± 3.10

0.4759 0.3880 0.5852 ± 0.0140 0.7210 ± 0.0090 0.7221 ± 0.0056

0.2376 0.3063 0.2484 ± 0.0103 0.0598 ± 0.0019 0.0582 ± 0.0016

behavior of QAOA-TCS, since it can still perform better than the baseline approaches in Flex, Grep, and Sed. The statistical analysis confirmed this trend with large effect sizes in most comparisons. In Gzip, which is the only program where DIV-GA performs better than QAOA-TCS, the result is not

24

Trovato et al.

Table 8 Mean and standard deviation of non-dominated solutions, HV, and IGD for QAOATCS compared to state-of-the-art methods on the 2% depolarizing error with sampling noise. The italic row reports the Ideal QAOA-TCS reference. Program Algorithm

Non-dom. sol. ↑

HV ↑

IGD ↓

Flex

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

8.0 187.0 137.4 ± 3.44 253.1 ± 67.65 229.1 ± 3.38

0.3995 0.4622 0.6668 ± 0.0103 0.7339 ± 0.2104 0.9599 ± 0.0075

0.3155 0.3543 0.2156 ± 0.0085 0.1429 ± 0.0029 0.0857 ± 0.0010

Grep

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

167.0 9.5 ± 0.53 70.0 422.4 ± 10.09 326.2 ± 3.08

0.3577 0.3985 0.3610 0.3084 0.5790 ± 0.0227 0.2947 ± 0.0135 0.9396 ± 0.0055 0.0582 ± 0.0048 0.7907 ± 0.0055 0.0758 ± 0.0013

Gzip

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

8.0 36.3 ± 0.82 102.3 ± 2.50 75.8 ± 19.05 89.5 ± 0.53

0.3332 0.4132 0.4360 0.2548 0.6071 ± 0.0255 0.1910 ± 0.0160 0.6848 ± 0.0748 0.0978 ± 0.0131 0.4828 ± 0.0031 0.2567 ± 0.0025

Sed

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

83.0 87.0 99.2 ± 9.54 117.2 ± 4.76 120.6 ± 3.10

0.4744 0.3868 0.5831 ± 0.0140 0.7128 ± 0.0075 0.7221 ± 0.0056

0.2289 0.2992 0.2560 ± 0.0103 0.0614 ± 0.0022 0.0582 ± 0.0016

Table 9 Mean and standard deviation of non-dominated solutions, HV, and IGD for QAOATCS compared with state-of-the-art methods under 5% depolarizing error with sampling noise. The italic row reports the Ideal QAOA-TCS reference. Program Algorithm

Non-dom. sol. ↑

HV ↑

IGD ↓

Flex

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

1.0 187.0 136.0 ± 4.52 278.0 ± 64.96 229.1 ± 3.38

0.3995 0.4622 0.6668 ± 0.0103 0.8573 ± 0.1927 0.9599 ± 0.0075

0.3580 0.3145 0.2158 ± 0.0087 0.1242 ± 0.0366 0.0857 ± 0.0010

Grep

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

167.0 9.5 ± 0.53 69.1 ± 1.29 428.0 ± 8.31 326.2 ± 3.08

0.3577 0.4027 0.3610 0.3216 0.5790 ± 0.0227 0.2864 ± 0.0137 0.9476 ± 0.0068 0.0530 ± 0.0045 0.7907 ± 0.0055 0.0758 ± 0.0013

Gzip

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

8.0 35.3 ± 0.82 104.1 ± 1.20 81.4 ± 17.48 89.5 ± 0.53

0.3325 0.4200 0.4360 0.2499 0.6071 ± 0.0255 0.1838 ± 0.0150 0.7067 ± 0.0605 0.0967 ± 0.0154 0.4828 ± 0.0031 0.2567 ± 0.0025

Sed

Additional Greedy SelectQA DIV-GA QAOA-TCS QAOA-TCS (Ideal)

83.0 78.0 99.2 ± 9.54 118.7 ± 3.80 120.6 ± 3.10

0.4743 0.3868 0.5830 ± 0.0140 0.7211 ± 0.0117 0.7221 ± 0.0056

0.2376 0.3046 0.2467 ± 0.0103 0.0606 ± 0.0028 0.0582 ± 0.0016

statistically significant in terms of the number of non-dominated solutions; furthermore, QAOA-TCS performs better than DIV-GA in HV and IGD, and such findings are statistically significant with a large effect size. Noise not only does not alter the performance of QAOA-TCS, but the approach also

An Empirical Study on Clustering-based QAOA for TCS

25

performs better in Flex and Grep, while in Gzip it achieves better HV and IGD results. We observed a similar consistent pattern when analyzing the results from executing QAOA-TCS on the other noise simulators. In all such executions, QAOA-TCS still performs better than the baselines in Flex, Grep, and Sed across all metrics, with statistical significance in most cases. The strong performance of QAOA-TCS under noisy configurations can be explained by the fact that QAOA runs only on small clusters, each representing a subproblem of the original optimization problem. Even if the ideal simulator identifies the best solution for each subproblem, combining these locally optimal solutions does not necessarily yield the best global solution when merged to construct the final solution for the whole problem. Therefore, noise may introduce variations in the selected local solutions that, after the merging phase, can still lead to competitive or even better global trade-offs. Finally, since each quantum subproblem is small, the resulting circuits are relatively shallow, which reduces both the probability that noise affects the computation and the magnitude of its impact on the final solution. Takeaway #3. QAOA-TCS is robust to noisy quantum environments and performs better than baseline approaches in three of four programs, with statistical analysis confirming the trend in most cases. Although on Gzip DIV-GA appears to be better than QAOA-TCS in terms of the number of non-dominated solutions, these results are not statistically significant.

5.1.4 RQ4.1 How efficient is QAOA-TCS compared with state-of-the-art approaches in its multi-objective formulation? As shown in Table 10, SelectQA and Additional Greedy are the fastest baselines, and statistical tests confirm this trend in almost all cases. For Flex and Grep, SelectQA is significantly faster than DIV-GA and almost all QAOATCS configurations, except for the depolarizing-noise ones. Looking at Gzip, Additional Greedy is the most efficient approach, although no statistically significant difference was found in the comparison with SelectQA. Finally, on Sed, Additional Greedy performed better than DIV-GA and QAOA-TCS, but without statistically relevant differences compared to SelectQA. However, these results should be interpreted cautiously since, unlike QAOA-TCS, DIVGA, and Additional Greedy, which were executed on the same local machine, SelectQA relied on D-Wave’s infrastructure. Therefore, external factors such as QPU availability, resource queues, and classical-quantum communication overhead may have affected its execution time.

26

Trovato et al.

Table 10 Execution time in seconds for each algorithm across the analyzed programs. Program

Algorithm

Mean (s)

Std. Dev. (s)

Flex

SelectQA DIV-GA Add-Greedy QAOA-TCS (Ideal simulator) QAOA-TCS (Sampling Noise) QAOA-TCS (Fake Brisbane) QAOA-TCS (Depol. 1%) QAOA-TCS (Depol. 2%) QAOA-TCS (Depol. 5%)

3.00 186.84 8.09 20.46 91.94 2133.57 46.54 49.43 48.02

< 0.01 18.00 < 0.01 0.34 16.97 21.88 1.57 2.05 1.58

Grep

SelectQA DIV-GA Add-Greedy QAOA-TCS (Ideal simulator) QAOA-TCS (Sampling Noise) QAOA-TCS (Fake Brisbane) QAOA-TCS (Depol. 1%) QAOA-TCS (Depol. 2%) QAOA-TCS (Depol. 5%)

2.99 69.91 9.58 81.59 61.26 2660.39 59.35 62.40 61.29

< 0.01 9.39 < 0.01 1.66 0.88 26.61 1.48 0.32 0.66

Gzip

Add-Greedy SelectQA DIV-GA QAOA-TCS (Ideal simulator) QAOA-TCS (Depol. 1%) QAOA-TCS (Depol. 5%) QAOA-TCS (Sampling Noise) QAOA-TCS (Depol. 2%) QAOA-TCS (Fake Brisbane)

0.27 2.99 11.87 16.46 22.37 23.49 24.11 24.31 1159.42

< 0.01 < 0.01 1.56 0.78 0.41 0.38 0.80 0.52 20.18

Sed

Add-Greedy SelectQA DIV-GA QAOA-TCS (Depol. 1%) QAOA-TCS (Depol. 2%) QAOA-TCS (Sampling Noise) QAOA-TCS (Depol. 5%) QAOA-TCS (Ideal simulator) QAOA-TCS (Fake Brisbane)

2.09 2.99 57.97 30.09 32.20 32.24 31.45 34.76 1488.14

< 0.01 < 0.01 2.57 0.62 0.56 0.54 0.59 2.38 20.13

Takeaway #4. QAOA-TCS appears to be less efficient than the Additional Greedy and SelectQA baselines, whose performance remained under ten seconds in each case.

5.2 Experimental Results of Single-Objective Algorithms This section presents the results of the comparison among all considered singleobjective algorithms. 5.2.1 RQ1.2 . How does the circuit depth of QAOA influence the effectiveness of QAOA-TCS in its single-objective formulation? To determine the best QAOA circuit depth, we ran QAOA-TCS ten times for each dataset at each depth configuration on the Ideal simulator and statistically compared the resulting f values.

An Empirical Study on Clustering-based QAOA for TCS

27

Regarding the GSDTSR dataset, the results indicated that the optimal circuit depth is p = 1. Regarding the other datasets, no statistically significant differences in the f values have been observed, indicating that depth is not a determining factor in the quality of QAOA-TCS results. For computational cost reasons, we chose p = 1 as the optimal setting also in this case. Takeaway #5. Our analysis did not find statistically significant differences in result quality when varying the QAOA depth, except for GSDTSR, where the best configuration was p = 1. This result is similar to that obtained in the multi-objective formulation.

Table 11 Execution cost and effectiveness of the final test suites produced by ideal QAOATCS and ideal IGDec-QAOA across GSDTSR, PaintControl, and IOF/ROL. Dataset

Algorithm

Execution Cost

Effectiveness

Mean

Std. Dev.

Mean

Std. Dev.

GSDTSR

QAOA-TCS IGDec-QAOA

4,760,360.115 7,011,764.235

0.000 314,443.248

7.571 7.804

0.000 0.112

PaintControl

QAOA-TCS IGDec-QAOA

1,165,500.000 474,543.400

0.000 130,380.215

14.455 8.382

0.000 0.477

IOF/ROL

QAOA-TCS IGDec-QAOA

64,190,011.000 10,801,269.300

0.000 10,957,484.553

435.101 91.852

0.000 33.548

Table 12 Execution cost and input diversity for final suites of ideal QAOA-TCS and ideal IGDec-QAOA on ELEVATORo2 . Algorithm

QAOA-TCS IGDec-QAOA

Execution Cost

Input Diversity

Mean

Std. Dev.

Mean

Std. Dev.

133,136.000 171,895.600

0.000 19,856.754

722.161 751.797

0.000 26.447

Table 13 Execution cost, passenger count, and travel distance for ideal QAOA-TCS and ideal IGDec-QAOA on ELEVATORo3 . Algorithm

QAOA-TCS IGDec-QAOA

Execution Cost Std. Dev.

Mean

Std. Dev.

151,174.000 228,366.400

0.000 6,974.035

15,583.000 18,085.500

0.000 332.167

Travel Distance QAOA-TCS IGDec-QAOA

Passenger Count

Mean

Mean 50,652.000 57,461.800

Std. Dev. 0.000 1,073.966

28

Trovato et al.

5.2.2 RQ2.2 .What is the effectiveness of QAOA-TCS compared with state-of-the-art approaches in its single-objective formulation when executed on an ideal simulator? As shown in Tables 11 to 13, when we evaluated QAOA-TCS against other single-objective approaches, neither approach consistently outperformed the other. On GSDTSR, QAOA-TCS found solutions with statistically significantly lower execution costs but lower effectiveness, although the latter was not statistically significant. The same behavior is also observed on IOF/ROL, whereas on PaintControl the opposite holds, as confirmed by statistical tests in both cases. On ELEVATORo2 , QAOA-TCS finds solutions with lower execution costs, and statistical tests show significant advantages. Nevertheless, IGDec-QAOA obtained significantly better results in terms of effectiveness. Finally, on ELEVATORo3 , QAOA-TCS finds better solutions in terms of execution costs, while IGDec-QAOA finds more effective subsuites. Such differences are also confirmed by statistical tests. One advantage of both QAOA-TCS and IGDec-QAOA is that they let developers prioritize certain objectives over others by increasing the weight of a given objective. This approach is useful when software engineers must adapt the testing strategy to specific budgets or needs. For example, in contexts where safety is a primary requirement, testers may be more focused on fault detection and code coverage, rather than the total execution cost of the suite; on the contrary, in contexts where the time to market must be reduced, testers may want to focus on execution time, even at the cost of overlooking some faults. Takeaway #6. The comparisons between QAOA-TCS and IGDecQAOA executed on the ideal simulator did not find any approach outperforming the other. Specifically, except for PaintControl and IOF/ROL, QAOA-TCS finds subsuites with lower execution costs, whereas IGDec-QAOA finds solutions with higher effectiveness. 5.2.3 RQ3.2 . How robust is QAOA-TCS to noisy environments in its single-objective formulation? As shown in Tables 14 to 16, QAOA-TCS executed on noise simulators remains stable, with results similar to the ideal configuration and no statistically significant reductions in most cases. In PaintControl, the Fake Brisbane configuration also outperformed the ideal one, achieving the best result in selecting the most effective subsuite. On GSDTSR, SelectQA achieved the most efficient final test suite, while IGDec-QAOA found the most effective solution, although neither result is statistically significant. On PaintControl, SelectQA again found the most efficient solution, although the statistical analysis does not always support this; meanwhile, QAOA-TCS performed better on Fake Brisbane in terms

An Empirical Study on Clustering-based QAOA for TCS

29

Table 14 Execution cost and effectiveness for QAOA-TCS under ideal and noisy backends, with IGDec-QAOA and baselines across GSDTSR, PaintControl, and IOF/ROL. Dataset

Algorithm

Backend

Execution Cost

Effectiveness

Mean

Std. Dev.

Mean

Std. Dev.

QAOA-TCS

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

4,760,360.115 8,718,030.344 9,415,096.470 8,581,464.059 9,958,825.121 9,917,680.314

0.000 854,123.279 1,228,184.813 898,137.807 1,084,539.609 755,688.405

7.571 7.556 7.570 7.510 7.567 7.516

0.000 0.076 0.087 0.104 0.117 0.150

IGDec-QAOA

Ideal simulator Noise

7,011,764.235 13,492,835.897

314,443.248 10,754,535.375

7.804 7.546

0.112 0.352

SelectQA BootQA

– –

37,450.930 177,112.778

0.000 105,666.698

3.607 2.388

0.000 0.883

QAOA-TCS

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

1,165,500.000 1,280,915.500 1,324,022.600 1,249,780.500 1,266,441.900 1,333,351.200

0.000 133,928.657 117,556.078 90,883.107 132,615.689 147,559.808

14.455 14.254 14.535 14.089 14.095 14.334

0.000 0.768 0.694 0.548 0.767 0.904

IGDec-QAOA

Ideal simulator Noise

474,543.400 665,046.200

130,380.215 271,370.831

8.382 8.249

0.477 0.898

SelectQA BootQA

– –

159,150.000 651,774.600

0.000 242,047.481

5.314 4.681

0.000 0.912

QAOA-TCS

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

64,190,011.000 67,106,136.200 66,306,510.700 66,468,837.300 67,198,194.600 67,147,794.900

0.000 1,080,994.454 1,146,640.452 677,719.930 673,543.891 1,293,047.297

435.101 431.113 427.149 428.841 429.711 429.386

0.000 3.199 3.836 1.977 2.361 4.357

IGDec-QAOA

Ideal simulator Noise

10,801,269.300 25,192,111.600

10,957,484.553 20,251,046.346

91.852 126.114

33.548 50.307

GSDTSR

PaintControl

IOF/ROL

Table 15 Execution cost and input diversity for QAOA-TCS under ideal and noisy backends, with IGDec-QAOA on Elevator. Algorithm

Backend

Execution Cost

Input Diversity

Mean

Std. Dev.

Mean

Std. Dev.

QAOA-TCS

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

133,136.000 134,086.900 134,097.700 134,541.200 134,450.000 134,798.400

0.000 567.045 680.828 617.643 759.870 1,043.149

722.161 721.297 721.502 722.590 722.288 722.275

0.000 0.827 1.484 0.875 1.565 1.676

IGDec-QAOA

Ideal simulator Noise

171,895.600 185,283.700

19,856.754 17,829.767

751.797 724.662

26.447 63.954

of effectiveness. On IOF/ROL, the results obtained in the ideal cases are confirmed also under noisy configurations, since noisy IGDec-QAOA found more efficient solutions, while noisy QAOA-TCS found more effective solutions; such results are always confirmed by the statistical tests. The results are consistent with the ideal cases for the Elevator datasets. In both ELEV AT ORo2 and ELEV AT ORo3 , QAOA-TCS finds efficient solutions, while IGDec-QAOA finds effective solutions, with statistical analysis confirming both results.

30

Trovato et al.

Table 16 Execution cost, passenger count, and travel distance for QAOA-TCS under ideal and noisy backends, with IGDec-QAOA on Elevator-o3. Algorithm

Backend

Execution Cost

Passenger Count

Mean

Std. Dev.

Mean

Std. Dev.

QAOA-TCS

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

151,174.000 154,704.600 156,858.200 155,394.400 156,584.700 158,309.000

0.000 1,743.549 1,579.536 2,851.423 1,581.175 1,377.001

15583.000 15,355.300 15,402.500 15,354.900 15,383.200 15,446.400

0.000 89.187 86.557 139.885 83.629 76.969

IGDec-QAOA

Ideal simulator Noise

228,366.400 226,640.400

6,974.035 19,202.746

18,085.500 17,298.200

332.167 1,579.883

Travel Distance

QAOA-TCS

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

Mean 50,652.000 49,579.400 49,758.900 49,616.300 49,671.800 49,814.700

Std. Dev. 0.000 292.890 254.745 444.212 295.775 247.575

IGDec-QAOA

Ideal simulator Noise

57,461.800 54,698.700

1,073.966 5,296.257

The obtained results indicate that no clear winner emerges between the two QAOA-based approaches. Indeed, neither QAOA-TCS nor IGDec-QAOA consistently dominates the other across all metrics. For this reason, from an effectiveness perspective, neither approach is generally preferable. Takeaway #7. The performance of single-objective QAOA-TCS executed on noisy environments is consistent with that obtained in the ideal simulator. However, no approach outperforms the others with QAOA-TCS generally finding more efficient subsuites, while IGDec-QAOA finds more effective subsuites. 5.2.4 RQ4.2 How efficient is QAOA-TCS compared with state-of-the-art approaches in its single-objective formulation? Table 17 reveals that BootQA and the ideal IGDec-QAOA are the most efficient approaches, consistently achieving the lowest execution times across all datasets. On GSDTSR, BootQA is statistically significantly faster than all QAOA-TCS approaches, while IGDec-QAOA is considerably slower than the depolarizing QAOA-TCS configurations. On PaintControl, IOF/ROL, ELEV AT ORo2 , and ELEV AT ORo3 ideal IGDec-QAOA is significantly faster than all QAOA-TCS configurations with large effect sizes, but, when executed on noisy environments, IGDec-QAOA on GSDTSR, IOF/ROL, ELEV AT ORo2 , and ELEV AT ORo3 has always worse results in terms of execution times than QAOA-TCS, except for the Fake Brisbane configuration; such observation is confirmed by the statistical tests with large effect sizes.

An Empirical Study on Clustering-based QAOA for TCS

31

Table 17 Execution time in seconds for each algorithm and backend across the analyzed datasets.

Dataset

Algorithm

Backend

QAOA-TCS

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

95.53 9.31 2,035.92 17.71 18.93 17.71

10.71 0.91 20.24 0.39 4.59 0.27

simulator IGDec-QAOA Ideal Noise

199.81 1,557.85

0.66 99.35

3.00 0.58

< 0.01 0.02

27.72 2.68 634.74 5.47 5.45 5.41

0.21 0.09 13.10 0.22 0.15 0.17

simulator IGDec-QAOA Ideal Noise

0.03 0.25

< 0.01 0.02

SelectQA BootQA

– –

2.99 0.91

< 0.01 0.04

QAOA-TCS

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

489.79 54.67 11,378.77 108.28 108.34 109.74

1.69 1.98 163.47 2.45 3.01 5.42

24.04 207.29

0.11 2.60

595.73 84.02 22,844.96 153.97 151.39 150.65

2.29 2.18 116.05 4.28 4.16 3.65

23.90 174.65

0.66 4.31

833.13 83.58 20,891.92 148.04 148.17 149.12

3.53 2.35 80.24 4.58 3.42 4.57

23.75 174.01

0.13 4.92

GSDTSR

SelectQA BootQA

– –

QAOA-TCS

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

PaintControl

IOF/ROL

simulator IGDec-QAOA Ideal Noise

QAOA-TCS ELEV AT ORo2

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

simulator IGDec-QAOA Ideal Noise

QAOA-TCS ELEV AT ORo3

Ideal simulator Sampling Noise Fake Brisbane Depol. 1% Depol. 2% Depol. 5%

simulator IGDec-QAOA Ideal Noise

Mean (s) Std. Dev. (s)

These results are interesting from a practitioner’s perspective because, although they do not represent large-scale systems, the adopted datasets come from small- and medium-scale industrial systems. Indeed, for the smallscale PaintControl dataset, all approaches and most QAOA-TCS configurations could select test cases in less than 6 seconds. Regarding IOF/ROL,

32

Trovato et al.

ELEV AT ORo2 , and ELEV AT ORo3 , although ideal IGDec-QAOA was executed in less than 25 seconds, in a noisy environment, some configurations require more than two minutes to complete the task. Such considerations suggest that the execution time is strictly problem-dependent, since in the case of the largest dataset, i.e., GSDTSR, the execution times of most QAOA-TCS configurations solved the problem in less than 20 seconds, while BootQA was executed in less than 1 second. This suggests that on larger datasets, QAOAbased approaches may suffer from scalability issues, since current limits on the number of supported qubits force them to rely on a hybrid classical-quantum architecture, thereby worsening performance. Given these efficiency results, we observed that, although on ideal simulators IGDec-QAOA performs much better than the other approaches, the situation is reversed when the QAOA-based approaches are executed on a realistic noisy environment, where QAOA-TCS performs the TCS task more efficiently than IGDec-QAOA in most cases. From this perspective, practitioners would choose QAOA-TCS over IGDec-QAOA only for efficiency. However, these results are hindered by the different computational environments used to run the approaches. As in the multi-objective settings, BootQA and SelectQA have been executed on D-Wave’s infrastructure, while QAOA-TCS and IGDecQAOA have been executed on the same traditional local machine; therefore, these results should be interpreted cautiously. Takeaway #8. From the efficiency perspective, IGDec-QAOA executed on the ideal simulator is the best-performing approach in most cases, but when executed on noisy environments, QAOA-TCS performs better than IGDec-QAOA in most cases.

6 Threats to Validity This section discusses the main threats to the validity of our study. Construct Validity. This threat entails the process we followed to collect data and implement the algorithms. We relied on state-of-the-art open-source tools (e.g., GNU and gcov). Furthermore, where possible, we reused the baselines’ original implementations (Trovato et al., 2024; Panichella et al., 2014; Wang et al., 2024b,a). Finally, we provide all scripts we implemented in our online appendix (Appendix, 2026) to enhance the verifiability of our results. Internal Validity. The stochastic nature of QAOA and QA introduces randomness in the outcomes. To reduce variance, we executed each configuration 10 times, in line with Trovato et al. (2024); Wang et al. (2024b). The decomposition size (N = 7) used for QAOA-TCS and IGDec-QAOA and the QAOA circuit depth (p = 1) chosen for IGDec-QAOA constitute another potential threat, as different decomposition granularities and circuit depths may alter

An Empirical Study on Clustering-based QAOA for TCS

33

effectiveness. We selected these values consistent with prior work on IGDecQAOA (Wang et al., 2024a) to enable fair comparisons between QAOA-TCS and IGDec-QAOA. The parameters used in the QUBO formalizations pose a potential threat; therefore, we employed the Optuna framework to determine such values for QAOA-TCS and IGDec-QAOA, while all other approaches were configured using the parameter settings adopted in their original works. Although execution time is a straightforward measure of efficiency, a further threat to internal validity is the different environments used to run the experiments. Indeed, while all state-of-the-art approaches, QAOA-TCS and IGDec-QAOA, have always been executed on the same machine, SelectQA and BootQA leveraged D-Wave’s infrastructure. For this reason, the runtime of both QA approaches could have been influenced by external factors, such as QPU availability, resource queues, and classical-quantum communication overhead, limiting the comparability of the execution times. External Validity. Our findings are based on executing QAOA-TCS on widely used datasets in the literature, particularly those used by the algorithms we compare with. However, a key concern is the generalizability of the results beyond the systems considered in this work, as their limited scale may not represent certain industrial scenarios. Furthermore, although we have evaluated the robustness of QAOA-TCS on noisy simulators, these environments cannot fully replicate the conditions encountered on real quantum devices. In particular, phenomena such as calibration drift (Yeter-Aydeniz et al., 2023), correlated errors (Harper and Flammia, 2023), and limited qubit connectivity (Cheng et al., 2024), which affect quantum algorithm performance, are hard to capture with noise models. Although simulators directly inspired by real quantum devices, such as Fake Brisbane, can account for many hardware characteristics, they cannot necessarily capture all these effects under actual operating conditions. Therefore, because the robustness observed under the considered noise models does not guarantee equivalent results on real quantum devices, future experiments should be performed on real quantum hardware. Conclusion Validity. A first threat concerns the choice of evaluation metrics; therefore, we have relied on metrics used in other well-established state-of-theart work (Trovato et al., 2024; Panichella et al., 2014; Wang et al., 2024b,a). We applied non-parametric statistical tests for non-normal distributions and parametric tests for normal distributions. Finally, we used a well-established effect-size measure to quantify the magnitude of the statistically significant differences between algorithms. No conclusion was finalized without statistically grounded evidence.

7 Conclusions and Future Work In this work, we have investigated in depth the effectiveness of QAOA-TCS, our novel clustering-based QAOA approach for regression test case selection. In

34

Trovato et al.

particular, we aimed to demonstrate its robustness to quantum noise by running additional experiments with noisy-environment simulators and to establish its advantages over both classical and state-of-the-art quantum approaches in effectiveness and efficiency. Since state-of-the-art approaches are divided into multi- and single-objective approaches, and to allow a fair comparison between them and QAOA-TCS, we have developed two versions of our approach, one multi-objective, which builds a Pareto frontier from a single solution, the other single-objective, yielding a single sub-suite after each execution. The results showed that multi-objective QAOA-TCS outperforms all the multi-objective state-of-the-art approaches in most cases and, more importantly, these results remain stable even when QAOA-TCS is subject to high levels of noise. In the single-objective formulation, no clear winner emerges among the compared approaches. Our previous QA approach, namely SelectQA, has been shown to be the most efficient for large problems in the multi-objective setting, while QAOA-TCS offers the best trade-off between effectiveness and efficiency in the single-objective setting when executed in realistic noisy environments. These findings justify further experiments using real quantum systems, which are left for future work. They would also allow us to fully evaluate the effectiveness of noise-mitigation strategies, such as zero-noise extrapolation, dynamical decoupling, and others, in the context of regression test case selection. From the practitioners’ perspective, the main reason for choosing QAOATCS over IGDec-QAOA and Quantum Annealing is its higher efficiency in realistic noisy environments, since all quantum-based approaches achieved comparable effectiveness. Nevertheless, in the multi-objective case, SelectQA, although being outperformed by QAOA-TCS in terms of effectiveness, was significantly better than QAOA-TCS in terms of efficiency, suggesting that the computational costs of each algorithm in solving the TCS problem are highly problem-dependent, making it challenging to establish a clear winner in terms of efficiency. In addition to demonstrating the robustness of QAOA-TCS under different noise models, our results indicate that noise does not necessarily degrade performance monotonically. In several cases, noisy executions yielded Paretofront indicators comparable to or even better than those obtained on the ideal simulator. While previous studies have suggested that stochasticity and specific noise structures can occasionally benefit variational optimization, the consistency of these patterns across multiple noise settings suggests additional mechanisms may be at play. In particular, the interaction between noiseinduced diversification and the decomposition-recombination strategy employed by QAOA-TCS deserves further investigation. Future work will therefore focus on systematically studying how noise, decomposition strategies, and problem structure affect the quality of the resulting Pareto frontiers, as well as on developing more robust decomposed variational approaches for software engineering applications.

An Empirical Study on Clustering-based QAOA for TCS

35

8 Declarations 8.1 Ethical approval Ethical approval: not applicable.

8.2 Informed consent Informed consent: not applicable.

8.3 Data Availability Statement The authors confirm that the data supporting the findings of this study are available at https://zenodo.org/records/20668761.

8.4 Conflict of interest The authors declare no conflicts of interest.

8.5 Clinical Trial Number Clinical Trial Number: not applicable.

8.6 Funding This work was supported by the European Union - Next Generation EU under Mission 4, Component 1 (CUP D53D23017570001 and E53D23016370001), and by the Italian Government (Ministry of University and Research) through the PRIN 2022 PNRR project P2022SELA7, “RECHARGE: monitoRing, tEsting, and CHaracterization of performAnce Regressions” – Decreto Direttoriale n. 1205, 28 July 2023.

References Akiba T, Sano S, Yanase T, Ohta T, Koyama M (2019) Optuna: A nextgeneration hyperparameter optimization framework. In: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Annosi M, Appio F, Martini A (2024) Institutional context and agile team innovation: a sensemaking approach to collective knowledge creation. Technovation 129

36

Trovato et al.

Appendix (2026) Online. https://zenodo.org/records/20668761 Arrieta A, Wang S, Markiegi U, Arruabarrena A, Etxeberria L, Sagardui G (2019) Pareto efficient multi-objective black-box test case selection for simulation-based testing. Information and Software Technology 114:137–154 Auger A, Bader J, Brockhoff D, Zitzler E (2009) Theory of the hypervolume indicator: optimal µ-distributions and the choice of the reference point. Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithms Bates S, Horwitz S (1993) Incremental program testing using program dependence graphs. In: Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pp 384–396 Cheng CY, Yang CY, Kuo YH, Wang RC, Cheng HC, Huang CYR (2024) Robust qubit mapping algorithm via double-source optimal routing on large quantum circuits. ACM Transactions on Quantum Computing 5(3), DOI 10.1145/3680291, URL https://doi.org/10.1145/3680291 Conover WJ (1998) Practical nonparametric statistics. 3rd ed New York, NY, USA: Wiley Deb K, Agrawal S, Pratab A, Meyarivan T (2000) A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: Nsga-ii. Proceedings of the Parallel Problem Solving from Nature VI Conference, Dunn OJ (1964) Multiple comparisons using rank sums. Technometrics Engström E, Runeson P, Skoglund M (2010) A systematic review on regression test selection techniques. Information and Software Technology 52(1):14–30 Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm. arXiv Fischer KF (1977) A test case selection method for the validation of software maintenance modifications. COMPSAC 77 INTERNATIONAL COMPUTER SOFTWARE AND APPLICATIONS CONFERENCE Harper R, Flammia ST (2023) Learning correlated noise in a 39-qubit quantum processor. PRX Quantum 4:040311, DOI 10.1103/PRXQuantum.4.040311, URL https://link.aps.org/doi/10.1103/PRXQuantum.4.040311 Harrold MJ, Gupta R, Soffa ML (1993) A methodology for controlling the size of a test suite. ACM Trans Softw Eng Methodol Hoare T, Milner R (2005) Grand challenges for computing research. The Computer Journal 48(1):49–52 Ishibuchi H, Imada R, Setoguchi Y, Nojima Y (2018) How to specify a reference point in hypervolume calculation for fair performance comparison. Evol Comput Jeandel E (2004) Universality in quantum computation. In: Dı́az J, Karhumäki J, Lepistö A, Sannella D (eds) Automata, Languages and Programming, Springer Berlin Heidelberg, Berlin, Heidelberg, pp 793–804 Kadowaki T, Nishimori H (1998) Quantum annealing in the transverse ising model. Physical Review E 58(5):5355 Knight W (2018) Serious quantum computers are finally here. what are we going to do with them. MIT Technology Review Retrieved on October 30:2018

An Empirical Study on Clustering-based QAOA for TCS

37

Kruskal WH, Wallis WA (1952) Use of ranks in one-criterion variance analysis. Journal of the American Statistical Association Meier A, Kock A (2023) The human factor in agility: exploring employee dedication in agile project organizations. Int J Proj Manag Moll N, Barkoutsos P, Bishop LS, Chow JM, Cross A, Egger DJ, Filipp S, Fuhrer A, Gambetta JM, Ganzhorn M, Kandala A, Mezzacapo A, Müller P, Riess W, Salis G, Smolin J, Tavernelli I, Temme K (2018) Quantum optimization using variational algorithms on near-term quantum devices. Quantum Sci Technol Panichella A, Oliveto R, Di Penta M, De Lucia A (2014) Improving multiobjective test case selection by injecting diversity in genetic algorithms. IEEE Transactions on Software Engineering 41(4):358–383 Perrouin G, Oster S, Sen S, Klein J, Baudry B, Le Traon Y (2012) Pairwise testing for software product lines: comparison of two approaches. Software Quality Journal 20:605–643 Riquelme N, Von Lücken C, Baran B (2015) Performance metrics in multiobjective optimization. 2015 Latin American Computing Conference (CLEI) Rothermel G, Harrold MJ (1993) A safe, efficient algorithm for regression test selection. In: 1993 Conference on Software Maintenance, IEEE, pp 358–367 Rothermel G, Harrold MJ (1996) Analyzing regression test selection techniques. IEEE Transactions on software engineering 22(8):529–551 Rothermel G, Harrold MJ (1998) Empirical studies of a safe regression test selection technique. IEEE Transactions on Software Engineering 24(6):401– 419 Sawyer SF (2009) Analysis of variance: The fundamental concepts. Journal of Manual and Manipulative Therapy Serrano M, Sánchez L, Santos-Olmo Aea (2024) Minimizing incident response time in real-world scenarios using quantum computing. Software Quality Journal Shapiro S, Wilk M (1965) An analysis of variance test for normality (complete samples). Biometrika Suzuki S (2009) A comparison of classical and quantum annealing dynamics. In: Journal of Physics: Conference Series, IOP Publishing, vol 143, p 012002 Trovato A, De Stefano M, Pecorelli F, Di Nucci D, De Lucia A (2024) Reformulating regression test suite optimization using quantum annealing – an empirical study. International Journal on Software Tools for Technology Transfer Trovato A, Beseda M, Di Nucci D (2025) A preliminary investigation on the usage of quantum approximate optimization algorithms for test case selection. Proceedings of the 2025 29th International Conference on Evaluation and Assessment in Software Engineering Companion Tukey JW (1962) The future of data analysis. Math Statist Van Moffaert K, Drugan M, Nowé A (2016) Hypervolume-based multi-objective reinforcement learning. Purshouse, RC, Fleming, PJ, Fonseca, CM, Greco, S, Shaw, J (eds) Evolutionary Multi-Criterion Optimization EMO 2013 Lecture Notes in Computer Science

38

Trovato et al.

VanderWeele TJ, Mathur MB (2019) Some desirable properties of the bonferroni correction: Is the bonferroni correction really so bad? American Journal of Epidemiology Vargha A, Delaney HD (2000) A critique and improvement of the cl common language effect size statistics of mcgraw and wong. Journal of Educational and Behavioral Statistics Wang S, Ali S, Gotlieb A (2013) Minimizing test suites in software product lines using weight-based genetic algorithms. In: Proceedings of the 15th annual conference on Genetic and evolutionary computation, pp 1493–1500 Wang X, Ali S, Yue T, Arcaini P (2024a) Quantum approximate optimization algorithm for test case optimization. IEEE Transactions on Software Engineering Wang X, Muqeet A, Yue T, Ali S, Arcaini P (2024b) Test case minimization with quantum annealers. ACM Transactions on Software Engineering and Methodology Ward JH (1963) Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association Xue Y, Li YF (2020) Multi-objective integer programming approaches for solving the multi-criteria test-suite minimization problem: Towards sound and complete solutions of a particular search-based software-engineering problem. ACM Transactions on Software Engineering and Methodology (TOSEM) 29(3):1–50 Yau SS, Kishimoto Z (1987) Method for revalidating modified programs in the maintenance phase. In: Proceedings-IEEE Computer Society’s International Computer Software & Applications Conference, IEEE, pp 272–277 Yeter-Aydeniz K, Parks Z, Thekkiniyedath AN, Gustafson E, Kemper AF, Pooser RC, Meurice Y, Dreher P (2023) Measuring qubit stability in a gatebased nisq hardware processor: K. yeter-aydeniz et al. Quantum information processing 22(2):96, DOI 10.1007/s11128-023-03826-4, URL https://link. springer.com/article/10.1007/s11128-023-03826-4 Yoo S, Harman M (2007) Pareto efficient multi-objective test case selection. In: Proceedings of the 2007 international symposium on Software testing and analysis, pp 140–150 Yoo S, Harman M (2010) Using hybrid algorithm for pareto efficient multiobjective test suite minimisation. Journal of Systems and Software 83(4):689– 701 Yoo S, Harman M (2012) Regression testing minimization, selection and prioritization: a survey. Software testing, verification and reliability 22(2):67–120 Yoo S, Harman M, Ur S (2011) Highly scalable multi objective test suite minimisation using graphics cards. In: Search Based Software Engineering: Third International Symposium, SSBSE 2011, Szeged, Hungary, September 10-12, 2011. Proceedings 3, Springer, pp 219–236

Related documents

• Investigating layer-selective transfer learning of quantum approximate optimization algorithm parameters for the Max-Cut problem#1358899
• Efficient Quantum Optimization via Dissipative False Vacuum Decay#1490661
• SUTURE: Syndrome-Guided Repair for Segmented Feasibility-Preserving VQAs on Noisy Hardware#1083427
• Provably scalable learning from quantum many-body data via locality#1326140
• An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory.#136047