Quantum algorithm for solving the test suite minimization problem

Abstract

Test-suite minimization problem is an essential problem in software engineering as its application helps to improve the software quality. This paper proposes a quantum algorithm to solve the test-suite minimization problem with high probability in $$O\left({\sqrt {{2^n}} } \right)$$, where $$n$$ is the number of test cases. It generates an incomplete superposition to find the best solution. It also handles the non-uniform amplitudes’ distribution case for the system with multisolutions. The proposed algorithm uses amplitude amplification techniques to search for the minimum number of test cases required to test all the requirements. The proposed algorithm employs two quantum search algorithms, Younes et al. algorithm for quantum searching via entanglement and partial diffusion to prepare incomplete superpositions that represent different search spaces such that the number of test cases is incremented in each search space, and updated Arima’s algorithm to handle the multisolutions case. The updated Arima’s algorithm searches for a quantum state that satisfies an oracle that represent the instance of the test-suite minimization problem.

Keywords

• quantum algorithm
• test-suite minimization
• superposition preparation
• quantum search