research-article

Automatic Repair of Quantum Programs via Unitary Operation

Authors:

Kai-Yuan CaiAuthors Info & Claims

ACM Transactions on Software Engineering and Methodology, Volume 33, Issue 6

Article No.: 154, Pages 1 - 43

https://doi.org/10.1145/3664604

Published: 28 June 2024 Publication History

Abstract

With the continuous advancement of quantum computing (QC), the demand for high-quality quantum programs (QPs) is growing. To avoid program failure, in software engineering, the technology of automatic program repair (APR) employs appropriate patches to remove potential bugs without the intervention of a human. However, the method tailored for repairing defective QPs is still absent. This article proposes, to the best of our knowledge, a new APR method named UnitAR that can repair QPs via unitary operation automatically. Based on the characteristics of superposition and entanglement in QC, the article constructs an algebraic model and adopts a generate-and-validate approach for the repair procedure. Furthermore, the article presents two schemes that can respectively promote the efficiency of generating patches and guarantee the effectiveness of applying patches. For the purpose of evaluating the proposed method, the article selects 29 mutated versions as well as five real-world buggy programs as the objects and introduces two traditional APR approaches GenProg and TBar as baselines. According to the experiments, UnitAR can fix 23 buggy programs, and this method demonstrates the highest efficiency and effectiveness among three APR approaches. Besides, the experimental results further manifest the crucial roles of two constituents involved in the framework of UnitAR.

References

[1]

Rui Abreu, Peter Zoeteweij, and Arjan J. C. Van Gemund. 2007. On the accuracy of spectrum-based fault localization. In Proceedings of the Testing: Academic and Industrial Conference Practice and Research Techniques-MUTATION (TAICPART-MUTATION’07). IEEE, 89–98.

Digital Library

[2]

Gadi Aleksandrowicz, Thomas Alexander, Panagiotis Barkoutsos, Luciano Bello, Yael Ben-Haim, David Bucher, Francisco Jose Cabrera-Hernádez, Jorge Carballo-Franquis, Adrian Chen, Chun-Fu Chen, Jerry M. Chow, Antonio D. Córcoles-Gonzales, Abigail J. Cross, Andrew Cross, Juan Cruz-Benito, Chris Culver, Salvador De La Puente González, Enrique De La Torre, Delton Ding, Eugene Dumitrescu, Ivan Duran, Pieter Eendebak, Mark Everitt, Ismael Faro Sertage, Albert Frisch, Andreas Fuhrer, Jay Gambetta, Borja Godoy Gago, Juan Gomez-Mosquera, Donny Greenberg, Ikko Hamamura, Vojtech Havlicek, Joe Hellmers, Łukasz Herok, Hiroshi Horii, Shaohan Hu, Takashi Imamichi, Toshinari Itoko, Ali Javadi-Abhari, Naoki Kanazawa, Anton Karazeev, Kevin Krsulich, Peng Liu, Yang Luh, Yunho Maeng, Manoel Marques, Francisco Jose Martín-Fernández, Douglas T. McClure, David McKay, Srujan Meesala, Antonio Mezzacapo, Nikolaj Moll, Diego Moreda Rodríguez, Giacomo Nannicini, Paul Nation, Pauline Ollitrault, Lee James O’Riordan, Hanhee Paik, Jesús Pérez, Anna Phan, Marco Pistoia, Viktor Prutyanov, Max Reuter, Julia Rice, Abdón Rodríguez Davila, Raymond Harry Putra Rudy, Mingi Ryu, Ninad Sathaye, Chris Schnabel, Eddie Schoute, Kanav Setia, Yunong Shi, Adenilton Silva, Yukio Siraichi, Seyon Sivarajah, John A. Smolin, Mathias Soeken, Hitomi Takahashi, Ivano Tavernelli, Charles Taylor, Pete Taylour, Kenso Trabing, Matthew Treinish, Wes Turner, Desiree Vogt-Lee, Christophe Vuillot, Jonathan A. Wildstrom, Jessica Wilson, Erick Winston, Christopher Wood, Stephen Wood, Stefan Wörner, Ismail Yunus Akhalwaya, and Christa Zoufal. 2019. Qiskit: An Open-source framework for quantum computing.

[3]

Shaukat Ali, Paolo Arcaini, Xinyi Wang, and Tao Yue. 2021. Assessing the effectiveness of input and output coverage criteria for testing quantum programs. In Proceedings of the 14th IEEE Conference on Software Testing, Verification and Validation (ICST’21). IEEE, 13–23.

