Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth

Chunlin Yang; Zexian Li; Hongmei Yao; Zhaobing Fan; Guofeng Zhang; Jianshe Liu

doi:10.22331/q-2025-07-22-1805

Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth

Chunlin Yang¹, Zexian Li², Hongmei Yao¹, Zhaobing Fan¹, Guofeng Zhang², and Jianshe Liu³

¹School of Mathematical and Sciences, Harbin Engineering University, China
²Department of Applied Mathematics, The Hong Kong Polytechnic University, China
³College of Underwater Acoustic Engineering, Harbin Engineering University, China

Published:	2025-07-22, volume 9, page 1805
Editor:	Jin-Peng Liu
Eprint:	arXiv:2405.18007v6
Doi:	https://doi.org/10.22331/q-2025-07-22-1805
Citation:	Quantum 9, 1805 (2025).

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

Updated after initial publication: This publication was updated to version v6 after the initial publication. The authors left the following comment on the arXiv:

26 pages, 8 figures

Abstract

Block encoding severs as an important data input model in quantum algorithms, enabling quantum computers to simulate non-unitary operators effectively. In this paper, we propose an efficient block-encoding protocol for sparse matrices based on a novel data structure, called the dictionary data structure, which classifies all non-zero elements according to their values and indices. Non-zero elements with the same values, lacking common column and row indices, belong to the same classification in our block-encoding protocol's dictionary. When compiled into the $\textit{{U(2), CNOT}}$ gate set, the protocol queries a $2^n \times 2^n$ sparse matrix with $s$ non-zero elements at a circuit depth of $\mathcal{O}(\log(ns))$, utilizing $\mathcal{O}(n^2s)$ ancillary qubits. This offers an exponential improvement in circuit depth relative to the number of system qubits, compared to existing methods [1,2] with a circuit depth of $\mathcal{O}(n)$. Moreover, in our protocol, the subnormalization, a scaled factor that influences the measurement probability of ancillary qubits, is minimized to $\sum_{l=0}^{s_0}\vert A_l\vert$, where $s_0$ denotes the number of classifications in the dictionary and $A_l$ represents the value of the $l$-th classification. Furthermore, we show that our protocol connects to linear combinations of unitaries (LCU) and the sparse access input model (SAIM). To demonstrate the practical utility of our approach, we provide several applications, including Laplacian matrices in graph problems and discrete differential operators.

Popular summary

End-to-end complexity analysis is a central challenge in quantum computing, particularly in addressing the input-output problem. Block encoding has emerged as a key data input model for quantum algorithms, enabling efficient computation. Drawing inspiration from classical multithreaded algorithms, the development of low-depth block encoding protocols is critical for establishing quantum advantage over classical parallel approaches. However, efficiently block encoding sparse matrices with low circuit depth and low subnormalization factor remains a significant hurdle.

To overcome this challenge, we introduce a novel unified dictionary data structure that generalizes and extends existing sparse matrix block-encoding methods. Using this framework, we design a dictionary-based block encoding that achieves substantially improved time complexity. Our theoretical analysis reveals a fundamental scaling law: the required circuit depth scales logarithmically with both the Hilbert space dimension ($\mathcal{O}(\log n)$ for $N=2^n$) and the sparsity ($\mathcal{O}(\log s)$). We demonstrate the protocol’s practical utility through applications in graph problems, 2D discrete Laplacian operators, and ocean acoustic generalized eigenvalue problems (GEPs).

► BibTeX data

@article{Yang2025dictionarybased,
  doi = {10.22331/q-2025-07-22-1805},
  url = {https://doi.org/10.22331/q-2025-07-22-1805},
  title = {Dictionary-based {B}lock {E}ncoding of {S}parse {M}atrices with {L}ow {S}ubnormalization and {C}ircuit {D}epth},
  author = {Yang, Chunlin and Li, Zexian and Yao, Hongmei and Fan, Zhaobing and Zhang, Guofeng and Liu, Jianshe},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1805},
  month = jul,
  year = {2025}
}

