Quantum algorithm for solving the test suite minimization problem
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2021-01-01
|
| Series: | Cogent Engineering |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1080/23311916.2021.1882116 |
| _version_ | 1797762643441745920 |
|---|---|
| author | Hager Hussein Ahmed Younes Walid Abdelmoez |
| author_facet | Hager Hussein Ahmed Younes Walid Abdelmoez |
| author_sort | Hager Hussein |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T19:30:23Z |
| format | Article |
| id | doaj.art-39f1ddfd732d436a8fc1cf28183be8c4 |
| institution | Directory Open Access Journal |
| issn | 2331-1916 |
| language | English |
| last_indexed | 2024-03-12T19:30:23Z |
| publishDate | 2021-01-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | Cogent Engineering |
| spelling | doaj.art-39f1ddfd732d436a8fc1cf28183be8c42023-08-02T04:33:47ZengTaylor & Francis GroupCogent Engineering2331-19162021-01-018110.1080/23311916.2021.18821161882116Quantum algorithm for solving the test suite minimization problemHager Hussein0Ahmed Younes1Walid Abdelmoez2College of Computing and Information Technology, Arab Academy for Science and TechnologyAlexandria UniversityCollege of Computing and Information Technology, Arab Academy for Science and TechnologyTest-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.http://dx.doi.org/10.1080/23311916.2021.1882116quantum algorithmtest-suite minimizationsuperposition preparationquantum search |
| spellingShingle | Hager Hussein Ahmed Younes Walid Abdelmoez Quantum algorithm for solving the test suite minimization problem Cogent Engineering quantum algorithm test-suite minimization superposition preparation quantum search |
| title | Quantum algorithm for solving the test suite minimization problem |
| title_full | Quantum algorithm for solving the test suite minimization problem |
| title_fullStr | Quantum algorithm for solving the test suite minimization problem |
| title_full_unstemmed | Quantum algorithm for solving the test suite minimization problem |
| title_short | Quantum algorithm for solving the test suite minimization problem |
| title_sort | quantum algorithm for solving the test suite minimization problem |
| topic | quantum algorithm test-suite minimization superposition preparation quantum search |
| url | http://dx.doi.org/10.1080/23311916.2021.1882116 |
| work_keys_str_mv | AT hagerhussein quantumalgorithmforsolvingthetestsuiteminimizationproblem AT ahmedyounes quantumalgorithmforsolvingthetestsuiteminimizationproblem AT walidabdelmoez quantumalgorithmforsolvingthetestsuiteminimizationproblem |