{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T22:47:46Z","timestamp":1784242066654,"version":"3.55.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>\n            With quantum computers promising advantages even in the near-term NISQ era, there is a lively community that develops software and toolkits for the design of corresponding quantum circuits. Although the underlying problems are different, expertise from the design automation community, which developed sophisticated design solutions for the conventional realm in the past decades, can help here. In this respect, decision diagrams provide a promising foundation for tackling many design tasks such as simulation, synthesis, and verification of quantum circuits. However, users of the corresponding tools often do not have a proper background or an intuition about how these methods based on decision diagrams work and what their strengths and limits are. In this work, we first review the concepts of how decision diagrams can be employed, e.g., for the simulation and verification of quantum circuits. Afterwards, in an effort to make decision diagrams for quantum computing more accessible, we then present a visualization tool for quantum decision diagrams, which allows users to explore the behavior of decision diagrams in the design tasks mentioned above. Finally, we present decision diagram-based tools for simulation and verification of quantum circuits using the methods discussed above as part of the open-source Munich Quantum Toolkit (MQT)\u2014a set of tools for quantum computing developed at the Technical University of Munich and the Johannes Kepler University Linz and released under the MIT license. More information about the corresponding tools is available at\n            <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"url\" xlink:href=\"https:\/\/github.com\/cda-tum\/ddsim\">https:\/\/github.com\/cda-tum\/ddsim<\/jats:ext-link>\n            . By this, we provide an introduction of the concepts and tools for potential users who would like to work with them as well as potential developers aiming to extend them.\n          <\/jats:p>","DOI":"10.1145\/3491246","type":"journal-article","created":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T20:54:09Z","timestamp":1645649649000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Tools for Quantum Computing Based on Decision Diagrams"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4993-7860","authenticated-orcid":false,"given":"Robert","family":"Wille","sequence":"first","affiliation":[{"name":"Johannes Kepler University Linz and Software Competence Center HagenbergGmbH (SCCH), Hagenberg, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1089-3263","authenticated-orcid":false,"given":"Stefan","family":"Hillmich","sequence":"additional","affiliation":[{"name":"Johannes Kepler University Linz, Linz, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4699-1316","authenticated-orcid":false,"given":"Lukas","family":"Burgholzer","sequence":"additional","affiliation":[{"name":"Johannes Kepler University Linz, Linz, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,30]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"317","volume-title":"Proceedings of the Design, Automation and Test in Europe Conference","year":"2006","unstructured":"Afshin Abdollahi and Massoud Pedram. 2006. Analysis and synthesis of quantum circuits by using quantum decision diagrams. In Proceedings of the Design, Automation and Test in Europe Conference. 317\u2013322."},{"key":"e_1_3_2_3_2","unstructured":"H\u00e9ctor Abraham et\u00a0al. 2019. Qiskit: An Open-source Framework for Quantum Computing. https:\/\/github.com\/Qiskit\/qiskit\/blob\/master\/Qiskit.bib."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_3_2_5_2","first-page":"188","volume-title":"Proceedings of the International Conference on CAD","year":"1993","unstructured":"R. Iris Bahar, Erica A. Frohm, Charles M. Gaona, Gary D. Hachtel, Enrico Macii, Abelardo Pardo, and Fabio Somenzi. 1993. Algebraic decision diagrams and their applications. In Proceedings of the International Conference on CAD. 188\u2013191."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-018-0124-x"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/136035.136043"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Lukas Burgholzer Hartwig Bauer and Robert Wille. 2021. Hybrid schr\u00f6dinger-feynman simulation of quantum circuits with decision diagrams arXiv:2105.07045. https:\/\/arxiv.org\/abs\/2105.07045.","DOI":"10.1109\/QCE52317.2021.00037"},{"key":"e_1_3_2_10_2","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference","author":"Burgholzer Lukas","year":"2021","unstructured":"Lukas Burgholzer, Richard Kueng, and Robert Wille. 2021. Random stimuli generation for the verification of quantum circuits. In Proceedings of the Asia and South Pacific Design Automation Conference."},{"key":"e_1_3_2_11_2","first-page":"356","volume-title":"Proceedings of the International Conference on Quantum Computing and Engineering","author":"Burgholzer Lukas","year":"2020","unstructured":"Lukas Burgholzer, Rudy Raymond, and Robert Wille. 2020. Verifying results of the IBM Qiskit quantum circuit compilation flow. In Proceedings of the International Conference on Quantum Computing and Engineering. 356\u2013365."},{"key":"e_1_3_2_12_2","first-page":"127","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference.","author":"Burgholzer Lukas","year":"2020","unstructured":"Lukas Burgholzer and Robert Wille. 2020. Improved DD-based equivalence checking of quantum circuits. In Proceedings of the Asia and South Pacific Design Automation Conference.127\u2013132."},{"key":"e_1_3_2_13_2","volume-title":"Proceedings of the Design Automation Conference.","author":"Burgholzer Lukas","year":"2020","unstructured":"Lukas Burgholzer and Robert Wille. 2020. The power of simulation for equivalence checking in quantum computing. In Proceedings of the Design Automation Conference."},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","DOI":"10.1109\/TCAD.2020.3032630","article-title":"Advanced equivalence checking for quantum circuits","author":"Burgholzer Lukas","year":"2021","unstructured":"Lukas Burgholzer and Robert Wille. 2021. Advanced equivalence checking for quantum circuits. IEEE Trans. CAD Integr. Circ. Syst. 40, 9 (2021), 1810\u20131824.","journal-title":"IEEE Trans. CAD Integr. Circ. Syst."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.simpa.2020.100051"},{"key":"e_1_3_2_16_2","article-title":"Open quantum assembly language","author":"Cross Andrew W.","year":"2017","unstructured":"Andrew W. Cross, Lev S. Bishop, John A. Smolin, and Jay M. Gambetta. 2017. Open quantum assembly language. arXiv:1707.03429. https:\/\/arxiv.org\/abs\/1707.03429.","journal-title":"arXiv:1707.03429"},{"key":"e_1_3_2_17_2","first-page":"415","volume-title":"Proceedings of the Design Automation Conference","year":"1994","unstructured":"Rolf Drechsler, Andisheh Sarabi, Michael Theobald, Bernd Becker, and Marek A. Perkowski. 1994. Efficient representation and manipulation of switching functions based on ordered kronecker functional decision diagrams. In Proceedings of the Design Automation Conference. 415\u2013419."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1002\/1097-024X(200009)30:11<1203::AID-SPE338>3.0.CO;2-N"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.324545"},{"key":"e_1_3_2_20_2","first-page":"212","volume-title":"Theory of Computing","author":"Grover Lov K.","year":"1996","unstructured":"Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In Theory of Computing. 212\u2013219."},{"key":"e_1_3_2_21_2","first-page":"176","volume-title":"Proceedings of the 50th IEEE International Symposium on Multiple-Valued Logic (ISMVL\u201920)","author":"Grurl Thomas","year":"2020","unstructured":"Thomas Grurl, J\u00fcrgen Fu\u00df, Stefan Hillmich, Lukas Burgholzer, and Robert Wille. 2020. Arrays vs. decision diagrams: A case study on quantum circuit simulators. In Proceedings of the 50th IEEE International Symposium on Multiple-Valued Logic (ISMVL\u201920). IEEE, 176\u2013181."},{"key":"e_1_3_2_22_2","volume-title":"Proceedings of the International Conference on CAD","author":"Grurl Thomas","year":"2020","unstructured":"Thomas Grurl, J\u00fcrgen Fu\u00df, and Robert Wille. 2020. Considering decoherence errors in the simulation of quantum circuits using decision diagrams. In Proceedings of the International Conference on CAD."},{"key":"e_1_3_2_23_2","volume-title":"Proceedings of the Design, Automation and Test in Europe","author":"Grurl Thomas","year":"2021","unstructured":"Thomas Grurl, Richard Kueng, J\u00fcrgen Fu\u00df, and Robert Wille. 2021. Stochastic quantum circuit simulation using decision diagrams. In Proceedings of the Design, Automation and Test in Europe."},{"key":"e_1_3_2_24_2","volume-title":"Proceedings of the Design, Automation and Test in Europe","author":"Hillmich Stefan","year":"2021","unstructured":"Stefan Hillmich, Richard Kueng, Igor L. Markov, and Robert Wille. 2021. As accurate as needed, as efficient as possible: Approximations in DD-based quantum circuit simulation. In Proceedings of the Design, Automation and Test in Europe."},{"key":"e_1_3_2_25_2","volume-title":"Proceedings of the Design Automation Conference.","author":"Hillmich Stefan","year":"2020","unstructured":"Stefan Hillmich, Igor L. Markov, and Robert Wille. 2020. Just like the real thing: Fast weak simulation of quantum computation. In Proceedings of the Design Automation Conference."},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","unstructured":"Xin Hong Yuan Feng Sanjiang Li and Mingsheng Ying. 2021. Equivalence checking of dynamic quantum circuits. arXiv:2106.01658 [quant-ph]. https:\/\/arxiv.org\/abs\/2106.01658.","DOI":"10.1145\/3508352.3549479"},{"key":"e_1_3_2_27_2","unstructured":"Xin Hong Xiangzhen Zhou Sanjiang Li Yuan Feng and Mingsheng Ying. 2020. A tensor network based decision diagram for representation of quantum circuits. arxiv:2009.02618 [quant-ph]. https:\/\/arxiv.org\/abs\/2009.02618."},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","DOI":"10.1142\/S0219749905001067","article-title":"\u201cNon-identity check\u201d is QMA-complete","author":"Janzing Dominik","year":"2005","unstructured":"Dominik Janzing, Pawel Wocjan, and Thomas Beth. 2005. \u201cNon-identity check\u201d is QMA-complete. Int. J. Quant. Inf. 3, 3 (2005), 463\u2013473.","journal-title":"Int. J. Quant. Inf."},{"key":"e_1_3_2_29_2","unstructured":"Lingling Lao Hans van Someren Imran Ashraf and Carmen G. Almudever. 2020. Timing and resource-aware mapping of quantum circuits to superconducting processors. arXiv:1908.04226 [quant-ph]. https:\/\/arxiv.org\/abs\/1908.04226."},{"key":"e_1_3_2_30_2","volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems","year":"2019","unstructured":"Atsushi Matsuo, Wakaki Hattori, and Shigeru Yamashita. 2019. Reducing the overhead of mapping quantum circuits to IBM Q system. In Proceedings of the IEEE International Symposium on Circuits and Systems (2019)."},{"key":"e_1_3_2_31_2","volume-title":"Proceedings of the International Symposium on Multi-Valued Logic","year":"2006","unstructured":"D. Michael Miller and Mitchell A. Thornton. 2006. QMDD: A decision diagram structure for reversible and quantum circuits. In Proceedings of the International Symposium on Multi-Valued Logic."},{"key":"e_1_3_2_32_2","first-page":"272","volume-title":"Proceedings of the Design Automation Conference","author":"Minato Shin-ichi","year":"1993","unstructured":"Shin-ichi Minato. 1993. Zero-suppressed BDDs for set manipulation in combinatorial problems. In Proceedings of the Design Automation Conference. 272\u2013277."},{"key":"e_1_3_2_33_2","first-page":"1015","volume-title":"Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems","author":"Murali Prakash","year":"2019","unstructured":"Prakash Murali, Jonathan M. Baker, Ali Javadi-Abhari, Frederic T. Chong, and Margaret Martonosi. 2019. Noise-adaptive compiler mappings for noisy intermediate-scale quantum computers. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems. 1015\u20131029."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"key":"e_1_3_2_35_2","first-page":"483","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference","author":"Niemann Philipp","year":"2014","unstructured":"Philipp Niemann, Robert Wille, and Rolf Drechsler. 2014. Efficient synthesis of quantum circuits implementing clifford group operations. In Proceedings of the Asia and South Pacific Design Automation Conference. 483\u2013488."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2459034"},{"key":"e_1_3_2_37_2","volume-title":"Quirk: Quantum Circuit Simulator","author":"authors Quirk","year":"2021","unstructured":"Quirk authors. 2021. Quirk: Quantum Circuit Simulator. Retrieved August 2, 2021 from https:\/\/algassert.com\/quirk."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_3_2_39_2","first-page":"73","article-title":"Quantum logic synthesis with formal verification","author":"Smith Kaitlin N.","year":"2019","unstructured":"Kaitlin N. Smith and Mitchell A. Thornton. 2019. Quantum logic synthesis with formal verification. IEEE Int. Midw. Symp. Circ. Syst. (2019), 73\u201376.","journal-title":"IEEE Int. Midw. Symp. Circ. Syst."},{"key":"e_1_3_2_40_2","first-page":"85","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference","year":"2012","unstructured":"Mathias Soeken, Robert Wille, Christoph Hilken, Nils Przigoda, and Rolf Drechsler. 2012. Synthesis of reversible circuits with minimal lines for large functions. In Proceedings of the Asia and South Pacific Design Automation Conference. 85\u201392."},{"key":"e_1_3_2_41_2","volume-title":"Proceedings of the International Conference on CAD","author":"Tan Bochen","year":"2020","unstructured":"Bochen Tan and Jason Cong. 2020. Optimal layout synthesis for quantum computing. In Proceedings of the International Conference on CAD."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:QINP.0000022725.70000.4a"},{"key":"e_1_3_2_43_2","unstructured":"Lieuwe Vinkhuijzen Tim Coopmans David Elkouss Vedran Dunjko and Alfons Laarman. 2021. LIMDD a decision diagram for simulation of quantum computing including stabilizer states. arXiv:2108.00931 [quant-ph]. Retrieved from https:\/\/arxiv.org\/abs\/2108.00931."},{"key":"e_1_3_2_44_2","first-page":"584","volume-title":"IEICE Trans. Fundam.","year":"2008","unstructured":"Shiou-An Wang, Chin-Yung Lu, I.-Ming Tsai, and Sy-Yen Kuo. 2008. An XQDD-based verification method for quantum circuits. In IEICE Trans. Fundam. 91, 2 (2008). 584\u2013594."},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719789"},{"key":"e_1_3_2_46_2","volume-title":"Proceedings of the Design Automation Conference","author":"Wille Robert","year":"2019","unstructured":"Robert Wille, Lukas Burgholzer, and Alwin Zulehner. 2019. Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations. In Proceedings of the Design Automation Conference (2019)."},{"key":"e_1_3_2_47_2","first-page":"220","volume-title":"Proceedings of the International Symposium on Multi-Valued Logic","year":"2008","unstructured":"Robert Wille, Daniel Gro\u00dfe, Lisa Teuber, Gerhard W. Dueck, and Rolf Drechsler. 2008. RevLib: An online resource for reversible functions and reversible circuits. In Proceedings of the International Symposium on Multi-Valued Logic. 220\u2013225."},{"key":"e_1_3_2_48_2","volume-title":"Proceedings of the International Conference on CAD","author":"Wille Robert","year":"2020","unstructured":"Robert Wille, Stefan Hillmich, and Lukas Burgholzer. 2020. JKQ: JKU tools for quantum computing. In Proceedings of the International Conference on CAD."},{"key":"e_1_3_2_49_2","unstructured":"Han-Sen Zhong et\u00a0al. [n.d.]. Quantum computational advantage using photons. arXiv:2012.01625. https:\/\/arxiv.org\/abs\/2012.01625."},{"key":"e_1_3_2_50_2","first-page":"121","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference.","author":"Zulehner Alwin","year":"2020","unstructured":"Alwin Zulehner, Stefan Hillmich, Igor L. Markov, and Robert Wille. 2020. Approximation of quantum states using decision diagrams. In Proceedings of the Asia and South Pacific Design Automation Conference.121\u2013126."},{"key":"e_1_3_2_51_2","volume-title":"Proceedings of the International Conference on CAD","author":"Zulehner Alwin","year":"2019","unstructured":"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 CAD."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2846658"},{"issue":"5","key":"e_1_3_2_53_2","first-page":"996","article-title":"One-pass design of reversible circuits: Combining embedding and synthesis for reversible logic","volume":"37","author":"Zulehner Alwin","year":"2018","unstructured":"Alwin Zulehner and Robert Wille. 2018. One-pass design of reversible circuits: Combining embedding and synthesis for reversible logic. IEEE Trans. CAD Integr. Circ. Syst. 37, 5 (2018), 996\u20131008.","journal-title":"IEEE Trans. CAD Integr. Circ. Syst."},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2834427"},{"key":"e_1_3_2_55_2","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1145\/3287624.3287704","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference.","author":"Zulehner Alwin","year":"2019","unstructured":"Alwin Zulehner and Robert Wille. 2019. Compiling SU(4) quantum circuits to IBM QX architectures. In Proceedings of the Asia and South Pacific Design Automation Conference.185\u2013190."},{"key":"e_1_3_2_56_2","volume-title":"Proceedings of the Design, Automation and Test in Europe Conference","author":"Zulehner Alwin","year":"2019","unstructured":"Alwin Zulehner and Robert Wille. 2019. Matrix-vector vs. matrix-matrix multiplication: Potential in DD-based simulation of quantum computations. In Proceedings of the Design, Automation and Test in Europe Conference."}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491246","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3491246","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:19Z","timestamp":1750183759000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3491246"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3491246"],"URL":"https:\/\/doi.org\/10.1145\/3491246","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}