More Web Proxy on the site http://driver.im/

research-article

Open access

An Automata-Based Framework for Verification and Bug Hunting in Quantum Circuits

Authors:

Ondřej Lengál,

Di-De YenAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 7, Issue PLDI

Article No.: 156, Pages 1218 - 1243

https://doi.org/10.1145/3591270

Published: 06 June 2023 Publication History

Abstract

We introduce a new paradigm for analysing and finding bugs in quantum circuits. In our approach, the problem is given by a ‍triple {P} C {Q} and the question is whether, given a set P of quantum states on the input of a circuit C, the set of quantum states on the output is equal to (or included in) a set Q. While this is not suitable to specify, e.g., functional correctness of a quantum circuit, it is sufficient to detect many bugs in quantum circuits. We propose a technique based on tree automata to compactly represent sets of quantum states and develop transformers to implement the semantics of quantum gates over this representation. Our technique computes with an algebraic representation of quantum states, avoiding the inaccuracy of working with floating-point numbers. We implemented the proposed approach in a prototype tool and evaluated its performance against various benchmarks from the literature. The evaluation shows that our approach is quite scalable, e.g., we managed to verify a large circuit with 40 qubits and 141,527 gates, or catch bugs injected into a circuit with 320 qubits and 1,758 gates, where all tools we compared with failed. In addition, our work establishes a connection between quantum program verification and automata, opening new possibilities to exploit the richness of automata theory and automata-based verification in the world of quantum computing.

References

[1]

2022. GMP: The GNU Multiple Precision Arithmetic Library. https://gmplib.org/

[2]

2022. The repository: Issue #200 (ZX-Checker produces invalid result). https://github.com/cda-tum/qcec/issues/200

[3]

Parosh Aziz Abdulla, Ahmed Bouajjani, Lukás Holík, Lisa Kaati, and Tomás Vojnar. 2008. Computing Simulations over Tree Automata. In Tools and Algorithms for the Construction and Analysis of Systems, 14th International Conference, TACAS 2008, Budapest, Hungary, March 29-April 6, 2008. Proceedings, C. R. Ramakrishnan and Jakob Rehof (Eds.) (LNCS, Vol. 4963). Springer, 93–108. https://doi.org/10.1007/978-3-540-78800-3_8

[4]

Parosh Aziz Abdulla, Johanna Högberg, and Lisa Kaati. 2007. Bisimulation Minimization of Tree Automata. Int. J. Found. Comput. Sci., 18, 4 (2007), 699–713. https://doi.org/10.1142/S0129054107004929

[5]

Parosh Aziz Abdulla, Bengt Jonsson, Pritha Mahata, and Julien d’Orso. 2002. Regular Tree Model Checking. In Computer Aided Verification, 14th International Conference, CAV 2002,Copenhagen, Denmark, July 27-31, 2002, Proceedings (LNCS, Vol. 2404). Springer, 555–568. https://doi.org/10.1007/3-540-45657-0_47

[6]

Dorit Aharonov. 2003. A Simple Proof that Toffoli and Hadamard are Quantum Universal. https://doi.org/10.48550/arxiv.quant-ph/0301040

[7]

Thorsten Altenkirch and Jonathan Grattage. 2005. A Functional Quantum Programming Language. In 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 26-29 June 2005, Chicago, IL, USA, Proceedings. IEEE Computer Society, 249–258. https://doi.org/10.1109/LICS.2005.1

Digital Library

[8]

Matthew Amy. 2018. Towards Large-scale Functional Verification of Universal Quantum Circuits. In Proceedings 15th International Conference on Quantum Physics and Logic, QPL 2018, Halifax, Canada, 3-7th June 2018, Peter Selinger and Giulio Chiribella (Eds.) (EPTCS, Vol. 287). 1–21. https://doi.org/10.4204/EPTCS.287.1

[9]

Matthew Amy. 2019. Formal Methods in Quantum Circuit Design. Ph. D. Dissertation. University of Waterloo.

[10]

