{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T18:29:48Z","timestamp":1769020188477,"version":"3.49.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T00:00:00Z","timestamp":1697500800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T00:00:00Z","timestamp":1697500800000},"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) grant funded by the Korea government(Ministry of Science and IC","award":["2019-0-00033"],"award-info":[{"award-number":["2019-0-00033"]}]},{"name":"National Research Foundation of Korea (NRF) funded by the Korean governmen","award":["RS-2023-00256221"],"award-info":[{"award-number":["RS-2023-00256221"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a method for efficient mixed polarity multiple controlled Toffoli (MPMCT) gate decomposition from the perspective of a cost metric related to Toffoli gates, namely Toffoli-depth. When using the technique presented in a previous study, there is a range in which Toffoli-depth (consequently T-depth) of the implemented circuit increases proportionally as the number of provided (clean) work qubits increases. In other words, using the previous technique may result in more inefficient MPMCT gates even though the number of helpful work qubits has increased. In this work, a technique is devised to provide sufficient help from clean work qubits at the central part of the implemented circuit as many as possible, thereby addressing the issues with the previous technique. Meanwhile, one of the representative algorithms that use MPMCT gates is Grover\u2019s algorithm. We show the implementation results for MPMCT gates according to the number of work qubits, using Grover\u2019s algorithm as an example. It is experimentally demonstrated that T-depth decreases much more quickly when using our method than the previous method.<\/jats:p>","DOI":"10.1007\/s11128-023-04142-7","type":"journal-article","created":{"date-parts":[[2023,10,17]],"date-time":"2023-10-17T08:02:08Z","timestamp":1697529728000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["MPMCT gate decomposition method reducing T-depth quickly in proportion to the number of work qubits"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3493-7278","authenticated-orcid":false,"given":"Jongheon","family":"Lee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yousung","family":"Kang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"You-Seok","family":"Lee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boheung","family":"Chung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dooho","family":"Choi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,17]]},"reference":[{"key":"4142_CR1","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"},{"key":"4142_CR2","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":"4142_CR3","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 Inf. Secur. (2022)","DOI":"10.1007\/978-3-031-08896-4_20"},{"issue":"10","key":"4142_CR4","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":"4","key":"4142_CR5","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"},{"key":"4142_CR6","unstructured":"Baker, J.M., Duckering, C., Hoover, A., Chong, F.T.: Decomposing quantum generalized toffoli with an arbitrary number of ancilla. arXiv:1904.01671 (2019)"},{"key":"4142_CR7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139034807","volume-title":"Quantum Error Correction","author":"DA Lidar","year":"2013","unstructured":"Lidar, D.A., Brun, T.A.: Quantum Error Correction. Cambridge University Press, Cambridge (2013)"},{"issue":"5","key":"4142_CR8","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.80.052312","volume":"80","author":"AG Fowler","year":"2009","unstructured":"Fowler, A.G., Stephens, A.M., Groszkowski, P.: High-threshold universal quantum computation on the surface code. Phys. Rev. A 80(5), 052312 (2009)","journal-title":"Phys. Rev. A"},{"issue":"12","key":"4142_CR9","doi-asserted-by":"publisher","first-page":"1","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), 1\u201339 (2018)","journal-title":"Quantum Inf. Process."},{"issue":"6","key":"4142_CR10","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":"4142_CR11","unstructured":"Lee, J.: A study on t-depth and toffoli-depth reduction techniques for efficient quantum circuit designs and their applications to hash functions. Ph.D. thesis, University of Science & Technology (2023)"},{"key":"4142_CR12","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":"4142_CR13","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":"4142_CR14","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"},{"issue":"1","key":"4142_CR15","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":"6","key":"4142_CR16","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."},{"key":"4142_CR17","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"},{"key":"4142_CR18","unstructured":"Cruz, P.M., Murta, B.: Shallow unitary decompositions of quantum fredkin and toffoli gates for connectivity-aware equivalent circuit averaging. arXiv:2305.18128 (2023)"},{"key":"4142_CR19","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"},{"issue":"5","key":"4142_CR20","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":"4142_CR21","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":"4142_CR22","doi-asserted-by":"crossref","unstructured":"Nielsen, M.A., Chuang, I.: Quantum computation and quantum information. Am. Assoc. Phys. Teachers (2002)","DOI":"10.1119\/1.1463744"},{"issue":"6","key":"4142_CR23","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1109\/TCAD.2003.811448","volume":"22","author":"VV Shende","year":"2003","unstructured":"Shende, V.V., Prasad, A.K., Markov, I.L., Hayes, J.P.: Synthesis of reversible logic circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 22(6), 710\u2013722 (2003)","journal-title":"IEEE Trans. Comput. Aided Des. Integr. Circuits Syst."},{"key":"4142_CR24","unstructured":"Gidney, C.: StackExchange: Creating bigger controlled nots from single qubit, Toffoli, and CNOT gates, without workspace. 2015. https:\/\/cs.stackexchange.com\/questions\/40933\/creating-bigger-controlled-nots-from-single-qubit-toffoli-and-cnot-gates-with (2015)"},{"key":"4142_CR25","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)"}],"updated-by":[{"DOI":"10.1007\/s11128-023-04172-1","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2023,11,27]],"date-time":"2023-11-27T00:00:00Z","timestamp":1701043200000}}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-023-04142-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-023-04142-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-023-04142-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T07:13:25Z","timestamp":1701155605000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-023-04142-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,17]]},"references-count":25,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2023,10]]}},"alternative-id":["4142"],"URL":"https:\/\/doi.org\/10.1007\/s11128-023-04142-7","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s11128-023-04172-1","asserted-by":"object"}]},"ISSN":["1573-1332"],"issn-type":[{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,17]]},"assertion":[{"value":"9 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 October 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 November 2023","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s11128-023-04172-1","URL":"https:\/\/doi.org\/10.1007\/s11128-023-04172-1","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"The software implementation for the suggested algorithm used to produce the circuits with optimized Toffoli-depth is not publicly available.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}],"article-number":"381"}}