{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T08:18:38Z","timestamp":1770970718617,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T00:00:00Z","timestamp":1768867200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T00:00:00Z","timestamp":1768867200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Institute of Information & communications Technology Planning & Evaluation (IITP) of Korea","award":["RS-2019-II190033"],"award-info":[{"award-number":["RS-2019-II190033"]}]},{"name":"Electronics and Telecommunications Research Institute, South Korea","award":["25ZS1320"],"award-info":[{"award-number":["25ZS1320"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    One of the key operations in various quantum algorithms, including Grover\u2019s algorithm, is the multi-controlled Toffoli (MCT) gate. This work proposes optimal design techniques for the MCT gate using the conditionally clean ancillae strategy, assuming that an arbitrary number of clean ancillae are available. We consider two primary cases: first, when only a single clean ancilla is available; and second, when the number of clean ancillae is\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {O}(n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:italic>n<\/jats:italic>\n                    is the number of controls in the MCT gate. For the case of a single clean ancilla, we propose a novel design method that achieves better efficiency compared to a previous approach. While prior work yields a Toffoli-depth of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {O}(n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , our proposed method reduces the Toffoli-depth to\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\mathcal {O}(\\sqrt{n})$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:msqrt>\n                              <mml:mi>n<\/mml:mi>\n                            <\/mml:msqrt>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Moreover, by employing this new technique as a subroutine within previously proposed methods for the cases of two or three clean ancillae, we demonstrate both logically and empirically an improvement in time complexity. Additionally, prior work addressed optimal designs only when the number of clean ancillae was up to approximately\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\log n$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , without providing efficient strategies beyond this regime. In this study, we also present efficient MCT gate constructions when a sufficiently large number of clean ancillae are available. We confirm, both theoretically and empirically, that the Toffoli-depth decreases as the number of clean ancillae increases. In conclusion, this work highlights that the optimal MCT design strategy depends on the availability of clean ancillae. It also indirectly suggests a threshold point at which the optimal design strategy transitions, depending on the number of ancillae provided.\n                  <\/jats:p>","DOI":"10.1007\/s11128-026-05056-w","type":"journal-article","created":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T13:59:18Z","timestamp":1768917558000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Logarithmic-depth MCT gate implementation method on a given arbitrary number of clean ancillae"],"prefix":"10.1007","volume":"25","author":[{"given":"Jongheon","family":"Lee","sequence":"first","affiliation":[]},{"given":"Yousung","family":"Kang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,20]]},"reference":[{"key":"5056_CR1","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"issue":"5","key":"5056_CR2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.67.052307","volume":"67","author":"N Shenvi","year":"2003","unstructured":"Shenvi, N., Kempe, J., Whaley, K.B.: Quantum random-walk search algorithm. Phys. Rev. A 67(5), 052307 (2003)","journal-title":"Phys. Rev. A"},{"issue":"1","key":"5056_CR3","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A Ambainis","year":"2007","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210\u2013239 (2007)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5056_CR4","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.79.012325","volume":"79","author":"V Poto\u010dek","year":"2009","unstructured":"Poto\u010dek, V., G\u00e1bris, A., Kiss, T., Jex, I.: Optimized quantum random-walk search algorithms on the hypercube. Phys. Rev. A 79(1), 012325 (2009)","journal-title":"Phys. Rev. A"},{"key":"5056_CR5","doi-asserted-by":"crossref","unstructured":"Abdessaied, N., Amy, M., Soeken, M., Drechsler, R.: Technology mapping of reversible circuits to clifford+ t quantum circuits. In: 2016 IEEE 46th International Symposium on Multiple-valued Logic (ISMVL), pp. 150\u2013155. IEEE (2016)","DOI":"10.1109\/ISMVL.2016.33"},{"issue":"12","key":"5056_CR6","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s11128-018-2107-3","volume":"17","author":"P Kim","year":"2018","unstructured":"Kim, P., Han, D., Jeong, K.C.: Time-space complexity of quantum search algorithms in symmetric cryptanalysis: applying to aes and sha-2. Quantum Inf. Process. 17(12), 339 (2018)","journal-title":"Quantum Inf. Process."},{"issue":"10","key":"5056_CR7","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s11128-023-04142-7","volume":"22","author":"J Lee","year":"2023","unstructured":"Lee, J., Kang, Y., Lee, Y.-S., Chung, B., Choi, D.: Mpmct gate decomposition method reducing t-depth quickly in proportion to the number of work qubits. Quantum Inf. Process. 22(10), 381 (2023)","journal-title":"Quantum Inf. Process."},{"issue":"5","key":"5056_CR8","doi-asserted-by":"publisher","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","volume":"52","author":"A Barenco","year":"1995","unstructured":"Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457 (1995)","journal-title":"Phys. Rev. A"},{"key":"5056_CR9","volume-title":"Quantum Computation and Quantum Information","author":"MA Nielsen","year":"2002","unstructured":"Nielsen, M.A., Chuang, I.: Quantum Computation and Quantum Information. American Association of Physics Teachers (2002)"},{"key":"5056_CR10","doi-asserted-by":"crossref","unstructured":"Miller, D.M., Wille, R., Sasanian, Z.: Elementary quantum gate realizations for multiple-control toffoli gates. In: 2011 41st IEEE International Symposium on Multiple-Valued Logic, pp. 288\u2013293. IEEE (2011)","DOI":"10.1109\/ISMVL.2011.54"},{"key":"5056_CR11","doi-asserted-by":"publisher","first-page":"2350","DOI":"10.1007\/s10773-017-3389-4","volume":"56","author":"Y He","year":"2017","unstructured":"He, Y., Luo, M.-X., Zhang, E., Wang, H.-K., Wang, X.-F.: Decompositions of n-qubit toffoli gates with linear circuit complexity. Int. J. Theor. Phys. 56, 2350\u20132361 (2017)","journal-title":"Int. J. Theor. Phys."},{"key":"5056_CR12","doi-asserted-by":"crossref","unstructured":"Niemann, P., Gupta, A., Drechsler, R.: T-depth optimization for fault-tolerant quantum circuits. In: 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL), pp. 108\u2013113. IEEE (2019)","DOI":"10.1109\/ISMVL.2019.00027"},{"key":"5056_CR13","unstructured":"Baker, J.M., Duckering, C., Hoover, A., Chong, F.T.: Decomposing quantum generalized toffoli with an arbitrary number of ancilla. arXiv preprint arXiv:1904.01671 (2019)"},{"issue":"1","key":"5056_CR14","doi-asserted-by":"publisher","first-page":"5886","DOI":"10.1038\/s41467-024-50065-x","volume":"15","author":"B Claudon","year":"2024","unstructured":"Claudon, B., Zylberman, J., Feniou, C., Debbasch, F., Peruzzo, A., Piquemal, J.-P.: Polylogarithmic-depth controlled-not gates without ancilla qubits. Nat. Commun. 15(1), 5886 (2024)","journal-title":"Nat. Commun."},{"key":"5056_CR15","unstructured":"Nie, J., Zi, W., Sun, X.: Quantum circuit for multi-qubit toffoli gate with optimal resource. arXiv preprint arXiv:2402.05053 (2024)"},{"key":"5056_CR16","doi-asserted-by":"crossref","unstructured":"Khattar, T., Gidney, C.: Rise of conditionally clean ancillae for optimizing quantum circuits. arXiv preprint arXiv:2407.17966 (2024)","DOI":"10.22331\/q-2025-05-21-1752"},{"key":"5056_CR17","doi-asserted-by":"crossref","unstructured":"Dutta, S., Wang, S., Baksi, A., Chattopadhyay, A., Maitra, S.: On exact space-depth trade-offs in multi-controlled toffoli decomposition. arXiv preprint arXiv:2502.01433 (2025)","DOI":"10.1103\/PhysRevA.111.052611"},{"issue":"4","key":"5056_CR18","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.87.042302","volume":"87","author":"P Selinger","year":"2013","unstructured":"Selinger, P.: Quantum circuits of t-depth one. Phys. Rev. A 87(4), 042302 (2013)","journal-title":"Phys. Rev. A"},{"issue":"10","key":"5056_CR19","doi-asserted-by":"publisher","first-page":"1476","DOI":"10.1109\/TCAD.2014.2341953","volume":"33","author":"M Amy","year":"2014","unstructured":"Amy, M., Maslov, D., Mosca, M.: Polynomial-time t-depth optimization of clifford+ t circuits via matroid partitioning. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 33(10), 1476\u20131489 (2014)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"issue":"1","key":"5056_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1038\/s41534-018-0072-4","volume":"4","author":"Y Nam","year":"2018","unstructured":"Nam, Y., Ross, N.J., Su, Y., Childs, A.M., Maslov, D.: Automated optimization of large quantum circuits with continuous parameters. Npj Quantum Inf. 4(1), 23 (2018)","journal-title":"Npj Quantum Inf."},{"key":"5056_CR21","doi-asserted-by":"crossref","unstructured":"Lee, J., Lee, S., Lee, Y.-S., Choi, D.: T-depth reduction method for efficient sha-256 quantum circuit construction. IET Information Security (2022)","DOI":"10.1007\/978-3-031-08896-4_20"},{"issue":"6","key":"5056_CR22","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.100.062326","volume":"100","author":"L Biswal","year":"2019","unstructured":"Biswal, L., Bhattacharjee, D., Chattopadhyay, A., Rahaman, H.: Techniques for fault-tolerant decomposition of a multicontrolled toffoli gate. Phys. Rev. A 100(6), 062326 (2019)","journal-title":"Phys. Rev. A"},{"key":"5056_CR23","doi-asserted-by":"crossref","unstructured":"Jaques, S., Naehrig, M., Roetteler, M., Virdia, F.: Implementing grover oracles for quantum key search on aes and lowmc. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 280\u2013310. Springer (2020)","DOI":"10.1007\/978-3-030-45724-2_10"},{"issue":"2","key":"5056_CR24","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/s11128-021-03398-1","volume":"21","author":"J Ha","year":"2022","unstructured":"Ha, J., Lee, J., Heo, J.: Resource analysis of quantum computing with noisy qubits for shor\u2019s factoring algorithms. Quantum Inf. Process. 21(2), 60 (2022)","journal-title":"Quantum Inf. Process."},{"issue":"4","key":"5056_CR25","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s11128-024-04365-2","volume":"23","author":"J Lee","year":"2024","unstructured":"Lee, J., Kang, Y., Lee, Y.-S., Chung, B., Choi, D.: Toffoli-depth reduction method preserving in-place quantum circuits and its application to sha3-256. Quantum Inf. Process. 23(4), 153 (2024)","journal-title":"Quantum Inf. Process."},{"issue":"6","key":"5056_CR26","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1109\/TCAD.2013.2244643","volume":"32","author":"M Amy","year":"2013","unstructured":"Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 32(6), 818\u2013830 (2013)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"issue":"2","key":"5056_CR27","doi-asserted-by":"publisher","first-page":"304","DOI":"10.4218\/etrij.2021-0442","volume":"45","author":"K-S Jin","year":"2023","unstructured":"Jin, K.-S., Cha, G.-I.: Qplayer: lightweight, scalable, and fast quantum simulator. ETRI J. 45(2), 304\u2013317 (2023)","journal-title":"ETRI J."},{"key":"5056_CR28","unstructured":"Gidney, C.: Why is an oracle qubit necessary in Grover\u2019s algorithm? https:\/\/quantumcomputing.stackexchange.com\/questions\/2145\/why-is-an-oracle-qubit-necessary-in-grovers-algorithm (2018)"},{"key":"5056_CR29","doi-asserted-by":"crossref","unstructured":"Dang, Q.: Fips 180-4, secure hash standard. Federal Information Processing Standards (NIST FIPS), National Institute of Standards and Technology, Gaithersburg, MD (2012)","DOI":"10.1080\/01611194.2012.687431"},{"key":"5056_CR30","volume-title":"Sha-3 Standard: Permutation-Based Hash and Extendable-Output Functions","author":"MJ Dworkin","year":"2015","unstructured":"Dworkin, M.J., et al.: Sha-3 Standard: Permutation-Based Hash and Extendable-Output Functions. US Department of Commerce, National Institute of Standards and Technology (NIST) (2015)"},{"key":"5056_CR31","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Guan, Z., Zhang, H.: An algorithm of optimization for linear nearest neighbor quantum circuits by parallel processing. In: 2018 Eighth International Conference on Instrumentation & Measurement, Computer, Communication and Control (IMCCC), pp. 1046\u20131050. IEEE (2018)","DOI":"10.1109\/IMCCC.2018.00218"},{"key":"5056_CR32","doi-asserted-by":"crossref","unstructured":"Datta, K., Kole, A., Sengupta, I., Drechsler, R.: Nearest neighbor mapping of quantum circuits to two-dimensional hexagonal qubit architecture. In: 2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL), pp. 35\u201342. IEEE (2022)","DOI":"10.1109\/ISMVL52857.2022.00013"},{"key":"5056_CR33","doi-asserted-by":"crossref","unstructured":"Duckering, C., Baker, J.M., Litteken, A., Chong, F.T.: Orchestrated trios: compiling for efficient communication in quantum programs with 3-qubit gates. In: Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 375\u2013385 (2021)","DOI":"10.1145\/3445814.3446718"},{"key":"5056_CR34","unstructured":"Cruz, P.M., Murta, B.: Shallow unitary decompositions of quantum fredkin and toffoli gates for connectivity-aware equivalent circuit averaging. arXiv preprint arXiv:2305.18128 (2023)"},{"key":"5056_CR35","doi-asserted-by":"publisher","first-page":"79","DOI":"10.22331\/q-2018-08-06-79","volume":"2","author":"J Preskill","year":"2018","unstructured":"Preskill, J.: Quantum computing in the nisq era and beyond. Quantum 2, 79 (2018)","journal-title":"Quantum"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-026-05056-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-026-05056-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-026-05056-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T07:26:00Z","timestamp":1770967560000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-026-05056-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,20]]},"references-count":35,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,1]]}},"alternative-id":["5056"],"URL":"https:\/\/doi.org\/10.1007\/s11128-026-05056-w","relation":{},"ISSN":["1573-1332"],"issn-type":[{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,20]]},"assertion":[{"value":"13 May 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 January 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This study used publicly available data, and no ethical approval or informed consent was required.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}},{"value":"We declare that we have no financial or non-financial Conflict of interest relevant to the content of this article.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable. This study does not contain any identifiable personal data requiring consent for publication.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}},{"value":"The software implementation for the suggested algorithm in the article is not publicly available.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code Availability"}}],"article-number":"33"}}