MD SAJID ANIS, Abby-Mitchell, and Héctor Abraham. 2021. Qiskit: An Open-source Framework for Quantum Computing. https://doi.org/10.5281/zenodo.2573505

[11]

Linda Anticoli, Carla Piazza, Leonardo Taglialegne, and Paolo Zuliani. 2016. Towards Quantum Programs Verification: From Quipper Circuits to QPMC. In Reversible Computation - 8th International Conference, RC 2016, Bologna, Italy, July 7-8, 2016, Proceedings, Simon J. Devitt and Ivan Lanese (Eds.) (LNCS, Vol. 9720). Springer, 213–219. https://doi.org/10.1007/978-3-319-40578-0_16

[12]

Frank Arute. 2019. Quantum supremacy using a programmable superconducting processor. Nature, 574, 7779 (2019), Oct., 505–510. issn:1476-4687 https://doi.org/10.1038/s41586-019-1666-5 Number: 7779 Publisher: Nature Publishing Group

[13]

Ethan Bernstein and Umesh V. Vazirani. 1993. Quantum complexity theory. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal (Eds.). ACM, 11–20. https://doi.org/10.1145/167088.167097

Digital Library

[14]

Jacob D. Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. 2017. Quantum machine learning. Nature, 549, 7671 (2017), 195–202. https://doi.org/10.1038/nature23474

[15]

Ahmed Bouajjani, Peter Habermehl, Adam Rogalewicz, and Tomáš Vojnar. 2012. Abstract regular (tree) model checking. International Journal on Software Tools for Technology Transfer, 14, 2 (2012), 167–191. https://doi.org/10.1007/s10009-011-0205-y

[16]

Ahmed Bouajjani, Bengt Jonsson, Marcus Nilsson, and Tayssir Touili. 2000. Regular Model Checking. In Computer Aided Verification, 12th International Conference, CAV 2000, Chicago, IL, USA, July 15-19, 2000, Proceedings, E. Allen Emerson and A. Prasad Sistla (Eds.) (LNCS, Vol. 1855). Springer, 403–418. https://doi.org/10.1007/10722167_31

[17]

P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani P. Roychowdhury, and Farrokh Vatan. 2000. A new universal and fault-tolerant quantum basis. Inf. Process. Lett., 75, 3 (2000), 101–107. https://doi.org/10.1016/S0020-0190(00)00084-3

Digital Library

[18]

Randal E. Bryant. 1986. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Trans. Computers, 35, 8 (1986), 677–691. https://doi.org/10.1109/TC.1986.1676819

Digital Library

[19]

Lukas Burgholzer, Richard Kueng, and Robert Wille. 2021. Random Stimuli Generation for the Verification of Quantum Circuits. In ASPDAC ’21: 26th Asia and South Pacific Design Automation Conference, Tokyo, Japan, January 18-21, 2021. ACM, 767–772. https://doi.org/10.1145/3394885.3431590

Digital Library

[20]

Lukas Burgholzer and Robert Wille. 2020. Advanced equivalence checking for quantum circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 40, 9 (2020), 1810–1824. https://doi.org/10.1109/TCAD.2020.3032630

[21]

Doron Bustan and Orna Grumberg. 2003. Simulation-based minimazation. ACM Trans. Comput. Log., 4, 2 (2003), 181–206. https://doi.org/10.1145/635499.635502

Digital Library

[22]

Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik. 2019. Quantum Chemistry in the Age of Quantum Computing. Chemical Reviews, 119, 19 (2019), 10856–10915. https://doi.org/10.1021/acs.chemrev.8b00803 arxiv:https://doi.org/10.1021/acs.chemrev.8b00803. 31469277

[23]

Christophe Chareton, Sébastien Bardin, François Bobot, Valentin Perrelle, and Benoît Valiron. 2021. An Automated Deductive Verification Framework for Circuit-Building Quantum Programs. In ESOP, Nobuko Yoshida (Ed.) (LNCS, Vol. 12648). Springer International Publishing, Cham. 148–177. https://doi.org/10.1007/978-3-030-72019-3_6

Digital Library

[24]