[4]

Kai-Yuan Cai, João W. Cangussu, Raymond A. DeCarlo, and Aditya P. Mathur. 2003. An overview of software cybernetics. In Proceedings of the 11th Annual International Workshop on Software Technology and Engineering Practice. IEEE, 77–86.

[5]

Kai-Yuan Cai, Hai Hu, Chang-Hai Jiang, and Feng Ye. 2009. Random testing with dynamically updated test profile. In Proceedings of the 20th International Symposium on Software Reliability Engineering (ISSRE’09). 1–2.

[6]

Kai-Yuan Cai, Kishor S. Trivedi, and Beibei Yin. 2021. S-ada: Software as an autonomous, dependable and affordable system. In Proceedings of the 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks-Supplemental Volume (DSN-S’21). IEEE, 17–18.

[7]

João W. Cangussu, Kai-Yuan Cai, Scott D. Miller, and Aditya P. Mathur. 2007. Software cybernetics. In Wiley Encyclopedia of Computer Science and Engineering.

[8]

Junjie Chen, Yihua Liang, Qingchao Shen, Jiajun Jiang, and Shuochuan Li. 2022. Toward understanding deep learning framework bugs. ACM Trans. Softw. Eng. Methodol. 32, 6 (2022), 1–31.

[9]

Mike Y. Chen, Emre Kiciman, Eugene Fratkin, Armando Fox, and Eric Brewer. 2002. Pinpoint: Problem determination in large, dynamic internet services. In Proceedings International Conference on Dependable Systems and Networks. IEEE, 595–604.

[10]

Tsong Yueh Chen, Hing Leung, and Ieng Kei Mak. 2005. Adaptive random testing. In Proceedings of the Advances in Computer Science-ASIAN 2004. Higher-Level Decision Making: 9th Asian Computing Science Conference. Springer, 320–329.

[11]

Valentin Dallmeier, Andreas Zeller, and Bertrand Meyer. 2009. Generating fixes from object behavior anomalies. In Proceedings of the IEEE/ACM International Conference on Automated Software Engineering. IEEE, 550–554.

[12]

Favio DeMarco, Jifeng Xuan, Daniel Le Berre, and Martin Monperrus. 2014. Automatic repair of buggy if conditions and missing preconditions with smt. In Proceedings of the 6th International Workshop on Constraints in Software Testing, Verification, and Analysis. 30–39.

Digital Library

[13]

Joe W. Duran and Simeon C. Ntafos. 1984. An evaluation of random testing. IEEE Trans. Softw. Eng.4 (1984), 438–444.

Digital Library

[14]

Dawson Engler, David Yu Chen, Seth Hallem, Andy Chou, and Benjamin Chelf. 2001. Bugs as deviant behavior: A general approach to inferring errors in systems code. ACM SIGOPS Operat. Syst. Rev. 35, 5 (2001), 57–72.

Digital Library

[15]

Richard P. Feynman. 1982. Simulating physics with computers. Int. J. Theor. Phys. 21, 6/7 (1982).

[16]

Daniel Fortunato, Jose Campos, and Rui Abreu. 2022. Mutation testing of quantum programs: A case study with Qiskit. IEEE Trans. Quant. Eng. 3 (2022), 1–17.

[17]

Daniel Fortunato, José Campos, and Rui Abreu. 2022. Mutation testing of quantum programs written in Qiskit. In Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion Proceedings. 358–359.

Digital Library

[18]

Daniel Fortunato, José Campos, and Rui Abreu. 2022. QMutPy: A mutation testing tool for quantum algorithms and applications in Qiskit. In Proceedings of the 31st ACM SIGSOFT International Symposium on Software Testing and Analysis. 797–800.

Digital Library

[19]

Antonio García de la Barrera, Ignacio García-Rodríguez de Guzmán, Macario Polo, and Mario Piattini. 2023. Quantum software testing: State of the art. J. Software: Evolution and Process 35, 4 (2023), e2419.

[20]

Luca Gazzola, Daniela Micucci, and Leonardo Mariani. 2018. Automatic software repair: A survey. In Proceedings of the 40th International Conference on Software Engineering. 1219–1219.

Digital Library

[21]

