{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:15:44Z","timestamp":1762272944695,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,7,27]],"date-time":"2022-07-27T00:00:00Z","timestamp":1658880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council"},{"name":"European Union\u2019s Horizon 2020","award":["101001318"],"award-info":[{"award-number":["101001318"]}]},{"name":"Hightech Agenda Bayern Plus"},{"name":"BMK, BMDW"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Transactions on Quantum Computing"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>\n            Quantum computers promise to solve important problems faster than conventional computers ever could. Underneath is a fundamentally different computational primitive that introduces new challenges for the development of software tools that aid designers of corresponding quantum algorithms. The different computational primitives render classical simulation of quantum circuits particularly challenging. While the logic simulation of conventional circuits is comparatively simple with linear complexity with respect to the number of gates, quantum circuit simulation has to deal with the exponential memory requirements to represent quantum states on non-quantum hardware with respect to the number of qubits.\n            <jats:italic>Decision Diagrams<\/jats:italic>\n            \u00a0(DDs) address this challenge through exploitation of redundancies in matrices and vectors to provide significantly more compact representations in many cases. Moreover, the probabilistic nature of quantum computations enables another angle to tackle the complexity: Quantum algorithms are resistant to some degree against small inaccuracies in the quantum state as these only lead to small changes in the outcome probabilities. We propose to exploit this resistance against (small) errors to gain even more compact decision diagrams. In this work, we investigate the potential of approximation in quantum circuit simulation in detail. To this end, we first present four dedicated schemes that exploit the error resistance and efficiently approximate quantum states represented by decision diagrams. Subsequently, we propose two simulation strategies that utilize those approximations schemes in order to improve the efficiency of DD-based quantum circuit simulation, while, at the same time, allowing the user to control the resulting degradation in accuracy. We empirically show that the proposed approximation schemes reduce the size of decision diagrams substantially and also analytically prove the effect of multiple approximations on the attained accuracy. Eventually, this enables speed-ups of the resulting approximate quantum circuit simulation of up to several orders of magnitudes\u2014again, while controlling the fidelity of the result.\n          <\/jats:p>","DOI":"10.1145\/3530776","type":"journal-article","created":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T16:32:11Z","timestamp":1650904331000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Approximating Decision Diagrams for Quantum Circuit Simulation"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1089-3263","authenticated-orcid":false,"given":"Stefan","family":"Hillmich","sequence":"first","affiliation":[{"name":"Johannes Kepler University Linz, Linz, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2258-4118","authenticated-orcid":false,"given":"Alwin","family":"Zulehner","sequence":"additional","affiliation":[{"name":"Johannes Kepler University Linz, Linz, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8291-648X","authenticated-orcid":false,"given":"Richard","family":"Kueng","sequence":"additional","affiliation":[{"name":"Johannes Kepler University Linz, Linz, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3826-527X","authenticated-orcid":false,"given":"Igor L.","family":"Markov","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor MI, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4993-7860","authenticated-orcid":false,"given":"Robert","family":"Wille","sequence":"additional","affiliation":[{"name":"Technical University of Munich, Munich, Germany and Software Competence Centrum Hagenberg (SCCH), Austria"}]}],"member":"320","published-online":{"date-parts":[[2022,7,27]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"124","article-title":"Algorithms for quantum computation: Discrete logarithms and factoring","author":"Shor P. W.","year":"1994","unstructured":"P. W. Shor. 1994. Algorithms for quantum computation: Discrete logarithms and factoring. Foundations of Computer Science (1994), 124\u2013134.","journal-title":"Foundations of Computer Science"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1038\/npjqi.2015.23"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-08-06-79"},{"key":"e_1_3_2_5_2","article-title":"Quantum algorithm implementations for beginners","author":"Coles Patrick J.","year":"2018","unstructured":"Patrick J. Coles, Stephan Eidenbenz, Scott Pakin, Adetokunbo Adedoyin, John Ambrosiano, Petr Anisimov, William Casper, Gopinath Chennupati, Carleton Coffrin, Hristo Djidjev, et\u00a0al. 2018. Quantum algorithm implementations for beginners. arXiv:1804.03719 (2018).","journal-title":"arXiv:1804.03719"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-0980-2"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.126.190505"},{"key":"e_1_3_2_8_2","unstructured":"H\u00e9ctor Abraham et\u00a0al. 2019. Qiskit: An Open-source Framework for Quantum Computing. (2019)."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-019-47174-9"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-019-0196-1"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2244643"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRC.2016.7738703"},{"key":"e_1_3_2_13_2","doi-asserted-by":"crossref","unstructured":"Alwin Zulehner Alexandru Paler and Robert Wille. 2019. An efficient methodology for mapping quantum circuits to the IBM QX architectures. 38 7 (2019) 1226\u20131236.","DOI":"10.1109\/TCAD.2018.2846658"},{"key":"e_1_3_2_14_2","first-page":"320","volume-title":"Foundations of Computer Science","author":"Brakerski Zvika","year":"2018","unstructured":"Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. 2018. A cryptographic test of quantumness and certifiable randomness from a single quantum device. In Foundations of Computer Science. 320\u2013331."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-018-9872-3"},{"key":"e_1_3_2_16_2","article-title":"Advanced equivalence checking of quantum circuits","author":"Burgholzer Lukas","year":"2020","unstructured":"Lukas Burgholzer and Robert Wille. 2020. Advanced equivalence checking of quantum circuits. IEEE Trans. on CAD of Integrated Circuits and Systems (2020).","journal-title":"IEEE Trans. on CAD of Integrated Circuits and Systems"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/QCE49297.2020.00051"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/1823458"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2834427"},{"key":"e_1_3_2_20_2","first-page":"317","volume-title":"Design, Automation and Test in Europe","author":"Abdollahi Afshin","year":"2006","unstructured":"Afshin Abdollahi and Massoud Pedram. 2006. Analysis and synthesis of quantum circuits by using quantum decision diagrams. In Design, Automation and Test in Europe. 317\u2013322."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1093\/ietfec\/e91-a.2.584"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2459034"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD45719.2019.8942057"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18072.2020.9218591"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/ASP-DAC47756.2020.9045454"},{"key":"e_1_3_2_27_2","volume-title":"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 Design, Automation and Test in Europe."},{"key":"e_1_3_2_28_2","volume-title":"Quantum Computation and Quantum Information (10th Anniversary edition)","author":"Nielsen Michael A.","year":"2016","unstructured":"Michael A. Nielsen and Isaac L. Chuang. 2016. Quantum Computation and Quantum Information (10th Anniversary edition). Cambridge University Press."},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.1993.580054"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18072.2020.9218555"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781316848142"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-018-0124-x"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.2.030316"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3400302.3415746"},{"issue":"1","key":"e_1_3_2_35_2","first-page":"42","article-title":"GNU Parallel - The command-line power tool","volume":"36","author":"Tange O.","year":"2011","unstructured":"O. Tange. 2011. GNU Parallel - The command-line power tool; login: The USENIX Magazine 36, 1 (2011), 42\u201347.","journal-title":"login: The USENIX Magazine"},{"key":"e_1_3_2_36_2","first-page":"90","volume-title":"Design, Automation and Test in Europe","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 Design, Automation and Test in Europe. 90\u201395."}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530776","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3530776","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:25Z","timestamp":1750183765000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3530776"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,27]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3530776"],"URL":"https:\/\/doi.org\/10.1145\/3530776","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"type":"print","value":"2643-6809"},{"type":"electronic","value":"2643-6817"}],"subject":[],"published":{"date-parts":[[2022,7,27]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-04-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}