Test Case Minimization with Quantum Annealers
arXiv:2308.05505 · doi:10.1145/3680467
Abstract
Quantum annealers are specialized quantum computers for solving combinatorial optimization problems using special characteristics of quantum computing (QC), such as superposition, entanglement, and quantum tunneling. Theoretically, quantum annealers can outperform classical computers. However, the currently available quantum annealers are small-scale, i.e., they have limited quantum bits (qubits); hence, they currently cannot demonstrate the quantum advantage. Nonetheless, research is warranted to develop novel mechanisms to formulate combinatorial optimization problems for quantum annealing (QA). However, solving combinatorial problems with QA in software engineering remains unexplored. Toward this end, we propose BootQA, the very first effort at solving the test case minimization (TCM) problem with QA. In BootQA, we provide a novel formulation of TCM for QA, followed by devising a mechanism to incorporate bootstrap sampling to QA to optimize the use of qubits. We also implemented our TCM formulation in three other optimization processes: classical simulated annealing (SA), QA without problem decomposition, and QA with an existing D-Wave problem decomposition strategy, and conducted an empirical evaluation with three real-world TCM datasets. Results show that BootQA outperforms QA without problem decomposition and QA with the existing decomposition strategy in terms of effectiveness. Moreover, BootQA's effectiveness is similar to SA. Finally, BootQA has higher efficiency in terms of time when solving large TCM problems than the other three optimization processes.
References in corpus (19)
- Quantum Annealing in the Transverse Ising Model
- Mathematical Foundation of Quantum Annealing
- Reinforcement Learning for Automatic Test Case Prioritization and Selection in Continuous Integration
- Test Case Selection and Prioritization Using Machine Learning: A Systematic Literature Review
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Quantum Annealing: An Overview
- Traffic Signal Optimization on a Square Lattice with Quantum Annealing
- A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
- Image Acquisition Planning for Earth Observation Satellites with a Quantum Annealer
- MOEA/D with Uniformly Randomly Adaptive Weights
- Multi-Objectivizing Software Configuration Tuning (for a single performance concern)
- Model Predictive Control for Finite Input Systems using the D-Wave Quantum Annealer
- Is Your Quantum Program Bug-Free?
- Implementation of a Hybrid Classical-Quantum Annealing Algorithm for Logistic Network Design
- QuSBT: Search-Based Testing of Quantum Programs
- Garden optimization problems for benchmarking quantum annealers
- Using Quantum Computers to Speed Up Dynamic Testing of Software
- A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing
- Quantum Computing for Software Engineering: Prospects