Xiaoyu Guo, Jianjun Zhao, and Pengzhan Zhao. 2024. On repairing quantum programs using ChatGPT. arXiv:2401.14913. Retrieved from https://arxiv.org/abs/2401.14913

[22]

Richard Hamlet. 1994. Random testing. Encycl. Softw. Eng. 2 (1994), 971–978.

[23]

Shahin Honarvar, Mohammad Reza Mousavi, and Rajagopal Nagarajan. 2020. Property-based testing of quantum programs in Q#. In Proceedings of the IEEE/ACM 42nd International Conference on Software Engineering Workshops. 430–435.

Digital Library

[24]

Zdenek Hradil. 1997. Quantum-state estimation. Phys. Rev. A 55, 3 (1997), R1561.

[25]

Rubing Huang, Weifeng Sun, Yinyin Xu, Haibo Chen, Dave Towey, and Xin Xia. 2019. A survey on adaptive random testing. IEEE Trans. Softw. Eng. 47, 10 (2019), 2052–2083.

[26]

Yipeng Huang and Margaret Martonosi. 2019. Statistical assertions for validating patterns and finding bugs in quantum programs. In Proceedings of the 46th International Symposium on Computer Architecture. 541–553.

Digital Library

[27]

Jiajun Jiang, Yingfei Xiong, Hongyu Zhang, Qing Gao, and Xiangqun Chen. 2018. Shaping program repair space with existing patches and similar code. In Proceedings of the 27th ACM SIGSOFT International Symposium on Software Testing and Analysis. 298–309.

Digital Library

[28]

James A. Jones and Mary Jean Harrold. 2005. Empirical evaluation of the tarantula automatic fault-localization technique. In Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering. 273–282.

Digital Library

[29]

René Just, Darioush Jalali, and Michael D. Ernst. 2014. Defects4J: A database of existing faults to enable controlled testing studies for Java programs. In Proceedings of the International Symposium on Software Testing and Analysis. 437–440.

Digital Library

[30]

Claire Le Goues. 2013. Automatic Program Repair Using Genetic Programming. Ph. D. Dissertation. University of Virginia.

[31]

Claire Le Goues, Michael Dewey-Vogt, Stephanie Forrest, and Westley Weimer. 2012. A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each. In Proceedings of the 34th International Conference on Software Engineering (ICSE’12). IEEE, 3–13.

[32]

Kui Liu, Anil Koyuncu, Dongsun Kim, and Tegawendé F. Bissyandé. 2019. Tbar: Revisiting template-based automated program repair. In Proceedings of the 28th ACM SIGSOFT International Symposium on Software Testing and Analysis. 31–42.

Digital Library

[33]

Sanjaya Lohani, Thomas A. Searles, Brian T. Kirby, and Ryan T. Glasser. 2021. On the experimental feasibility of quantum state reconstruction via machine learning. IEEE Trans. Quant. Eng. 2 (2021), 1–10.

[34]

Fan Long and Martin Rinard. 2015. Staged program repair with condition synthesis. In Proceedings of the 10th Joint Meeting on Foundations of Software Engineering. 166–178.

Digital Library

[35]

Fan Long and Martin Rinard. 2016. Automatic patch generation by learning correct code. In Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 298–312.

Digital Library

[36]

Peixun Long and Jianjun Zhao. 2024. Testing multi-subroutine quantum programs: From unit testing to integration testing. ACM Trans. Softw. Eng. Methodol. Just Accepted (April 2024).

Digital Library

[37]

Joseph M. Lukens, Kody J. H. Law, Ajay Jasra, and Pavel Lougovski. 2020. A practical and efficient approach for Bayesian quantum state estimation. New J. Phys. 22, 6 (2020), 063038.

[38]

Junjie Luo, Pengzhan Zhao, Zhongtao Miao, Shuhan Lan, and Jianjun Zhao. 2022. A comprehensive study of bug fixes in quantum programs. In Proceedings of the IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER’22). IEEE, 1239–1246.

[39]

Junpeng Lv, Bei-Bei Yin, and Kai-Yuan Cai. 2014. On the asymptotic behavior of adaptive testing strategy for software reliability assessment. IEEE Trans. Softw. Eng. 40, 4 (2014), 396–412.

Digital Library

[40]

Sergey Mechtaev, Jooyong Yi, and Abhik Roychoudhury. 2016. Angelix: Scalable multiline program patch synthesis via symbolic analysis. In Proceedings of the 38th International Conference on Software Engineering. 691–701.

