{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:11:33Z","timestamp":1760033493996,"version":"build-2065373602"},"reference-count":73,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","funder":[{"DOI":"10.13039\/501100001711","name":"SNSF","doi-asserted-by":"crossref","award":["207967"],"award-info":[{"award-number":["207967"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,10,9]]},"abstract":"<jats:p>Classical simulation of quantum circuits is critical for the development of implementations of quantum  \nalgorithms: it does not require access to specialized hardware, facilitates debugging by allowing direct access  \nto the quantum state, and is the only way to test on inputs that are too big for current NISQ computers.<\/jats:p>\n          <jats:p>Many quantum algorithms rely on invariants that result in sparsity in the state vector. A sparse state vector  \nsimulator only computes with non-zero amplitudes. For important classes of algorithms, this results in an  \nasymptotic improvement in simulation time. While promising prior work has investigated ways to exploit  \nsparsity, it is still unclear what is the best way to scale sparse simulation to modern multi-core architectures.<\/jats:p>\n          <jats:p>In this work, we address this challenge and present qblaze, a highly optimized sparse state vector simulator  \nbased on (i) a compact sorted array representation, and (ii) new, easily parallelizable and highly-scalable  \nalgorithms for all quantum operations. Our extensive experimental evaluation shows that qblaze is often  \norders-of-magnitude more efficient than prior sparse state vector simulators even on a single thread, and also  \nthat qblaze scales well to a large number of CPU cores.<\/jats:p>\n          <jats:p>Overall, our work enables testing quantum algorithms on input sizes that were previously out of reach.<\/jats:p>","DOI":"10.1145\/3763066","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:49:50Z","timestamp":1759999790000},"page":"444-470","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["qblaze: An Efficient and Scalable Sparse Quantum Simulator"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-5394-4340","authenticated-orcid":false,"given":"Hristo","family":"Venev","sequence":"first","affiliation":[{"name":"INSAIT, Sofia University St. Kliment Ohridski, Sofia, Bulgaria"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2320-9178","authenticated-orcid":false,"given":"Thien","family":"Udomsrirungruang","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, United Kingdom"},{"name":"INSAIT, Sofia University St. Kliment Ohridski, Sofia, Bulgaria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9393-0925","authenticated-orcid":false,"given":"Dimitar","family":"Dimitrov","sequence":"additional","affiliation":[{"name":"INSAIT, Sofia University St. Kliment Ohridski, Sofia, Bulgaria"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7470-0489","authenticated-orcid":false,"given":"Timon","family":"Gehr","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0054-9568","authenticated-orcid":false,"given":"Martin","family":"Vechev","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"},{"name":"INSAIT, Sofia University St. Kliment Ohridski, Sofia, Bulgaria"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/s43588-021-00119-7"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/DATE.2006.244176"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.83.5162"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_13"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.100.012305"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-01-13-220"},{"key":"e_1_2_1_8_1","volume-title":"Circuit for Shor\u2019s algorithm using 2n+3 qubits. Quantum Info. Comput., 3, 2","author":"Beauregard Stephane","year":"2003","unstructured":"Stephane Beauregard. 2003. Circuit for Shor\u2019s algorithm using 2n+3 qubits. Quantum Info. Comput., 3, 2 (2003), mar, 175\u2013185. issn:1533-7146"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.54.1034"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.05.025"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88702-7_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-006-0150-x"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1021\/acs.jctc.2c00574"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MC.2022.3217021"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1021\/acs.chemrev.8b00803"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/s0002-9904-1910-01892-9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-01-13-221"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-019-0648-8"},{"volume-title":"Introduction to algorithms (4 ed.)","author":"Cormen Thomas H.","key":"e_1_2_1_20_1","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2022. Introduction to algorithms (4 ed.). The MIT Press. isbn:978-0-262-04630-5"},{"key":"e_1_2_1_21_1","unstructured":"Steven A. Cuccaro Thomas G. Draper Samuel A. Kutin and David Petrie Moulton. 2004. A new quantum ripple-carry addition circuit. arxiv:quant-ph\/0410184."},{"key":"e_1_2_1_22_1","unstructured":"Thomas G. Draper. 2000. Addition on a quantum computer. arxiv:quant-ph\/0008033."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-020-01004-3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/s43588-021-00024-z"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep03023"},{"key":"e_1_2_1_26_1","volume-title":"International Reed-Muller Workshop.","author":"Goodman David","year":"2007","unstructured":"David Goodman, Mitchell A Thornton, David Y Feinstein, and D Michael Miller. 2007. Quantum logic circuit simulation based on the QMDD data structure. In International Reed-Muller Workshop."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.57.127"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevX.14.011009"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2021-03-15-410"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462177"},{"key":"e_1_2_1_31_1","volume-title":"QDD: A quantum computer emulation library. https:\/\/web.archive.org\/web\/20021210200357\/http:\/\/home.plutonium.net\/~dagreve\/qdd.html","author":"Greve David","year":"1999","unstructured":"David Greve. 1999. QDD: A quantum computer emulation library. https:\/\/web.archive.org\/web\/20021210200357\/http:\/\/home.plutonium.net\/~dagreve\/qdd.html"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. arxiv:quant-ph\/9605043.","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2022.3182628"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_2_1_35_1","volume-title":"Svore","author":"H\u00e4ner Thomas","year":"2017","unstructured":"Thomas H\u00e4ner, Martin Roetteler, and Krysta M. Svore. 2017. Factoring using 2n+2 qubits with Toffoli based modular multiplication. arxiv:1611.07995. arxiv:1611.07995"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3491248"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.95.050501"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0808245105"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.2172\/366453"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550488"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TQE.2024.3364546"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.273.5278.1073"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","unstructured":"Seth Lloyd Silvano Garnerone and Paolo Zanardi. 2015. Quantum algorithms for topological and geometric analysis of big data. arxiv:arXiv:1408.3106 [quant-ph]. https:\/\/doi.org\/10.48550\/arXiv.1408.3106 10.48550\/arXiv.1408.3106","DOI":"10.48550\/arXiv.1408.3106"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","unstructured":"Seth Lloyd Masoud Mohseni and Patrick Rebentrost. 2013. Quantum algorithms for supervised and unsupervised machine learning. arxiv:arXiv:1307.0411 [quant-ph]. https:\/\/doi.org\/10.48550\/arXiv.1307.0411 10.48550\/arXiv.1307.0411","DOI":"10.48550\/arXiv.1307.0411"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/050644756"},{"key":"e_1_2_1_46_1","unstructured":"Microsoft. 2020. Q# Language Specification. https:\/\/github.com\/microsoft\/qsharp-language\/tree\/main\/Specifications\/Language##q-language"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2006.35"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9480"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3547334"},{"key":"e_1_2_1_50_1","volume-title":"Chuang","author":"Nielsen Michael A.","year":"2010","unstructured":"Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press. isbn:978-1-139-49548-6"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38986-3_11"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/wcms.1481"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009894"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.130503"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-024-02411-5"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.74.022320"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539795293172"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3689760"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651157"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature12290"},{"key":"e_1_2_1_61_1","volume-title":"Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. 10, 3","author":"Den Nes Maarten Van","year":"2010","unstructured":"Maarten Van Den Nes. 2010. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. 10, 3 (2010), 258\u2013271. issn:1533-7146"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","unstructured":"Hristo Venev Thien Udomsrirungruang Dimitar Dimitrov Timon Gehr and Martin Vechev. 2025. Artifact for \"qblaze: An Efficient and Scalable Sparse Quantum Simulator\". https:\/\/doi.org\/10.5281\/zenodo.16929865 10.5281\/zenodo.16929865","DOI":"10.5281\/zenodo.16929865"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","unstructured":"Hristo Venev Thien Udomsrirungruang Dimitar Dimitrov Timon Gehr and Martin Vechev. 2025. Artifact for \"qblaze: An Efficient and Scalable Sparse Quantum Simulator\". https:\/\/doi.org\/10.5281\/zenodo.16925511 10.5281\/zenodo.16925511","DOI":"10.5281\/zenodo.16925511"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","unstructured":"F. Verstraete and J. I. Cirac. 2004. Renormalization algorithms for quantum-many body systems in two and higher dimensions. https:\/\/doi.org\/10.48550\/arXiv.cond-mat\/0407066 arXiv:cond-mat\/0407066 10.48550\/arXiv.cond-mat\/0407066","DOI":"10.48550\/arXiv.cond-mat\/0407066"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:QINP.0000022725.70000.4a"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.91.147902"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2023-09-11-1108"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.131.180601"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1093\/ietfec\/e91-a.2.584"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/QCE60285.2024.00132"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.96.170503"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD45719.2019.8942057"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2834427"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763066","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:44:39Z","timestamp":1760031879000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763066"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":73,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763066"],"URL":"https:\/\/doi.org\/10.1145\/3763066","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-03-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}