Details
| Original language | English |
|---|---|
| Title of host publication | 27th ACM International Systems and Software Product Line Conference |
| Subtitle of host publication | SPLC 2023 |
| Editors | Paolo Arcaini, Maurice H. ter Beek, Gilles Perrouin, Iris Reinhartz-Berger, Miguel R. Luaces, Christa Schwanninger, Shaukat Ali, Mahsa Varshosaz, Angelo Gargantini, Stefania Gnesi, Malte Lochau, Laura Semini, Hironori Washizaki |
| Publisher | Association for Computing Machinery (ACM) |
| Pages | 1-7 |
| Number of pages | 7 |
| ISBN (electronic) | 9798400700910 |
| Publication status | Published - 28 Aug 2023 |
| Event | 27th ACM International Systems and Software Product Line Conference, SPLC 2023 - Tokyo, Japan Duration: 28 Aug 2023 → 1 Sept 2023 |
Publication series
| Name | ACM International Conference Proceeding Series |
|---|---|
| Volume | A-1 |
Abstract
Feature modeling is a technique to model the variability of configurable systems. When working with feature models, it is possible to analyze them, for instance, by counting the number of valid configurations, searching feature model anomalies, or creating samples of configurations for testing. Classical feature model analysis techniques are based on solving algorithmic problems such as boolean satisfiability, satisfiability modulo theories, or integer linear programming. Existing analysis approaches provide satisfactory solutions for small and medium-sized problem instances, but scaling issues are observed for large-sized feature models. Quantum computers provide up to superpolynomial speedups for specific algorithmic problems and have the potential to solve those scaling issues. This paper analyzes the algorithmic techniques used in classical product line analysis and identifies potentials and challenges for quantum speedups. Our findings show that quantum algorithms like QAOA and Grover have the potential to speed up SAT and ILP-based feature model analysis techniques, but only after additional improvements in quantum hardware have been made.
Keywords
- feature model analysis, quantum algorithms, quantum computing
ASJC Scopus subject areas
- Computer Science(all)
- Human-Computer Interaction
- Computer Science(all)
- Computer Networks and Communications
- Computer Science(all)
- Computer Vision and Pattern Recognition
- Computer Science(all)
- Software
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
27th ACM International Systems and Software Product Line Conference: SPLC 2023. ed. / Paolo Arcaini; Maurice H. ter Beek; Gilles Perrouin; Iris Reinhartz-Berger; Miguel R. Luaces; Christa Schwanninger; Shaukat Ali; Mahsa Varshosaz; Angelo Gargantini; Stefania Gnesi; Malte Lochau; Laura Semini; Hironori Washizaki. Association for Computing Machinery (ACM), 2023. p. 1-7 (ACM International Conference Proceeding Series; Vol. A-1).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Quantum Computing for Feature Model Analysis
T2 - 27th ACM International Systems and Software Product Line Conference, SPLC 2023
AU - Eichhorn, Domenik
AU - Pett, Tobias
AU - Osborne, Tobias
AU - Schaefer, Ina
N1 - Funding Information: This work has been supported by the German Federal Ministry for Education and Research in the project QuBRA (reference number: 13N16303) and the Baden-Württemberg Ministry of Economic Affairs, Labour and Tourism in the project SEQUOIA End-to-End (reference number: WM3-4332-149/44.). The authors would also like to thank Christoph Seidl for his valuable input to discussions about this work.
PY - 2023/8/28
Y1 - 2023/8/28
N2 - Feature modeling is a technique to model the variability of configurable systems. When working with feature models, it is possible to analyze them, for instance, by counting the number of valid configurations, searching feature model anomalies, or creating samples of configurations for testing. Classical feature model analysis techniques are based on solving algorithmic problems such as boolean satisfiability, satisfiability modulo theories, or integer linear programming. Existing analysis approaches provide satisfactory solutions for small and medium-sized problem instances, but scaling issues are observed for large-sized feature models. Quantum computers provide up to superpolynomial speedups for specific algorithmic problems and have the potential to solve those scaling issues. This paper analyzes the algorithmic techniques used in classical product line analysis and identifies potentials and challenges for quantum speedups. Our findings show that quantum algorithms like QAOA and Grover have the potential to speed up SAT and ILP-based feature model analysis techniques, but only after additional improvements in quantum hardware have been made.
AB - Feature modeling is a technique to model the variability of configurable systems. When working with feature models, it is possible to analyze them, for instance, by counting the number of valid configurations, searching feature model anomalies, or creating samples of configurations for testing. Classical feature model analysis techniques are based on solving algorithmic problems such as boolean satisfiability, satisfiability modulo theories, or integer linear programming. Existing analysis approaches provide satisfactory solutions for small and medium-sized problem instances, but scaling issues are observed for large-sized feature models. Quantum computers provide up to superpolynomial speedups for specific algorithmic problems and have the potential to solve those scaling issues. This paper analyzes the algorithmic techniques used in classical product line analysis and identifies potentials and challenges for quantum speedups. Our findings show that quantum algorithms like QAOA and Grover have the potential to speed up SAT and ILP-based feature model analysis techniques, but only after additional improvements in quantum hardware have been made.
KW - feature model analysis
KW - quantum algorithms
KW - quantum computing
UR - http://www.scopus.com/inward/record.url?scp=85175991500&partnerID=8YFLogxK
U2 - 10.1145/3579027.3608971
DO - 10.1145/3579027.3608971
M3 - Conference contribution
AN - SCOPUS:85175991500
T3 - ACM International Conference Proceeding Series
SP - 1
EP - 7
BT - 27th ACM International Systems and Software Product Line Conference
A2 - Arcaini, Paolo
A2 - ter Beek, Maurice H.
A2 - Perrouin, Gilles
A2 - Reinhartz-Berger, Iris
A2 - Luaces, Miguel R.
A2 - Schwanninger, Christa
A2 - Ali, Shaukat
A2 - Varshosaz, Mahsa
A2 - Gargantini, Angelo
A2 - Gnesi, Stefania
A2 - Lochau, Malte
A2 - Semini, Laura
A2 - Washizaki, Hironori
PB - Association for Computing Machinery (ACM)
Y2 - 28 August 2023 through 1 September 2023
ER -