Article

Generating Failing Test Suites for Quantum Programs With Search

Authors:

Xinyi Wang,

Paolo Arcaini,

Tao Yue,

Shaukat AliAuthors Info & Claims

Search-Based Software Engineering: 13th International Symposium, SSBSE 2021, Bari, Italy, October 11–12, 2021, Proceedings

Pages 9 - 25

https://doi.org/10.1007/978-3-030-88106-1_2

Published: 11 October 2021 Publication History

Abstract

Testing quantum programs requires systematic, automated, and intelligent methods due to their inherent complexity, such as their superposition and entanglement. To this end, we present a search-based approach, called Quantum Search-Based Testing (QuSBT), for automatically generating test suites of a given size depending on available testing budget, with the aim of maximizing the number of failing test cases in the test suite. QuSBT consists of definitions of the problem encoding, failure types, test assessment with statistical tests, fitness function, and test case generation with a Genetic Algorithm (GA). To empirically evaluate QuSBT, we compared it with Random Search (RS) by testing six quantum programs. We assessed the effectiveness of QuSBT and RS with 30 carefully designed faulty versions of the six quantum programs. Results show that QuSBT provides a viable solution for testing quantum programs, and achieved a significant improvement over RS in 87% of the faulty programs, and no significant difference in the rest of 13% of the faulty programs.

References

[1]

Agresti, A.: An Introduction to Categorical Data Analysis, 3 edn. Wiley-Blackwell (2019)

Google Scholar

[2]

Ali, S., Arcaini, P., Wang, X., Yue, T.: Assessing the effectiveness of input and output coverage criteria for testing quantum programs. In: 2021 14th IEEE Conference on Software Testing, Verification and Validation (ICST), pp. 13–23 (2021).

Crossref

Google Scholar

[3]

Arcuri, A., Briand, L.: A practical guide for using statistical tests to assess randomized algorithms in software engineering. In: Proceedings of the 33rd International Conference on Software Engineering, ICSE 2011, pp. 1–10. ACM, New York (2011)

Google Scholar

[4]

Arcuri A and Fraser G Parameter tuning or default values? An empirical investigation in search-based software engineering Empir. Softw. Eng. 2013 18 594-623

Crossref

Google Scholar

[5]

Benítez-Hidalgo A, Nebro AJ, García-Nieto J, Oregi I, and Del Ser J jMetalPy: a Python framework for multi-objective optimization with metaheuristics Swarm Evol. Comput. 2019 51 100598

Crossref

Google Scholar

[6]

Gimeno-Segovia M, Harrigan N, and Johnston E Programming Quantum Computers: Essential Algorithms and Code Samples 2019 Newton O’Reilly Media, Inc.

Google Scholar

[7]

Honarvar, S., Mousavi, M.R., Nagarajan, R.: Property-based testing of quantum programs in Q#. In: Proceedings of the IEEE/ACM 42nd International Conference on Software Engineering Workshops, ICSEW 2020, pp. 430–435. Association for Computing Machinery, New York (2020)

Google Scholar

[8]

Huang, Y., Martonosi, M.: QDB: from quantum algorithms towards correct quantum programs. In: 9th Workshop on Evaluation and Usability of Programming Languages and Tools (PLATEAU 2018). OpenAccess Series in Informatics (OASIcs), vol. 67, pp. 4:1–4:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2019)

Google Scholar

[9]

Li, G., Zhou, L., Yu, N., Ding, Y., Ying, M., Xie, Y.: Projection-based runtime assertions for testing and debugging quantum programs. Proc. ACM Program. Lang. 4(OOPSLA), 1–29 (2020)

Google Scholar

[10]

Liu, J., Byrd, G.T., Zhou, H.: Quantum circuits for dynamic runtime assertions in quantum computation. In: Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 1017–1030 (2020)

Google Scholar

[11]

Miranskyy, A., Zhang, L.: On testing quantum programs. In: 2019 IEEE/ACM 41st International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER), pp. 57–60 (2019)

Google Scholar

[12]

Wang, J., Ma, F., Jiang, Y.: Poster: fuzz testing of quantum program. In: 2021 14th IEEE Conference on Software Testing, Verification and Validation (ICST), pp. 466–469 (2021).

Crossref

Google Scholar

[13]

Wille, R., Van Meter, R., Naveh, Y.: IBM’s Qiskit tool chain: working with and developing for real quantum computers. In: 2019 Design, Automation Test in Europe Conference Exhibition (DATE), pp. 1234–1240 (2019)

Google Scholar

Cited By

View all

