{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T11:00:24Z","timestamp":1753441224914,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2020,8,27]],"date-time":"2020-08-27T00:00:00Z","timestamp":1598486400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,8,27]],"date-time":"2020-08-27T00:00:00Z","timestamp":1598486400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100007837","name":"Universit\u00e4t Bremen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100007837","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Quantum systems provide a new way of conducting computations based on the so-called qubits. Due to the potential for significant speed-ups, this field received significant research attention in recent years. The Clifford+T library is a very promising and popular gate library for these kinds of computations. Unlike other libraries considered so far, it consists of only a small number of gates for all of which robust, fault-tolerant realizations are known for many technologies that seem to be promising for large-scale quantum computing. As a consequence, (logic) synthesis of Clifford+T quantum circuits became an important research problem. However, previous work in this area has several drawbacks: Corresponding approaches are either only applicable to very small quantum systems or lead to circuits that are far from being optimal. The latter is mainly caused by the fact that current synthesis realizes the desired circuit by a local, i.e.,\u00a0column-wise, consideration of the underlying unitary transformation matrix to be synthesized. In this paper, we analyze the conceptual drawbacks of this approach and propose to overcome them by taking a global view of the matrices and perform a separation of concerns regarding individual synthesis steps. We precisely describe a corresponding algorithm as well as its efficient implementation on top of decision diagrams. Experimental results confirm the resulting benefits and show improvements of up to several orders of magnitudes in costs compared to previous work.<\/jats:p>","DOI":"10.1007\/s11128-020-02816-0","type":"journal-article","created":{"date-parts":[[2020,8,27]],"date-time":"2020-08-27T05:02:26Z","timestamp":1598504546000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Advanced exact synthesis of Clifford+T circuits"],"prefix":"10.1007","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0826-0985","authenticated-orcid":false,"given":"Philipp","family":"Niemann","sequence":"first","affiliation":[]},{"given":"Robert","family":"Wille","sequence":"additional","affiliation":[]},{"given":"Rolf","family":"Drechsler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,27]]},"reference":[{"issue":"6","key":"2816_CR1","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. on CAD 32(6), 818\u2013830 (2013). https:\/\/doi.org\/10.1109\/TCAD.2013.2244643","journal-title":"IEEE Trans. on CAD"},{"key":"2816_CR2","first-page":"3457","volume":"52","author":"A Barenco","year":"1995","unstructured":"Barenco, A., Bennett, C.H., Cleve, R., DiVinchenzo, D., Margolus, N., Shor, P., Sleator, T., Smolin, J., Weinfurter, H.: Elementary gates for quantum computation. Am. Phys. Soc. 52, 3457\u20133467 (1995)","journal-title":"Am. Phys. Soc."},{"issue":"8","key":"2816_CR3","doi-asserted-by":"publisher","first-page":"080502","DOI":"10.1103\/PhysRevLett.114.080502","volume":"114","author":"A Bocharov","year":"2015","unstructured":"Bocharov, A., Roetteler, M., Svore, K.M.: Efficient synthesis of universal repeat-until-success quantum circuits. Phys. Rev. Lett. 114(8), 080502 (2015)","journal-title":"Phys. Rev. Lett."},{"issue":"3","key":"2816_CR4","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/S0020-0190(00)00084-3","volume":"75","author":"PO Boykin","year":"2000","unstructured":"Boykin, P.O., Mor, T., Pulver, M., Roychowdhury, V., Vatan, F.: A new universal and fault-tolerant quantum basis. Inf. Process. Lett. 75(3), 101\u2013107 (2000)","journal-title":"Inf. Process. Lett."},{"key":"2816_CR5","doi-asserted-by":"publisher","unstructured":"Brayton, R., Mishchenko, A.: ABC: An academic industrial-strength verification tool. In: Computer Aided Verification, pp. 24\u201340 (2010). https:\/\/doi.org\/10.1007\/978-3-642-14295-6_5","DOI":"10.1007\/978-3-642-14295-6_5"},{"issue":"8","key":"2816_CR6","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"RE Bryant","year":"1986","unstructured":"Bryant, R.E.: Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35(8), 677\u2013691 (1986)","journal-title":"IEEE Trans. Comput."},{"key":"2816_CR7","doi-asserted-by":"crossref","unstructured":"Burgholzer, L., Wille, R.: Improved DD-based equivalence checking of quantum circuits. In: ASP Design Automation Conference, pp. 127\u2013132 (2020)","DOI":"10.1109\/ASP-DAC47756.2020.9045153"},{"key":"2816_CR8","doi-asserted-by":"crossref","unstructured":"Burgholzer, L., Wille, R.: Advanced equivalence checking for quantum circuits. arXiv:2004.08420 (2020)","DOI":"10.1109\/ASP-DAC47756.2020.9045153"},{"issue":"1","key":"2816_CR9","first-page":"81","volume":"6","author":"CM Dawson","year":"2006","unstructured":"Dawson, C.M., Nielsen, M.A.: The solovay-kitaev algorithm. Quantum Info. Comput. 6(1), 81\u201395 (2006)","journal-title":"Quantum Info. Comput."},{"issue":"1","key":"2816_CR10","doi-asserted-by":"publisher","first-page":"015003","DOI":"10.1088\/2058-9565\/1\/1\/015003","volume":"1","author":"O Di Matteo","year":"2016","unstructured":"Di Matteo, O., Mosca, M.: Parallelizing quantum circuit synthesis. Quantum Sci. Technol. 1(1), 015003 (2016)","journal-title":"Quantum Sci. Technol."},{"key":"2816_CR11","doi-asserted-by":"publisher","first-page":"052312","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, 052312 (2009). https:\/\/doi.org\/10.1103\/PhysRevA.80.052312","journal-title":"Phys. Rev. A"},{"issue":"3","key":"2816_CR12","doi-asserted-by":"publisher","first-page":"032332","DOI":"10.1103\/PhysRevA.87.032332","volume":"87","author":"B Giles","year":"2013","unstructured":"Giles, B., Selinger, P.: Exact synthesis of multiqubit Clifford+T circuits. Phys. Rev. A 87(3), 032332 (2013). https:\/\/doi.org\/10.1103\/PhysRevA.87.032332","journal-title":"Phys. Rev. A"},{"issue":"15\u201316","key":"2816_CR13","first-page":"1261","volume":"14","author":"D Gosset","year":"2014","unstructured":"Gosset, D., Kliuchnikov, V., Mosca, M., Russo, V.: An algorithm for the t-count. Quantum Info. Comput. 14(15\u201316), 1261\u20131276 (2014)","journal-title":"Quantum Info. Comput."},{"key":"2816_CR14","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"issue":"11","key":"2816_CR15","doi-asserted-by":"publisher","first-page":"2317","DOI":"10.1109\/TCAD.2006.871622","volume":"25","author":"P Gupta","year":"2006","unstructured":"Gupta, P., Agrawal, A., Jha, N.K.: An algorithm for synthesis of reversible logic circuits. IEEE Trans. CAD 25(11), 2317\u20132330 (2006)","journal-title":"IEEE Trans. CAD"},{"issue":"4","key":"2816_CR16","doi-asserted-by":"publisher","first-page":"55:1","DOI":"10.1145\/3064834","volume":"13","author":"M Houshmand","year":"2017","unstructured":"Houshmand, M., Sedighi, M., Zamani, M.S., Marjoei, K.: Quantum circuit synthesis targeting to improve one-way quantum computation pattern cost metrics. J. Emerg. Technol. Comput. Syst. 13(4), 55:1\u201355:27 (2017). https:\/\/doi.org\/10.1145\/3064834","journal-title":"J. Emerg. Technol. Comput. Syst."},{"key":"2816_CR17","unstructured":"Jones, N.C.: Logic synthesis for fault-tolerant quantum computers. arXiv:1310.7290 (2013)"},{"issue":"48","key":"2816_CR18","doi-asserted-by":"publisher","first-page":"18681","DOI":"10.1073\/pnas.0808245105","volume":"105","author":"I Kassal","year":"2008","unstructured":"Kassal, I., Jordan, S.P., Love, P.J., Mohseni, M., Aspuru-Guzik, A.: Polynomial-time quantum algorithm for the simulation of chemical dynamics. Proc. Natl. Acad. Sci. 105(48), 18681\u201318686 (2008)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"2816_CR19","unstructured":"Kliuchnikov, V., Bocharov, A., Roetteler, M., Yard, J.: A framework for approximating qubit unitaries. arXiv:1510.03888 (2015)"},{"issue":"19","key":"2816_CR20","doi-asserted-by":"publisher","first-page":"190502","DOI":"10.1103\/PhysRevLett.110.190502","volume":"110","author":"V Kliuchnikov","year":"2013","unstructured":"Kliuchnikov, V., Maslov, D., Mosca, M.: Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits. Phys. Rev. Lett. 110(19), 190502 (2013)","journal-title":"Phys. Rev. Lett."},{"issue":"7\u20138","key":"2816_CR21","first-page":"607","volume":"13","author":"V Kliuchnikov","year":"2013","unstructured":"Kliuchnikov, V., Maslov, D., Mosca, M.: Fast and efficient exact synthesis of single-qubit unitaries generated by Clifford and T gates. Quantum Inf. Comput. 13(7\u20138), 607\u2013630 (2013)","journal-title":"Quantum Inf. Comput."},{"issue":"6","key":"2816_CR22","doi-asserted-by":"publisher","first-page":"1350","DOI":"10.1109\/TVLSI.2013.2269869","volume":"22","author":"C Lin","year":"2014","unstructured":"Lin, C., Chakrabarti, A., Jha, N.K.: FTQLS: fault-tolerant quantum logic synthesis. IEEE Trans. VLSI Syst. 22(6), 1350\u20131363 (2014). https:\/\/doi.org\/10.1109\/TVLSI.2013.2269869","journal-title":"IEEE Trans. VLSI Syst."},{"key":"2816_CR23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813870","volume-title":"Quantum Computer Science: An Introduction","author":"ND Mermin","year":"2007","unstructured":"Mermin, N.D.: Quantum Computer Science: An Introduction. Cambridge University Press, Cambridge (2007)"},{"key":"2816_CR24","doi-asserted-by":"crossref","unstructured":"Miller, D.M., Wille, R., Sasanian, Z.: Elementary quantum gate realizations for multiple-control Toffolli gates. In: Int\u2019l Symposium on Multi-Valued Logic, pp. 288\u2013293 (2011)","DOI":"10.1109\/ISMVL.2011.54"},{"key":"2816_CR25","volume-title":"Quantum Computation and Quantum Information","author":"M Nielsen","year":"2000","unstructured":"Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"2816_CR26","doi-asserted-by":"crossref","unstructured":"Niemann, P., Wille, R., Drechsler, R.: Efficient synthesis of quantum circuits implementing Clifford group operations. In: ASP Design Automation Conference, pp. 483\u2013488 (2014)","DOI":"10.1109\/ASPDAC.2014.6742938"},{"key":"2816_CR27","doi-asserted-by":"crossref","unstructured":"Niemann, P., Wille, R., Drechsler, R.: Equivalence checking in multi-level quantum systems. In: Reversible Computation, pp. 201\u2013215 (2014)","DOI":"10.1007\/978-3-319-08494-7_16"},{"key":"2816_CR28","doi-asserted-by":"crossref","unstructured":"Niemann, P., Wille, R., Drechsler, R.: Improved synthesis of Clifford+T quantum functionality. In: Design, Automation and Test in Europe, pp. 597\u2013600 (2018)","DOI":"10.23919\/DATE.2018.8342078"},{"issue":"1","key":"2816_CR29","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1109\/TCAD.2015.2459034","volume":"35","author":"P Niemann","year":"2016","unstructured":"Niemann, P., Wille, R., Miller, D.M., Thornton, M.A., Drechsler, R.: QMDDs: Efficient quantum function representation and manipulation. IEEE Trans. CAD 35(1), 86\u201399 (2016). https:\/\/doi.org\/10.1109\/TCAD.2015.2459034","journal-title":"IEEE Trans. CAD"},{"key":"2816_CR30","unstructured":"Russell, T.: The exact synthesis of 1- and 2-qubit Clifford+T circuits. ArXiv e-prints (2014)"},{"issue":"3&4","key":"2816_CR31","first-page":"262","volume":"11","author":"M Saeedi","year":"2011","unstructured":"Saeedi, M., Arabzadeh, M., Zamani, M.S., Sedighi, M.: Block-based quantum-logic synthesis. Quantum Inf. Comput. 11(3&4), 262\u2013277 (2011)","journal-title":"Quantum Inf. Comput."},{"issue":"4","key":"2816_CR32","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/1877745.1877747","volume":"6","author":"M Saeedi","year":"2010","unstructured":"Saeedi, M., Zamani, M.S., Sedighi, M., Sasanian, Z.: Synthesis of reversible circuit using cycle-based approach. J. Emerg. Technol. Comput. Syst. 6(4), 13 (2010)","journal-title":"J. Emerg. Technol. Comput. Syst."},{"issue":"6","key":"2816_CR33","doi-asserted-by":"publisher","first-page":"1000","DOI":"10.1109\/TCAD.2005.855930","volume":"25","author":"VV Shende","year":"2006","unstructured":"Shende, V.V., Bullock, S.S., Markov, I.L.: Synthesis of quantum-logic circuits. IEEE Trans. CAD 25(6), 1000\u20131010 (2006)","journal-title":"IEEE Trans. CAD"},{"issue":"6","key":"2816_CR34","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. CAD 22(6), 710\u2013722 (2003)","journal-title":"IEEE Trans. CAD"},{"key":"2816_CR35","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Foundations of Computer Science pp. 124\u2013134 (1994)"},{"key":"2816_CR36","doi-asserted-by":"crossref","unstructured":"Soeken, M., Wille, R., Hilken, C., Przigoda, N., Drechsler, R.: Synthesis of reversible circuits with minimal lines for large functions. In: ASP Design Automation Conference, pp. 85\u201392 (2012)","DOI":"10.1109\/ASPDAC.2012.6165069"},{"issue":"1&2","key":"2816_CR37","first-page":"87","volume":"16","author":"J Welch","year":"2016","unstructured":"Welch, J., Bocharov, A., Svore, K.M.: Efficient approximation of diagonal unitaries over the Clifford+T basis. Quantum Inf. Comput. 16(1&2), 87\u2013104 (2016)","journal-title":"Quantum Inf. Comput."},{"key":"2816_CR38","unstructured":"We have winners! ...of the IBM qiskit developer challenge. https:\/\/www.ibm.com\/blogs\/research\/2018\/08\/winners-qiskit-developer-challenge\/. Accessed: 2020-02-20"},{"key":"2816_CR39","doi-asserted-by":"crossref","unstructured":"Wille, R., Gro\u00dfe, D., Miller, D.M., Drechsler, R.: Equivalence checking of reversible circuits. In: Int\u2019l Symposium on Multi-Valued Logic, pp. 324\u2013330 (2009)","DOI":"10.1109\/ISMVL.2009.19"},{"key":"2816_CR40","doi-asserted-by":"crossref","unstructured":"Wille, R., Gro\u00dfe, D., Teuber, L., Dueck, G.W., Drechsler, R.: RevLib: an online resource for reversible functions and reversible circuits. In: Int\u2019l Symposium on Multi-Valued Logic, pp. 220\u2013225 (2008). RevLib is available at http:\/\/www.revlib.org","DOI":"10.1109\/ISMVL.2008.43"},{"key":"2816_CR41","doi-asserted-by":"crossref","unstructured":"Wille, R., Soeken, M., Otterstedt, C., Drechsler, R.: Improving the mapping of reversible circuits to quantum circuits using multiple target lines. In: ASP Design Automation Conference, pp. 85\u201392 (2013)","DOI":"10.1109\/ASPDAC.2013.6509587"},{"issue":"9&10","key":"2816_CR42","first-page":"721","volume":"10","author":"S Yamashita","year":"2010","unstructured":"Yamashita, S., Markov, I.L.: Fast equivalence - checking for quantum circuits. Quantum Inf. Comput. 10(9&10), 721\u2013734 (2010)","journal-title":"Quantum Inf. Comput."},{"key":"2816_CR43","doi-asserted-by":"crossref","unstructured":"Zulehner, A., Wille, R.: Improving synthesis of reversible circuits: Exploiting redundancies in paths and nodes of QMDDs. In: Reversible Computation, pp. 232\u2013247 (2017)","DOI":"10.1007\/978-3-319-59936-6_18"},{"issue":"5","key":"2816_CR44","first-page":"996","volume":"37","author":"A Zulehner","year":"2017","unstructured":"Zulehner, A., Wille, R.: One-pass design of reversible circuits: Combining embedding and synthesis for reversible logic. IEEE Trans. CAD 37(5), 996\u20131008 (2017)","journal-title":"IEEE Trans. CAD"},{"issue":"5","key":"2816_CR45","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1109\/TCAD.2018.2834427","volume":"38","author":"A Zulehner","year":"2019","unstructured":"Zulehner, A., Wille, R.: Advanced simulation of quantum computations. IEEE Trans. CAD 38(5), 848\u2013859 (2019)","journal-title":"IEEE Trans. CAD"},{"key":"2816_CR46","doi-asserted-by":"crossref","unstructured":"Zulehner, A., Wille, R.: Compiling SU(4) quantum circuits to IBM QX architectures. In: ASP Design Automation Conference, pp. 185\u2013190 (2019)","DOI":"10.1145\/3287624.3287704"},{"key":"2816_CR47","doi-asserted-by":"crossref","unstructured":"Zulehner, A., Wille, R.: Matrix-vector vs. matrix-matrix multiplication: Potential in DD-based simulation of quantum computations. In: Design, Automation and Test in Europe, pp. 90\u201395 (2019)","DOI":"10.23919\/DATE.2019.8714836"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-020-02816-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-020-02816-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-020-02816-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,27]],"date-time":"2021-08-27T00:06:13Z","timestamp":1630022773000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-020-02816-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,27]]},"references-count":47,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["2816"],"URL":"https:\/\/doi.org\/10.1007\/s11128-020-02816-0","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2020,8,27]]},"assertion":[{"value":"16 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"317"}}