Tian-Fu Chen, Jie-Hong R. Jiang, and Min-Hsiu Hsieh. 2022. Partial Equivalence Checking of Quantum Circuits. In 2022 IEEE International Conference on Quantum Computing and Engineering (QCE). 594–604. https://doi.org/10.1109/QCE53715.2022.00082

[25]

Yu-Fang Chen, Kai-Min Chung, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai, and Di-De Yen. 2023. An Automata-based Framework for Verification and Bug Hunting in Quantum Circuits. https://doi.org/10.5281/zenodo.7811406

Digital Library

[26]

Yu-Fang Chen, Kai-Min Chung, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai, and Di-De Yen. 2023. An Automata-based Framework for Verification and Bug Hunting in Quantum Circuits (Technical Report). arxiv:2301.07747.

[27]

Yu-Fang Chen, Chih-Duo Hong, Anthony W Lin, and Philipp Rümmer. 2017. Learning to prove safety over parameterised concurrent systems. In 2017 Formal Methods in Computer Aided Design (FMCAD). 76–83. https://doi.org/10.23919/FMCAD.2017.8102244

[28]

Yu-Fang Chen, Chiao Hsieh, Ondřej Lengál, Tsung-Ju Lii, Ming-Hsien Tsai, Bow-Yaw Wang, and Farn Wang. 2016. PAC learning-based verification and model synthesis. In Proceedings of the 38th International Conference on Software Engineering. 714–724. https://doi.org/10.1145/2884781.2884860

Digital Library

[29]

Yu-Fang Chen, Ondřej Lengál, Tony Tan, and Zhilin Wu. 2017. Register automata with linear arithmetic. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). 1–12. https://doi.org/10.1109/LICS.2017.8005111

[30]

Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig. 2018. Quantum Machine Learning: A Classical Perspective. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474, 2209 (2018), January, https://doi.org/10.1098/rspa.2017.0551

[31]

Bob Coecke and Ross Duncan. 2011. Interacting quantum observables: categorical algebra and diagrammatics. New Journal of Physics, 13, 4 (2011), apr, 043016. https://doi.org/10.1088/1367-2630/13/4/043016

[32]

Hubert Comon, Max Dauchet, Rémi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, and Marc Tommasi. 2008. Tree automata techniques and applications.

[33]

Patrick Cousot and Radhia Cousot. 1977. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. In Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977, Robert M. Graham, Michael A. Harrison, and Ravi Sethi (Eds.). ACM, 238–252. https://doi.org/10.1145/512950.512973

Digital Library

[34]

Loris D’Antoni, Margus Veanes, Benjamin Livshits, and David Molnar. 2015. Fast: A Transducer-Based Language for Tree Manipulation. ACM Trans. Program. Lang. Syst., 38, 1 (2015), 1:1–1:32. https://doi.org/10.1145/2791292

Digital Library

[35]

Christopher M. Dawson and Michael A. Nielsen. 2006. The Solovay-Kitaev algorithm. Quantum Inf. Comput., 6, 1 (2006), 81–95. https://doi.org/10.26421/QIC6.1-6

[36]

Loris D’Antoni and Margus Veanes. 2017. The power of symbolic automata and transducers. In International Conference on Computer Aided Verification. 47–67. https://doi.org/10.1007/978-3-319-63387-9_3

[37]

Mark Ettinger, Peter Høyer, and Emanuel Knill. 2004. The quantum query complexity of the hidden subgroup problem is polynomial. Inf. Process. Lett., 91, 1 (2004), 43–48. https://doi.org/10.1016/j.ipl.2004.01.024

Digital Library

[38]

Andrew Fagan and Ross Duncan. 2019. Optimising Clifford Circuits with Quantomatic. Electronic Proceedings in Theoretical Computer Science, 287 (2019), jan, 85–105. https://doi.org/10.4204/eptcs.287.5

[39]

