Quantum Circuits for Sparse Isometries

Emanuel Malvetti; Raban Iten; Roger Colbeck

doi:10.22331/q-2021-03-15-412

Quantum Circuits for Sparse Isometries

Emanuel Malvetti¹, Raban Iten², and Roger Colbeck³

¹Department of Chemistry, Technische Universität München, Lichtenbergstraße 4, 85747 Garching, Germany
²ETH Zürich, 8093 Zürich, Switzerland
³Department of Mathematics, University of York, YO10 5DD, UK

Published:	2021-03-15, volume 5, page 412
Eprint:	arXiv:2006.00016v2
Doi:	https://doi.org/10.22331/q-2021-03-15-412
Citation:	Quantum 5, 412 (2021).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

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.

Featured image: CNOT count for sparse state preparation decompositions of $n$ qubit states with $2^s$ non-zero entries.

Popular summary

In order to realise a quantum computation on a quantum computer it is useful to break it down into a sequence of elementary gates. The number of elementary gates required for an arbitrary quantum computation scales exponentially in the number of qubits the computation acts on. However, useful quantum computations often come from a much smaller class and hence we would like decomposition methods that can exploit additional structure. In this work we introduce decomposition schemes that work on the set of sparse computations, showing that the number of elementary gates required dramatically decreases with the sparseness. Minimizing the number of elementary gates is particularly important for near term quantum devices, since each additional gate adds noise to the computation. We optimize our decomposition schemes for sparse computations on such devices, i.e., for a small number of qubits. The decomposition schemes have been implemented in UniversalQCompiler, an open source software package for compiling quantum computations.

► BibTeX data

@article{Malvetti2021quantumcircuits,
  doi = {10.22331/q-2021-03-15-412},
  url = {https://doi.org/10.22331/q-2021-03-15-412},
  title = {Quantum {C}ircuits for {S}parse {I}sometries},
  author = {Malvetti, Emanuel and Iten, Raban and Colbeck, Roger},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {412},
  month = mar,
  year = {2021}
}

► References

[1] 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–3467 (1995).
https://doi.org/10.1103/PhysRevA.52.3457

[2] V. V. Shende, I. L. Markov, and S. S. Bullock, ``Minimal universal two-qubit controlled-not-based circuits,'' Phys. Rev. A 69, 062321 (2004).
https://doi.org/10.1103/PhysRevA.69.062321

[3] 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–985.
https://doi.org/10.1109/DATE.2004.1269020

[4] 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–1010 (2006).
https://doi.org/10.1109/TCAD.2005.855930

[5] M. Plesch and Č. Brukner, ``Quantum-state preparation with universal gate decompositions,'' Phys. Rev. A 83, 032302 (2011).
https://doi.org/10.1103/PhysRevA.83.032302

[6] V. Bergholm, J. J. Vartiainen, M. Möttönen, and M. M. Salomaa, ``Quantum circuits with uniformly controlled one-qubit gates,'' Phys. Rev. A 71, 052330 (2005).
https://doi.org/10.1103/PhysRevA.71.052330

[7] R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, ``Quantum circuits for isometries,'' Phys. Rev. A 93, 032318 (2016a).
https://doi.org/10.1103/PhysRevA.93.032318

[8] E. Knill, ``Approximation by quantum circuits,'' e-print arXiv:quant-ph/9508006 (1995).
arXiv:quant-ph/9508006

[9] R. Iten, R. Colbeck, and M. Christandl, ``Quantum circuits for quantum channels,'' Physical Review A 95, 052316 (2016b).
https://doi.org/10.1103/PhysRevA.95.052316

[10] R. Iten, O. Reardon-Smith, L. Mondada, E. Redmond, R. Singh Kohli, and R. Colbeck, ``Introduction to UniversalQCompiler,'' e-print arXiv:1904.01072 (2019).
arXiv:1904.01072

[11] 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–722 (2003).
https://doi.org/10.1109/TCAD.2003.811448

[12] S. P. Jordan and P. Wocjan, ``Efficient quantum circuits for arbitrary sparse unitaries,'' Phys. Rev. A 80, 062301 (2009).
https://doi.org/10.1103/PhysRevA.80.062301

[13] V. Kliuchnikov, ``Synthesis of unitaries with Clifford+T circuits,'' e-print arXiv:1306.3200 (2013).
arXiv:1306.3200

[14] T. G. de Brugière, M. Baboulin, B. Valiron, and C. Allouche, ``Quantum circuits synthesis using Householder transformations,'' Computer Physics Communications 248, 107001 (2020).
https://doi.org/10.1016/j.cpc.2019.107001

[15] D. Maslov, ``Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization,'' Phys. Rev. A 93, 022311 (2016).
https://doi.org/10.1103/PhysRevA.93.022311

[16] A. S. Householder, ``Unitary triangularization of a nonsymmetric matrix,'' J. ACM 5, 339–342 (1958).
https://doi.org/10.1145/320941.320947

[17] 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).
https://doi.org/10.1103/PhysRevA.74.022323

