{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T04:16:52Z","timestamp":1777954612133,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":61,"publisher":"ACM","funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1901381, CCF-2115104, CCF-2119352, CCF-2107241"],"award-info":[{"award-number":["CCF-1901381, CCF-2115104, CCF-2119352, CCF-2107241"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,16]]},"DOI":"10.1145\/3694906.3743325","type":"proceedings-article","created":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T16:19:56Z","timestamp":1752682796000},"page":"269-283","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["POPQC: Parallel Optimization for Quantum Circuits"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1302-2391","authenticated-orcid":false,"given":"Pengyu","family":"Liu","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8302-6844","authenticated-orcid":false,"given":"Jatin","family":"Arora","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA, Amazon Web Services and Carnegie Mellon University"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8123-5148","authenticated-orcid":false,"given":"Mingkuan","family":"Xu","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2623-4986","authenticated-orcid":false,"given":"Umut A.","family":"Acar","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2025,7,16]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Algorithms: Parallel and Sequential","author":"Acar Umut A.","year":"2022","unstructured":"Umut A. Acar and Guy E. Blelloch. Algorithms: Parallel and Sequential. 2022. http:www.algorithms-book.com."},{"key":"e_1_3_2_1_2_1","first-page":"769","volume-title":"Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018","author":"Acar Umut A.","year":"2018","unstructured":"Umut A. Acar, Arthur Chargu\u00e9raud, Adrien Guatto, Mike Rainey, and Filip Sieczkowski. Heartbeat scheduling: Provable efficiency for nested parallelism. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, pages 769--782, 2018."},{"key":"e_1_3_2_1_3_1","first-page":"499","volume-title":"ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA)","author":"Acar Umut A.","year":"2011","unstructured":"Umut A. Acar, Arthur Chargu\u00e9raud, and Mike Rainey. Oracle scheduling: Controlling granularity in implicitly parallel languages. In ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), pages 499--518, 2011."},{"key":"e_1_3_2_1_4_1","volume-title":"Formal methods in quantum circuit design","author":"Amy Matthew","year":"2019","unstructured":"Matthew Amy. Formal methods in quantum circuit design. 2019."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2014.2341953"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434299"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591284"},{"key":"e_1_3_2_1_8_1","volume-title":"Local optimization of quantum circuits (extended version). arXiv preprint arXiv:25021 9526","author":"Arora Jatin","year":"2025","unstructured":"Jatin Arora, Mingkuan Xu, Sam Westrick, Pengyu Liu, Dantong Li, Yongshan Ding, and Umut A Acar. Local optimization of quantum circuits (extended version). arXiv preprint arXiv:25021 9526, 2025."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/VDAT50263.2020.9190279"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01011339"},{"key":"e_1_3_2_1_11_1","volume-title":"et al. Pennylane: Automatic differentiation of hybrid quantum-classical computations. arXiv preprint arXiv:1811.04968","author":"Bergholm Ville","year":"2018","unstructured":"Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M Sohaib Alam, Guillermo Alonso-Linaje, B AkashNarayanan, Ali Asadi, et al. Pennylane: Automatic differentiation of hybrid quantum-classical computations. arXiv preprint arXiv:1811.04968, 2018."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature23474"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1087072"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/QCE49297.2020.00036"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-021-03582-4"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1201\/9780429500459-11"},{"key":"e_1_3_2_1_17_1","volume-title":"Florian Marquardt, and Li Li. Quantum circuit optimization with deep reinforcement learning. arXiv preprint arXiv:2103.07585","author":"F\u00f6sel Thomas","year":"2021","unstructured":"Thomas F\u00f6sel, Murphy Yuezhen Niu, Florian Marquardt, and Li Li. Quantum circuit optimization with deep reinforcement learning. arXiv preprint arXiv:2103.07585, 2021."},{"key":"e_1_3_2_1_18_1","volume-title":"Remarks on matsumoto and amano's normal form for single-qubit clifford+ t operators. arXiv preprint arXiv:1312.6584","author":"Giles Brett","year":"2013","unstructured":"Brett Giles and Peter Selinger. Remarks on matsumoto and amano's normal form for single-qubit clifford+ t operators. arXiv preprint arXiv:1312.6584, 2013."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO50266.2020.00027"},{"key":"e_1_3_2_1_20_1","volume-title":"A fast quantum mechanical algorithm for database search. arXiv preprint quant-ph\/9605043","author":"Grover Lov K","year":"1996","unstructured":"Lov K Grover. A fast quantum mechanical algorithm for database search. arXiv preprint quant-ph\/9605043, 1996."},{"key":"e_1_3_2_1_21_1","volume-title":"Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502","author":"Harrow Aram W","year":"2009","unstructured":"Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103(15):150502, 2009."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434318"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3498325"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2019.10.004"},{"key":"e_1_3_2_1_25_1","volume-title":"Identity check is qmacomplete","author":"Janzing Dominik","year":"2003","unstructured":"Dominik Janzing, Pawel Wocjan, and Thomas Beth. Identity check is qmacomplete, 2003."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0301-0104(01)00318-4"},{"key":"e_1_3_2_1_27_1","series-title":"Electronic Proceedings in Theoretical Computer Science","first-page":"229","volume-title":"Proceedings 16th International Conference on Quantum Physics and Logic","author":"Kissinger Aleks","year":"2019","unstructured":"Aleks Kissinger and John van de Wetering. PyZX: Large Scale Automated Diagrammatic Reasoning. In Bob Coecke and Matthew Leifer, editors, Proceedings 16th International Conference on Quantum Physics and Logic, Chapman University, Orange, CA, USA., 10--14 June 2019, volume 318 of Electronic Proceedings in Theoretical Computer Science, pages 229--241. Open Publishing Association, 2020."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-conmatphys-031119-050605"},{"key":"e_1_3_2_1_29_1","volume-title":"Quantum search compiler (qsearch) v2.0, version v2.0, 10","author":"Lancu Costin","year":"2020","unstructured":"Costin Lancu, Marc Davis, Ethan Smith, and USDOE. Quantum search compiler (qsearch) v2.0, version v2.0, 10 2020."},{"key":"e_1_3_2_1_30_1","volume-title":"Qasmbench: A low-level qasm benchmark suite for nisq evaluation and simulation. arXiv preprint arXiv:2005.13018","author":"Li Ang","year":"2021","unstructured":"Ang Li, Samuel Stein, Sriram Krishnamoorthy, and James Ang. Qasmbench: A low-level qasm benchmark suite for nisq evaluation and simulation. arXiv preprint arXiv:2005.13018, 2021."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304023"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3649831"},{"key":"e_1_3_2_1_33_1","volume-title":"Popqc: Parallel optimization for quantum circuits (extended version). arXiv preprint arXiv:2506.13720","author":"Liu Pengyu","year":"2025","unstructured":"Pengyu Liu, Jatin Arora, Mingkuan Xu, and Umut A. Acar. Popqc: Parallel optimization for quantum circuits (extended version). arXiv preprint arXiv:2506.13720, 2025."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2015.7059001"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO56248.2022.00077"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.93.025001"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","unstructured":"S. A. Moses C. H. Baldwin M. S. Allman R. Ancona L. Ascarrunz C. Barnes J. Bartolotta B. Bjork P. Blanchard M. Bohn J. G. Bohnet N. C. Brown N. Q. Burdick W. C. Burton S. L. Campbell J. P. Campora III au2 C. Carron J. Chambers J. W. Chan Y. H. Chen A. Chernoguzov E. Chertkov J. Colina J. P. Curtis R. Daniel M. DeCross D. Deen C. Delaney J. M. Dreiling C. T. Ertsgaard J. Esposito B. Estey M. Fabrikant C. Figgatt C. Foltz M. Foss-Feig D. Francois J. P. Gaebler T. M. Gatterman C. N. Gilbreth J. Giles E. Glynn A. Hall A. M. Hankin A. Hansen D. Hayes B. Higashi I. M. Hoffman B. Horning J. J. Hout R.Jacobs J. Johansen L. Jones J. Karcz T. Klein P. Lauria P. Lee D. Liefer C. Lytle S. T. Lu D. Lucchetti A. Malm M. Matheny B. Mathewson K. Mayer D. B. Miller M. Mills B. Neyenhuis L. Nugent S. Olson J. Parks G. N. Price Z. Price M. Pugh A. Ransford A. P. Reed C. Roman M. Rowe C. Ryan-Anderson S. Sanders J. Sedlacek P. Shevchuk P. Siegfried T. Skripka B. Spaun R. T. Sprenkle R. P. Stutz M. Swallows R. I. Tobey A. Tran T. Tran E. Vogt C. Volin J. Walker A. M. Zolot and J. M. Pino. A race track trapped-ion quantum processor 2023.","DOI":"10.1103\/PhysRevX.13.041052"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304075"},{"key":"e_1_3_2_1_39_1","volume-title":"Automated optimization of large quantum circuits with continuous parameters. npj Quantum Information, 4(1), may","author":"Nam Yunseong","year":"2018","unstructured":"Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov. Automated optimization of large quantum circuits with continuous parameters. npj Quantum Information, 4(1), may 2018."},{"key":"e_1_3_2_1_40_1","volume-title":"Quantum computation and quantum information","author":"Nielsen Michael A","year":"2002","unstructured":"Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002."},{"key":"e_1_3_2_1_41_1","volume-title":"Decomposing and routing quantum circuits under constraints for neutral atom architectures. arXiv preprint arXiv:2307.14996","author":"Nottingham Natalia","year":"2023","unstructured":"Natalia Nottingham, Michael A Perlin, Ryan White, Hannes Bernien, Frederic T Chong, and Jonathan M Baker. Decomposing and routing quantum circuits under constraints for neutral atom architectures. arXiv preprint arXiv:2307.14996, 2023."},{"key":"e_1_3_2_1_42_1","first-page":"18182","article-title":"Reinforcement learning for optimization of variational quantum circuit architectures","volume":"34","author":"Ostaszewski Mateusz","year":"2021","unstructured":"Mateusz Ostaszewski, Lea M Trenkwalder, Wojciech Masarczyk, Eleanor Scerri, and Vedran Dunjko. Reinforcement learning for optimization of variational quantum circuit architectures. Advances in Neural Information Processing Systems, 34:18182--18194, 2021.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms5213"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-08-06-79"},{"key":"e_1_3_2_1_45_1","volume-title":"Beyond nisq: The megaquop machine","author":"Preskill John","year":"2024","unstructured":"John Preskill. Beyond nisq: The megaquop machine, 2024."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-021-03585-1"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/00107514.2014.964942"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304018"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/abe107"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3297858.3304007"},{"key":"e_1_3_2_1_52_1","volume-title":"An introduction to cartan's kak decomposition for qc programmers. arXiv preprint quant-ph\/0507171","author":"Tucci Robert R","year":"2005","unstructured":"Robert R Tucci. An introduction to cartan's kak decomposition for qc programmers. arXiv preprint quant-ph\/0507171, 2005."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA53966.2022.00057"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371115"},{"key":"e_1_3_2_1_55_1","first-page":"1234","volume-title":"Automation & Test in Europe Conference & Exhibition (DATE)","author":"Wille Robert","year":"2019","unstructured":"Robert Wille, Rod Van Meter, and Yehuda Naveh. Ibm's qiskit tool chain: Working with and developing for real quantum computers. In 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1234--1240. IEEE, 2019."},{"key":"e_1_3_2_1_56_1","volume-title":"Frederic T Chong, and Costin Iancu. Qgo: Scalable quantum circuit optimization using automated synthesis. arXiv preprint arXiv:2012.09835","author":"Wu Xin-Chuan","year":"2020","unstructured":"Xin-Chuan Wu, Marc Grau Davis, Frederic T Chong, and Costin Iancu. Qgo: Scalable quantum circuit optimization using automated synthesis. arXiv preprint arXiv:2012.09835, 2020."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA51647.2021.00023"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591254"},{"key":"e_1_3_2_1_59_1","volume-title":"Optimizing quantum circuits, fast and slow. arXiv preprint arXiv:2411.04104","author":"Xu Amanda","year":"2024","unstructured":"Amanda Xu, Abtin Molavi, Swamit Tannu, and Aws Albarghouthi. Optimizing quantum circuits, fast and slow. arXiv preprint arXiv:2411.04104, 2024."},{"key":"e_1_3_2_1_60_1","first-page":"625","volume-title":"Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2022","author":"Xu Mingkuan","year":"2022","unstructured":"Mingkuan Xu, Zikun Li, Oded Padon, Sina Lin, Jessica Pointing, Auguste Hirth, Henry Ma, Jens Palsberg, Alex Aiken, Umut A. Acar, and Zhihao Jia. Quartz: Superoptimization of quantum circuits. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2022, page 625--640, New York, NY, USA, 2022. Association for Computing Machinery."},{"key":"e_1_3_2_1_61_1","volume-title":"Qfast: Conflating search and numerical optimization for scalable quantum circuit synthesis","author":"Younis Ed","year":"2021","unstructured":"Ed Younis, Koushik Sen, Katherine Yelick, and Costin Iancu. Qfast: Conflating search and numerical optimization for scalable quantum circuit synthesis, 2021."}],"event":{"name":"SPAA '25: 37th ACM Symposium on Parallelism in Algorithms and Architectures","location":"Portland OR USA","acronym":"SPAA '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGARCH ACM Special Interest Group on Computer Architecture","EATCS European Association for Theoretical Computer Science"]},"container-title":["Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3694906.3743325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T19:19:05Z","timestamp":1777922345000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3694906.3743325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,16]]},"references-count":61,"alternative-id":["10.1145\/3694906.3743325","10.1145\/3694906"],"URL":"https:\/\/doi.org\/10.1145\/3694906.3743325","relation":{},"subject":[],"published":{"date-parts":[[2025,7,16]]},"assertion":[{"value":"2025-07-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}