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

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 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 (QAOA-TCS), 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 state-of-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 quantum-based 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 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 state-of-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.

Background and Related Work

This section provides a more detailed introduction to TCS and how state-of-the-art algorithms solve it.

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 $\Gamma= \{\tau_1, \tau_2, \ldots, \tau_n\}$ be the starting regression test suite which we aim to optimize; let $F = \{f_1, f_2, \ldots, f_m\}$ be the set of objectives of our selection. Multi-objective TCS aims at finding a Pareto-optimal set $P$, such that the $\forall p \in P$, $p \subseteq\Gamma$, 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 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.

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 $TS$, 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 randomeriwa 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 Service¹, 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.

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,

where $\alpha,\beta\in\mathbb{C}$ are probability amplitudes satisfying

as $|\alpha|^2$ and $|\beta|^2$ denote the probability of measuring $|0\rangle$ or $|1\rangle$, respectively. Another important property is that an isolated quantum system is described by unitary transformations, represented by matrices $U$, thus satisfying

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

where $n \in\mathbb{N}$ represents the number of qubits, $|x\rangle$ denotes the computational basis state corresponding to the binary representation of the $x \in\mathbb{N}$, and $c_x \in\mathbb{C}$ are probability amplitudes satisfying

A multipartite state is called separable if it can be written as

where $|\psi_i\rangle$ denotes the state of the $i$-th qubit. Otherwise, the state is entangled. For example, since the Bell state

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

where each layer may itself be decomposed as