Eric Felt, Gary York, Robert K. Brayton, and Alberto L. Sangiovanni-Vincentelli. 1993. Dynamic variable reordering for BDD minimization. In Proceedings of the European Design Automation Conference 1993, EURO-DAC ’93 with EURO-VHDL’93, Hamburg, Germany, September 20-24, 1993. IEEE Computer Society, 130–135. https://doi.org/10.1109/EURDAC.1993.410627

[40]

Yuan Feng, Ernst Moritz Hahn, Andrea Turrini, and Shenggang Ying. 2017. Model checking omega-regular properties for quantum Markov chains. In 28th International Conference on Concurrency Theory (CONCUR 2017). https://doi.org/10.4230/LIPIcs.CONCUR.2017.35

[41]

Yuan Feng, Ernst Moritz Hahn, Andrea Turrini, and Lijun Zhang. 2015. QPMC: A Model Checker for Quantum Programs and Protocols. In International Symposium on Formal Methods, Nikolaj Bjørner and Frank de Boer (Eds.). Springer International Publishing, 265–272. https://doi.org/10.1007/978-3-319-19249-9_17

[42]

Yuan Feng and Mingsheng Ying. 2021. Quantum Hoare logic with classical variables. ACM Transactions on Quantum Computing, 2, 4 (2021), 1–43. https://doi.org/10.1145/3456877

Digital Library

[43]

Yuan Feng, Nengkun Yu, and Mingsheng Ying. 2013. Model checking quantum Markov chains. J. Comput. Syst. Sci., 79, 7 (2013), 1181–1198. https://doi.org/10.1016/j.jcss.2013.04.002

[44]

Alexander S. Green, Peter LeFanu Lumsdaine, Neil J. Ross, Peter Selinger, and Benoît Valiron. 2013. Quipper: a scalable quantum programming language. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, Seattle, WA, USA, June 16-19, 2013, Hans-Juergen Boehm and Cormac Flanagan (Eds.). ACM, 333–342. https://doi.org/10.1145/2491956.2462177

Digital Library

[45]

Lov K. Grover. 1996. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996, Gary L. Miller (Ed.). ACM, 212–219. https://doi.org/10.1145/237814.237866

Digital Library

[46]

Wakaki Hattori and Shigeru Yamashita. 2018. Quantum Circuit Optimization by Changing the Gate Order for 2D Nearest Neighbor Architectures. In Reversible Computation - 10th International Conference, RC 2018, Leicester, UK, September 12-14, 2018, Proceedings, Jarkko Kari and Irek Ulidowski (Eds.) (LNCS, Vol. 11106). Springer, 228–243. https://doi.org/10.1007/978-3-319-99498-7_16

[47]

Matthias Heizmann, Yu-Fang Chen, Daniel Dietsch, Marius Greitschus, Jochen Hoenicke, Yong Li, Alexander Nutz, Betim Musa, Christian Schilling, and Tanja Schindler. 2018. Ultimate Automizer and the search for perfect interpolants. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 447–451. https://doi.org/10.1007/978-3-319-89963-3_30

[48]

Kesha Hietala, Robert Rand, Shih-Han Hung, Xiaodi Wu, and Michael Hicks. 2019. Verified optimization in a quantum intermediate representation. arXiv preprint arXiv:1904.06319.

[49]

Toshinari Itoko, Rudy Raymond, Takashi Imamichi, and Atsushi Matsuo. 2020. Optimization of quantum circuit mapping using gate transformation and commutation. Integr., 70 (2020), 43–50. https://doi.org/10.1016/j.vlsi.2019.10.004

Digital Library

[50]

Dominik Janzing, Pawel Wocjan, and Thomas Beth. 2005. "Non-Identity-Check" Is QMA-complete. International Journal of Quantum Information, 03, 03 (2005), 463–473. https://doi.org/10.1142/S0219749905001067

[51]

Ondřej Lengál, Jiří Šimáček, and Tomáš Vojnar. 2012. VATA: A library for efficient manipulation of non-deterministic tree automata. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems. 79–94. https://doi.org/10.1007/978-3-642-28756-5_7

Digital Library

[52]

