{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T03:58:57Z","timestamp":1773374337842,"version":"3.50.1"},"reference-count":21,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T00:00:00Z","timestamp":1615766400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/M013472\/1"],"award-info":[{"award-number":["EP\/M013472\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/T001011\/1"],"award-info":[{"award-number":["EP\/T001011\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","award":["200020-165843"],"award-info":[{"award-number":["200020-165843"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We consider the task of breaking down a quantum computation given as an isometry into C-NOTs and single-qubit gates, while keeping the number of C-NOT gates small. Although several decompositions are known for general isometries, here we focus on a method based on Householder reflections that adapts well in the case of sparse isometries. We show how to use this method to decompose an arbitrary isometry before illustrating that the method can lead to significant improvements in the case of sparse isometries. We also discuss the classical complexity of this method and illustrate its effectiveness in the case of sparse state preparation by applying it to randomly chosen sparse states.<\/jats:p>","DOI":"10.22331\/q-2021-03-15-412","type":"journal-article","created":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T18:00:21Z","timestamp":1615831221000},"page":"412","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":41,"title":["Quantum Circuits for Sparse Isometries"],"prefix":"10.22331","volume":"5","author":[{"given":"Emanuel","family":"Malvetti","sequence":"first","affiliation":[{"name":"Department of Chemistry, Technische Universit\u00e4t M\u00fcnchen, Lichtenbergstra\u00dfe 4, 85747 Garching, Germany"}]},{"given":"Raban","family":"Iten","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, 8093 Z\u00fcrich, Switzerland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3591-0576","authenticated-orcid":false,"given":"Roger","family":"Colbeck","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of York, YO10 5DD, UK"}]}],"member":"9598","published-online":{"date-parts":[[2021,3,15]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, ``Elementary gates for quantum computation,'' Phys. Rev. A 52, 3457\u20133467 (1995).","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"1","doi-asserted-by":"publisher","unstructured":"V. V. Shende, I. L. Markov, and S. S. Bullock, ``Minimal universal two-qubit controlled-not-based circuits,'' Phys. Rev. A 69, 062321 (2004).","DOI":"10.1103\/PhysRevA.69.062321"},{"key":"2","doi-asserted-by":"publisher","unstructured":"V. V. Shende, I. L. Markov, and S. S. Bullock, ``Smaller two-qubit circuits for quantum communication and computation,'' in Proceedings Design, Automation and Test in Europe Conference and Exhibition, Vol. 2 (2004) pp. 980\u2013985.","DOI":"10.1109\/DATE.2004.1269020"},{"key":"3","doi-asserted-by":"publisher","unstructured":"V. V. Shende, S. S. Bullock, and I. L. Markov, ``Synthesis of quantum-logic circuits,'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000\u20131010 (2006).","DOI":"10.1109\/TCAD.2005.855930"},{"key":"4","doi-asserted-by":"publisher","unstructured":"M. Plesch and \u010c. Brukner, ``Quantum-state preparation with universal gate decompositions,'' Phys. Rev. A 83, 032302 (2011).","DOI":"10.1103\/PhysRevA.83.032302"},{"key":"5","doi-asserted-by":"publisher","unstructured":"V. Bergholm, J. J. Vartiainen, M. M\u00f6tt\u00f6nen, and M. M. Salomaa, ``Quantum circuits with uniformly controlled one-qubit gates,'' Phys. Rev. A 71, 052330 (2005).","DOI":"10.1103\/PhysRevA.71.052330"},{"key":"6","doi-asserted-by":"publisher","unstructured":"R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, ``Quantum circuits for isometries,'' Phys. Rev. A 93, 032318 (2016a).","DOI":"10.1103\/PhysRevA.93.032318"},{"key":"7","unstructured":"E. Knill, ``Approximation by quantum circuits,'' e-print arXiv:quant-ph\/9508006 (1995)."},{"key":"8","doi-asserted-by":"publisher","unstructured":"R. Iten, R. Colbeck, and M. Christandl, ``Quantum circuits for quantum channels,'' Physical Review A 95, 052316 (2016b).","DOI":"10.1103\/PhysRevA.95.052316"},{"key":"9","unstructured":"R. Iten, O. Reardon-Smith, L. Mondada, E. Redmond, R. Singh Kohli, and R. Colbeck, ``Introduction to UniversalQCompiler,'' e-print arXiv:1904.01072 (2019)."},{"key":"10","doi-asserted-by":"publisher","unstructured":"V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, ``Synthesis of reversible logic circuits,'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 22, 710\u2013722 (2003).","DOI":"10.1109\/TCAD.2003.811448"},{"key":"11","doi-asserted-by":"publisher","unstructured":"S. P. Jordan and P. Wocjan, ``Efficient quantum circuits for arbitrary sparse unitaries,'' Phys. Rev. A 80, 062301 (2009).","DOI":"10.1103\/PhysRevA.80.062301"},{"key":"12","unstructured":"V. Kliuchnikov, ``Synthesis of unitaries with Clifford+T circuits,'' e-print arXiv:1306.3200 (2013)."},{"key":"13","doi-asserted-by":"publisher","unstructured":"T. G. de Brugi\u00e8re, M. Baboulin, B. Valiron, and C. Allouche, ``Quantum circuits synthesis using Householder transformations,'' Computer Physics Communications 248, 107001 (2020).","DOI":"10.1016\/j.cpc.2019.107001"},{"key":"14","doi-asserted-by":"publisher","unstructured":"D. Maslov, ``Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization,'' Phys. Rev. A 93, 022311 (2016).","DOI":"10.1103\/PhysRevA.93.022311"},{"key":"15","doi-asserted-by":"publisher","unstructured":"A. S. Householder, ``Unitary triangularization of a nonsymmetric matrix,'' J. ACM 5, 339\u2013342 (1958).","DOI":"10.1145\/320941.320947"},{"key":"16","doi-asserted-by":"publisher","unstructured":"P. A. Ivanov, E. S. Kyoseva, and N. V. Vitanov, ``Engineering of arbitrary $\\mathrm{U}(n)$ transformations by quantum Householder reflections,'' Phys. Rev. A 74, 022323 (2006).","DOI":"10.1103\/PhysRevA.74.022323"},{"key":"17","doi-asserted-by":"publisher","unstructured":"B. Torosov, E. Kyoseva, and N. Vitanov, ``Fault-tolerant composite Householder reflection,'' Journal of Physics B: Atomic 48, 135502 (2015).","DOI":"10.1088\/0953-4075\/48\/13\/135502"},{"key":"18","unstructured":"S. Fenner, ``Implementing the fanout gate by a Hamiltonian,'' e-print arXiv:quant-ph\/0309163 (2003)."},{"key":"19","unstructured":"P. Heggernes and P. Matstoms, ``Finding good column orderings for sparse QR factorization,'' in Second SIAM Conference on Sparse Matrices (1996)."},{"key":"20","unstructured":"C. Gidney, ``Factoring with $n+2$ clean qubits and $n-1$ dirty qubits,'' e-print arXiv:1706.07884 (2017)."}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-03-15-412\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T18:00:49Z","timestamp":1615831249000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-03-15-412\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,15]]},"references-count":21,"URL":"https:\/\/doi.org\/10.22331\/q-2021-03-15-412","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,15]]},"article-number":"412"}}