Quantum Approximate Optimization Algorithm for Test Case Optimization
arXiv:2312.15547 · doi:10.1109/TSE.2024.3479421
Abstract
Test case optimization (TCO) reduces software testing cost while preserving its effectiveness, but solving TCO problems for large-scale and complex systems requires substantial computational resources. Quantum approximate optimization algorithms (QAOAs) are promising combinatorial optimization algorithms that rely on quantum computational resources, with the potential efficiency advantages over classical approaches. Several proof-of-concept applications of QAOAs for solving combinatorial problems, such as portfolio optimization, energy systems, and job scheduling, have been proposed. Given the lack of investigation into QAOA's application to TCO problems, and motivated by the computational challenges of TCO problems and the potential of QAOAs, we present IGDec-QAOA to formulate a TCO problem as a QAOA problem and solve it on both ideal and noisy quantum computer simulators, as well as on a real quantum computer. To solve bigger TCO problems that require many qubits, which are unavailable currently, we integrate a problem decomposition strategy with the QAOA. We performed an empirical evaluation with five TCO problems and four publicly available industrial datasets from ABB, Google, and Orona to compare various configurations of IGDec-QAOA, assess its decomposition strategy of handling large datasets, and compare its performance with classical algorithms (i.e., GA and Random Search). Based on the evaluation results achieved on an ideal simulator, we recommend the best configuration of our approach for TCO problems. We also demonstrate that it can reach the same effectiveness as GA and outperform GA in two out of five test case optimization problems. In addition, we observe that, on a noisy simulator, IGDec-QAOA achieved similar performance to that from an ideal simulator. Finally, we demonstrate the feasibility of IGDec-QAOA on a real quantum computer in the presence of noise.
References in corpus (18)
- Quantum algorithm for solving linear systems of equations
- Ising formulations of many NP problems
- Quantum optimization using variational algorithms on near-term quantum devices
- Simulation of Electronic Structure Hamiltonians Using Quantum Computers
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Quantum Computing for Finance: State of the Art and Future Prospects
- QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
- Reinforcement Learning for Automatic Test Case Prioritization and Selection in Continuous Integration
- Emerging quantum computing algorithms for quantum chemistry
- Test Case Selection and Prioritization Using Machine Learning: A Systematic Literature Review
- Near-optimal quantum circuit for Grover's unstructured search using a transverse field
- Benchmarking the performance of portfolio optimization with QAOA
- Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
- Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
- Incorporating fault-proneness estimations into coverage-based test case prioritization methods
- Using Quantum Computers to Speed Up Dynamic Testing of Software
- Quantum Computing for Software Engineering: Prospects
- Test Case Minimization with Quantum Annealers