Junyi Liu, Bohua Zhan, Shuling Wang, Shenggang Ying, Tao Liu, Yangjia Li, Mingsheng Ying, and Naijun Zhan. 2019. Formal verification of quantum algorithms using quantum Hoare logic. In International conference on computer aided verification. 187–207. https://doi.org/10.1007/978-3-030-25543-5_12

[53]

Vsevolod Livinskii, Dmitry Babokin, and John Regehr. 2020. Random testing for C and C++ compilers with YARPGen. Proc. ACM Program. Lang., 4, OOPSLA (2020), 196:1–196:25. https://doi.org/10.1145/3428264

Digital Library

[54]

Paul Massey, John A. Clark, and Susan Stepney. 2005. Evolution of a human-competitive quantum fourier transform algorithm using genetic programming. In Genetic and Evolutionary Computation Conference, GECCO 2005, Proceedings, Washington DC, USA, June 25-29, 2005, Hans-Georg Beyer and Una-May O’Reilly (Eds.). ACM, 1657–1663. https://doi.org/10.1145/1068009.1068288

Digital Library

[55]

Paulo Mateus, Jaime Ramos, Amílcar Sernadas, and Cristina Sernadas. 2009. Temporal Logics for Reasoning about Quantum Systems. Cambridge University Press, 389–413. https://doi.org/10.1017/CBO9781139193313.011

[56]

Nikolaj Moll, Panagiotis Barkoutsos, Lev S Bishop, Jerry M Chow, Andrew Cross, Daniel J Egger, Stefan Filipp, Andreas Fuhrer, Jay M Gambetta, Marc Ganzhorn, Abhinav Kandala, Antonio Mezzacapo, Peter Müller, Walter Riess, Gian Salis, John Smolin, Ivano Tavernelli, and Kristan Temme. 2018. Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology, 3, 3 (2018), jun, 030503. https://doi.org/10.1088/2058-9565/aab822

[57]

Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov. 2018. Automated optimization of large quantum circuits with continuous parameters. npj Quantum Information, 4 (2018), https://doi.org/10.1038/s41534-018-0072-4

[58]

Daniel Neider and Nils Jansen. 2013. Regular Model Checking Using Solver Technologies and Automata Learning. In NASA Formal Methods, 5th International Symposium, NFM 2013, Moffett Field, CA, USA, May 14-16, 2013. Proceedings, Guillaume Brat, Neha Rungta, and Arnaud Venet (Eds.) (LNCS, Vol. 7871). Springer, 16–31. https://doi.org/10.1007/978-3-642-38088-4_2

[59]

Michael A. Nielsen and Isaac L. Chuang. 2011. Quantum Computation and Quantum Information: 10th Anniversary Edition (10th ed.). Cambridge University Press, USA. isbn:978-1-10-700217-3

Digital Library

[60]

Philipp Niemann, Robert Wille, D. Michael Miller, Mitchell A. Thornton, and Rolf Drechsler. 2016. QMDDs: Efficient Quantum Function Representation and Manipulation. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 35, 1 (2016), 86–99. https://doi.org/10.1109/TCAD.2015.2459034

Digital Library

[61]

Edwin Pednault, John A. Gunnels, Giacomo Nannicini, Lior Horesh, Thomas Magerlein, Edgar Solomonik, Erik W. Draeger, Eric T. Holland, and Robert Wisnieff. 2017. Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral. CoRR, abs/1710.05867 (2017), arxiv:1710.05867

[62]

Tom Peham, Lukas Burgholzer, and Robert Wille. 2022. Equivalence checking paradigms in quantum circuit design: a case study. In DAC ’22: 59th ACM/IEEE Design Automation Conference, San Francisco, California, USA, July 10 - 14, 2022, Rob Oshana (Ed.). ACM, 517–522. https://doi.org/10.1145/3489517.3530480

Digital Library

[63]

Simon Perdrix. 2008. Quantum entanglement analysis based on abstract interpretation. In International Static Analysis Symposium. 270–282. https://doi.org/10.1007/978-3-540-69166-2_18

Digital Library

[64]