[18] B. Torosov, E. Kyoseva, and N. Vitanov, ``Fault-tolerant composite Householder reflection,'' Journal of Physics B: Atomic 48, 135502 (2015).
https://doi.org/10.1088/0953-4075/48/13/135502

[19] S. Fenner, ``Implementing the fanout gate by a Hamiltonian,'' e-print arXiv:quant-ph/0309163 (2003).
arXiv:quant-ph/0309163

[20] P. Heggernes and P. Matstoms, ``Finding good column orderings for sparse QR factorization,'' in Second SIAM Conference on Sparse Matrices (1996).

[21] C. Gidney, ``Factoring with $n+2$ clean qubits and $n-1$ dirty qubits,'' e-print arXiv:1706.07884 (2017).
arXiv:1706.07884

Cited by

[1] Debora Ramacciotti, Andreea I. Lefterovici, and Antonio F. Rotundo, "Simple quantum algorithm to efficiently prepare sparse states", Physical Review A 110 3, 032609 (2024).

[2] Kin Man Lai and Xin Wang, "Group sparse matrix optimization for efficient quantum state transformation", Physical Review A 110 2, 022445 (2024).

[3] Fereshte Mozafari, Giovanni De Micheli, and Yuxiang Yang, "Efficient deterministic preparation of quantum states using decision diagrams", Physical Review A 106 2, 022617 (2022).

[4] José Alex de Carvalho and Adenilton José da Silva, Anais do I Simpósio Brasileiro de Computação e Comunicação Quânticas (SBCCQ 2026) 155 (2026).

[5] Israel F Araujo, Hyeondo Oh, Nayeli A Rodríguez-Briones, and Daniel K Park, "Schmidt quantum compressor", Quantum Science and Technology 10 3, 035016 (2025).

[6] Davide Orsucci and Vedran Dunjko, "On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number", Quantum 5, 573 (2021).

[7] Ananda Roy, Sameer Erramilli, and Robert M. Konik, "Efficient quantum circuits based on the quantum natural gradient", Physical Review Research 6 4, 043083 (2024).

[8] S S Gayathri, R. Kumar, and Samiappan Dhanalakshmi, "Efficient Floating-point Division Quantum Circuit using Newton-Raphson Division", Journal of Physics: Conference Series 2335 1, 012058 (2022).

[9] Hanyu Wang, Daniel Bochen Tan, and Jason Cong, Proceedings of the 43rd IEEE/ACM International Conference on Computer-Aided Design 1 (2024) ISBN:9798400710773.

[10] Kin Man Lai and Xin Wang, "Optimizing quantum transformation matrices: Block decomposition approach for efficient gate reduction", Physical Review A 111 4, 042613 (2025).

[11] Josh Green and Jingbo Wang, "Quantum encoding of functions and images with matrix product states", Physical Review A 113 5, 052616 (2026).

[12] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan, "Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications", Physical Review Letters 129 23, 230504 (2022).

[13] Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari, and Ryan Babbush, "Quartic Quantum Speedups for Planted Inference", Physical Review X 15 2, 021077 (2025).

[14] Cyrill Bösch, Malte Schade, Giacomo Aloisi, Scott D. Keating, and Andreas Fichtner, "Quantum wave simulation with sources and loss functions", Physical Review Research 7 3, 033225 (2025).