Digital Library

[41]

Eñaut Mendiluze, Shaukat Ali, Paolo Arcaini, and Tao Yue. 2021. Muskit: A mutation analysis tool for quantum software testing. In Proceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering (ASE’21). IEEE, 1266–1270.

Digital Library

[42]

Andriy Miranskyy and Lei Zhang. 2019. On testing quantum programs. In Proceedings of the IEEE/ACM 41st International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER’19). IEEE, 57–60.

Digital Library

[43]

Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information. Cambridge University Press.

Digital Library

[44]

Hanyu Pei, Beibei Yin, Linzhi Huang, and Kai-Yuan Cai. 2023. A dynamic random testing strategy in the context of cloud computing. Softw. Qual. J. 31, 1 (2023), 243–277.

Digital Library

[45]

Yu Pei, Carlo A. Furia, Martin Nordio, Yi Wei, Bertrand Meyer, and Andreas Zeller. 2014. Automated fixing of programs with contracts. IEEE Trans. Softw. Eng. 40, 5 (2014), 427–449.

Digital Library

[46]

Yu Pei, Yi Wei, Carlo A. Furia, Martin Nordio, and Bertrand Meyer. 2011. Code-based automated program fixing. In Proceedings of the 26th IEEE/ACZInternational Conference on Automated Software Engineering (ASE’11). IEEE, 392–395.

Digital Library

[47]

Mauro Pezzè and Michal Young. 2008. Software Testing and Analysis: Process, Principles, and Techniques. John Wiley & Sons.

Digital Library

[48]

Thomas Reps, Thomas Ball, Manuvir Das, and James Larus. 1997. The use of program profiling for software maintenance with applications to the year 2000 problem. In Proceedings of the 6th European Software Engineering Conference Held Jointly with the 5th ACM SIGSOFT International Symposium on Foundations of Software Engineering. 432–449.

Digital Library

[49]

Naoto Sato and Ryota Katsube. 2023. Locating buggy segments in quantum program debugging. arXiv:2309.04266. Retrieved from https://arxiv.org/abs/2309.04266

[50]

Chang-ai Sun, Hepeng Dai, Guan Wang, Dave Towey, Tsong Yueh Chen, and Kai-Yuan Cai. 2019. Dynamic random testing of web services: A methodology and evaluation. IEEE Trans. Serv. Comput. 15, 2 (2019), 736–751.

[51]

Jiyuan Wang, Fucheng Ma, and Yu Jiang. 2021. Poster: Fuzz testing of quantum program. In Proceedings of the 14th IEEE Conference on Software Testing, Verification and Validation (ICST’21). IEEE, 466–469.

[52]

Jiyuan Wang, Qian Zhang, Guoqing Harry Xu, and Miryung Kim. 2021. QDiff: Differential testing of quantum software stacks. In Proceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering (ASE’21). IEEE, 692–704.

Digital Library

[53]

Xinyi Wang, Paolo Arcaini, Tao Yue, and Shaukat Ali. 2021. Application of combinatorial testing to quantum programs. In Proceedings of the IEEE 21st International Conference on Software Quality, Reliability and Security (QRS’21). IEEE, 179–188.

[54]

Xinyi Wang, Paolo Arcaini, Tao Yue, and Shaukat Ali. 2022. QuSBT: Search-based testing of quantum programs. In Proceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion Proceedings. 173–177.

Digital Library

[55]

Xinyi Wang, Paolo Arcaini, Tao Yue, and Shaukat Ali. 2023. QuCAT: A Combinatorial Testing Tool for Quantum Software. In Proceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering (ASE’23). IEEE, 2066–2069.

[56]

Xinyi Wang, Tongxuan Yu, Paolo Arcaini, Tao Yue, and Shaukat Ali. 2022. Mutation-based test generation for quantum programs with multi-objective search. In Proceedings of the Genetic and Evolutionary Computation Conference. 1345–1353.

Digital Library

[57]

Zan Wang, Jian Gao, Xiang Chen, Hao-jie Fu, and Xiang-Yu Fan. 2018. Automatic program repair techniques: A survery. Chin. J. Comput. 41, 3 (2018), 588–610.

[58]

Yi Wei, Yu Pei, Carlo A. Furia, Lucas S. Silva, Stefan Buchholz, Bertrand Meyer, and Andreas Zeller. 2010. Automated fixing of programs with contracts. In Proceedings of the 19th International Symposium on Software Testing and Analysis. 61–72.