Vasilis Samoladas. 2008. Improved BDD Algorithms for the Simulation of Quantum Circuits. In Algorithms - ESA 2008, 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings, Dan Halperin and Kurt Mehlhorn (Eds.) (LNCS, Vol. 5193). Springer, 720–731. https://doi.org/10.1007/978-3-540-87744-8_60

Digital Library

[65]

Peter W. Shor. 1994. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994. IEEE Computer Society, 124–134. https://doi.org/10.1109/SFCS.1994.365700

Digital Library

[66]

Mathias Soeken, Robert Wille, Gerhard W. Dueck, and Rolf Drechsler. 2010. Window optimization of reversible and quantum circuits. In 13th IEEE International Symposium on Design and Diagnostics of Electronic Circuits and Systems, DDECS 2010, Vienna, Austria, April 14-16, 2010. IEEE Computer Society, 341–345. https://doi.org/10.1109/DDECS.2010.5491754

[67]

Lee Spector. 2006. Automatic Quantum Computer Programming: A Genetic Programming Approach.

[68]

Yuan-Hung Tsai, Jie-Hong R. Jiang, and Chiao-Shan Jhang. 2021. Bit-Slicing the Hilbert Space: Scaling Up Accurate Quantum Circuit Simulation. In 58th ACM/IEEE Design Automation Conference, DAC 2021, San Francisco, CA, USA, December 5-9, 2021. IEEE, 439–444. https://doi.org/10.1109/DAC18074.2021.9586191

Digital Library

[69]

Dominique Unruh. 2019. Quantum Hoare logic with ghost variables. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). 1–13. https://doi.org/10.1109/LICS.2019.8785779

[70]

George F. Viamontes, Igor L. Markov, and John P. Hayes. 2007. Checking equivalence of quantum circuits and states. In 2007 International Conference on Computer-Aided Design, ICCAD 2007, San Jose, CA, USA, November 5-8, 2007, Georges G. E. Gielen (Ed.). IEEE Computer Society, 69–74. https://doi.org/10.1109/ICCAD.2007.4397246

[71]

George F. Viamontes, Igor L. Markov, and John P. Hayes. 2009. Quantum Circuit Simulation. Springer. isbn:978-90-481-3064-1 https://doi.org/10.1007/978-90-481-3065-8

[72]

Dave Wecker and Krysta M. Svore. 2014. LIQUiěrt > : A Software Design Architecture and Domain-Specific Language for Quantum Computing. CoRR, abs/1402.4467 (2014), arXiv:1402.4467. arxiv:1402.4467

[73]

Chun-Yu Wei, Yuan-Hung Tsai, Chiao-Shan Jhang, and Jie-Hong R. Jiang. 2022. Accurate BDD-based unitary operator manipulation for scalable and robust quantum circuit verification. In DAC ’22: 59th ACM/IEEE Design Automation Conference, San Francisco, California, USA, July 10 - 14, 2022, Rob Oshana (Ed.). ACM, 523–528. https://doi.org/10.1145/3489517.3530481

Digital Library

[74]

R. Wille, D. Groß e, L. Teuber, G. W. Dueck, and R. Drechsler. 2008. RevLib: An Online Resource for Reversible Functions and Reversible Circuits. In Int’l Symp. on Multi-Valued Logic. 220–225. https://doi.org/10.1109/ISMVL.2008.43 RevLib is available at http://www.revlib.org

Digital Library

[75]

Robert Wille, Rod Van Meter, and Yehuda Naveh. 2019. IBM’s Qiskit Tool Chain: Working with and Developing for Real Quantum Computers. In Design, Automation & Test in Europe Conference & Exhibition, DATE 2019, Florence, Italy, March 25-29, 2019, Jürgen Teich and Franco Fummi (Eds.). IEEE, 1234–1240. https://doi.org/10.23919/DATE.2019.8715261

[76]

Ming Xu, Jianling Fu, Jingyi Mei, and Yuxin Deng. 2022. Model checking QCTL plus on quantum Markov chains. Theor. Comput. Sci., 913 (2022), 43–72. https://doi.org/10.1016/j.tcs.2022.01.044