Long PZhao J(2024)Testing Multi-Subroutine Quantum Programs: From Unit Testing to Integration TestingACM Transactions on Software Engineering and Methodology10.1145/365633933:6(1-61)Online publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1145/3656339
Ali SRoychoudhury APaiva AAbreu RStorey M(2024)Quantum Software Testing 101Proceedings of the 2024 IEEE/ACM 46th International Conference on Software Engineering: Companion Proceedings10.1145/3639478.3643059(426-427)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639478.3643059
Khan AAkbar MLahtinen VPaavola MNiazi MAlatawi MAlotaibi S(2024)Agile meets quantum: a novel genetic algorithm model for predicting the success of quantum software development projectAutomated Software Engineering10.1007/s10515-024-00434-z31:1Online publication date: 4-Apr-2024
https://dl.acm.org/doi/10.1007/s10515-024-00434-z
Show More Cited By

Index Terms

Generating Failing Test Suites for Quantum Programs With Search

Index terms have been assigned to the content through auto-classification.

Recommendations

Mutation-based test generation for quantum programs with multi-objective search
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference

Mutation testing is often used for designing new tests, and involves changing a program in minor ways, which results in mutated versions of the program, i.e., mutants. An effective test suite should find faults (or kill mutants) with a minimum number of ...
Generating failing test suites for quantum programs with search (hot off the press track at GECCO 2022)
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference Companion

The inherent complexity of quantum programs, due to features such as superposition and entanglement, makes their testing particularly challenging. To tackle these challenges, we present a search-based approach, called Quantum Search-Based Testing (QuSBT),...
Prioritizing random combinatorial test suites
SAC '17: Proceedings of the Symposium on Applied Computing

The behaviour of a system under test can be influenced by several factors, such as system configurations, user inputs, and so on. It has also been observed that many failures are caused by only a small number of factors. Combinatorial testing aims at ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Search-Based Software Engineering: 13th International Symposium, SSBSE 2021, Bari, Italy, October 11–12, 2021, Proceedings

Oct 2021

175 pages

ISBN:978-3-030-88105-4

DOI:10.1007/978-3-030-88106-1

Editors:
Una-May O'Reilly
Massachusetts Institute of Technology, Cambridge, MA, USA
,
Xavier Devroey
Delft University of Technology, Delft, The Netherlands

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 11 October 2021

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Long PZhao J(2024)Testing Multi-Subroutine Quantum Programs: From Unit Testing to Integration TestingACM Transactions on Software Engineering and Methodology10.1145/365633933:6(1-61)Online publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1145/3656339
Ali SRoychoudhury APaiva AAbreu RStorey M(2024)Quantum Software Testing 101Proceedings of the 2024 IEEE/ACM 46th International Conference on Software Engineering: Companion Proceedings10.1145/3639478.3643059(426-427)Online publication date: 14-Apr-2024
https://dl.acm.org/doi/10.1145/3639478.3643059
Khan AAkbar MLahtinen VPaavola MNiazi MAlatawi MAlotaibi S(2024)Agile meets quantum: a novel genetic algorithm model for predicting the success of quantum software development projectAutomated Software Engineering10.1007/s10515-024-00434-z31:1Online publication date: 4-Apr-2024
https://dl.acm.org/doi/10.1007/s10515-024-00434-z
Abreu RFernandes JLlana LTavares GCampos JZhao J(2022)Metamorphic testing of oracle quantum programsProceedings of the 3rd International Workshop on Quantum Software Engineering10.1145/3528230.3529189(16-23)Online publication date: 18-May-2022
https://dl.acm.org/doi/10.1145/3528230.3529189
Oldfield NYue TAli SCampos JZhao J(2022)Investigating quantum cause-effect graphsProceedings of the 3rd International Workshop on Quantum Software Engineering10.1145/3528230.3529186(8-15)Online publication date: 18-May-2022
https://dl.acm.org/doi/10.1145/3528230.3529186
Pontolillo GMousavi MCampos JZhao J(2022)A multi-lingual benchmark for property-based testing of quantum programsProceedings of the 3rd International Workshop on Quantum Software Engineering10.1145/3528230.3528395(1-7)Online publication date: 18-May-2022
https://dl.acm.org/doi/10.1145/3528230.3528395
Wang XArcaini PYue TAli SWagner M(2022)Generating failing test suites for quantum programs with search (hot off the press track at GECCO 2022)Proceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534067(47-48)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534067
Ali SYue TAbreu R(2022)When software engineering meets quantum computingCommunications of the ACM10.1145/351234065:4(84-88)Online publication date: 19-Mar-2022
https://dl.acm.org/doi/10.1145/3512340
Wang XYu TArcaini PYue TAli SWagner M(2022)Mutation-based test generation for quantum programs with multi-objective searchProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528869(1345-1353)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528869
Wang XArcaini PYue TAli SDwyer M(2022)QuSBTProceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion Proceedings10.1145/3510454.3516839(173-177)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510454.3516839

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Mutation-based test generation for quantum programs with multi-objective search