{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T17:39:42Z","timestamp":1779385182034,"version":"3.53.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T00:00:00Z","timestamp":1726617600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61832015"],"award-info":[{"award-number":["61832015"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2024,11,30]]},"abstract":"<jats:p>Quantum circuit testing is essential for detecting potential faults in realistic quantum devices, while the testing process itself also suffers from the inexactness and unreliability of quantum operations. This article alleviates the issue by proposing a novel framework of automatic test pattern generation (ATPG) for robust testing of logical quantum circuits. We introduce the stabilizer projector decomposition (SPD) for representing the quantum test pattern and construct the test application (i.e., state preparation and measurement) using Clifford-only circuits, which are rather robust and efficient as evidenced in the fault-tolerant quantum computation. However, it is generally hard to generate SPDs due to the exponentially growing number of the stabilizer projectors. To circumvent this difficulty, we develop an SPD generation algorithm, as well as several acceleration techniques that can exploit both locality and sparsity in generating SPDs. The effectiveness of our algorithms are validated by (1) theoretical guarantees under reasonable conditions and (2) experimental results on commonly used benchmark circuits, such as Quantum Fourier Transform (QFT), Quantum Volume (QV), and Bernstein-Vazirani (BV) in IBM Qiskit.<\/jats:p>","DOI":"10.1145\/3689333","type":"journal-article","created":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T11:20:25Z","timestamp":1724152825000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Automatic Test Pattern Generation for Robust Quantum Circuit Testing"],"prefix":"10.1145","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0772-6635","authenticated-orcid":false,"given":"Kean","family":"Chen","sequence":"first","affiliation":[{"name":"Institute of Software, Chinese Academy of Sciences and University of Chinese Academy of Sciences, Beijing, China and Department of Computer and Information Science, University of Pennsylvania, Philadelphia, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4847-702X","authenticated-orcid":false,"given":"Mingsheng","family":"Ying","sequence":"additional","affiliation":[{"name":"Centre for Quantum Software and Information, University of Technology Sydney, Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,9,18]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Qiskit. [n. d.]. https:\/\/qiskit.org"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.177901"},{"issue":"6","key":"e_1_3_3_5_2","doi-asserted-by":"crossref","first-page":"062337","DOI":"10.1103\/PhysRevA.95.062337","article-title":"Unbiased simulation of near-clifford quantum circuits","volume":"95","author":"Bennink Ryan S.","year":"2017","unstructured":"Ryan S. Bennink, Erik M. Ferragut, Travis S. Humble, Jason A. Laska, James J. Nutaro, Mark G. Pleszkoch, and Raphael C. Pooser. 2017. Unbiased simulation of near-clifford quantum circuits. Physical Review A 95, 6 (2017), 062337.","journal-title":"Physical Review A"},{"issue":"3","key":"e_1_3_3_6_2","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1109\/TCAD.2017.2717783","article-title":"Detection and diagnosis of single faults in quantum circuits","volume":"37","author":"Bera Debajyoti","year":"2017","unstructured":"Debajyoti Bera. 2017. Detection and diagnosis of single faults in quantum circuits. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems 37, 3 (2017), 587\u2013600.","journal-title":"IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300921"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"e_1_3_3_9_2","article-title":"Clifford circuit optimization with templates and symbolic Pauli gates","author":"Bravyi Sergey","year":"2021","unstructured":"Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov. 2021. Clifford circuit optimization with templates and symbolic Pauli gates. arXiv preprint arXiv:2105.02291 (2021).","journal-title":"arXiv preprint arXiv:2105.02291"},{"key":"e_1_3_3_10_2","article-title":"Towards verification of dynamic quantum circuits","author":"Burgholzer Lukas","year":"2021","unstructured":"Lukas Burgholzer and Robert Wille. 2021. Towards verification of dynamic quantum circuits. arXiv preprint arXiv:2106.01099 (2021).","journal-title":"arXiv preprint arXiv:2106.01099"},{"issue":"10","key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"100501","DOI":"10.1103\/PhysRevLett.127.100501","article-title":"Exploiting dynamic quantum circuits in a quantum algorithm with superconducting qubits","volume":"127","author":"C\u00f3rcoles Antonio D.","year":"2021","unstructured":"Antonio D. C\u00f3rcoles, Maika Takita, Ken Inoue, Scott Lekuch, Zlatko K. Minev, Jerry M. Chow, and Jay M. Gambetta. 2021. Exploiting dynamic quantum circuits in a quantum algorithm with superconducting qubits. Physical Review Letters 127, 10 (2021), 100501.","journal-title":"Physical Review Letters"},{"issue":"83","key":"e_1_3_3_12_2","first-page":"1","article-title":"CVXPY: A python-embedded modeling language for convex optimization","volume":"17","author":"Diamond Steven","year":"2016","unstructured":"Steven Diamond and Stephen Boyd. 2016. CVXPY: A python-embedded modeling language for convex optimization. Journal of Machine Learning Research 17, 83 (2016), 1\u20135.","journal-title":"Journal of Machine Learning Research"},{"issue":"10","key":"e_1_3_3_13_2","doi-asserted-by":"crossref","first-page":"S347","DOI":"10.1088\/1464-4266\/7\/10\/021","article-title":"Scalable noise estimation with random unitary operators","volume":"7","author":"Emerson Joseph","year":"2005","unstructured":"Joseph Emerson, Robert Alicki, and Karol \u017byczkowski. 2005. Scalable noise estimation with random unitary operators. Journal of Optics B: Quantum and Semiclassical Optics 7, 10 (2005), S347.","journal-title":"Journal of Optics B: Quantum and Semiclassical Optics"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.86.032324"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.80.052312"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.71.062310"},{"key":"e_1_3_3_17_2","article-title":"The Heisenberg representation of quantum computers","author":"Gottesman Daniel","year":"1998","unstructured":"Daniel Gottesman. 1998. The Heisenberg representation of quantum computers. arXiv preprint quant-ph\/9807006 (1998).","journal-title":"arXiv preprint quant-ph\/9807006"},{"issue":"12","key":"e_1_3_3_18_2","doi-asserted-by":"crossref","first-page":"122107","DOI":"10.1063\/1.2393152","article-title":"Hudson\u2019s theorem for finite-dimensional quantum systems","volume":"47","author":"Gross David","year":"2006","unstructured":"David Gross. 2006. Hudson\u2019s theorem for finite-dimensional quantum systems. Journal of Mathematical Physics 47, 12 (2006), 122107.","journal-title":"Journal of Mathematical Physics"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"issue":"8","key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"080504","DOI":"10.1103\/PhysRevLett.122.080504","article-title":"Fault-tolerant logical gates in the IBM quantum experience","volume":"122","author":"Harper Robin","year":"2019","unstructured":"Robin Harper and Steven T. Flammia. 2019. Fault-tolerant logical gates in the IBM quantum experience. Physical Review Letters 122, 8 (2019), 080504.","journal-title":"Physical Review Letters"},{"issue":"12","key":"e_1_3_3_21_2","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1038\/s41567-020-0992-8","article-title":"Efficient learning of quantum noise","volume":"16","author":"Harper Robin","year":"2020","unstructured":"Robin Harper, Steven T. Flammia, and Joel J. Wallman. 2020. Efficient learning of quantum noise. Nature Physics 16, 12 (2020), 1184\u20131188.","journal-title":"Nature Physics"},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","unstructured":"Nicholas C. Harris Yangjin Ma Jacob Mower Tom Baehr-Jones Dirk Englund Michael Hochberg and Christophe Galland. 2014. Efficient compact and low loss thermo-optic phase shifter in silicon. Optics Express 22 9 (2014).","DOI":"10.1364\/OE.22.010487"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/ATS.2004.84"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01007479"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(73)90028-6"},{"issue":"4","key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/s10836-009-5109-3","article-title":"Adaptive debug and diagnosis without fault dictionaries","volume":"25","author":"Holst Stefan","year":"2009","unstructured":"Stefan Holst and Hans-Joachim Wunderlich. 2009. Adaptive debug and diagnosis without fault dictionaries. Journal of Electronic Testing 25, 4 (2009), 259\u2013268.","journal-title":"Journal of Electronic Testing"},{"issue":"9","key":"e_1_3_3_28_2","doi-asserted-by":"crossref","first-page":"090501","DOI":"10.1103\/PhysRevLett.118.090501","article-title":"Application of a resource theory for magic states to fault-tolerant quantum computing","volume":"118","author":"Howard Mark","year":"2017","unstructured":"Mark Howard and Earl Campbell. 2017. Application of a resource theory for magic states to fault-tolerant quantum computing. Physical Review Letters 118, 9 (2017), 090501.","journal-title":"Physical Review Letters"},{"issue":"20","key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"200401","DOI":"10.1103\/PhysRevLett.96.200401","article-title":"Identification and distance measures of measurement apparatus","volume":"96","author":"Ji Zhengfeng","year":"2006","unstructured":"Zhengfeng Ji, Yuan Feng, Runyao Duan, and Mingsheng Ying. 2006. Identification and distance measures of measurement apparatus. Physical Review Letters 96, 20 (2006), 200401.","journal-title":"Physical Review Letters"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-006-0145-1"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.106.180504"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/0317052"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aab822"},{"key":"e_1_3_3_34_2","unstructured":"Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum computation and quantum information. Cambridge university press."},{"key":"e_1_3_3_35_2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1109\/ASPDAC.2012.6164942","volume-title":"17th Asia and South Pacific Design Automation Conference","author":"Paler Alexandru","year":"2012","unstructured":"Alexandru Paler, Ilia Polian, and John P. Hayes. 2012. Detection and diagnosis of faulty quantum circuits. In 17th Asia and South Pacific Design Automation Conference. IEEE, 181\u2013186."},{"issue":"7","key":"e_1_3_3_36_2","doi-asserted-by":"crossref","first-page":"070501","DOI":"10.1103\/PhysRevLett.115.070501","article-title":"Estimating outcome probabilities of quantum circuits using quasiprobabilities","volume":"115","author":"Pashayan Hakop","year":"2015","unstructured":"Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. 2015. Estimating outcome probabilities of quantum circuits using quasiprobabilities. Physical Review Letters 115, 7 (2015), 070501.","journal-title":"Physical Review Letters"},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","unstructured":"Emanuele Pelucchi Giorgos Fagas Igor Aharonovich Dirk Englund Eden Figueroa Qihuang Gong H\u00fcbel Hannes Jin Liu Chao-Yang Lu Nobuyuki Matsuda Jian-Wei Pan Florian Schreck Fabio Sciarrino Christine Silberhorn Jianwei Wang and K. J\u00f6ns. 2022. The potential and global outlook of integrated photonics for quantum technologies. Nature Reviews Physics 4 3 (2022) 194\u2013208.","DOI":"10.1038\/s42254-021-00398-z"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-022-04721-1"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-08-05-170"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1147\/rd.104.0278"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41566-019-0532-1"},{"key":"e_1_3_3_43_2","volume-title":"VLSI Test Principles and Architectures: Design for Testability","author":"Wang Laung-Terng","year":"2006","unstructured":"Laung-Terng Wang, Cheng-Wen Wu, and Xiaoqing Wen. 2006. VLSI Test Principles and Architectures: Design for Testability. Elsevier."},{"key":"e_1_3_3_44_2","article-title":"Equivalence checking of sequential quantum circuits","author":"Wang Qisheng","year":"2021","unstructured":"Qisheng Wang, Riling Li, and Mingsheng Ying. 2021. Equivalence checking of sequential quantum circuits. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems (2021).","journal-title":"IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.62.052316"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689333","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689333","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:45Z","timestamp":1750291545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689333"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,18]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,11,30]]}},"alternative-id":["10.1145\/3689333"],"URL":"https:\/\/doi.org\/10.1145\/3689333","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,18]]},"assertion":[{"value":"2023-08-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}