Digital Library

[77]

Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, and Umut A Acar. 2022. Quartz: superoptimization of Quantum circuits. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 625–640. https://doi.org/10.1145/3519939.3523433

Digital Library

[78]

Shigeru Yamashita and Igor L. Markov. 2010. Fast equivalence-checking for quantum circuits. Quantum Inf. Comput., 10, 9&10 (2010), 721–734. https://doi.org/10.26421/QIC10.9-10-1

[79]

Peng Yan, Hanru Jiang, and Nengkun Yu. 2022. On incorrectness logic for Quantum programs. Proceedings of the ACM on Programming Languages, 6, OOPSLA1 (2022), 1–28. https://doi.org/10.1145/3527316

Digital Library

[80]

Mingsheng Ying. 2012. Floyd-Hoare logic for quantum programs. ACM Transactions on Programming Languages and Systems (TOPLAS), 33, 6 (2012), 1–49. https://doi.org/10.1145/2049706.2049708

Digital Library

[81]

Mingsheng Ying. 2021. Model Checking for Verification of Quantum Circuits. In International Symposium on Formal Methods. 23–39. https://doi.org/10.1007/978-3-030-90870-6_2

Digital Library

[82]

Mingsheng Ying and Yuan Feng. 2021. Model Checking Quantum Systems: Principles and Algorithms. Cambridge University Press.

[83]

Mingsheng Ying, Yangjia Li, Nengkun Yu, and Yuan Feng. 2014. Model-checking linear-time properties of quantum systems. ACM Transactions on Computational Logic (TOCL), 15, 3 (2014), 1–31. https://doi.org/10.1145/2629680

Digital Library

[84]

Fang Yu, Tevfik Bultan, Marco Cova, and Oscar H Ibarra. 2008. Symbolic string verification: An automata-based approach. In International SPIN Workshop on Model Checking of Software. 306–324. https://doi.org/10.1007/978-3-540-85114-1_21

Digital Library

[85]

Fang Yu, Tevfik Bultan, and Oscar H. Ibarra. 2011. Relational String Verification Using Multi-Track Automata. Int. J. Found. Comput. Sci., 22, 8 (2011), 1909–1924. https://doi.org/10.1142/S0129054111009112

[86]

Nengkun Yu and Jens Palsberg. 2021. Quantum abstract interpretation. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 542–558. https://doi.org/10.1145/3453483.3454061

Digital Library

[87]

Li Zhou, Nengkun Yu, and Mingsheng Ying. 2019. An applied quantum Hoare logic. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. 1149–1162. https://doi.org/10.1145/3314221.3314584

Digital Library

[88]

Alwin Zulehner, Stefan Hillmich, and Robert Wille. 2019. How to Efficiently Handle Complex Values? Implementing Decision Diagrams for Quantum Computing. In Proceedings of the International Conference on Computer-Aided Design, ICCAD 2019, Westminster, CO, USA, November 4-7, 2019, David Z. Pan (Ed.). ACM, 1–7. https://doi.org/10.1109/ICCAD45719.2019.8942057

[89]

Alwin Zulehner and Robert Wille. 2019. Advanced Simulation of Quantum Computations. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 38, 5 (2019), 848–859. https://doi.org/10.1109/TCAD.2018.2834427

Cited By

Abdulla PChen YChen YHolík LLengál OLin JLo FTsai W(2025)Verifying Quantum Circuits with Level-Synchronized Tree AutomataProceedings of the ACM on Programming Languages10.1145/37048689:POPL(923-953)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704868
Gemeinhardt FKlikovits SWimmer M(2025)GeQuPI: Quantum Program Improvement with Multi-Objective Genetic ProgrammingJournal of Systems and Software10.1016/j.jss.2024.112223219(112223)Online publication date: Jan-2025
https://doi.org/10.1016/j.jss.2024.112223
Fang WYing M(2024)Symbolic Execution for Quantum Error Correction ProgramsProceedings of the ACM on Programming Languages10.1145/36564198:PLDI(1040-1065)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656419
Show More Cited By

