EUVIMEDEUVIMED entdecken
Crossref

Test Case Minimization with Quantum Annealers

Xinyi Wang, Asmar Muqeet, Tao Yue, Shaukat Ali, Paolo Arcaini

ACM Transactions on Software Engineering and Methodology · 31.01.2025 · 34 (1) · 1-24

DOI: 10.1145/3680467 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Software Engineering and Methodology, online erschienen am 26.12.2024. Verfasst von Xinyi Wang und 4 weiteren Autor:innen. Die Arbeit wurde bisher 14-mal zitiert (Crossref) und nennt 68 Literaturangaben. Gefördert von: Research Council of Norway, Engineerable AI Techniques for Practical Applications of High-Quality Machine Learning-Based Systems Project, ERATO HASUO Metamathematics for Systems Design.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Quantum annealers are specialized quantum computers for solving combinatorial optimization problems with special quantum computing characteristics, e.g., superposition and entanglement. Theoretically, quantum annealers can outperform classic computers. However, current quantum annealers are constrained by a limited number of qubits and cannot demonstrate quantum advantages. Nonetheless, research is needed to develop novel mechanisms to formulate combinatorial optimization problems for quantum annealing (QA). However, QA applications in software engineering remain unexplored. Thus, we propose BootQA , the very first effort at solving test case minimization (TCM) problems on classical software with QA. We provide a novel TCM formulation for QA and utilize bootstrap sampling to optimize the qubit usage. We also implemented our TCM formulation in three other optimization processes: 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 regarding 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.

Förderung

  • Research Council of Norway
  • Engineerable AI Techniques for Practical Applications of High-Quality Machine Learning-Based Systems Project
  • ERATO HASUO Metamathematics for Systems Design
  • JST

Zitieren

APA

Wang, X., Muqeet, A., Yue, T., Ali, S., & Arcaini, P. (2025). Test Case Minimization with Quantum Annealers. ACM Transactions on Software Engineering and Methodology, 34(1), 1-24. https://doi.org/10.1145/3680467

Vancouver

Wang X, Muqeet A, Yue T, Ali S, Arcaini P. Test Case Minimization with Quantum Annealers. ACM Transactions on Software Engineering and Methodology. 2025;34(1):1-24. doi:10.1145/3680467

BibTeX
@article{Wang2025,
  author = {Wang, Xinyi and Muqeet, Asmar and Yue, Tao and Ali, Shaukat and Arcaini, Paolo},
  title = {Test Case Minimization with Quantum Annealers},
  journal = {ACM Transactions on Software Engineering and Methodology},
  year = {2025},
  volume = {34},
  number = {1},
  pages = {1--24},
  doi = {10.1145/3680467}
}
Kostenlos starten →