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

Regression testing assesses whether software components that have already been developed and tested continue to work correctly after modifications. The ideal regression testing approach re-executes the whole test suite after each modification, which is unfeasible in real-world scenarios due to its enormous computational burden. Therefore, optimized approaches have been developed, also referred to as Test Case Selection. 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. The objective is to thoroughly evaluate its performance and compare it with state-of-the-art classical and quantum approaches, as well as its robustness to quantum noise. The 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, QAOA-based methods have comparable performance. In terms of efficiency, our previous method based on quantum annealing, namely SelectQA, is the most efficient for large problems with a multi-objective formulation, whereas QAOA-TCS offers the best trade-off between effectiveness and efficiency in the single-objective formulation when executed on realistic noisy simulators. However, such analysis is constrained by the different computational environments used to run the algorithms.