{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T17:15:29Z","timestamp":1767374129495,"version":"3.41.2"},"reference-count":41,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T00:00:00Z","timestamp":1753142400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Stable Supporting Fund of Acoustic Science and Technology Laboratory","award":["JCKYS2024604SSJS001"],"award-info":[{"award-number":["JCKYS2024604SSJS001"]}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"crossref","award":["3072024XX2401"],"award-info":[{"award-number":["3072024XX2401"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Hong Kong Research Grant Council","award":["15213924"],"award-info":[{"award-number":["15213924"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62173288"],"award-info":[{"award-number":["62173288"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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 {U(2), CNOT}<\/mml:mtext><\/mml:mrow><\/mml:math> gate set, the protocol queries a 2<\/mml:mn>n<\/mml:mi><\/mml:msup>&#x00D7;<\/mml:mo>2<\/mml:mn>n<\/mml:mi><\/mml:msup><\/mml:math> sparse matrix with s<\/mml:mi><\/mml:math> non-zero elements at a circuit depth of O<\/mml:mi><\/mml:mrow>(<\/mml:mo>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>n<\/mml:mi>s<\/mml:mi>)<\/mml:mo>)<\/mml:mo><\/mml:math>, utilizing O<\/mml:mi><\/mml:mrow>(<\/mml:mo>n<\/mml:mi>2<\/mml:mn><\/mml:msup>s<\/mml:mi>)<\/mml:mo><\/mml:math> ancillary qubits. This offers an exponential improvement in circuit depth relative to the number of system qubits, compared to existing methods \\cite{clader2022quantum,zhang2024circuit} with a circuit depth of O<\/mml:mi><\/mml:mrow>(<\/mml:mo>n<\/mml:mi>)<\/mml:mo><\/mml:math>. Moreover, in our protocol, the subnormalization, a scaled factor that influences the measurement probability of ancillary qubits, is minimized to &#x2211;<\/mml:mo>l<\/mml:mi>=<\/mml:mo>0<\/mml:mn><\/mml:mrow>s<\/mml:mi>0<\/mml:mn><\/mml:msub><\/mml:mrow><\/mml:munderover>|<\/mml:mo>A<\/mml:mi>l<\/mml:mi><\/mml:msub>|<\/mml:mo><\/mml:math>, where s<\/mml:mi>0<\/mml:mn><\/mml:msub><\/mml:math> denotes the number of classifications in the dictionary and A<\/mml:mi>l<\/mml:mi><\/mml:msub><\/mml:math> represents the value of the l<\/mml:mi><\/mml:math>-th classification. Furthermore, we show that our protocol connects to linear combinations of unitaries (<\/mml:mo>L<\/mml:mi>C<\/mml:mi>U<\/mml:mi>)<\/mml:mo><\/mml:math> and the sparse access input model (<\/mml:mo>S<\/mml:mi>A<\/mml:mi>I<\/mml:mi>M<\/mml:mi>)<\/mml:mo><\/mml:math>. To demonstrate the practical utility of our approach, we provide several applications, including Laplacian matrices in graph problems and discrete differential operators.<\/jats:p>","DOI":"10.22331\/q-2025-07-22-1805","type":"journal-article","created":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T09:25:36Z","timestamp":1753176336000},"page":"1805","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":2,"title":["Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth"],"prefix":"10.22331","volume":"9","author":[{"given":"Chunlin","family":"Yang","sequence":"first","affiliation":[{"name":"School of Mathematical and Sciences, Harbin Engineering University, China"}]},{"given":"Zexian","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, The Hong Kong Polytechnic University, China"}]},{"given":"Hongmei","family":"Yao","sequence":"additional","affiliation":[{"name":"School of Mathematical and Sciences, Harbin Engineering University, China"}]},{"given":"Zhaobing","family":"Fan","sequence":"additional","affiliation":[{"name":"School of Mathematical and Sciences, Harbin Engineering University, China"}]},{"given":"Guofeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics, The Hong Kong Polytechnic University, China"}]},{"given":"Jianshe","family":"Liu","sequence":"additional","affiliation":[{"name":"College of Underwater Acoustic Engineering, Harbin Engineering University, China"}]}],"member":"9598","published-online":{"date-parts":[[2025,7,22]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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\u201323, 2022. 10.1109\/TQE.2022.3231194.","DOI":"10.1109\/TQE.2022.3231194"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1038\/s41534-024-00835-8"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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\u2013558, 1992. 10.1098\/rspa.1992.0167.","DOI":"10.1098\/rspa.1992.0167"},{"key":"3","doi-asserted-by":"publisher","unstructured":"P. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124\u2013134, 1994. 10.1109\/SFCS.1994.365700.","DOI":"10.1109\/SFCS.1994.365700"},{"key":"4","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, 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\u2013204, 2019. 10.1145\/3313276.3316366.","DOI":"10.1145\/3313276.3316366"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/s00220-006-0150-x"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs and Robin Kothari. Simulating sparse hamiltonians with star decompositions. In Theory of Quantum Computation, Communication, and Cryptography, pages 94\u2013103, 2011. 10.1007\/978-3-642-18073-6_8.","DOI":"10.1007\/978-3-642-18073-6_8"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs. On the relationship between continuous- and discrete-time quantum walk. Communications in Mathematical Physics, pages 581\u2013603, 2010. 10.1007\/s00220-009-0930-1.","DOI":"10.1007\/s00220-009-0930-1"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1145\/2591796.2591854"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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\u20131950, 2017. 10.1137\/16M1087072.","DOI":"10.1137\/16M1087072"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Shantanav Chakraborty, Andr\u00e1s Gily\u00e9n, 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\u201333:14, 2019. 10.4230\/LIPIcs.ICALP.2019.33.","DOI":"10.4230\/LIPIcs.ICALP.2019.33"},{"key":"12","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevX.13.041041"},{"key":"13","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1088\/0253-6102\/45\/5\/013"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, (11\u201312): 901\u2013924, 2012. 10.26421\/QIC12.11-12-1.","DOI":"10.26421\/QIC12.11-12-1"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PRXQuantum.2.040203"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3: 163, 2019. 10.22331\/q-2019-07-12-163.","DOI":"10.22331\/q-2019-07-12-163"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Joran van Apeldoorn and Andr\u00e1s Gily\u00e9n. Improvements in Quantum SDP-Solving with Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132, pages 99:1\u201399:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 2019. 10.4230\/LIPIcs.ICALP.2019.99.","DOI":"10.4230\/LIPIcs.ICALP.2019.99"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2022-12-13-876"},{"key":"19","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2023-06-02-1031"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1016\/j.jocs.2024.102480"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevA.101.022316"},{"key":"22","doi-asserted-by":"publisher","unstructured":"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\u2013113, 2022. 10.1109\/QCE53715.2022.00029.","DOI":"10.1109\/QCE53715.2022.00029"},{"key":"23","unstructured":"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."},{"key":"24","unstructured":"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."},{"key":"25","doi-asserted-by":"publisher","unstructured":"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\u2013827, 2024. 10.1137\/22M1484298.","DOI":"10.1137\/22M1484298"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Christoph S\u00fcnderhauf, 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.","DOI":"10.22331\/q-2024-01-11-1226"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Keiiti Aki and Paul G Richards. Quantitative Seismology, Second Edition. University Science Books, 2002. 10.1007\/978-1-4419-8678-8.","DOI":"10.1007\/978-1-4419-8678-8"},{"key":"28","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1007\/978-1-4419-8678-8"},{"key":"29","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1016\/j.image.2021.116299"},{"key":"30","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1016\/j.cviu.2024.104216"},{"key":"31","doi-asserted-by":"publisher","unstructured":"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\u201321, 2020. 10.1109\/OAJPE.2019.2952776.","DOI":"10.1109\/OAJPE.2019.2952776"},{"key":"32","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1016\/j.cam.2024.116332"},{"key":"33","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevX.8.041015"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry and Andrew M. Childs. Black-box hamiltonian simulation and unitary implementation. Quantum Information and Computation, 12: 29\u201362, 2012. 10.5555\/2231036.2231040.","DOI":"10.5555\/2231036.2231040"},{"key":"35","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevX.13.041041"},{"key":"36","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1103\/PhysRevLett.129.230504"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Toma\u017e 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.","DOI":"10.1088\/1367-2630\/10\/4\/043026"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Drago\u0161 Cvetkovi\u0107, Peter Rowlinson, and Slobodan Simi\u0107. An Introduction to the Theory of Graph Spectra. Cambridge University Press, 2009. 10.1017\/CBO9780511801518.","DOI":"10.1017\/CBO9780511801518"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Lin Lin. Lecture notes on quantum algorithms for scientific computation. arXiv preprint arXiv:2201.08309, 2022. 10.48550\/arXiv.2201.08309.","DOI":"10.48550\/arXiv.2201.08309"},{"key":"40","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.22331\/q-2023-03-20-956"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-07-22-1805\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T09:25:38Z","timestamp":1753176338000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-07-22-1805\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,22]]},"references-count":41,"URL":"https:\/\/doi.org\/10.22331\/q-2025-07-22-1805","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2025,7,22]]},"article-number":"1805"}}