► References

[1] B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng. Quantum resources required to block-encode a matrix of classical data. IEEE Transactions on Quantum Engineering, 3: 1–23, 2022. 10.1109/TQE.2022.3231194.
https://doi.org/10.1109/TQE.2022.3231194

[2] Xiaoming Zhang and Xiao Yuan. Circuit complexity of quantum access models for encoding classical data. npj Quantum Information, page 42, 2024. 10.1038/s41534-024-00835-8.
https://doi.org/10.1038/s41534-024-00835-8

[3] David Deutsch and Richard Jozsa. Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 439 (1907): 553–558, 1992. 10.1098/rspa.1992.0167.
https://doi.org/10.1098/rspa.1992.0167

[4] P. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994. 10.1109/SFCS.1994.365700.
https://doi.org/10.1109/SFCS.1994.365700

[5] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters, 103 (15): 150502, 2009. 10.1103/PhysRevLett.103.150502.
https://doi.org/10.1103/PhysRevLett.103.150502

[6] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, page 193–204, 2019. 10.1145/3313276.3316366.
https://doi.org/10.1145/3313276.3316366

[7] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse hamiltonians. Communications in Mathematical Physics, 2007. 10.1007/s00220-006-0150-x.
https://doi.org/10.1007/s00220-006-0150-x

[8] Andrew M. Childs and Robin Kothari. Simulating sparse hamiltonians with star decompositions. In Theory of Quantum Computation, Communication, and Cryptography, pages 94–103, 2011. 10.1007/978-3-642-18073-6_8.
https://doi.org/10.1007/978-3-642-18073-6_8

[9] Andrew M. Childs. On the relationship between continuous- and discrete-time quantum walk. Communications in Mathematical Physics, pages 581–603, 2010. 10.1007/s00220-009-0930-1.
https://doi.org/10.1007/s00220-009-0930-1

[10] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse hamiltonians. In Proceedings of the forty-sixth annual ACM symposium on Theory of computing, 2014. 10.1145/2591796.2591854.
https://doi.org/10.1145/2591796.2591854

[11] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46 (6): 1920–1950, 2017. 10.1137/16M1087072.
https://doi.org/10.1137/16M1087072

[12] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: Improved regression techniques via faster hamiltonian simulation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132, pages 33:1–33:14, 2019. 10.4230/LIPIcs.ICALP.2019.33.
https://doi.org/10.4230/LIPIcs.ICALP.2019.33

[13] Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, and Nathan Wiebe. Exponential quantum speedup in simulating coupled classical oscillators. Physical Review X, 13: 041041, 2023a. 10.1103/PhysRevX.13.041041.
https://doi.org/10.1103/PhysRevX.13.041041

[14] Long Gui-Lu. General quantum interference principle and duality computer. Communications in Theoretical Physics, 45 (5): 825, 2006. 10.1088/0253-6102/45/5/013.
https://doi.org/10.1088/0253-6102/45/5/013

[15] Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, (11–12): 901–924, 2012. 10.26421/QIC12.11-12-1.
https://doi.org/10.26421/QIC12.11-12-1

[16] John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Grand unification of quantum algorithms. PRX quantum, 2 (4): 040203, 2021. 10.1103/PRXQuantum.2.040203.
https://doi.org/10.1103/PRXQuantum.2.040203

[17] Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3: 163, 2019. 10.22331/q-2019-07-12-163.
https://doi.org/10.22331/q-2019-07-12-163

[18] Joran van Apeldoorn and András Gilyén. Improvements in Quantum SDP-Solving with Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132, pages 99:1–99:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. 10.4230/LIPIcs.ICALP.2019.99.
https://doi.org/10.4230/LIPIcs.ICALP.2019.99

[19] Quynh T. Nguyen, Bobak T. Kiani, and Seth Lloyd. Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra. Quantum, 6: 876, 2022. 10.22331/q-2022-12-13-876.
https://doi.org/10.22331/q-2022-12-13-876

