{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:03:31Z","timestamp":1750309411646,"version":"3.41.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T00:00:00Z","timestamp":1728345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"AnaGlobe, ASUS, Delta Electronics, Google, Maxeda Technology, TSMC, NSTC of Taiwan","award":["NSTC 110-2221-E-002-177-MY3, NSTC 113-2218-E-002-041, NSTC 113-2223-E-002-007, and NSTC 113-2640-E-002-001"],"award-info":[{"award-number":["NSTC 110-2221-E-002-177-MY3, NSTC 113-2218-E-002-041, NSTC 113-2223-E-002-007, and NSTC 113-2640-E-002-001"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2024,11,30]]},"abstract":"<jats:p>Topological quantum error correction (TQEC) using the surface code is among the most promising techniques for fault-tolerant quantum circuits. The required resource of a TQEC circuit can be modeled as a space-time volume of a three-dimensional diagram by describing the defect movement along the time axis. For large-scale complex problems, it is crucial to minimize the space-time volume for a quantum algorithm with a reasonable physical qubit number and computation time. Previous work proposed an automated tool for bridge compression on a large-scale TQEC circuit. However, the existing automated bridge compression is only for dual defects and not for primal defects. This paper presents an algorithm to simultaneously perform bridge compression on primal and dual defects. In addition, the automatic compression algorithm performs initialization\/measurement simplification and flipping to improve the compression. Compared with the state-of-the-art work, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 53%.<\/jats:p>","DOI":"10.1145\/3695252","type":"journal-article","created":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T08:31:02Z","timestamp":1726302662000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Bridge-based Algorithm for Simultaneous Primal and Dual Defects Compression on Topologically Quantum-error-corrected Circuits"],"prefix":"10.1145","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2776-0582","authenticated-orcid":false,"given":"Wei-Hsiang","family":"Tseng","sequence":"first","affiliation":[{"name":"Graduate Institute of Electronics Engineering, National Taiwan University, Taipei, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0564-5719","authenticated-orcid":false,"given":"Yao-Wen","family":"Chang","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering\/Graduate Institute of Electronics Engineering, National Taiwan University, Taipei, Taiwan"}]}],"member":"320","published-online":{"date-parts":[[2024,10,8]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.26.20"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-014-0867-y"},{"issue":"4","key":"e_1_3_1_4_2","doi-asserted-by":"crossref","first-page":"624","DOI":"10.1587\/transfun.E102.A.624","article-title":"Compaction of topological quantum circuits by modularization","volume":"102","author":"Asai Kota","year":"2019","unstructured":"Kota Asai and Shigeru Yamashita. 2019. Compaction of topological quantum circuits by modularization. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 102, 4 (April2019), 624\u2013632.","journal-title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"},{"key":"e_1_3_1_5_2","unstructured":"Dezs\u0151 Bal\u00e1zs J\u00fcttner Alp\u00e1r and Kov\u00e1cs P\u00e9ter. 2011. The LEMON Graph Library. (2011). https:\/\/lemon.cs.elte.hu\/trac\/lemon"},{"key":"e_1_3_1_6_2","first-page":"55","volume-title":"Proceedings of IEEE Asian Test Symposium","author":"Devitt Simon","year":"2012","unstructured":"Simon Devitt and Kae Nemoto. 2012. Programming a topological quantum computer. In Proceedings of IEEE Asian Test Symposium. Niigata, Japan, 55\u201360."},{"key":"e_1_3_1_7_2","first-page":"169","volume-title":"Proceedings of IEEE\/ACM Asia and South Pacific Design Automation Conference","author":"Falkenstern Paul","year":"2010","unstructured":"Paul Falkenstern, Yuan Xie, Yao-Wen Chang, and Yu Wang. 2010. Three-dimensional integrated circuits (3D IC) floorplan and power\/ground network co-synthesis. In Proceedings of IEEE\/ACM Asia and South Pacific Design Automation Conference. Taipei, Taiwan, 169\u2013174."},{"key":"e_1_3_1_8_2","article-title":"A bridge to lower overhead quantum computation","author":"Fowler Austin G.","year":"2012","unstructured":"Austin G. Fowler and Simon J. Devitt. 2012. A bridge to lower overhead quantum computation. arXiv preprint arXiv:1209.0510 (April2012).","journal-title":"arXiv preprint arXiv:1209.0510"},{"key":"e_1_3_1_9_2","article-title":"Topological cluster state quantum computing","author":"Fowler Austin G.","year":"2009","unstructured":"Austin G. Fowler and Kovid Goyal. 2009. Topological cluster state quantum computing. arXiv preprint arXiv:0805.3202 (February2009).","journal-title":"arXiv preprint arXiv:0805.3202"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.86.032324"},{"key":"e_1_3_1_11_2","first-page":"212","volume-title":"Proceedings of ACM Symposium on Theory of Computing","author":"Grover Lov K.","year":"1996","unstructured":"Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of ACM Symposium on Theory of Computing. Philadelphia, PA, 212\u2013219."},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"e_1_3_1_13_2","first-page":"457","volume-title":"Proceedings of ACM\/IEEE Design Automation Conference","author":"Hsu Chen-Hao","year":"2021","unstructured":"Chen-Hao Hsu, Wan-Hsuan Lin, Wei-Hsiang Tseng, and Yao-Wen Chang. 2021. A bridge-based compression algorithm for topological quantum circuits.. In Proceedings of ACM\/IEEE Design Automation Conference. San Francisco, CA, 457\u2013462."},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2014.2337302"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2017.2760511"},{"key":"e_1_3_1_16_2","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1109\/FPGA.1995.242049","volume-title":"Proceedings of ACM International Symposium on Field-Programmable Gate Arrays","author":"McMurchie L.","year":"1995","unstructured":"L. McMurchie and C. Ebeling. 1995. PathFinder: A negotiation-based performance-driven router for FPGAs. In Proceedings of ACM International Symposium on Field-Programmable Gate Arrays. Monterey, CA, 111\u2013117."},{"key":"e_1_3_1_17_2","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen Michael A.","year":"2001","unstructured":"Michael A. Nielsen and Isaac Chuang. 2001. Quantum Computation and Quantum Information. Cambridge University Press."},{"key":"e_1_3_1_18_2","article-title":"Quantum circuit optimization by topological compaction in the surface code","author":"Paetznick Adam","year":"2013","unstructured":"Adam Paetznick and Austin G. Fowler. 2013. Quantum circuit optimization by topological compaction in the surface code. arXiv preprint arXiv:1304.2807 (April2013).","journal-title":"arXiv preprint arXiv:1304.2807"},{"key":"e_1_3_1_19_2","article-title":"SurfBraid: A concept tool for preparing and resource estimating quantum circuits protected by the surface code","author":"Paler Alexandru","year":"2019","unstructured":"Alexandru Paler. 2019. SurfBraid: A concept tool for preparing and resource estimating quantum circuits protected by the surface code. arXiv preprint arXiv:1902.02417 (February2019).","journal-title":"arXiv preprint arXiv:1902.02417"},{"key":"e_1_3_1_20_2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1145\/2765491.2765524","volume-title":"Proceedings of IEEE\/ACM International Symposium on Nanoscale Architectures","author":"Paler Alexandru","year":"2012","unstructured":"Alexandru Paler, Simon Devitt, Kae Nemoto, and Ilia Polian. 2012. Synthesis of topological quantum circuits. In Proceedings of IEEE\/ACM International Symposium on Nanoscale Architectures. Amsterdam, Netherlands, 181\u2013187."},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1038\/srep30600"},{"issue":"1","key":"e_1_3_1_22_2","first-page":"1","article-title":"Mapping of topological quantum circuits to physical hardware","volume":"4","author":"Paler Alexandru","year":"2014","unstructured":"Alexandru Paler, Simon J. Devitt, Kae Nemoto, and Ilia Polian. 2014. Mapping of topological quantum circuits to physical hardware. Scientific Reports 4, 1 (April2014), 1\u201310.","journal-title":"Scientific Reports"},{"issue":"1","key":"e_1_3_1_23_2","first-page":"1","article-title":"Synthesis of arbitrary quantum circuits to topological assembly: Systematic, online and compact","volume":"7","author":"Paler Alexandru","year":"2017","unstructured":"Alexandru Paler, Austin G. Fowler, and Robert Wille. 2017. Synthesis of arbitrary quantum circuits to topological assembly: Systematic, online and compact. Scientific Reports 7, 1 (September2017), 1\u201316.","journal-title":"Scientific Reports"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20860-2_9"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1088\/2058-9565\/aa66eb"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.94.042337"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/6\/199"},{"key":"e_1_3_1_28_2","unstructured":"Boris Sch\u00e4ling. 2019. The Boost C++ Libraries. (2019). https:\/\/www.boost.org\/users\/history\/version_1_72_0"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598347011"},{"key":"e_1_3_1_30_2","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1145\/3489517.3530483","volume-title":"Proceedings of ACM\/IEEE Design Automation Conference","author":"Tseng Wei-Hsiang","year":"2022","unstructured":"Wei-Hsiang Tseng and Yao-Wen Chang. 2022. A bridge-based algorithm for simultaneous primal and dual defects compression on topologically quantum-error-corrected circuits. In Proceedings of ACM\/IEEE Design Automation Conference. San Francisco, CA, 535\u2013540."},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2022.3161597"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL.2008.43"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695252","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3695252","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:11Z","timestamp":1750294691000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3695252"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,8]]},"references-count":31,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,11,30]]}},"alternative-id":["10.1145\/3695252"],"URL":"https:\/\/doi.org\/10.1145\/3695252","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2024,10,8]]},"assertion":[{"value":"2024-04-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-10-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}