[15] Priyanka Mukhopadhyay, "CS-count-optimal quantum circuits for arbitrary multi-qubit unitaries", Scientific Reports 14 1, 13916 (2024).

[16] Yuan Shi, Kristin M. Beck, Veronika Anneliese Kruse, and Stephen B. Libby, "Preparing angular momentum eigenstates using engineered quantum walks", Physical Review A 110 6, 062214 (2024).

[17] Lin Zeng, Yan Chang, Xuejian Zhang, Weifeng Xue, Shibin Zhang, Lili Yan, and Zhijian Gou, "Distributed machine learning based on quantum cloud with quantum homomorphic encryption", Future Generation Computer Systems 175, 108053 (2026).

[18] Rod Rofougaran, Ralph Wang, Akshay Ajagekar, and Fengqi You, "Encoding proteins as quantum states with approximate quantum state preparation by iterated sparse state preparation", Quantum Science and Technology 10 2, 025029 (2025).

[19] Ben Zindorf and Sougato Bose, "Efficient implementation of multicontrolled quantum gates", Physical Review Applied 24 4, 044030 (2025).

[20] Yanqi Song, Jing Li, Yusen Wu, Sujuan Qin, Qiaoyan Wen, and Fei Gao, "A resource-efficient quantum convolutional neural network", Frontiers in Physics 12, 1362690 (2024).

[21] Marko J. Rančić, "Noisy intermediate-scale quantum computing algorithm for solving an n -vertex MaxCut problem with log( n ) qubits", Physical Review Research 5 1, L012021 (2023).

[22] Tiago M. L. de Veras, Leon D. da Silva, and Adenilton J. da Silva, "Double sparse quantum state preparation", Quantum Information Processing 21 6, 204 (2022).

[23] Hanyu Wang, Jason Cong, and Giovanni De Micheli, 2024 Design, Automation & Test in Europe Conference & Exhibition (DATE) 1 (2024) ISBN:978-3-9819263-8-5.

[24] Israel F. Araujo, Carsten Blank, Ismael C. S. Araújo, and Adenilton J. da Silva, "Low-Rank Quantum State Preparation", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 43 1, 161 (2024).

[25] Kouhei Nakaji, Shumpei Uno, Yohichi Suzuki, Rudy Raymond, Tamiya Onodera, Tomoki Tanaka, Hiroyuki Tezuka, Naoki Mitsuda, and Naoki Yamamoto, "Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicators", Physical Review Research 4 2, 023136 (2022).

[26] Priyanka Mukhopadhyay, "Synthesis of V-count-optimal quantum circuits for multiqubit unitaries", Physical Review A 109 5, 052619 (2024).

[27] Andriy Miranskyy, Mushahid Khan, and Udson Mendes, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 234 (2024) ISBN:979-8-3315-4137-8.

[28] Xuejian Zhang, Yan Chang, Lin Zeng, Weifeng Xue, Lili Yan, and Shibin Zhang, "Universal and holistic privacy protection in quantum computing: a novel approach through quantum circuit equivalence homomorphic encryption", Quantum Science and Technology 9 4, 045043 (2024).

[29] Rui Mao, Guojing Tian, and Xiaoming Sun, "Toward optimal circuit size for sparse quantum state preparation", Physical Review A 110 3, 032439 (2024).

[30] Donya Sadat Rezaeishad and Foroogh Sadat Tabataba, "Scalable photonic quantum processing via isometric energy-conserving transformations: bridging hybrid optical modes", Optics Continuum 4 11, 2501 (2025).

[31] Seon-Geun Jeong, Kyeong-Hwan Moon, and Won-Joo Hwang, "Hybrid quantum neural networks for efficient protein-ligand binding affinity prediction", EPJ Quantum Technology 12 1, 120 (2025).

[32] Vittorio Pagni, Gary Schmiedinghoff, Kevin Lively, Michael Epping, and Michael Felderer, 2025 IEEE International Conference on Quantum Computing and Engineering (QCE) 230 (2025) ISBN:979-8-3315-5736-2.

