{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T20:30:51Z","timestamp":1792787451886,"version":"4.5.0"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:00:00Z","timestamp":1780876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"National Science Foundation","award":["CCF-2239484"],"award-info":[{"award-number":["CCF-2239484"]}]},{"name":"Amazon","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}],"id":[{"id":"https:\/\/ror.org\/04mv4n011","id-type":"ROR","asserted-by":"crossref"}]},{"name":"VMware","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}],"id":[{"id":"https:\/\/ror.org\/01mwmh458","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Defense Advanced Research Projects Agency","award":["N66001-21-C-4018"],"award-info":[{"award-number":["N66001-21-C-4018"]}],"id":[{"id":"https:\/\/ror.org\/02caytj08","id-type":"ROR","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["CCF-2124080"],"award-info":[{"award-number":["CCF-2124080"]}]},{"name":"National Science Foundation","award":["CNS-2052947"],"award-info":[{"award-number":["CNS-2052947"]}]},{"name":"National Science Foundation","award":["DMS-2231533"],"award-info":[{"award-number":["DMS-2231533"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,6,8]]},"abstract":"<jats:p>\n                    Optimizing a quantum circuit is hard because it requires exploring a vast space of functionally equivalent circuits, produced by applying local circuit rewrites such as gate cancellation and commutation. Each additional rewrite can exponentially expand the space of equivalent circuits, so existing optimizers can only explore a tiny fraction of this space and often produce suboptimal results. We present\n                    <jats:sc>Quasar<\/jats:sc>\n                    , a new quantum circuit optimizer that can generate a\n                    <jats:italic toggle=\"yes\">step-limited optimal<\/jats:italic>\n                    circuit: given a bound on rewrite iterations, it returns the lowest-cost circuit reachable within that bound. To achieve this,\n                    <jats:sc>Quasar<\/jats:sc>\n                    constructs two complementary e-graphs for the quantum circuit\u2019s graph and sequence representations.\n                    <jats:sc>Quasar<\/jats:sc>\n                    then infers an atomic rewrite set for application on both e-graphs, which improves optimization performance by orders of magnitude. Finally,\n                    <jats:sc>Quasar<\/jats:sc>\n                    employs a series of new optimization techniques to ensure both soundness and scalability of equality saturation on quantum circuits. Across standard benchmarks,\n                    <jats:sc>Quasar<\/jats:sc>\n                    achieves geometric-mean reductions of 20.2% in 2-qubit gate count, 33.5% in total gate count, and 24.2% in circuit depth, and a 21.4% fidelity improvement over unoptimized circuits, outperforming or matching state-of-the-art rewrite-based optimizers on 75%, 92%, 62%, and 80% of circuits, respectively.\n                  <\/jats:p>","DOI":"10.1145\/3808254","type":"journal-article","created":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T18:04:09Z","timestamp":1780941849000},"page":"174-199","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Equality Saturation for Quantum Circuit Optimization"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-5703-2582","authenticated-orcid":false,"given":"Ganxiang","family":"Yang","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-7282-9358","authenticated-orcid":false,"given":"Paige","family":"Raun","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3733-5168","authenticated-orcid":false,"given":"Runzhou","family":"Tao","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6812-6182","authenticated-orcid":false,"given":"Ronghui","family":"Gu","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"},{"name":"CertiK, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,8]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1038\/s43588-025-00942-2"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-025-07047-7"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","unstructured":"G. Aleksandrowicz T. Alexander P. Barkoutsos L. Bello Y. Ben-Haim D. Bucher F. J. Cabrera-Hern\u00e1ndez J. Carballo-Franquis A. Chen C. Chen J. M. Chow A. D. C\u00f3rcoles-Gonzales A. J. Cross A. Cross J. Cruz-Benito C. Culver S. D. L. P. Gonz\u00e1lez E. D. L. Torre D. Ding E. Dumitrescu I. Duran P. Eendebak M. Everitt I. F. Sertage A. Frisch A. Fuhrer J. Gambetta B. G. Gago J. Gomez-Mosquera D. Greenberg I. Hamamura V. Havlicek J. Hellmers H. Horii T. Imamichi A. Javadi-Abhari N. Kanazawa A. Karazeev K. Krsulich P. Liu Y. Luh M. Marques F. J. Mart\u00edn-Fern\u00e1ndez D. T. McClure D. McKay A. Mezzacapo N. Moll D. M. Rodr\u00edguez G. Nannicini P. Nation P. Ollitrault L. J. O\u2019Riordan J. P\u00e9rez A. Phan M. Pistoia V. Prutyanov M. Reuter J. Rice R. H. P. Rudy C. Schnabel E. Schoute Y. Siraichi J. A. Smolin M. Soeken H. Takahashi I. Tavernelli C. Taylor P. Taylour M. Treinish W. Turner D. Vogt-Lee C. Vuillot J. A. Wildstrom J. Wilson E. Winston C. Wood S. Wood S. W\u00f6rner I. Y. Akhalwaya and C. Zoufal. 2019. Qiskit: an open-source framework for quantum computing. (2019). doi: 10.5281\/zenodo.2562110","DOI":"10.5281\/zenodo.2562110"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab9359"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3511715"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi David Gosset and Robert K\u00f6nig. 2018. Quantum advantage with shallow circuits. Science 362 6412 (Oct. 2018) 308\u2013311. doi: 10.1126\/science.aar3106","DOI":"10.1126\/science.aar3106"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3669940.3707262"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640392"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037754"},{"key":"e_1_3_1_12_2","unstructured":"D. Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. arXiv:quant-ph\/0201067 [quantph] https:\/\/arxiv.org\/abs\/quant-ph\/0201067"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.100.032328"},{"key":"e_1_3_1_14_2","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 [quant-ph] https:\/\/arxiv.org\/abs\/quant-ph\/0410184"},{"key":"e_1_3_1_15_2","unstructured":"Christopher M. Dawson and Michael A. Nielsen. 2005. The Solovay-Kitaev algorithm. arXiv:quant-ph\/0505030 [quantph] https:\/\/arxiv.org\/abs\/quant-ph\/0505030"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73595-3_13"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1066100.1066102"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","unstructured":"Cirq Developers. 2025. Cirq. doi: 10.5281\/zenodo.16867504","DOI":"10.5281\/zenodo.16867504"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/micro.2018.00072"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/isca45697.2020.00054"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322228"},{"key":"e_1_3_1_22_2","unstructured":"Eddie Farhi. 2017. Quantum supremacy through the quantum approximate optimization algorithm. In APS March Meeting Abstracts Vol. 2017. A19\u2013004."},{"key":"e_1_3_1_23_2","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 [quant-ph] https:\/\/arxiv.org\/abs\/1411.4028"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","unstructured":"John Forrest Ted Ralphs Stefan Vigerske Haroldo Gambini Santos John Forrest Lou Hafer Bjarni Kristjansson jpfasano Edwin Straver Jan-Willem Miles Lubin rlougee a andre jpgoncal1 Samuel Brito h-i gassmann Cristina Matthew Saltzman tosttost Bruno Pitrus Fumiaki MATSUSHIMA Patrick Vossler Ron @ SWGY and to st. 2024. coin-or\/Cbc: Release releases\/2.10.12. doi: 10.5281\/zenodo.13347261","DOI":"10.5281\/zenodo.13347261"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","unstructured":"Amir Kafshdar Goharshady Chun Kit Lam and Lionel Parreaux. 2024. Fast and Optimal Extraction for Sparse Equality Graphs. Proc. ACM Program. Lang. 8 OOPSLA2 Article 361 (Oct. 2024) 27 pages. doi: 10.1145\/3689801","DOI":"10.1145\/3689801"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","unstructured":"Amar Hadzihasanovic Kang Feng Ng and Quanlong Wang. 2018. Two complete axiomatisations of pure-state qubit quantum computing. In Proceedings of the 33rd annual ACM\/IEEE symposium on logic in computer science. 502\u2013511. doi: 10.1145\/3209108.3209128","DOI":"10.1145\/3209108.3209128"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3428201"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434318"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","unstructured":"Emmanuel Jeandel Simon Perdrix and Renaud Vilmart. 2018. A complete axiomatisation of the ZX-calculus for Clifford+ T quantum mechanics. In Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science. 559\u2013568. doi: 10.1145\/3209108.3209131","DOI":"10.1145\/3209108.3209131"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3341301.3359630"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.4204\/eptcs.318.14"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","unstructured":"Adrian Lehmann Ben Caldwell Bhakti Shah and Robert Rand. 2024. VyZX: Formal Verification of a Graphical Quantum Language. doi: 10.1145\/3807780","DOI":"10.1145\/3807780"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/MC.1980.1653748"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3649831"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1103\/physrevlett.95.030505"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/cgo51591.2021.9370310"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","unstructured":"Zhengyang Liu Stefan Mada and John Regehr. 2024. Minotaur: A SIMD-Oriented Synthesizing Superoptimizer. Proc. ACM Program. Lang. 8 OOPSLA2 Article 326 (Oct. 2024) 25 pages. doi: 10.1145\/3689766","DOI":"10.1145\/3689766"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/36206.36194"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/18\/2\/023023"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41534-018-0072-4"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1093\/imamat\/25.3.241"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485496"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/909447"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.5555\/1972505"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737959"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","unstructured":"Tirthak Patel Ed Younis Costin Iancu Wibe de Jong and Devesh Tiwari. 2022. Quest: systematically approximating quantum circuits for higher output fidelity. In Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 514\u2013528. doi: 10.1145\/3503222.3507739","DOI":"10.1145\/3503222.3507739"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/qce57702.2023.00087"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms5213"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-08-06-79"},{"key":"e_1_3_1_50_2","unstructured":"Raimondas Sasnauskas Yang Chen Peter Collingbourne Jeroen Ketema Gratian Lup Jubi Taneja and John Regehr. 2018. Souper: A Synthesizing Superoptimizer. arXiv:1711.04422 [cs.PL] https:\/\/arxiv.org\/abs\/1711.04422"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/2451116.2451150"},{"key":"e_1_3_1_52_2","unstructured":"Yunong Shi Runzhou Tao Xupeng Li Ali Javadi-Abhari Andrew W Cross Frederic T Chong and Ronghui Gu. 2019. Certiq: a mostly-automated verification of a realistic quantum compiler. arXiv preprint arXiv:1908.08963 (2019)."},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/ab8e92"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","unstructured":"Gus Henry Smith Andrew Liu Steven Lyubomirsky Scott Davidson Joseph McMahan Michael Taylor Luis Ceze and Zachary Tatlock. 2021. Pure tensor program rewriting via access patterns (representation pearl). In Proceedings of the 5th ACM SIGPLAN International Symposium on Machine Programming. 21\u201331. doi: 10.1145\/3460945.3464953","DOI":"10.1145\/3460945.3464953"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_59"},{"key":"e_1_3_1_56_2","volume-title":"Equality saturation: engineering challenges and applications","author":"Stepp Michael Benjamin","year":"2011","unstructured":"Michael Benjamin Stepp. 2011. Equality saturation: engineering challenges and applications. University of California, San Diego."},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","unstructured":"Runzhou Tao Yunong Shi Jianan Yao John Hui Frederic T Chong and Ronghui Gu. 2021. Gleipnir: Toward practical error analysis for quantum programs. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 48\u201364. doi: 10.1145\/3453483.3454029","DOI":"10.1145\/3453483.3454029"},{"key":"e_1_3_1_58_2","doi-asserted-by":"publisher","unstructured":"Runzhou Tao Yunong Shi Jianan Yao Xupeng Li Ali Javadi-Abhari Andrew W Cross Frederic T Chong and Ronghui Gu. 2022. Giallar: Push-button verification for the Qiskit quantum compiler. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation. 641\u2013656. doi: 10.1145\/3519939.3523431","DOI":"10.1145\/3519939.3523431"},{"key":"e_1_3_1_59_2","unstructured":"Runzhou Tao Hongzheng Zhu Jason Nieh Jianan Yao and Ronghui Gu. 2025. Quantum virtual machines. In 19th USENIX Symposium on Operating Systems Design and Implementation (OSDI 25). 411\u2013428."},{"key":"e_1_3_1_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/1594834.1480915"},{"key":"e_1_3_1_61_2","doi-asserted-by":"crossref","unstructured":"Aleksei Tiurin Chris Barrett Dan R. Ghica and Nick Hu. 2025. Equivalence Hypergraphs: DPO Rewriting for Monoidal E-Graphs. arXiv:2406.15882 [cs.LO] https:\/\/arxiv.org\/abs\/2406.15882","DOI":"10.1109\/LICS65433.2025.00023"},{"key":"e_1_3_1_62_2","doi-asserted-by":"publisher","DOI":"10.1145\/3763062"},{"key":"e_1_3_1_63_2","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407799"},{"key":"e_1_3_1_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/ismvl.2008.43"},{"key":"e_1_3_1_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434304"},{"key":"e_1_3_1_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/hpca51647.2021.00023"},{"key":"e_1_3_1_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3591254"},{"key":"e_1_3_1_68_2","doi-asserted-by":"publisher","unstructured":"Amanda Xu Abtin Molavi Swamit Tannu and Aws Albarghouthi. 2025. Optimizing quantum circuits fast and slow. In Proceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems Volume 1. 777\u2013793. doi: 10.1145\/3669940.3707240","DOI":"10.1145\/3669940.3707240"},{"key":"e_1_3_1_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519939.3523433"},{"key":"e_1_3_1_70_2","doi-asserted-by":"publisher","unstructured":"Ganxiang Yang Paige Raun Runzhou Tao and Ronghui Gu. 2026. Equality Saturation for Quantum Circuit Optimization (Artifact). doi: 10.5281\/zenodo.19571754","DOI":"10.5281\/zenodo.19571754"},{"key":"e_1_3_1_71_2","first-page":"255","article-title":"Equality saturation for tensor graph superoptimization","volume":"3","author":"Yang Yichen","year":"2021","unstructured":"Yichen Yang, Phitchaya Phothilimthana, Yisu Wang, Max Willsey, Sudip Roy, and Jacques Pienaar. 2021. Equality saturation for tensor graph superoptimization. Proceedings of Machine Learning and Systems 3 (2021), 255\u2013268.","journal-title":"Proceedings of Machine Learning and Systems"},{"key":"e_1_3_1_72_2","doi-asserted-by":"publisher","DOI":"10.1109\/dac63849.2025.11132728"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808254","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3808254","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T10:42:57Z","timestamp":1790073777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3808254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,8]]},"references-count":71,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2026,6,8]]}},"alternative-id":["10.1145\/3808254"],"URL":"https:\/\/doi.org\/10.1145\/3808254","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,8]]},"assertion":[{"value":"2025-11-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-03","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}