{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T19:30:17Z","timestamp":1776108617867,"version":"3.50.1"},"reference-count":47,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T00:00:00Z","timestamp":1776038400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"PRESTO JST Grant","award":["JPMJPR1916"],"award-info":[{"award-number":["JPMJPR1916"]}]},{"name":"MEXT Q-LEAP Grant","award":["JPMXS0120319794"],"award-info":[{"award-number":["JPMXS0120319794"]}]},{"name":"MEXT Q-LEAP Grant","award":["JPMXS0118068682"],"award-info":[{"award-number":["JPMXS0118068682"]}]},{"name":"JST Moonshot R&D Grant","award":["JPMJMS2061"],"award-info":[{"award-number":["JPMJMS2061"]}]},{"name":"JST CREST Grant","award":["JPMJCR23I4"],"award-info":[{"award-number":["JPMJCR23I4"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Encoding logical qubits with surface codes and performing multi-qubit logical operations with lattice surgery is one of the most promising approaches to demonstrate fault-tolerant quantum computing. Thus, a method to efficiently schedule a sequence of lattice-surgery operations is vital for high-performance fault-tolerant quantum computing. A possible strategy to improve the throughput of lattice-surgery operations is splitting a large instruction into several small instructions, such as Bell state preparation and measurements, and executing a part of them in advance. However, scheduling methods to fully utilize this idea have yet to be explored. In this paper, we propose a fast and high-performance scheduling algorithm for lattice-surgery instructions leveraging this strategy. We achieved this by converting the scheduling problem of lattice-surgery instructions to a graph problem of embedding 3D paths into a 3D lattice, which enables us to explore efficient scheduling by solving path search problems in the 3D lattice. Based on this reduction, we propose a method to solve the path-finding problems, the look-ahead Dijkstra projection. We numerically show that this method reduced the execution time of benchmark programs generated from quantum phase estimation algorithms by 3.8 times compared with a naive method based on greedy algorithms. Our study establishes the relation between the lattice-surgery scheduling and graph search problems, which leads to further theoretical analysis on compiler optimization of fault-tolerant quantum computing.<\/jats:p>","DOI":"10.22331\/q-2026-04-13-2061","type":"journal-article","created":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T17:59:11Z","timestamp":1776103151000},"page":"2061","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":0,"title":["Efficient and high-performance routing of lattice-surgery paths on three-dimensional lattice"],"prefix":"10.22331","volume":"10","author":[{"given":"Kou","family":"Hamada","sequence":"first","affiliation":[{"name":"Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yasunari","family":"Suzuki","sequence":"additional","affiliation":[{"name":"NTT Computer and Data Science Laboratories, NTT Corporation, Musashino 180-8585, Japan"},{"name":"JST, PRESTO, 4-1-8 Honcho, Kawaguchi, Saitama, 332-0012, Japan"},{"name":"Center for Quantum Computing, RIKEN, 2-1 Hirosawa, Wako, Saitama 351-0198, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuuki","family":"Tokunaga","sequence":"additional","affiliation":[{"name":"NTT Computer and Data Science Laboratories, NTT Corporation, Musashino 180-8585, Japan"},{"name":"Faculty of Information Science and Technology, Hokkaido University, Sapporo 060-0814, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2026,4,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Peter W. Shor. ``Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer''. SIAM Review 41, 303\u2013332 (1999). doi: 10.1137\/S0036144598347011.","DOI":"10.1137\/S0036144598347011"},{"key":"1","doi-asserted-by":"publisher","unstructured":"A. Yu. Kitaev. ``Quantum measurements and the abelian stabilizer problem'' (1995). doi: 10.48550\/arXiv.quant-ph\/9511026. arXiv:quant-ph\/9511026.","DOI":"10.48550\/arXiv.quant-ph\/9511026"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Seth Lloyd. ``Universal quantum simulators''. Science 273, 1073\u20131078 (1996). doi: 10.1126\/science.273.5278.1073.","DOI":"10.1126\/science.273.5278.1073"},{"key":"3","doi-asserted-by":"publisher","unstructured":"A. Yu. Kitaev. ``Quantum computations: algorithms and error correction''. Russian Mathematical Surveys 52, 1191\u20131249 (1997). doi: 10.1070\/RM1997v052n06ABEH002155.","DOI":"10.1070\/RM1997v052n06ABEH002155"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Sergey B. Bravyi and Alexei Yu. Kitaev. ``Quantum codes on a lattice with boundary'' (1998). doi: 10.48550\/arXiv.quant-ph\/9811052. arXiv:quant-ph\/9811052.","DOI":"10.48550\/arXiv.quant-ph\/9811052"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. ``Surface codes: Towards practical large-scale quantum computation''. Physical Review A 86, 032324 (2012). doi: 10.1103\/PhysRevA.86.032324.","DOI":"10.1103\/PhysRevA.86.032324"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Clare Horsman, Austin G. Fowler, Simon Devitt, and Rodney Van Meter. ``Surface code quantum computing by lattice surgery''. New Journal of Physics 14, 123011 (2012). doi: 10.1088\/1367-2630\/14\/12\/123011.","DOI":"10.1088\/1367-2630\/14\/12\/123011"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Austin G. Fowler and Craig Gidney. ``Low overhead quantum computation using lattice surgery'' (2018). doi: doi.org\/10.48550\/arXiv.1808.06709. arXiv:1808.06709.","DOI":"10.48550\/arXiv.1808.06709"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Michael E. Beverland, Prakash Murali, Matthias Troyer, Krysta M. Svore, Torsten Hoeffler, Vadym Kliuchnikov, Guang Hao Low, Mathias Soeken, Aarthi Sundaram, and Alexander Vaschillo. ``Assessing requirements to scale to practical quantum advantage'' (2022). doi: 10.48550\/arXiv.2211.07629. arXiv:2211.07629.","DOI":"10.48550\/arXiv.2211.07629"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. ``Encoding electronic spectra in quantum circuits with linear t complexity''. Physical Review X 8, 041015 (2018). doi: 10.1103\/PhysRevX.8.041015.","DOI":"10.1103\/PhysRevX.8.041015"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Nobuyuki Yoshioka, Tsuyoshi Okubo, Yasunari Suzuki, Yuki Koizumi, and Wataru Mizukami. ``Hunting for quantum-classical crossover in condensed matter problems''. npj Quantum Information 10, 45 (2024). doi: 10.1038\/s41534-024-00839-4.","DOI":"10.1038\/s41534-024-00839-4"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Ali JavadiAbhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T. Chong, and Margaret Martonosi. ``ScaffCC: A framework for compilation and analysis of quantum computing programs''. In Proceedings of the 11th ACM Conference on Computing Frontiers. CF '14. Association for Computing Machinery (2014). doi: 10.1145\/2597917.2597939.","DOI":"10.1145\/2597917.2597939"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Qiskit contributors. ``Qiskit: An open-source framework for quantum computing''. url: doi.org\/10.5281\/zenodo.2573505.","DOI":"10.5281\/zenodo.2573505"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan. ``t|ket>: a retargetable compiler for NISQ devices''. Quantum Science and Technology 6, 014003 (2020). doi: 10.1088\/2058-9565\/ab8e92.","DOI":"10.1088\/2058-9565\/ab8e92"},{"key":"14","doi-asserted-by":"publisher","unstructured":"George Watkins, Hoang Minh Nguyen, Keelan Watkins, Steven Pearce, Hoi-Kwan Lau, and Alexandru Paler. ``A high performance compiler for very large scale surface code computations''. Quantum 8, 1354 (2024). doi: 10.22331\/q-2024-05-22-1354.","DOI":"10.22331\/q-2024-05-22-1354"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Daniel Herr, Franco Nori, and Simon J. Devitt. ``Optimization of lattice surgery is np-hard''. Npj quantum information 3, 35 (2017). doi: 10.1038\/s41534-017-0035-1.","DOI":"10.1038\/s41534-017-0035-1"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Abtin Molavi, Amanda Xu, Swamit Tannu, and Aws Albarghouthi. ``Compilation for surface code quantum computers'' (2023). doi: 10.48550\/arXiv.2311.18042. arXiv:2311.18042.","DOI":"10.48550\/arXiv.2311.18042"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Daniel Litinski. ``A game of surface codes: Large-scale quantum computing with lattice surgery''. Quantum 3, 128 (2019). doi: 10.22331\/q-2019-03-05-128.","DOI":"10.22331\/q-2019-03-05-128"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Daniel Litinski. ``Magic state distillation: Not as costly as you think''. Quantum 3, 205 (2019). doi: 10.22331\/q-2019-12-02-205.","DOI":"10.22331\/q-2019-12-02-205"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Lingling Lao, Bas van Wee, Imran Ashraf, J. van Someren, Nader Khammassi, Koen Bertels, and Carmen G. Almudever. ``Mapping of lattice surgery-based quantum circuits on surface code architectures''. Quantum Science and Technology 4, 015005 (2018). doi: 10.1088\/2058-9565\/aadd1a.","DOI":"10.1088\/2058-9565\/aadd1a"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Michael Beverland, Vadym Kliuchnikov, and Eddie Schoute. ``Surface code compilation via edge-disjoint paths''. PRX Quantum 3, 020342 (2022). doi: 10.1103\/PRXQuantum.3.020342.","DOI":"10.1103\/PRXQuantum.3.020342"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L. Chuang. ``Hamiltonian simulation by qubitization''. Quantum 3, 163 (2019). doi: 10.22331\/q-2019-07-12-163.","DOI":"10.22331\/q-2019-07-12-163"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Austin G. Fowler, Adam C. Whiteside, and Lloyd C. L. Hollenberg. ``Towards practical classical processing for the surface code''. Physical review letters 108, 180501 (2012). doi: 10.1103\/PhysRevLett.108.180501.","DOI":"10.1103\/PhysRevLett.108.180501"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Rajeev Acharya, Igor Aleiner, Richard Allen, Trond I. Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Juan Atalaya, Ryan Babbush, et al. ``Suppressing quantum errors by scaling a surface code logical qubit''. Nature 614, 676\u2013681 (2023). doi: 10.1038\/s41586-022-05434-1.","DOI":"10.1038\/s41586-022-05434-1"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Benjamin J. Brown, Katharina Laubscher, Markus S. Kesselring, and James R. Wootton. ``Poking holes and cutting corners to achieve clifford gates with the surface code''. Physical Review X 7, 021029 (2017). doi: 10.1103\/PhysRevX.7.021029.","DOI":"10.1103\/PhysRevX.7.021029"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Michael L. Fredman and Robert Endre Tarjan. ``Fibonacci heaps and their uses in improved network optimization algorithms''. J. ACM 34, 596\u2013615 (1987). doi: 10.1145\/28869.28874.","DOI":"10.1145\/28869.28874"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Allyson Silva, Xiangyi Zhang, Zak Webb, Mia Kramer, Chan-Woo Yang, Xiao Liu, Jessica Lemieux, Ka-Wai Chen, Artur Scherer, and Pooya Ronagh. ``Multi-qubit lattice surgery scheduling''. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Pages 1\u20131. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2024). url: doi.org\/10.4230\/lipics.tqc.2024.1.","DOI":"10.4230\/lipics.tqc.2024.1"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Austin G. Fowler. ``Time-optimal quantum computation'' (2012). doi: 10.48550\/arXiv.1210.4626. arXiv:1210.4626.","DOI":"10.48550\/arXiv.1210.4626"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Mingzheng Zhu, Hao Fu, Jun Wu, Chi Zhang, Wei Xie, and Xiang-Yang Li. ``Ecmas: Efficient circuit mapping and scheduling for surface code''. In 2024 IEEE\/ACM International Symposium on Code Generation and Optimization (CGO). Page 158\u2013169. IEEE (2024). doi: 10.1109\/cgo57630.2024.10444874.","DOI":"10.1109\/cgo57630.2024.10444874"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Mingzheng Zhu, Hao Fu, Haishan Song, Jun Wu, Chi Zhang, Wei Xie, and Xiangyang Li. ``Ecmas+: Efficient circuit mapping and scheduling for surface code encoded circuit on quantum cloud platform''. ACM Transactions on Architecture and Code Optimization 22, 1\u201325 (2025). doi: 10.1145\/3760783.","DOI":"10.1145\/3760783"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Google Quantum AI. ``Suppressing quantum errors by scaling a surface code logical qubit''. Nature 614, 676\u2013681 (2023). doi: 10.1038\/s41586-022-05434-1.","DOI":"10.1038\/s41586-022-05434-1"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Google Quantum AI and Collaborators. ``Quantum error correction below the surface code threshold''. Nature 638, 920\u2013926 (2024). doi: 10.1038\/s41586-024-08449-y.","DOI":"10.1038\/s41586-024-08449-y"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Hengyun Zhou, Chen Zhao, Madelyn Cain, Dolev Bluvstein, Nishad Maskara, Casey Duckering, Hong-Ye Hu, Sheng-Tao Wang, Aleksander Kubica, and Mikhail D. Lukin. ``Low-overhead transversal fault tolerance for universal quantum computation''. Nature 646, 303\u2013308 (2025). doi: 10.1038\/s41586-025-09543-5.","DOI":"10.1038\/s41586-025-09543-5"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Craig Gidney, Michael Newman, Peter Brooks, and Cody Jones. ``Yoked surface codes''. Nature Communications 16 (2025). doi: 10.1038\/s41467-025-59714-1.","DOI":"10.1038\/s41467-025-59714-1"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Theodore J. Yoder, Eddie Schoute, Patrick Rall, Emily Pritchett, Jay M. Gambetta, Andrew W. Cross, Malcolm Carroll, and Michael E. Beverland. ``Tour de gross: A modular quantum computer based on bivariate bicycle codes'' (2025). doi: 10.48550\/ARXIV.2506.03094.","DOI":"10.48550\/ARXIV.2506.03094"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Qian Xu, J. Pablo Bonilla Ataides, Christopher A. Pattison, Nithin Raveendran, Dolev Bluvstein, Jonathan Wurtz, Bane Vasi\u0107, Mikhail D. Lukin, Liang Jiang, and Hengyun Zhou. ``Constant-overhead fault-tolerant quantum computation with reconfigurable atom arrays''. Nature Physics 20, 1084\u20131090 (2024). doi: 10.1038\/s41567-024-02479-z.","DOI":"10.1038\/s41567-024-02479-z"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Lawrence Z. Cohen, Isaac H. Kim, Stephen D. Bartlett, and Benjamin J. Brown. ``Low-overhead fault-tolerant quantum computing using long-range connectivity''. Science Advances 8 (2022). doi: 10.1126\/sciadv.abn1717.","DOI":"10.1126\/sciadv.abn1717"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Naomi H Nickerson, Ying Li, and Simon C Benjamin. ``Topological quantum computing with a very noisy network and local error rates approaching one percent''. Nature communications 4, 1756 (2013). url: doi.org\/10.1038\/ncomms2773.","DOI":"10.1038\/ncomms2773"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Hector Bombin, Isaac H Kim, Daniel Litinski, Naomi Nickerson, Mihir Pant, Fernando Pastawski, Sam Roberts, and Terry Rudolph. ``Interleaving: Modular architectures for fault-tolerant photonic quantum computing'' (2021). url: doi.org\/10.48550\/arXiv.2103.08612.","DOI":"10.48550\/arXiv.2103.08612"},{"key":"39","doi-asserted-by":"publisher","unstructured":"J Eli Bourassa, Rafael N Alexander, Michael Vasmer, Ashlesha Patil, Ilan Tzitrin, Takaya Matsuura, Daiqin Su, Ben Q Baragiola, Saikat Guha, Guillaume Dauphinais, et al. ``Blueprint for a scalable photonic fault-tolerant quantum computer''. Quantum 5, 392 (2021). url: doi.org\/10.22331\/q-2021-02-04-392.","DOI":"10.22331\/q-2021-02-04-392"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Christopher Pattison, Gefen Baranes, Juan Pablo Bonilla Ataides, Mikhail D Lukin, and Hengyun Zhou. ``Constant-rate entanglement distillation for fast quantum interconnects''. In Proceedings of the 52nd Annual International Symposium on Computer Architecture. Pages 257\u2013270. (2025). url: doi.org\/10.1145\/3695053.373106.","DOI":"10.1145\/3695053.373106"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Yuya Maeda, Yasunari Suzuki, Toshiki Kobayashi, Takashi Yamamoto, Yuuki Tokunaga, and Keisuke Fujii. ``Logical entanglement distribution between distant 2d array qubits'' (2025). url: doi.org\/10.48550\/arXiv.2503.14894.","DOI":"10.48550\/arXiv.2503.14894"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Christopher Chamberland and Earl T Campbell. ``Universal quantum computing with twist-free and temporally encoded lattice surgery''. PRX Quantum 3, 010331 (2022). url: doi.org\/10.1103\/PRXQuantum.3.010331.","DOI":"10.1103\/PRXQuantum.3.010331"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Matt McEwen, Dave Bacon, and Craig Gidney. ``Relaxing hardware requirements for surface code circuits using time-dynamics''. Quantum 7, 1172 (2023). url: doi.org\/10.22331\/q-2023-11-07-1172.","DOI":"10.22331\/q-2023-11-07-1172"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Michael A Nielsen and Isaac L Chuang. ``Quantum computation and quantum information''. Cambridge university press. (2010). url: doi.org\/10.1017\/CBO9780511976667.","DOI":"10.1017\/CBO9780511976667"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Neil J Ross and Peter Selinger. ``Optimal ancilla-free clifford+ t approximation of z-rotations'' (2014). url: doi.org\/10.48550\/arXiv.1403.2975.","DOI":"10.48550\/arXiv.1403.2975"},{"key":"46","doi-asserted-by":"publisher","unstructured":"David P DiVincenzo. ``Quantum gates and circuits''. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454, 261\u2013276 (1998). url: doi.org\/10.1098\/rspa.1998.0159.","DOI":"10.1098\/rspa.1998.0159"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-04-13-2061\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T17:59:15Z","timestamp":1776103155000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2026-04-13-2061\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,13]]},"references-count":47,"URL":"https:\/\/doi.org\/10.22331\/q-2026-04-13-2061","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,13]]},"article-number":"2061"}}