[20] Haoya Li, Hongkang Ni, and Lexing Ying. On efficient quantum block encoding of pseudo-differential operators. Quantum, 7: 1031, 2023. 10.22331/q-2023-06-02-1031.
https://doi.org/10.22331/q-2023-06-02-1031

[21] Diyi Liu, Weijie Du, Lin Lin, James P. Vary, and Chao Yang. An efficient quantum circuit for block encoding a pairing hamiltonian. Journal of Computational Science, 85: 102480, 2025. 10.1016/j.jocs.2024.102480.
https://doi.org/10.1016/j.jocs.2024.102480

[22] Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. Physical Review A, 101 (2): 022316, 2020. 10.1103/PhysRevA.101.022316.
https://doi.org/10.1103/PhysRevA.101.022316

[23] Daan Camps and Roel Van Beeumen. Fable: Fast approximate quantum circuits for block-encodings. 2022 IEEE International Conference on Quantum Computing and Engineering, pages 104–113, 2022. 10.1109/QCE53715.2022.00029.
https://doi.org/10.1109/QCE53715.2022.00029

[24] Parker Kuklinski and Benjamin Rempfer. S-fable and ls-fable: Fast approximate block-encoding algorithms for unstructured sparse matrices, 2024. URL https://arxiv.org/abs/2401.04234.
arXiv:2401.04234

[25] Zexian Li, Xiao-Ming Zhang, Chunlin Yang, and Guofeng Zhang. Binary tree block encoding of classical matrix, 2025. URL https://arxiv.org/abs/2504.05624.
arXiv:2504.05624

[26] Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit quantum circuits for block encodings of certain sparse matrices. SIAM Journal on Matrix Analysis and Applications, 45 (1): 801–827, 2024. 10.1137/22M1484298.
https://doi.org/10.1137/22M1484298

[27] Christoph Sünderhauf, Earl Campbell, and Joan Camps. Block-encoding structured matrices for data input in quantum computing. Quantum, 8: 1226, 2024. 10.22331/q-2024-01-11-1226.
https://doi.org/10.22331/q-2024-01-11-1226

[28] Keiiti Aki and Paul G Richards. Quantitative Seismology, Second Edition. University Science Books, 2002. 10.1007/978-1-4419-8678-8.
https://doi.org/10.1007/978-1-4419-8678-8

[29] Finn B Jensen, William A Kuperman, Michael B Porter, Henrik Schmidt, and Alexandra Tolstoy. Computational ocean acoustics. Springer New York, 2011. 10.1007/978-1-4419-8678-8.
https://doi.org/10.1007/978-1-4419-8678-8

[30] Jun Xiao, Rui Zhao, and Kin-Man Lam. Bayesian sparse hierarchical model for image denoising. Signal Processing: Image Communication, 96: 116299, 2021. 10.1016/j.image.2021.116299.
https://doi.org/10.1016/j.image.2021.116299

[31] Weimin Yuan, Yuanyuan Wang, Ruirui Fan, Yuxuan Zhang, Guangmei Wei, Cai Meng, and Xiangzhi Bai. Simultaneous image denoising and completion through convolutional sparse representation and nonlocal self-similarity. Computer Vision and Image Understanding, 249: 104216, 2024. 10.1016/j.cviu.2024.104216.
https://doi.org/10.1016/j.cviu.2024.104216

[32] A. Abusalah, O. Saad, J. Mahseredjian, U. Karaagac, and I. Kocar. Accelerated sparse matrix-based computation of electromagnetic transients. IEEE Open Access Journal of Power and Energy, 7: 13–21, 2020. 10.1109/OAJPE.2019.2952776.
https://doi.org/10.1109/OAJPE.2019.2952776