Digital Library

[59]

Westley Weimer, Zachary P. Fry, and Stephanie Forrest. 2013. Leveraging program equivalence for adaptive program repair: Models and first results. In Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering (ASE’13). IEEE, 356–366.

Digital Library

[60]

Westley Weimer, ThanhVu Nguyen, Claire Le Goues, and Stephanie Forrest. 2009. Automatically finding patches using genetic programming. In Proceedings of the IEEE 31st International Conference on Software Engineering. IEEE, 364–374.

Digital Library

[61]

Hongji Yang, Feng Chen, and Suleiman Aliyu. 2017. Modern software cybernetics: New trends. J. Syst. Softw. 124 (2017), 169–186.

Digital Library

[62]

Pengzhan Zhao, Zhongtao Miao, Shuhan Lan, and Jianjun Zhao. 2023. Bugs4Q: A benchmark of existing bugs to enable controlled testing and debugging studies for quantum programs. J. Syst. Softw. 205 (2023), 111805.

Digital Library

[63]

Pengzhan Zhao, Jianjun Zhao, and Lei Ma. 2021. Identifying bug patterns in quantum programs. In Proceedings of the IEEE/ACM 2nd International Workshop on Quantum Software Engineering (Q-SE’21). IEEE, 16–21.

[64]

Qihao Zhu, Zeyu Sun, Yuan-an Xiao, Wenjie Zhang, Kang Yuan, Yingfei Xiong, and Lu Zhang. 2021. A syntax-guided edit decoder for neural program repair. In Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 341–353.

Digital Library

Cited By

Yang HNong YZhang TLuo XCai H(2024)Learning to Detect and Localize Multilingual BugsProceedings of the ACM on Software Engineering10.1145/36608041:FSE(2190-2213)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660804
Gao XShen CJiang WLin CLi QWang QLi QGuan X(2024)Fairness in machine learning: definition, testing, debugging, and applicationScience China Information Sciences10.1007/s11432-023-4060-x67:9Online publication date: 15-Aug-2024
https://doi.org/10.1007/s11432-023-4060-x

Index Terms

Automatic Repair of Quantum Programs via Unitary Operation
1. Computer systems organization
  1. Architectures
    1. Other architectures
      1. Quantum computing
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging

Recommendations

Quantum computing via the Bethe ansatz

We recognize quantum circuit model of computation as factorisable scattering model and propose that a quantum computer is associated with a quantum many-body system solved by the Bethe ansatz. As an typical example to support our perspectives on quantum ...
Towards Higher-Level Abstractions for Quantum Computing
ACSW '22: Proceedings of the 2022 Australasian Computer Science Week

Quantum Computing (QC) has emerged as a field of ever-increasing activity as it promises to revolutionize computation and enable the solution of computational problems that we (realistically) cannot solve with Classical Computing to date. However, ...
Integrable quantum computation

Integrable quantum computation is defined as quantum computing via the integrable condition, in which two-qubit gates are either nontrivial unitary solutions of the Yang---Baxter equation or the Swap gate (permutation). To make the definition clear, in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Software Engineering and Methodology

ACM Transactions on Software Engineering and Methodology Volume 33, Issue 6

July 2024

951 pages

EISSN:1557-7392

DOI:10.1145/3613693

Editor:
Mauro Pezzé
USI Universitá della Svizzera italiana and SIT Schaffhausen Institute of Technology, Switzerland

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 28 June 2024

Online AM: 11 May 2024

Accepted: 11 April 2024

Revised: 28 March 2024

Received: 08 September 2023

Published in TOSEM Volume 33, Issue 6

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
212
Total Downloads

Downloads (Last 12 months)212
Downloads (Last 6 weeks)33

Reflects downloads up to 04 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yang HNong YZhang TLuo XCai H(2024)Learning to Detect and Localize Multilingual BugsProceedings of the ACM on Software Engineering10.1145/36608041:FSE(2190-2213)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660804
Gao XShen CJiang WLin CLi QWang QLi QGuan X(2024)Fairness in machine learning: definition, testing, debugging, and applicationScience China Information Sciences10.1007/s11432-023-4060-x67:9Online publication date: 15-Aug-2024
https://doi.org/10.1007/s11432-023-4060-x

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.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents