{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T01:47:35Z","timestamp":1773193655179,"version":"3.50.1"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2023,4,6]],"date-time":"2023-04-06T00:00:00Z","timestamp":1680739200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2023,4,6]]},"abstract":"<jats:p>In this article, we present a novel method for synthesizing quantum circuits from user-supplied components. Given input-output state vectors and component quantum gates, our synthesizer aims to construct a quantum circuit that implements the provided functionality in terms of the supplied component gates.\u00a0To achieve this, we basically use an enumerative search with pruning. To accelerate the procedure, however, we perform the search and pruning at the module level; instead of simply enumerating candidate circuits by appending component gates in sequence, we stack modules, which are groups of gate operations.  \nWith this modular approach, we can effectively reduce the search space by directing the search in a way that bridges the gap between the current circuit and the input-output specification.  \nEvaluation on 17 benchmark problems shows that our technique is highly effective at synthesizing quantum circuits. Our method successfully synthesized 16 out of 17 benchmark circuits in 96.6 seconds on average. On the other hand, the conventional, gate-level synthesis algorithm succeeded in 10 problems with an average time of 639.1 seconds. Our algorithm increased the speed of the baseline by 20.3x for the 10 problems commonly solved by both approaches.<\/jats:p>","DOI":"10.1145\/3586039","type":"journal-article","created":{"date-parts":[[2023,4,6]],"date-time":"2023-04-06T21:06:02Z","timestamp":1680815162000},"page":"348-375","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Modular Component-Based Quantum Circuit Synthesis"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-1676-8417","authenticated-orcid":false,"given":"Chan Gu","family":"Kang","sequence":"first","affiliation":[{"name":"Korea University, South Korea"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1900-7654","authenticated-orcid":false,"given":"Hakjoo","family":"Oh","sequence":"additional","affiliation":[{"name":"Korea University, South Korea"}]}],"member":"320","published-online":{"date-parts":[[2023,4,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.2562111"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386007"},{"key":"#cr-split#-e_1_2_1_3_1.1","unstructured":"D. Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0201067 10.48550\/ARXIV.QUANT-PH"},{"key":"#cr-split#-e_1_2_1_3_1.2","unstructured":"D. Coppersmith. 2002. An approximate Fourier transform useful in quantum factoring. https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0201067"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/qute.201900015"},{"key":"#cr-split#-e_1_2_1_5_1.1","unstructured":"Marc Grau Davis Ethan Smith Ana Tudor Koushik Sen Irfan Siddiqi and Costin Iancu. 2019. Heuristics for Quantum Compiling with a Continuous Gate Set. https:\/\/doi.org\/10.48550\/ARXIV.1912.02727 10.48550\/ARXIV.1912.02727"},{"key":"#cr-split#-e_1_2_1_5_1.2","unstructured":"Marc Grau Davis Ethan Smith Ana Tudor Koushik Sen Irfan Siddiqi and Costin Iancu. 2019. Heuristics for Quantum Compiling with a Continuous Gate Set. https:\/\/doi.org\/10.48550\/ARXIV.1912.02727"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/QCE49297.2020.00036"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.6599601"},{"key":"#cr-split#-e_1_2_1_8_1.1","unstructured":"Thomas G. Draper. 2000. Addition on a Quantum Computer. https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0008033 10.48550\/ARXIV.QUANT-PH"},{"key":"#cr-split#-e_1_2_1_8_1.2","unstructured":"Thomas G. Draper. 2000. Addition on a Quantum Computer. https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0008033"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.62.062314"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062351"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093333.3009851"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2737977"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316366"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cpc.2019.107001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499370.2462177"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.69.062311"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.93.032318"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806799.1806833"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3434335"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-07-12-163"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-021-01745-x"},{"key":"e_1_2_1_23_1","volume-title":"Constructions and Applications of W-States","author":"McClung James","unstructured":"James McClung . 2020. Constructions and Applications of W-States . Worcester Polytechnic Institute . James McClung. 2020. Constructions and Applications of W-States. Worcester Polytechnic Institute."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.93.130502"},{"key":"e_1_2_1_25_1","volume-title":"Generation of three-qubit entangled states using superconducting phase qubits. Nature, 467, 7315","author":"Neeley Matthew","year":"2010","unstructured":"Matthew Neeley , Radoslaw C Bialczak , M Lenander , Erik Lucero , Matteo Mariantoni , AD O\u2019connell , D Sank , H Wang , M Weides , and J Wenner . 2010. Generation of three-qubit entangled states using superconducting phase qubits. Nature, 467, 7315 ( 2010 ), 570\u2013573. Matthew Neeley, Radoslaw C Bialczak, M Lenander, Erik Lucero, Matteo Mariantoni, AD O\u2019connell, D Sank, H Wang, M Weides, and J Wenner. 2010. Generation of three-qubit entangled states using superconducting phase qubits. Nature, 467, 7315 (2010), 570\u2013573."},{"key":"e_1_2_1_26_1","volume-title":"Chuang","author":"Nielsen Michael A.","year":"2011","unstructured":"Michael A. Nielsen and Isaac L . Chuang . 2011 . Quantum Computation and Quantum Information: 10th Anniversary Edition (10th ed.). Cambridge University Press , USA. isbn:1107002176 Michael A. Nielsen and Isaac L. Chuang. 2011. Quantum Computation and Quantum Information: 10th Anniversary Edition (10th ed.). Cambridge University Press, USA. isbn:1107002176"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2813885.2738007"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3453483.3454040"},{"key":"e_1_2_1_29_1","unstructured":"QK. 2022. Task 1.7. https:\/\/github.com\/microsoft\/QuantumKatas\/blob\/main\/Superposition\/Workbook_Superposition.ipynb \t\t\t\t  QK. 2022. Task 1.7. https:\/\/github.com\/microsoft\/QuantumKatas\/blob\/main\/Superposition\/Workbook_Superposition.ipynb"},{"key":"e_1_2_1_30_1","unstructured":"QK. 2022. Task 2.1. https:\/\/github.com\/microsoft\/QuantumKatas\/blob\/main\/GHZGame\/Workbook_GHZGame.ipynb \t\t\t\t  QK. 2022. Task 2.1. https:\/\/github.com\/microsoft\/QuantumKatas\/blob\/main\/GHZGame\/Workbook_GHZGame.ipynb"},{"key":"e_1_2_1_31_1","unstructured":"QK. 2022. Task 2.3. https:\/\/github.com\/microsoft\/QuantumKatas\/blob\/0bc1b11ad2b29e358a9100dea7d0b9a973f5f9fd\/Superposition\/Workbook_Superposition_Part2.ipynb \t\t\t\t  QK. 2022. Task 2.3. https:\/\/github.com\/microsoft\/QuantumKatas\/blob\/0bc1b11ad2b29e358a9100dea7d0b9a973f5f9fd\/Superposition\/Workbook_Superposition_Part2.ipynb"},{"key":"e_1_2_1_32_1","first-page":"11","article-title":"Optimal Ancilla-Free CLIFFORD+V Approximation of Z-Rotations. Quantum Info","volume":"15","author":"Ross Neil J.","year":"2015","unstructured":"Neil J. Ross . 2015 . Optimal Ancilla-Free CLIFFORD+V Approximation of Z-Rotations. Quantum Info . Comput. , 15 , 11 \u2013 12 (2015), sep, 932\u2013950. issn:1533-7146 Neil J. Ross. 2015. Optimal Ancilla-Free CLIFFORD+V Approximation of Z-Rotations. Quantum Info. Comput., 15, 11\u201312 (2015), sep, 932\u2013950. issn:1533-7146","journal-title":"Comput."},{"key":"e_1_2_1_33_1","unstructured":"SE. 2018. How can I build a circuit to generate an equal superposition of 3 outcomes for 2 qubits? https:\/\/quantumcomputing.stackexchange.com\/questions\/2310\/how-can-i-build-a-circuit-to-generate-an-equal-superposition-of-3-outcomes-for-2 \t\t\t\t  SE. 2018. How can I build a circuit to generate an equal superposition of 3 outcomes for 2 qubits? https:\/\/quantumcomputing.stackexchange.com\/questions\/2310\/how-can-i-build-a-circuit-to-generate-an-equal-superposition-of-3-outcomes-for-2"},{"key":"e_1_2_1_34_1","unstructured":"SE. 2018. How can the state 0 + M^-1\/2 \\DOTSI \u2211op \\slimits@ _j=1^M j be generated? https:\/\/quantumcomputing.stackexchange.com\/questions\/4545\/how-can-the-state-lvert0-ranglem-1-2-sum-j-1m-lvert-j-rangle-be-genera \t\t\t\t  SE. 2018. How can the state 0 + M^-1\/2 \\DOTSI \u2211op \\slimits@ _j=1^M j be generated? https:\/\/quantumcomputing.stackexchange.com\/questions\/4545\/how-can-the-state-lvert0-ranglem-1-2-sum-j-1m-lvert-j-rangle-be-genera"},{"key":"e_1_2_1_35_1","unstructured":"SE. 2018. How do I build a gate from a matrix on Qiskit? https:\/\/quantumcomputing.stackexchange.com\/questions\/4975\/how-do-i-build-a-gate-from-a-matrix-on-qiskit \t\t\t\t  SE. 2018. How do I build a gate from a matrix on Qiskit? https:\/\/quantumcomputing.stackexchange.com\/questions\/4975\/how-do-i-build-a-gate-from-a-matrix-on-qiskit"},{"key":"e_1_2_1_36_1","unstructured":"SE. 2018. How to create a quantum algorithm that produces 2n-bit sequences with equal number of 1-bits? https:\/\/mathoverflow.net\/questions\/301733\/how-to-create-a-quantum-algorithm-that-produces-2-n-bit-sequences-with-equal-num \t\t\t\t  SE. 2018. How to create a quantum algorithm that produces 2n-bit sequences with equal number of 1-bits? https:\/\/mathoverflow.net\/questions\/301733\/how-to-create-a-quantum-algorithm-that-produces-2-n-bit-sequences-with-equal-num"},{"key":"e_1_2_1_37_1","unstructured":"SE. 2019. Quantum circuit for a three-qubit bit-flip code. https:\/\/quantumcomputing.stackexchange.com\/questions\/9175\/quantum-circuit-for-a-three-qubit-bit-flip-code \t\t\t\t  SE. 2019. Quantum circuit for a three-qubit bit-flip code. https:\/\/quantumcomputing.stackexchange.com\/questions\/9175\/quantum-circuit-for-a-three-qubit-bit-flip-code"},{"key":"e_1_2_1_38_1","unstructured":"SE. 2020. Generalized construction of W basis. https:\/\/quantumcomputing.stackexchange.com\/questions\/13077\/generalized-construction-of-w-basis \t\t\t\t  SE. 2020. Generalized construction of W basis. https:\/\/quantumcomputing.stackexchange.com\/questions\/13077\/generalized-construction-of-w-basis"},{"key":"e_1_2_1_39_1","unstructured":"SE. 2020. Quantum Circuit explaination. https:\/\/quantumcomputing.stackexchange.com\/questions\/12552\/quantum-circuit-explaination \t\t\t\t  SE. 2020. Quantum Circuit explaination. https:\/\/quantumcomputing.stackexchange.com\/questions\/12552\/quantum-circuit-explaination"},{"key":"e_1_2_1_40_1","unstructured":"SE. 2020. Transforming 100 state into 000+111 state using only Hadamard and CNOT gates. https:\/\/quantumcomputing.stackexchange.com\/questions\/14642\/transforming-100-rangle-state-into-000-rangle-111-rangle-state-using-on \t\t\t\t  SE. 2020. Transforming 100 state into 000+111 state using only Hadamard and CNOT gates. https:\/\/quantumcomputing.stackexchange.com\/questions\/14642\/transforming-100-rangle-state-into-000-rangle-111-rangle-state-using-on"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.855930"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548693"},{"key":"e_1_2_1_44_1","volume-title":"Synthesizing Imperative Programs from Examples Guided by Static Analysis","author":"So Sunbeom","unstructured":"Sunbeom So and Hakjoo Oh. 2017. Synthesizing Imperative Programs from Examples Guided by Static Analysis . In Static Analysis, Francesco Ranzato (Ed.). Springer International Publishing , Cham . 364\u2013381. Sunbeom So and Hakjoo Oh. 2017. Synthesizing Imperative Programs from Examples Guided by Static Analysis. In Static Analysis, Francesco Ranzato (Ed.). Springer International Publishing, Cham. 364\u2013381."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183895.3183901"},{"key":"e_1_2_1_46_1","unstructured":"Qiskit Transpiler. 2022. transpiler-qiskit-transpiler. https:\/\/qiskit.org\/documentation\/apidoc\/transpiler.html \t\t\t\t  Qiskit Transpiler. 2022. transpiler-qiskit-transpiler. https:\/\/qiskit.org\/documentation\/apidoc\/transpiler.html"},{"key":"#cr-split#-e_1_2_1_47_1.1","unstructured":"Robert R. Tucci. 2005. An Introduction to Cartan's KAK Decomposition for QC Programmers. https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0507171 10.48550\/ARXIV.QUANT-PH"},{"key":"#cr-split#-e_1_2_1_47_1.2","unstructured":"Robert R. Tucci. 2005. An Introduction to Cartan's KAK Decomposition for QC Programmers. https:\/\/doi.org\/10.48550\/ARXIV.QUANT-PH\/0507171"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462174"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3062341.3062365"},{"key":"e_1_2_1_50_1","volume-title":"QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space. https:\/\/doi.org\/10.48550\/ARXIV.2003.04462","author":"Younis Ed","year":"2020","unstructured":"Ed Younis , Koushik Sen , Katherine Yelick , and Costin Iancu . 2020 . QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space. https:\/\/doi.org\/10.48550\/ARXIV.2003.04462 10.48550\/ARXIV.2003.04462 Ed Younis, Koushik Sen, Katherine Yelick, and Costin Iancu. 2020. QFAST: Quantum Synthesis Using a Hierarchical Continuous Circuit Space. https:\/\/doi.org\/10.48550\/ARXIV.2003.04462"},{"key":"e_1_2_1_51_1","volume-title":"Tower: Data Structures in Quantum Superposition. arXiv preprint arXiv:2205.10255.","author":"Yuan Charles","year":"2022","unstructured":"Charles Yuan and Michael Carbin . 2022 . Tower: Data Structures in Quantum Superposition. arXiv preprint arXiv:2205.10255. Charles Yuan and Michael Carbin. 2022. Tower: Data Structures in Quantum Superposition. arXiv preprint arXiv:2205.10255."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3586039","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3586039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:10Z","timestamp":1750178770000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3586039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4,6]]},"references-count":55,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2023,4,6]]}},"alternative-id":["10.1145\/3586039"],"URL":"https:\/\/doi.org\/10.1145\/3586039","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,6]]},"assertion":[{"value":"2023-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}