[33] Zhaoli Shen, Guoliang Han, Yutong Liu, Bruno Carpentieri, Chun Wen, and Jianjun Wang. Weak dangling block reordering and multi-step block compression for efficiently computing and updating pagerank solutions. Journal of Computational and Applied Mathematics, 458: 116332, 2025. 10.1016/j.cam.2024.116332.
https://doi.org/10.1016/j.cam.2024.116332

[34] Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear t complexity. Physical Review X, 8: 041015, 2018. 10.1103/PhysRevX.8.041015.
https://doi.org/10.1103/PhysRevX.8.041015

[35] Dominic W. Berry and Andrew M. Childs. Black-box hamiltonian simulation and unitary implementation. Quantum Info. Comput., 12 (1–2): 29–62, January 2012. ISSN 1533-7146. 10.26421/QIC12.1-2.
https://doi.org/10.26421/QIC12.1-2

[36] Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, and Nathan Wiebe. Exponential quantum speedup in simulating coupled classical oscillators. Physical Review X, 13: 041041, 2023b. 10.1103/PhysRevX.13.041041.
https://doi.org/10.1103/PhysRevX.13.041041

[37] Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. Quantum state preparation with optimal circuit depth: Implementations and applications. Physical review letters, 129: 230504, 2022. 10.1103/PhysRevLett.129.230504.
https://doi.org/10.1103/PhysRevLett.129.230504

[38] Tomaž Prosen. Third quantization: a general method to solve master equations for quadratic open fermi systems. New Journal of Physics, 10 (4): 043026, 2008. 10.1088/1367-2630/10/4/043026.
https://doi.org/10.1088/1367-2630/10/4/043026

[39] Dragoš Cvetković, Peter Rowlinson, and Slobodan Simić. An Introduction to the Theory of Graph Spectra. Cambridge University Press, 2009. 10.1017/CBO9780511801518.
https://doi.org/10.1017/CBO9780511801518

[40] Lin Lin. Lecture notes on quantum algorithms for scientific computation. arXiv preprint arXiv:2201.08309, 2022. 10.48550/arXiv.2201.08309.
https://doi.org/10.48550/arXiv.2201.08309
arXiv:2201.08309

[41] Pei Yuan and Shengyu Zhang. Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits. Quantum, 7: 956, 2023. 10.22331/q-2023-03-20-956.
https://doi.org/10.22331/q-2023-03-20-956

Cited by

[1] Zexian Li, Xiao-Ming Zhang, Chunlin Yang, and Guofeng Zhang, "Binary Tree Block Encoding of Classical Matrix", IEEE Transactions on Quantum Engineering 7, 1 (2026).

[2] Jiaxin Li, Zhaobing Fan, Hongmei Yao, Chunlin Yang, Shao-Ming Fei, Zi-Tong Zhou, Meng-Han Dou, and Teng-Yang Ma, "Variational quantum algorithm for generalized eigenvalue problems of non-Hermitian systems", Physical Review A 113 1, 012406 (2026).

[3] Sapthagiri Miriyala and Venkata Ramireddy Chirra, "From Quantum Algorithm Primitives to Design Patterns: A Unified Framework for NISQ and Fault‐Tolerant Regimes", Advanced Quantum Technologies 9 6, e70310 (2026).

[4] Shah Ishmam Mohtashim, Manas Sajjan, and Sabre Kais, "Continuous-Time Quantum-Walk Centrality for Protein Residue Interaction Networks", Journal of the American Chemical Society 148 27, 29206 (2026).

[5] Abhishek Setty, "Block Encoding of Sparse Matrices via Coherent Permutation", arXiv:2508.21667, (2025).

[6] Matic Petrič and René Zander, "Block-encodings as programming abstractions: The Eclipse Qrisp BlockEncoding Interface", arXiv:2604.18276, (2026).

[7] Dekuan Dong, Yingzhou Li, and Jungong Xue, "Products between block-encodings", arXiv:2509.15779, (2025).

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

Could not fetch ADS cited-by data during last attempt 2026-08-10 23:35:00: Cannot retrieve data from ADS due to rate limitations.

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.