Index Terms

An Automata-Based Framework for Verification and Bug Hunting in Quantum Circuits

Recommendations

Verifying Quantum Circuits with Level-Synchronized Tree Automata

We present a new method for the verification of quantum circuits based on a novel symbolic representation of sets of quantum states using level-synchronized tree automata (LSTAs). LSTAs extend classical tree automata by labeling each transition with a ...
An XQDD-Based Verification Method for Quantum Circuits

Synthesis of quantum circuits is essential for building quantum computers. It is important to verify that the circuits designed perform the correct functions. In this paper, we propose an algorithm which can be used to verify the quantum circuits ...
Automatic translation of quantum circuits to optimized one-way quantum computation patterns

One-way quantum computation (1WQC) is a model of universal quantum computations in which a specific highly entangled state called a cluster state (or graph state) allows for quantum computation by only single-qubit measurements. The needed computations ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 7, Issue PLDI

June 2023

2020 pages

EISSN:2475-1421

DOI:10.1145/3554310

Editor:
Michael Hicks
Amazon, USA

Issue’s Table of Contents

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2023

Published in PACMPL Volume 7, Issue PLDI

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
1,159
Total Downloads

Downloads (Last 12 months)590
Downloads (Last 6 weeks)71

Reflects downloads up to 29 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abdulla PChen YChen YHolík LLengál OLin JLo FTsai W(2025)Verifying Quantum Circuits with Level-Synchronized Tree AutomataProceedings of the ACM on Programming Languages10.1145/37048689:POPL(923-953)Online publication date: 9-Jan-2025
https://dl.acm.org/doi/10.1145/3704868
Gemeinhardt FKlikovits SWimmer M(2025)GeQuPI: Quantum Program Improvement with Multi-Objective Genetic ProgrammingJournal of Systems and Software10.1016/j.jss.2024.112223219(112223)Online publication date: Jan-2025
https://doi.org/10.1016/j.jss.2024.112223
Fang WYing M(2024)Symbolic Execution for Quantum Error Correction ProgramsProceedings of the ACM on Programming Languages10.1145/36564198:PLDI(1040-1065)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656419
Deng HTao RPeng YWu X(2024)A Case for Synthesis of Recursive Quantum Unitary ProgramsProceedings of the ACM on Programming Languages10.1145/36329018:POPL(1759-1788)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632901
Tan SXiang DLu LLu JJiang QChen MYin JTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)MorphQPV: Exploiting Isomorphism in Quantum Programs to Facilitate Confident VerificationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651360(671-688)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651360
Lewis MZuliani PSoudjani S(2024)Automated Verification of Silq Quantum Programs using SMT Solvers2024 IEEE International Conference on Quantum Software (QSW)10.1109/QSW62656.2024.00027(125-134)Online publication date: 7-Jul-2024
https://doi.org/10.1109/QSW62656.2024.00027
De Stefano MPecorelli FDi Nucci DPalomba FDe Lucia A(2024)The quantum frontier of software engineeringInformation and Software Technology10.1016/j.infsof.2024.107525175:COnline publication date: 18-Nov-2024
https://dl.acm.org/doi/10.1016/j.infsof.2024.107525
(2024)ReferencesFoundations of Quantum Programming10.1016/B978-0-44-315942-8.00030-7(435-447)Online publication date: 2024
https://doi.org/10.1016/B978-0-44-315942-8.00030-7
Ying M(2024)Analysis of quantum programsFoundations of Quantum Programming10.1016/B978-0-44-315942-8.00019-8(169-230)Online publication date: 2024
https://doi.org/10.1016/B978-0-44-315942-8.00019-8
Mei JMartens JLaarman A(2024)Disentangling the Gap Between Quantum and #SATTheoretical Aspects of Computing – ICTAC 202410.1007/978-3-031-77019-7_2(17-40)Online publication date: 25-Nov-2024
https://dl.acm.org/doi/10.1007/978-3-031-77019-7_2
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Figures

Tables

Media

View Issue’s Table of Contents