where $m_d$ 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 $U_d^{(j)}$ act on disjoint subsets of qubits and therefore can be executed in parallel. The quantity $p \in\mathbb{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

where $x=(x_1,\ldots,x_k)^T$ and $x_i\in\{0,1\}$ and $Q\in\mathbb{R}^{k\times k}$ is a symmetric or upper-triangular matrix, while $k\in\mathbb{N}$. QAOA then relies on the construction of a variational quantum state called “ansatz” defined as

where $i$ is an imaginary unit, $p\in\mathbb{N}$ denotes the depth of the ansatz according to Eqs. (8) and (9), $\gamma,\beta\in\mathbb{R}^p$,

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

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

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 $2^n$ possible outcomes following the multinomial distribution given by

where $m=\sum_{i=0}^{2^n-1}n_i$ and $\vec{n}=(n_0,n_1,\ldots,n_{2^n-1})$ denote the total number of measurements and a specific output vector of measured “counts”. Defining the measured frequencies as $f_i=\frac{n_i}{m}$, we can describe the standard deviation, i.e., the “fluctuations” caused by sampling noise as

thus being of order $O(1/\sqrt{m})$. The sampling noise was implemented via Aer Simulator² 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³ 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 $p_d$, 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 $\rho$ can be described as

This channel was implemented via depolarizing_error()⁴ 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 $p_d=\{0.01,0.02,0.05\}$.

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 $t_k$, the value of its decision variable $z_k$ is flipped while keeping the others fixed, yielding a new fitness $f'(x)$; the impact of $t_k$ 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, QAOA-TCS produces stable, reproducible decompositions independent of random initialization, making its results robust across executions. Further details are given in the following section.

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.

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 $\Gamma= \{\tau_1, \tau_2, \ldots, \tau_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 $x_i \in\{0,1\}$, where $x_i = 1$ indicates that test case $\tau_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 $\tau_i$ is included in the final suite if and only if it was selected ($x_i = 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).

Why Does Clustering Improve QAOA-TCS Beyond Hardware Constraints?

Ward’s hierarchical clustering serves a dual purpose as a decomposition strategy in QAOA-TCS.

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.

#	Definition
$i$	index identifying a test case
$k$	index identifying a statement
$\Gamma$	the initial regression test suite
$T_k$	list of test cases executing the $k$-th statement
$x_i$	binary variable specifying whether the $i$-th test case has been selected
$\operatorname{cost}(\tau_i)$	(normalized) execution cost of the $i$-th test
$e_i$	binary variable specifying whether the $i$-th test case detected faults in the past
$f_i$	the failure rate, i.e., the percentage of times a test detected a fault in the past
$d_i$	the $i$-th test case diversity
$p_i$	(normalized) passenger count of the $i$-th test case
$t_i$	(normalized) travel distance of the $i$-th test case
$\alpha$	weight factor modulating the contrast ratio between the objectives of the problem
$P$	penalty coefficient modeling the importance of constraints of the problem when searching for the solution

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 $x_i \in\{0,1\}$, which indicates whether the test case $\tau_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

where $\alpha$ is a weight factor regulating the trade-off between objectives, and $P$ is a penalty coefficient enforcing statement coverage constraints.

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

where $cost(\tau_i)$ indicates the normalized execution cost of the test case $\tau_i$, and $f_i$ is its failure rate, i.e., the rate $\tau_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 $d_i$, thus describing the objective function as:

In the third formulation, the weighted sum combines the execution cost objective with passenger count $p_i$ and travel distance $t_i$, as

where $\alpha$, $\beta$, and $\gamma$ are weight coefficients that balance the three objectives.

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.

Research Goals and Research Questions

The main objective of this evaluation is to assess the performance of QAOA-TCS 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:

RQ{sub}1. To what extent does the circuit depth of QAOA impact the effectiveness of QAOA-TCS in its multi- and single-objective formulations?

RQ{sub}2. 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?

RQ{sub}3. How robust is QAOA-TCS to noisy quantum environments in its multi- and single-objective formulations?

RQ{sub}4. 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.

Evaluating the Multi-Objective QAOA-TCS

Next, we present the experimental design to compare multi-objective QAOA-TCS with state-of-the-art multi-objective test case selection approaches.

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)⁵. 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.

Program	LOC	# TCs	Description
Flex	10,459	567	Fast lexical analyzer
Grep	10,068	808	Regular expression utility
Gzip	5,680	215	Data compression program
Sed	14,427	360	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 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⁶: (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 = \{P_1, \ldots, P_l\}$ as the set of $l$ different Pareto frontiers generated by each algorithm during each run, the reference frontier $P_{\mathrm{ref}}$ is defined as:

where $\forall p \in P_{\mathrm{ref}}, \nexists q \in P_{\mathrm{ref}} : q \succ 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$ 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 $P_{ref}$ 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_version2⁷, 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 $H_0$: “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 $H_0$: “There is no statistically significant difference between the pair.” Effect size was quantified via the Vargha–Delaney $\hat{A}_{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), $\hat{A}_{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| \in(0.2,0.5]$, medium $|d| \in(0.5,0.8]$, and large $|d| > 0.8$.

All results and implementations are provided in our replication package (Appendix, 2026).

Evaluating the Single-Objective QAOA-TCS

Next, we present the experimental design to compare single-objective QAOA-TCS with state-of-the-art single-objective test case selection approaches.

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).

Dataset	# TCs	Description
GSDTSR	5,553	Google shared dataset of test suite results
Paint Control	89	Painting robot test suite
IOF/ROL	1,941	Robot test suite
Elevator	1,925	Test elevator scheduler

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 elevator-scheduling dispatcher. Since this dataset comes with different attributes for its test cases, it also enables the formalization of two different optimization scenarios: (i) $ELEVATOR_{o2}$, in which the test cases are characterized by execution cost and input diversity; (ii) $ELEVATOR_{o3}$, 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 single-objective approach ten times, in line with Wang et al. (2024b); Trovato et al. (2024). BootQA was cloned from its GitHub page⁸ 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.

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 $ELEVATOR_{o2}$, and execution time, passenger counts, and travel distance for $ELEVATOR_{o3}$.

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 (§ 6.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.

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 $H_0$: “There is no statistically significant difference between the groups of data.”

• We compared QAOA-TCS and IGDec-QAOA on IOF/ROL, ELEVATOR$_{o2}$, and ELEVATOR$_{o3}$ using the Mann–Whitney U test and $\hat{A}_{12}$ with the null hypothesis $H_0$: “There is no statistically significant difference between the groups of data.”

• For the GSDTSR dataset, we used the Kruskal–Wallis H test with Bonferroni-corrected Dunn’s test and $\hat{A}_{12}$ with the null hypothesis $H_0$: “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 $\hat{A}_{12}$ for comparing the failure rates and the execution costs, respectively, with the null hypothesis $H_0$: “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.

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).

Experimental Results of Multi-Objective Algorithms

This section presents and discusses the results of the comparisons of the multi-objective algorithms for TCS.

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 QAOA-TCS executed over the different configurations, with all $p$-values exceeding 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.

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 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.

Program	Algorithm	Non-dom. sol. ↑	HV ↑	IGD ↓
Flex	Additional Greedy	199.0	0.3995	0.3872
	SelectQA	187.0	0.4622	0.3313
	DIV-GA	139.7 ± 0.67	0.6668 ± 0.0103	0.2148 ± 0.0077
	QAOA-TCS	229.1 ± 3.38	0.9599 ± 0.0075	0.0857 ± 0.0010
Grep	Additional Greedy	167.0	0.3577	0.4082
	SelectQA	9.5 ± 0.53	0.3610	0.2553
	DIV-GA	70.0	0.5790 ± 0.0227	0.3309 ± 0.0131
	QAOA-TCS	326.2 ± 3.08	0.7907 ± 0.0055	0.0758 ± 0.0013
Gzip	Additional Greedy	72.0	0.3348	0.3773
	SelectQA	38.3 ± 0.82	0.4380	0.2999
	DIV-GA	104.9 ± 0.32	0.6103 ± 0.0257	0.2804 ± 0.0171
	QAOA-TCS	89.5 ± 0.53	0.4828 ± 0.0031	0.2567 ± 0.0025
Sed	Additional Greedy	83.0	0.4744	0.2359
	SelectQA	83.0	0.3868	0.3011
	DIV-GA	99.2 ± 9.54	0.5831 ± 0.0140	0.2495 ± 0.0103
	QAOA-TCS	120.6 ± 3.10	0.7221 ± 0.0056	0.0582 ± 0.0016

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.

RQ3.1. How robust is QAOA-TCS to noisy quantum environments in its multi-objective formulation?

For each noisy configuration, Table 5 to Table 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-of-the-art approaches and assess the degradation or preservation of QAOA-TCS compared to its ideal execution.

Program	Algorithm	Non-dom. sol. ↑	HV ↑	IGD ↓
Flex	Additional Greedy	1.0	0.3995	0.3024
Flex	SelectQA	187.0	0.4622	0.3686
Flex	DIV-GA	139.4 ± 0.70	0.6668 ± 0.0103	0.2146 ± 0.0084
Flex	QAOA-TCS	241.8 ± 63.90	0.6966 ± 0.1926	0.1372 ± 0.0116
Flex	QAOA-TCS (Ideal)	229.1 ± 3.38	0.9599 ± 0.0075	0.0857 ± 0.0010
Grep	Additional Greedy	167.0	0.3577	0.4021
Grep	SelectQA	9.5 ± 0.53	0.3610	0.3079
Grep	DIV-GA	70.0	0.5790 ± 0.0227	0.2980 ± 0.0135
Grep	QAOA-TCS	419.2 ± 7.50	0.9384 ± 0.0157	0.0700 ± 0.0131
Grep	QAOA-TCS (Ideal)	326.2 ± 3.08	0.7907 ± 0.0055	0.0758 ± 0.0013
Gzip	Additional Greedy	8.0	0.3332	0.4210
Gzip	SelectQA	35.3 ± 0.82	0.4360	0.2464
Gzip	DIV-GA	96.9 ± 6.74	0.6071 ± 0.0255	0.1938 ± 0.0152
Gzip	QAOA-TCS	85.3 ± 19.59	0.7186 ± 0.0813	0.0931 ± 0.0193
Gzip	QAOA-TCS (Ideal)	89.5 ± 0.53	0.4828 ± 0.0031	0.2567 ± 0.0025
Sed	Additional Greedy	83.0	0.4776	0.2323
Sed	SelectQA	84.0	0.3907	0.3033
Sed	DIV-GA	99.2 ± 9.54	0.5845 ± 0.0140	0.2485 ± 0.0103
Sed	QAOA-TCS	115.8 ± 4.64	0.7143 ± 0.0075	0.0609 ± 0.0014
Sed	QAOA-TCS (Ideal)	120.6 ± 3.10	0.7221 ± 0.0056	0.0582 ± 0.0016

Program	Algorithm	Non-dom. sol. $\uparrow$	HV $\uparrow$	IGD $\downarrow$
Flex	Additional Greedy	1.0	0.3995	0.3580
	SelectQA	187.0	0.4622	0.3145
	DIV-GA	136.0 $\pm$ 4.52	0.6668 $\pm$ 0.0103	0.2158 $\pm$ 0.0087
	QAOA-TCS	278.0 $\pm$ 64.96	0.8573 $\pm$ 0.1927	0.1242 $\pm$ 0.0366
	QAOA-TCS (Ideal)	229.1 $\pm$ 3.38	0.9599 $\pm$ 0.0075	0.0857 $\pm$ 0.0010
Grep	Additional Greedy	167.0	0.3577	0.4027
	SelectQA	9.5 $\pm$ 0.53	0.3610	0.3216
	DIV-GA	69.1 $\pm$ 1.29	0.5790 $\pm$ 0.0227	0.2864 $\pm$ 0.0137
	QAOA-TCS	428.0 $\pm$ 8.31	0.9476 $\pm$ 0.0068	0.0530 $\pm$ 0.0045
	QAOA-TCS (Ideal)	326.2 $\pm$ 3.08	0.7907 $\pm$ 0.0055	0.0758 $\pm$ 0.0013
Gzip	Additional Greedy	8.0	0.3325	0.4200
	SelectQA	35.3 $\pm$ 0.82	0.4360	0.2499
	DIV-GA	104.1 $\pm$ 1.20	0.6071 $\pm$ 0.0255	0.1838 $\pm$ 0.0150
	QAOA-TCS	81.4 $\pm$ 17.48	0.7067 $\pm$ 0.0605	0.0967 $\pm$ 0.0154
	QAOA-TCS (Ideal)	89.5 $\pm$ 0.53	0.4828 $\pm$ 0.0031	0.2567 $\pm$ 0.0025
Sed	Additional Greedy	83.0	0.4743	0.2376
	SelectQA	78.0	0.3868	0.3046
	DIV-GA	99.2 $\pm$ 9.54	0.5830 $\pm$ 0.0140	0.2467 $\pm$ 0.0103
	QAOA-TCS	118.7 $\pm$ 3.80	0.7211 $\pm$ 0.0117	0.0606 $\pm$ 0.0028
	QAOA-TCS (Ideal)	120.6 $\pm$ 3.10	0.7221 $\pm$ 0.0056	0.0582 $\pm$ 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 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

Program	Algorithm	Non-dom. sol. $\uparrow$	HV $\uparrow$	IGD $\downarrow$
Flex	Additional Greedy	10.0	0.3996	0.3455
	SelectQA	187.0	0.4622	0.3237
	DIV-GA	136.9 $\pm$ 3.38	0.6668 $\pm$ 0.0103	0.2147 $\pm$ 0.0087
	QAOA-TCS	278.7 $\pm$ 70.19	0.8198 $\pm$ 0.2104	0.1336 $\pm$ 0.0294
	QAOA-TCS (Ideal)	229.1 $\pm$ 3.38	0.9599 $\pm$ 0.0075	0.0857 $\pm$ 0.0010
Grep	Additional Greedy	167.0	0.3577	0.3991
	SelectQA	9.5 $\pm$ 0.53	0.3610	0.3097
	DIV-GA	70.0	0.5790 $\pm$ 0.0227	0.2939 $\pm$ 0.0136
	QAOA-TCS	419.8 $\pm$ 11.14	0.9427 $\pm$ 0.0079	0.0589 $\pm$ 0.0029
	QAOA-TCS (Ideal)	326.2 $\pm$ 3.08	0.7907 $\pm$ 0.0055	0.0758 $\pm$ 0.0013
Gzip	Additional Greedy	3.0	0.3332	0.4225
	SelectQA	35.3 $\pm$ 0.82	0.4360	0.2456
	DIV-GA	104.0 $\pm$ 1.15	0.6071 $\pm$ 0.0255	0.1865 $\pm$ 0.0149
	QAOA-TCS	83.2 $\pm$ 16.73	0.7090 $\pm$ 0.0685	0.0934 $\pm$ 0.0183
	QAOA-TCS (Ideal)	89.5 $\pm$ 0.53	0.4828 $\pm$ 0.0031	0.2567 $\pm$ 0.0025
Sed	Additional Greedy	83.0	0.4779	0.2332
	SelectQA	79.0	0.3909	0.3046
	DIV-GA	99.2 $\pm$ 9.54	0.5845 $\pm$ 0.0140	0.2469 $\pm$ 0.0103
	QAOA-TCS	118.2 $\pm$ 3.91	0.7196 $\pm$ 0.0104	0.0610 $\pm$ 0.0025
	QAOA-TCS (Ideal)	120.6 $\pm$ 3.10	0.7221 $\pm$ 0.0056	0.0582 $\pm$ 0.0016

Program	Algorithm	Non-dom. sol. $\uparrow$	HV $\uparrow$	IGD $\downarrow$
Flex	Additional Greedy	1.0	0.3996	0.3183
	SelectQA	187.0	0.4622	0.3535
	DIV-GA	134.0 $\pm$ 7.26	0.6668 $\pm$ 0.0103	0.2154 $\pm$ 0.0084
	QAOA-TCS	254.8 $\pm$ 63.44	0.7412 $\pm$ 0.2061	0.1403 $\pm$ 0.0043
	QAOA-TCS (Ideal)	229.1 $\pm$ 3.38	0.9599 $\pm$ 0.0075	0.0857 $\pm$ 0.0010
Grep	Additional Greedy	167.0	0.3577	0.4002
	SelectQA	9.5 $\pm$ 0.53	0.3610	0.3147
	DIV-GA	69.9 $\pm$ 0.32	0.5790 $\pm$ 0.0227	0.2905 $\pm$ 0.0136
	QAOA-TCS	424.0 $\pm$ 10.24	0.9471 $\pm$ 0.0069	0.0541 $\pm$ 0.0014
	QAOA-TCS (Ideal)	326.2 $\pm$ 3.08	0.7907 $\pm$ 0.0055	0.0758 $\pm$ 0.0013
Gzip	Additional Greedy	8.0	0.3325	0.4299
	SelectQA	35.3 $\pm$ 0.82	0.4360	0.2411
	DIV-GA	101.0 $\pm$ 4.45	0.6071 $\pm$ 0.0255	0.1824 $\pm$ 0.0140
	QAOA-TCS	88.9 $\pm$ 14.64	0.7357 $\pm$ 0.0658	0.0821 $\pm$ 0.0210
	QAOA-TCS (Ideal)	89.5 $\pm$ 0.53	0.4828 $\pm$ 0.0031	0.2567 $\pm$ 0.0025
Sed	Additional Greedy	83.0	0.4759	0.2376
	SelectQA	78.0	0.3880	0.3063
	DIV-GA	99.2 $\pm$ 9.54	0.5852 $\pm$ 0.0140	0.2484 $\pm$ 0.0103
	QAOA-TCS	117.1 $\pm$ 3.75	0.7210 $\pm$ 0.0090	0.0598 $\pm$ 0.0019
	QAOA-TCS (Ideal)	120.6 $\pm$ 3.10	0.7221 $\pm$ 0.0056	0.0582 $\pm$ 0.0016
Program	Algorithm	Non-dom. sol. $\uparrow$	HV $\uparrow$	IGD $\downarrow$
Flex	Additional Greedy	8.0	0.3995	0.3155
	SelectQA	187.0	0.4622	0.3543
	DIV-GA	137.4 $\pm$ 3.44	0.6668 $\pm$ 0.0103	0.2156 $\pm$ 0.0085
	QAOA-TCS	253.1 $\pm$ 67.65	0.7339 $\pm$ 0.2104	0.1429 $\pm$ 0.0029
	QAOA-TCS (Ideal)	229.1 $\pm$ 3.38	0.9599 $\pm$ 0.0075	0.0857 $\pm$ 0.0010
Grep	Additional Greedy	167.0	0.3577	0.3985
	SelectQA	9.5 $\pm$ 0.53	0.3610	0.3084
	DIV-GA	70.0	0.5790 $\pm$ 0.0227	0.2947 $\pm$ 0.0135
	QAOA-TCS	422.4 $\pm$ 10.09	0.9396 $\pm$ 0.0055	0.0582 $\pm$ 0.0048
	QAOA-TCS (Ideal)	326.2 $\pm$ 3.08	0.7907 $\pm$ 0.0055	0.0758 $\pm$ 0.0013
Gzip	Additional Greedy	8.0	0.3332	0.4132
	SelectQA	36.3 $\pm$ 0.82	0.4360	0.2548
	DIV-GA	102.3 $\pm$ 2.50	0.6071 $\pm$ 0.0255	0.1910 $\pm$ 0.0160
	QAOA-TCS	75.8 $\pm$ 19.05	0.6848 $\pm$ 0.0748	0.0978 $\pm$ 0.0131
	QAOA-TCS (Ideal)	89.5 $\pm$ 0.53	0.4828 $\pm$ 0.0031	0.2567 $\pm$ 0.0025
Sed	Additional Greedy	83.0	0.4744	0.2289
	SelectQA	87.0	0.3868	0.2992
	DIV-GA	99.2 $\pm$ 9.54	0.5831 $\pm$ 0.0140	0.2560 $\pm$ 0.0103
	QAOA-TCS	117.2 $\pm$ 4.76	0.7128 $\pm$ 0.0075	0.0614 $\pm$ 0.0022
	QAOA-TCS (Ideal)	120.6 $\pm$ 3.10	0.7221 $\pm$ 0.0056	0.0582 $\pm$ 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 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.

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 QAOA-TCS 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, DIV-GA, 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.

Program	Algorithm	Mean (s)	Std. Dev. (s)
Flex	SelectQA	3.00	< 0.01
	DIV-GA	186.84	18.00
	Add-Greedy	8.09	< 0.01
	QAOA-TCS (Ideal simulator)	20.46	0.34
	QAOA-TCS (Sampling Noise)	91.94	16.97
	QAOA-TCS (Fake Brisbane)	2133.57	21.88
	QAOA-TCS (Depol. 1%)	46.54	1.57
	QAOA-TCS (Depol. 2%)	49.43	2.05
	QAOA-TCS (Depol. 5%)	48.02	1.58
Grep	SelectQA	2.99	< 0.01
	DIV-GA	69.91	9.39
	Add-Greedy	9.58	< 0.01
	QAOA-TCS (Ideal simulator)	81.59	1.66
	QAOA-TCS (Sampling Noise)	61.26	0.88
	QAOA-TCS (Fake Brisbane)	2660.39	26.61
	QAOA-TCS (Depol. 1%)	59.35	1.48
	QAOA-TCS (Depol. 2%)	62.40	0.32
	QAOA-TCS (Depol. 5%)	61.29	0.66
Gzip	Add-Greedy	0.27	< 0.01
	SelectQA	2.99	< 0.01
	DIV-GA	11.87	1.56
	QAOA-TCS (Ideal simulator)	16.46	0.78
	QAOA-TCS (Depol. 1%)	22.37	0.41
	QAOA-TCS (Depol. 5%)	23.49	0.38
	QAOA-TCS (Sampling Noise)	24.11	0.80
	QAOA-TCS (Depol. 2%)	24.31	0.52
	QAOA-TCS (Fake Brisbane)	1159.42	20.18
Sed	Add-Greedy	2.09	< 0.01
	SelectQA	2.99	< 0.01
	DIV-GA	57.97	2.57
	QAOA-TCS (Depol. 1%)	30.09	0.62
	QAOA-TCS (Depol. 2%)	32.20	0.56
	QAOA-TCS (Sampling Noise)	32.24	0.54
	QAOA-TCS (Depol. 5%)	31.45	0.59
	QAOA-TCS (Ideal simulator)	34.76	2.38
	QAOA-TCS (Fake Brisbane)	1488.14	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.

Experimental Results of Single-Objective Algorithms

This section presents the results of the comparison among all considered single-objective algorithms.

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.

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.

Algorithm	Execution Cost		Input Diversity
	Mean	Std. Dev.	Mean	Std. Dev.
QAOA-TCS	133,136.000	0.000	722.161	0.000
IGDec-QAOA	171,895.600	19,856.754	751.797	26.447

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 Table 11 to Table 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 ELEVATOR$_{o2}$, 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 ELEVATOR$_{o3}$, 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.

Dataset	Algorithm	Execution Cost		Effectiveness
		Mean	Std. Dev.	Mean	Std. Dev.
GSDTSR	QAOA-TCS	4,760,360.115	0.000	7.571	0.000
GSDTSR	IGDec-QAOA	7,011,764.235	314,443.248	7.804	0.112
PaintControl	QAOA-TCS	1,165,500.000	0.000	14.455	0.000
PaintControl	IGDec-QAOA	474,543.400	130,380.215	8.382	0.477
IOF/ROL	QAOA-TCS	64,190,011.000	0.000	435.101	0.000
IOF/ROL	IGDec-QAOA	10,801,269.300	10,957,484.553	91.852	33.548

Algorithm	Execution Cost		Passenger Count
	Mean	Std. Dev.	Mean	Std. Dev.
QAOA-TCS	151,174.000	0.000	15,583.000	0.000
IGDec-QAOA	228,366.400	6,974.035	18,085.500	332.167
	Travel Distance
QAOA-TCS	50,652.000	0.000
IGDec-QAOA	57,461.800	1,073.966

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 IGDec-QAOA 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.

RQ3.2. How robust is QAOA-TCS to noisy environments in its single-objective formulation?

As shown in Table 14 to Table 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.

Dataset	Algorithm	Backend	Execution Cost Mean	Execution Cost Std. Dev.	Effectiveness Mean	Effectiveness Std. Dev.
GSDTSR	QAOA-TCS	Ideal simulator	4,760,360.115	0.000	7.571	0.000
GSDTSR	QAOA-TCS	Sampling Noise	8,718,030.344	854,123.279	7.556	0.076
GSDTSR	QAOA-TCS	Fake Brisbane	9,415,096.470	1,228,184.813	7.570	0.087
GSDTSR	QAOA-TCS	Depol. 1%	8,581,464.059	898,137.807	7.510	0.104
GSDTSR	QAOA-TCS	Depol. 2%	9,958,825.121	1,084,539.609	7.567	0.117
GSDTSR	QAOA-TCS	Depol. 5%	9,917,680.314	755,688.405	7.516	0.150
GSDTSR	IGDec-QAOA	Ideal simulator	7,011,764.235	314,443.248	7.804	0.112
GSDTSR	IGDec-QAOA	Noise	13,492,835.897	10,754,535.375	7.546	0.352
GSDTSR	SelectQA	–	37,450.930	0.000	3.607	0.000
GSDTSR	BootQA	–	177,112.778	105,666.698	2.388	0.883
PaintControl	QAOA-TCS	Ideal simulator	1,165,500.000	0.000	14.455	0.000
PaintControl	QAOA-TCS	Sampling Noise	1,280,915.500	133,928.657	14.254	0.768
PaintControl	QAOA-TCS	Fake Brisbane	1,324,022.600	117,556.078	14.535	0.694
PaintControl	QAOA-TCS	Depol. 1%	1,249,780.500	90,883.107	14.089	0.548
PaintControl	QAOA-TCS	Depol. 2%	1,266,441.900	132,615.689	14.095	0.767
PaintControl	QAOA-TCS	Depol. 5%	1,333,351.200	147,559.808	14.334	0.904
PaintControl	IGDec-QAOA	Ideal simulator	474,543.400	130,380.215	8.382	0.477
PaintControl	IGDec-QAOA	Noise	665,046.200	271,370.831	8.249	0.898
PaintControl	SelectQA	–	159,150.000	0.000	5.314	0.000
PaintControl	BootQA	–	651,774.600	242,047.481	4.681	0.912
IOF/ROL	QAOA-TCS	Ideal simulator	64,190,011.000	0.000	435.101	0.000
IOF/ROL	QAOA-TCS	Sampling Noise	67,106,136.200	1,080,994.454	431.113	3.199
IOF/ROL	QAOA-TCS	Fake Brisbane	66,306,510.700	1,146,640.452	427.149	3.836
IOF/ROL	QAOA-TCS	Depol. 1%	66,468,837.300	677,719.930	428.841	1.977
IOF/ROL	QAOA-TCS	Depol. 2%	67,198,194.600	673,543.891	429.711	2.361
IOF/ROL	QAOA-TCS	Depol. 5%	67,147,794.900	1,293,047.297	429.386	4.357
IOF/ROL	IGDec-QAOA	Ideal simulator	10,801,269.300	10,957,484.553	91.852	33.548
IOF/ROL	IGDec-QAOA	Noise	25,192,111.600	20,251,046.346	126.114	50.307

Algorithm	Backend	Execution Cost Mean	Execution Cost Std. Dev.	Passenger Count Mean	Passenger Count Std. Dev.
QAOA-TCS	Ideal simulator	151,174.000	0.000	15583.000	0.000
QAOA-TCS	Sampling Noise	154,704.600	1,743.549	15,355.300	89.187
QAOA-TCS	Fake Brisbane	156,858.200	1,579.536	15,402.500	86.557
QAOA-TCS	Depol. 1%	155,394.400	2,851.423	15,354.900	139.885
QAOA-TCS	Depol. 2%	156,584.700	1,581.175	15,383.200	83.629
QAOA-TCS	Depol. 5%	158,309.000	1,377.001	15,446.400	76.969
IGDec-QAOA	Ideal simulator	228,366.400	6,974.035	18,085.500	332.167
IGDec-QAOA	Noise	226,640.400	19,202.746	17,298.200	1,579.883
		Travel Distance
QAOA-TCS	Ideal simulator	50,652.000	0.000
QAOA-TCS	Sampling Noise	49,579.400	292.890
QAOA-TCS	Fake Brisbane	49,758.900	254.745
QAOA-TCS	Depol. 1%	49,616.300	444.212
QAOA-TCS	Depol. 2%	49,671.800	295.775
QAOA-TCS	Depol. 5%	49,814.700	247.575
IGDec-QAOA	Ideal simulator	57,461.800	1,073.966
IGDec-QAOA	Noise	54,698.700	5,296.257

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 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 $\mathit{ELEVATOR}_{02}$ and $\mathit{ELEVATOR}_{03}$, QAOA-TCS finds efficient solutions, while IGDec-QAOA finds effective solutions, with statistical analysis confirming both results.

Algorithm	Backend	Execution Cost Mean	Execution Cost Std. Dev.	Input Diversity Mean	Input Diversity Std. Dev.
QAOA-TCS	Ideal simulator	133,136.000	0.000	722.161	0.000
QAOA-TCS	Sampling Noise	134,086.900	567.045	721.297	0.827
QAOA-TCS	Fake Brisbane	134,097.700	680.828	721.502	1.484
QAOA-TCS	Depol. 1%	134,541.200	617.643	722.590	0.875
QAOA-TCS	Depol. 2%	134,450.000	759.870	722.288	1.565
QAOA-TCS	Depol. 5%	134,798.400	1,043.149	722.275	1.676
IGDec-QAOA	Ideal simulator	171,895.600	19,856.754	751.797	26.447
IGDec-QAOA	Noise	185,283.700	17,829.767	724.662	63.954

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.

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, ELEVATORo2, and ELEVATORo3 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, ELEVATORo2, and ELEVATORo3 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.

Dataset	Algorithm	Backend	Mean (s)	Std. Dev. (s)
GSDTSR	QAOA-TCS	Ideal simulator	95.53	10.71
GSDTSR	QAOA-TCS	Sampling Noise	9.31	0.91
GSDTSR	QAOA-TCS	Fake Brisbane	2,035.92	20.24
GSDTSR	QAOA-TCS	Depol. 1%	17.71	0.39
GSDTSR	QAOA-TCS	Depol. 2%	18.93	4.59
GSDTSR	QAOA-TCS	Depol. 5%	17.71	0.27
GSDTSR	IGDec-QAOA	Ideal simulator	199.81	0.66
GSDTSR	IGDec-QAOA	Noise	1,557.85	99.35
GSDTSR	SelectQA	–	3.00	< 0.01
GSDTSR	BootQA	–	0.58	0.02
PaintControl	QAOA-TCS	Ideal simulator	27.72	0.21
PaintControl	QAOA-TCS	Sampling Noise	2.68	0.09
PaintControl	QAOA-TCS	Fake Brisbane	634.74	13.10
PaintControl	QAOA-TCS	Depol. 1%	5.47	0.22
PaintControl	QAOA-TCS	Depol. 2%	5.45	0.15
PaintControl	QAOA-TCS	Depol. 5%	5.41	0.17
PaintControl	IGDec-QAOA	Ideal simulator	0.03	< 0.01
PaintControl	IGDec-QAOA	Noise	0.25	0.02
PaintControl	SelectQA	–	2.99	< 0.01
PaintControl	BootQA	–	0.91	0.04
IOF/ROL	QAOA-TCS	Ideal simulator	489.79	1.69
IOF/ROL	QAOA-TCS	Sampling Noise	54.67	1.98
IOF/ROL	QAOA-TCS	Fake Brisbane	11,378.77	163.47
IOF/ROL	QAOA-TCS	Depol. 1%	108.28	2.45
IOF/ROL	QAOA-TCS	Depol. 2%	108.34	3.01
IOF/ROL	QAOA-TCS	Depol. 5%	109.74	5.42
IOF/ROL	IGDec-QAOA	Ideal simulator	24.04	0.11
IOF/ROL	IGDec-QAOA	Noise	207.29	2.60
$ELEVATOR_{o_2}$	QAOA-TCS	Ideal simulator	595.73	2.29
$ELEVATOR_{o_2}$	QAOA-TCS	Sampling Noise	84.02	2.18
$ELEVATOR_{o_2}$	QAOA-TCS	Fake Brisbane	22,844.96	116.05
$ELEVATOR_{o_2}$	QAOA-TCS	Depol. 1%	153.97	4.28
$ELEVATOR_{o_2}$	QAOA-TCS	Depol. 2%	151.39	4.16
$ELEVATOR_{o_2}$	QAOA-TCS	Depol. 5%	150.65	3.65
$ELEVATOR_{o_2}$	IGDec-QAOA	Ideal simulator	23.90	0.66
$ELEVATOR_{o_2}$	IGDec-QAOA	Noise	174.65	4.31
$ELEVATOR_{o_3}$	QAOA-TCS	Ideal simulator	833.13	3.53
$ELEVATOR_{o_3}$	QAOA-TCS	Sampling Noise	83.58	2.35
$ELEVATOR_{o_3}$	QAOA-TCS	Fake Brisbane	20,891.92	80.24
$ELEVATOR_{o_3}$	QAOA-TCS	Depol. 1%	148.04	4.58
$ELEVATOR_{o_3}$	QAOA-TCS	Depol. 2%	148.17	3.42
$ELEVATOR_{o_3}$	QAOA-TCS	Depol. 5%	149.12	4.57
$ELEVATOR_{o_3}$	IGDec-QAOA	Ideal simulator	23.75	0.13
$ELEVATOR_{o_3}$	IGDec-QAOA	Noise	174.01	4.92

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 small-scale PaintControl dataset, all approaches and most QAOA-TCS configurations could select test cases in less than 6 seconds. Regarding IOF/ROL, ELEVATOR$_{\mathrm{o2}}$, and ELEVATOR$_{\mathrm{o3}}$, 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, QAOA-based 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 IGDec-QAOA 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.

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 effectiveness. We selected these values consistent with prior work on IGDec-QAOA (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-the-art 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.

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 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 QAOA-TCS 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 Pareto-front 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 noise-induced 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.

Declarations

Ethical approval

Ethical approval: not applicable.

Informed consent

Informed consent: not applicable.

Data Availability Statement

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

Conflict of interest

The authors declare no conflicts of interest.

Clinical Trial Number

Clinical Trial Number: not applicable.

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.