Quantum algorithm for solving the test-suite minimization problem

作     者：Hussein, Hager Younes, Ahmed Abdelmoez, Walid 

作者机构：Arab Acad Sci & Technol Coll Comp & Informat Technol Dept Software Engn Alexandria Egypt Alexandria Univ Fac Sci Dept Math & Comp Sci Alexandria Egypt Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England 

出 版 物：《COGENT ENGINEERING》 (Cogent Eng.)

年 卷 期：2021年第8卷第1期

页      面：Article: 1882116页

主　　题：Quantum Algorithm Test-Suite Minimization Superposition Preparation Quantum Search 

摘      要：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(root 2(n)), 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.