{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T12:10:26Z","timestamp":1771243826166,"version":"3.50.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2027,1,2]],"date-time":"2027-01-02T00:00:00Z","timestamp":1798848000000},"content-version":"vor","delay-in-days":325,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["OMA-2016245"],"award-info":[{"award-number":["OMA-2016245"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Toffoli gates are key building blocks in quantum programs, and on most current quantum computers, they must be implemented with smaller gates. Such an implementation requires five 2-qubit gates if we assume that each gate can operate on any two qubits. However, many current quantum computers have only 2-qubit gates that operate on neighboring qubits; we call them neighbor gates. How many neighbor gates are required to implement a Toffoli gate? In this article, we show that six neighbor gates are necessary and sufficient, and we generalize to a characterization of all 3-qubit diagonal gates.<\/jats:p>","DOI":"10.1145\/3787463","type":"journal-article","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T21:04:06Z","timestamp":1767387846000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Toffoli Requires Six Quantum Neighbor Gates"],"prefix":"10.1145","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-9104-0621","authenticated-orcid":false,"given":"Keli","family":"Huang","sequence":"first","affiliation":[{"name":"Computer Science, University of California, Los Angeles","place":["Los Angeles, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4747-365X","authenticated-orcid":false,"given":"Jens","family":"Palsberg","sequence":"additional","affiliation":[{"name":"Computer Science, University of California, Los Angeles","place":["Los Angeles, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,11]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry Craig Gidney Mario Motta Jarrod R. McClean and Ryan Babbush. 2019. Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization. Quantum 3 (2019) 208. DOI:10.22331\/q-2019-12-02-208","DOI":"10.22331\/q-2019-12-02-208"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry Yuan Su Casper Gyurik Robbie King Joao Basso Alexander Del Toro Barba Abhishek Rajput Nathan Wiebe Vedran Dunjko and Ryan Babbush. 2024. Analyzing prospects for quantum advantage in topological data analysis. PRX Quantum 5 1 (2024) 010319. DOI:10.1103\/PRXQuantum.5.010319","DOI":"10.1103\/PRXQuantum.5.010319"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISVLSI.2018.00063"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","unstructured":"Kuan-Yu Chang and Chun-Yi Lee. 2021. Mapping nearest neighbor compliant quantum circuits onto a 2-D hexagonal architecture. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 41 10 (2021) 3373\u20133386. DOI:10.1109\/TCAD.2021.3127868","DOI":"10.1109\/TCAD.2021.3127868"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640386"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.18420\/inf2022_94"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISMVL52857.2022.00013"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3445814.3446718"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","unstructured":"Azim Farghadan and Naser Mohammadzadeh. 2017. Quantum circuit physical design flow for 2D nearest-neighbor architectures. International Journal of Circuit Theory and Applications 45 7 (2017) 989\u20131000. DOI:10.1002\/cta.2335","DOI":"10.1002\/cta.2335"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","unstructured":"Joshua J. Goings Alec White Joonho Lee Christofer S. Tautermann Matthias Degroote Craig Gidney Toru Shiozaki Ryan Babbush and Nicholas C. Rubin. 2022. Reliably assessing the electronic structure of cytochrome P450 on today\u2019s classical computers and tomorrow\u2019s quantum computers. Proceedings of the National Academy of Sciences 119 38 (2022) e2203533119. DOI:10.1073\/pnas.2203533119","DOI":"10.1073\/pnas.2203533119"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","unstructured":"Wakaki Hattori and Shigeru Yamashita. 2019. Mapping a quantum circuit to 2D nearest neighbor architecture by changing the gate order. IEICE TRANSACTIONS on Information and Systems 102 11 (2019) 2127\u20132134. DOI:10.1587\/transinf.2018EDP7439","DOI":"10.1587\/transinf.2018EDP7439"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139020411"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","unstructured":"Joonho Lee Dominic W. Berry Craig Gidney William J. Huggins Jarrod R. McClean Nathan Wiebe and Ryan Babbush. 2021. Even more efficient quantum computations of chemistry through tensor hypercontraction. PRX Quantum 2 3 (2021) 030305. DOI:10.1103\/PRXQuantum.2.030305","DOI":"10.1103\/PRXQuantum.2.030305"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","unstructured":"Christopher C. Paige and Musheng Wei. 1994. History and generality of the CS decomposition. Linear Algebra Appl. 208 (1994) 303\u2013326. DOI:10.1016\/0024-3795(94)90446-4","DOI":"10.1016\/0024-3795(94)90446-4"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","unstructured":"Jens Palsberg and Nengkun Yu. 2024. Optimal implementation of quantum gates with two controls. Linear Algebra Appl. (2024). DOI:10.1016\/j.laa.2024.03.039","DOI":"10.1016\/j.laa.2024.03.039"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","unstructured":"Byeongyong Park and Doyeol Ahn. 2023. Reducing CNOT count in quantum Fourier transform for the linear nearest-neighbor architecture. Scientific Reports 13 1 (2023) 8638. DOI:10.1038\/s41598-023-35625-3","DOI":"10.1038\/s41598-023-35625-3"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","unstructured":"Nicholas C. Rubin Dominic W. Berry Alina Kononov Fionn D. Malone Tanuj Khattar Alec White Joonho Lee Hartmut Neven Ryan Babbush and Andrew D. Baczewski. 2024. Quantum computation of stopping power for inertial fusion target design. Proceedings of the National Academy of Sciences 121 23 (2024) e2317772121. DOI:10.1073\/pnas.2317772121","DOI":"10.1073\/pnas.2317772121"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120725.1120847"},{"key":"e_1_3_2_20_1","unstructured":"Vivek V. Shende and Igor L. Markov. 2008. On the CNOT-cost of TOFFOLI gates. arXiv:0803.2316. Retrieved from https:\/\/arxiv.org\/abs\/0803.23166"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","unstructured":"Yuan Su Dominic W. Berry Nathan Wiebe Nicholas Rubin and Ryan Babbush. 2021. Fault-tolerant quantum simulations of chemistry in first quantization. PRX Quantum 2 4 (2021) 040332. DOI:10.1103\/PRXQuantum.2.040332","DOI":"10.1103\/PRXQuantum.2.040332"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2014.6742939"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","unstructured":"Nengkun Yu Runyao Duan and Mingsheng Ying. 2013. Five two-qubit gates are necessary for implementing toffoli gate. Physical Review A (2013). DOI:10.1103\/PhysRevA.88.010304","DOI":"10.1103\/PhysRevA.88.010304"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","unstructured":"Nengkun Yu and Mingsheng Ying. 2015. Optimal simulation of Deutsch gates and the Fredkin gate. Physical Review A (2015). DOI:10.1103\/PhysRevA.91.032302","DOI":"10.1103\/PhysRevA.91.032302"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","unstructured":"Peng Zhao Peng Xu Dong Lan Xinsheng Tan Haifeng Yu and Yang Yu. 2020. Switchable next-nearest-neighbor coupling for controlled two-qubit operations. Physical Review Applied 14 6 (2020) 064016. DOI:10.1103\/PhysRevApplied.14.064016","DOI":"10.1103\/PhysRevApplied.14.064016"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3787463","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3787463","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,16]],"date-time":"2026-02-16T11:23:58Z","timestamp":1771241038000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3787463"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,11]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3787463"],"URL":"https:\/\/doi.org\/10.1145\/3787463","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,11]]},"assertion":[{"value":"2025-02-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-14","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}