[33] Yunya Liu, Jiakun Liu, Jordan R. Raney, and Pai Wang, "Quantum computing for solid mechanics and structural engineering – A demonstration with Variational Quantum Eigensolver", Extreme Mechanics Letters 67, 102117 (2024).

[34] Vadym Kliuchnikov, Kristin Lauter, Romy Minko, Adam Paetznick, and Christophe Petit, "Shorter quantum circuits via single-qubit gate approximation", Quantum 7, 1208 (2023).

[35] Shamminuj Aktar, Andreas Bartschi, Abdel-Hameed A. Badawy, and Stephan Eidenbenz, "A Divide-and-Conquer Approach to Dicke State Preparation", IEEE Transactions on Quantum Engineering 3, 1 (2022).

[36] Vlad Gheorghiu, Michele Mosca, and Priyanka Mukhopadhyay, "T-count and T-depth of any multi-qubit unitary", npj Quantum Information 8 1, 141 (2022).

[37] Jefferson D. S. Silva, Thiago Melo D. Azevedo, Israel F. Araujo, and Adenilton J. da Silva, "Linear Decomposition of Approximate Multicontrolled Single Qubit Gates", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 44 4, 1304 (2025).

[38] Mihael Erakovic, Freek Witteveen, Dylan Harley, Jakob Günther, Moritz Bensberg, Oinam Romesh Meitei, Minsik Cho, Troy Van Voorhis, Markus Reiher, and Matthias Christandl, "High Ground State Overlap via Quantum Embedding Methods", PRX Life 3 1, 013003 (2025).

[39] Carsten Blank and Francesco Petruccione, "1. Quantum Applications - Fachbeitrag: Vielversprechend: Monte-Carlo-ähnliche Methoden auf dem Quantencomputer ", Digitale Welt 5 4, 40 (2021).

[40] Vladimir V. Arsoski, "Multi-controlled single-qubit unitary gates based on the quantum Fourier transform and deep decomposition", The Journal of Supercomputing 81 11, 1202 (2025).

[41] Lingdong Meng, Ziyang Li, and Panchi Li, "Design of Quantum Associative Classifier based on Hamming Distance and Grover’s Algorithm", International Journal of Theoretical Physics 63 2, 33 (2024).

[42] Calvin Ku, Yu-Cheng Chen, Alice Hu, and Min-Hsiu Hsieh, "Optimizing quantum chemistry simulations with a hybrid quantization scheme", Communications Physics 9 1, 148 (2026).

[43] Alvin Gonzales, Rebekah Herrman, Colin Campbell, Igor Gaidai, Ji Liu, Teague Tomesh, and Zain H. Saleem, "Efficient sparse state preparation via quantum walks", npj Quantum Information 11 1, 143 (2025).

[44] Guangyi Li, Yu Gan, Zeguan Wu, Xueyue Zhang, Zheshen Zhang, and Junyu Liu, "Stab-QRAM: A Clifford-Only Quantum Oracle for Affine Boolean Data", arXiv:2509.26494, (2025).

[45] Luca Cappelli, Claudio Sanavio, Alessandro Andrea Zecchi, Giuseppe Murante, and Sauro Succi, "Quantum Algorithm for the Fixed-Radius Neighbor Search", arXiv:2507.03445, (2025).

[46] Lvzhou Li and Jingquan Luo, "Nearly Optimal Circuit Size for Sparse Quantum State Preparation", arXiv:2406.16142, (2024).

[47] Renaud Vilmart, Sunheang Ty, and Chetra Mang, "Resource-Efficient Synthesis of Sparse Quantum States", arXiv:2508.05386, (2025).

[48] Vladimir V. Arsoski, "Multi-controlled single-qubit unitary gates based on the quantum Fourier transform and deep decomposition", arXiv:2408.00935, (2024).

[49] Gekko Budiutama, Shunsuke Daimon, Xinchi Huang, Hirofumi Nishi, and Yu-ichiro Matsushita, "Approximate Amplitude Encoding with the Adaptive Interpolating Quantum Transform", arXiv:2603.03803, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 22:47:25) and SAO/NASA ADS (last updated successfully 2026-08-09 22:47:28). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.