Researchers from Simula Research Laboratory and the National Institute of Informatics have used Quantum Approximate Optimization Algorithms (QAOAs) to solve software test case optimization problems. The team used a problem decomposition strategy with the QAOA to solve larger test optimization problems. They tested their approach using data from ABB, Google, and Orona, and found that their strategy could match the effectiveness of a Genetic Algorithm and outperform it in two out of five test case optimization problems. The researchers believe their work could improve as larger-scale quantum computers become available. The paper was published in arXiv named: “GUESS WHAT QUANTUM COMPUTING CAN DO FOR TEST OPTIMIZATION”.
Quantum Computing and Test Optimization
Quantum computing has the potential to revolutionize various fields, including finance, complex physics and chemistry simulations, and drug discovery. Among these applications, optimization applications are expected to demonstrate a quantum advantage in the near future, especially for solving combinatorial optimization problems. Quantum Approximate Optimization Algorithms (QAOAs) are promising optimization algorithms that combine quantum-classical algorithms.
QAOAs and Software Engineering
Many problems in software engineering are optimization problems, such as test case minimization and optimal requirements allocation for inspection. Thus, QAOAs have the potential to solve such problems efficiently. However, there has not been any effort to investigate applying QAOAs for solving software engineering problems.
LOCH-QAOA: A New Approach
In a recent study, a team from Simula Research Laboratory and the National Institute of Informatics proposed an approach based on QAOAs, which is called LOCH-QAOA, to solve test case optimization (TCO) problems. They demonstrated how to formulate optimization objectives for TCO problems as a generic function in the Ising formulation such that QAOAs can be applied to solve them.
Problem Decomposition Strategy
To solve problems with a large number of test cases that cannot be directly solved with current quantum computers having a limited number of qubits, the team applied an impact-guided decomposition strategy adapted from D-Wave to break down a complex TCO problem into a set of smaller and more manageable sub-problems so that they can be solved with current quantum computers.
Empirical Evaluation of LOCH-QAOA
The team performed an empirical evaluation with five industrial case studies from ABB, Google, and Orona to demonstrate LOCH-QAOA’s capability of finding approximate optimal solutions for TCO problems. They studied various configurations of LOCH-QAOA and compared its performance with classical algorithms, i.e., Genetic Algorithm (GA) and Random Search (RS).
Results and Future Prospects
Based on the results of the empirical evaluation, the team selected the best configurations for LOCH-QAOA to solve the TCO problems. The effectiveness of the approach was on par with GA, with 2 (out of 5) TCO problems outperforming GA. This demonstrates the benefit of using LOCH-QAOA for solving TCO problems with currently available small-scale quantum computers. The team envisions a further improvement of LOCH-QAOA’s performance in the future when large-scale quantum computers are accessible.
This paper does not intend to demonstrate the quantum advantage of solving TCO problems with QAOA over classical approaches. This is practically impossible since only small-scale noisy quantum computers are currently available. Rather, we demonstrate how TCO problems can be formulated and solved with QAOA by achieving comparable performance as classical approaches with manageable execution costs, which should be considered as a cornerstone for future quantum computing applications in solving software engineering optimization problems.
Summary
Quantum Approximate Optimization Algorithms (QAOAs) have been used for the first time to solve software test case optimization problems, demonstrating potential for efficient problem-solving in software engineering. The study found that the effectiveness of this quantum approach was on par with traditional methods, even outperforming them in two out of five test case optimization problems.
- Researchers from Simula Research Laboratory and the National Institute of Informatics have explored the use of Quantum Approximate Optimization Algorithms (QAOAs) for test case optimization in software engineering.
- QAOAs are hybrid algorithms, combining quantum and classical algorithms, and have shown potential in solving combinatorial optimization problems such as portfolio optimization and job scheduling.
- The team formulated a software test case optimization problem as a QAOA problem and solved it on quantum computer simulators.
- To tackle larger test optimization problems that require many qubits, currently unavailable, they integrated a problem decomposition strategy with the QAOA.
- An empirical evaluation was conducted with five test case optimization problems and four industrial datasets from ABB, Google, and Orona.
- The results showed that their strategy can reach the same effectiveness as the Genetic Algorithm (GA) and outperform GA in two out of five test case optimization problems.
- The researchers clarified that their work does not demonstrate the quantum advantage of solving test case optimization problems with QAOA over classical approaches, but rather how these problems can be formulated and solved with QAOA.