Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2405.18007 · Quantum

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

Published Jul 22, 2025• 4 citations
arXivHTMLPDF

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} gate set, the protocol queries a 2n×2n sparse matrix with s non-zero elements at a circuit depth of O(log⁡(ns)) , utilizing O(n2s) 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(n) . Moreover, in our protocol, the subnormalization, a scaled factor that influences the measurement probability of ancillary qubits, is minimized to ∑l=0s0|Al| , where s0 denotes the number of classifications in the dictionary and Al 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.

DOI
10.22331/q-2025-07-22-1805

Related papers

Block encoding of sparse matrices with a periodic diagonal structure

Alessandro Andrea Zecchi, Claudio Sanavio, Luca Cappelli +3 more

Block encoding is a successful technique used in several powerful quantum algorithms. In this work we provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure. The proposed methodology is based on the linear combination of unitaries (LCU) framework and on an efficient unitary operator used to project the complex exponential at a frequency $ω$ multiplied by the computational basis into its real and imaginary components. We demonstrate a distinct computational advantage with a $\mathcal{O}(\text{poly}(n))$ gate complexity, where $n$ is the number of qubits, in the worst-case scenario used for banded matrices, and $\mathcal{O}(n)$ when dealing with a simple diagonal matrix, compared to the exponential scaling of general-purpose methods for dense matrices. Various applications for the presented methodology are discussed in the context of solving differential problems such as the advection-diffusion-reaction (ADR) dynamics, using quantum algorithms with optimal scaling, e.g., quantum singular value transformation (QSVT). Numerical results are used to validate the analytical formulation.

quant-pharXiv:2602.10589•Feb 12, 2026•0 citations

Practical block encodings of matrix polynomials that can also be trivially controlled

Martina Nibbi, Filippo Della Chiara, Yizhi Shen +2 more

Quantum circuits naturally implement unitary operations on input quantum states. However, non-unitary operations can also be implemented through "block encodings", where additional ancilla qubits are introduced and later measured. While block encoding underlies a host of well-established theoretical applications, its implementation in practice has been prohibitively expensive for current quantum hardware. In this paper, we present practical and explicit block encoding circuits implementing matrix polynomial transformations of a target matrix. With standard approaches, block-encoding a degree-d matrix polynomial requires a circuit depth scaling as d times the depth for block-encoding the original matrix alone. By leveraging the recently introduced Fast One-Qubit Controlled Select Linear Combination of Unitaries (FOQCS-LCU) framework, we show that the additional circuit-depth overhead required for encoding matrix polynomials can be reduced to scale linearly in d with no dependence on system size or the cost of block encoding the original matrix. Moreover, we demonstrate that the FOQCS-LCU circuits and their associated matrix polynomial transformations can be controlled with negligible overhead, enabling efficient applications such as Hadamard tests. Finally, we provide explicit hardware-efficient circuits for representative non-unitary operators, namely quantum spin models, together with detailed non-asymptotic gate counts and circuit depths.

quant-pharXiv:2601.18767•Jan 27, 2026•0 citations

Circuit complexity of quantum access models for encoding classical data

Xiao‐Ming Zhang, Xiao Yuan

Abstract How to efficiently encode classical data is a fundamental task in quantum computing. While many existing works treat classical data encoding as a black box in oracle-based quantum algorithms, their explicit constructions are crucial for the efficiency of practical algorithm implementations. Here, we unveil the mystery of the classical data encoding black box and study the Clifford + T complexity in constructing several typical quantum access models. For general matrices (even including sparse ones), we prove that sparse-access input models and block-encoding both require nearly linear circuit complexities relative to the matrix dimension. We also give construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is a linear combination of polynomial terms of efficiently implementable unitaries. As a typical example, we propose improved block-encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a select oracle for Pauli strings, which hold independent values. Our access model constructions provide considerable flexibility, allowing for tunable ancillary qubit numbers and offering corresponding space-time trade-offs.

arXiv:2311.11365•npj Quantum Information•Apr 23, 2024•21 citations

Quantum block encoding for one-pair semiseparable matrices

Giacomo Antonioli, Paola Boito, Gianna M. Del Corso +1 more

Quantum block encoding (QBE) is a crucial step in the development of most quantum algorithms, as it provides an embedding of a given matrix into a suitable larger unitary matrix. Historically, the development of efficient techniques for QBE has mostly focused on sparse matrices; less effort has been devoted to data-sparse (e.g., rank-structured) matrices. In this work we examine a particular case of rank structure, namely, one-pair semiseparable matrices. We present a new block encoding approach that relies on a suitable factorization of the given matrix as the product of triangular and diagonal factors. To encode the matrix, the algorithm needs $2\log(N)+7$ ancillary qubits. Assuming that the data input oracles can be implemented with polylogarithmic depth, or that a QRAM input model is available, our proposed method requires $\mathcal{O}({\rm polylog} (N))$ time and has an error of $\mathcal{O}(N^2)$, where $N$ is the matrix size.

quant-pharXiv:2603.19130•Numerical Algorithms•Mar 20, 2026•0 citations

Efficient quantum access model for sparse structured matrices using linear combination of “things”

Abeynaya Gnanasekaran, Amit Surana

We present a novel framework for Linear Combination of Unitaries (LCU)-style decomposition tailored to structured sparse matrices, which frequently arise in the numerical solution of partial differential equations (PDEs). While LCU is a foundational primitive in both variational and fault-tolerant quantum algorithms, conventional approaches based on the Pauli basis can require a number of terms that scales quadratically with matrix size. We introduce the Sigma basis, a compact set of simple, non-unitary operators that can better capture sparsity and structure, enabling decompositions with only polylogarithmic scaling in the number of terms. We develop both numerical and semi-analytical methods for computing Sigma basis decompositions of arbitrary matrices. Given this new basis is comprised of non-unitary operators, we leverage the concept of unitary completion to design efficient quantum circuits for evaluating observables in variational quantum algorithms and for constructing block encodings in fault-tolerant quantum algorithms. We compare our method to related techniques like unitary dilation, and demonstrate its effectiveness through several PDE examples, showing exponential improvements in decomposition size while retaining circuit efficiency.

arXiv:2507.03714•Physical Review A•Jan 16, 2026•1 citation

Sparse block encoding with low subnormalisation for quantum linear solvers on unstructured meshes

Leigh Lapworth, Jarrett Smalley, Christoph Sünderhauf

Unstructured meshes are widely used in modelling and simulation in Computational Fluid Dynamics (CFD) due to their geometric flexibility. However, they require an efficient block encoding circuit describing the system. Here, we present a new block encoding methodology for unstructured mesh solvers based on decomposing the system matrix into a sum of 1-sparse matrices. This block encoding is engineered to reduce subnormalisation even in the absence of structure by hiding the contribution of large matrix elements behind others. We investigate three methods of 1-sparse decomposition. Our circuit constructions can optionally take advantage of limited matrix bandwidth and repeated values. For example we consider digitisation (reduced precision), where the number of multiplexed rotation gates is equal to the number of non-unique matrix entries. We evaluate our methodologies using 2D and 3D CFD matrices for unstructured aerofoil meshes, structured cavity, and duct meshes, with and without matrix preconditioning. Our results show that we are able to achieve a block encoding with a near constant subnormalisation factor as the number of matrix preconditioning infill levels increases. This significantly reduces the subnormalised condition number and, in one case, reduces the degree of the QSP polynomial approximation to $1/x$ by 100,000. Reduced precision digitisation is shown to become more effective as the number of preconditioning infill levels is increased and, in one case, reduces the number of multiplexed rotations from 2,785,576 to 546 whilst maintaining an infidelity of $2.6\times10^{-5}$ relative to the classical solution. The effect of digitisation on QSVT solutions is demonstrated using 2D and 3D unstructured mesh aerofoil cases. Due to its flexibility and automatic applicability, we believe our 1-sparse decomposition block encoding can offer benefits to other quantum applications.

quant-pharXiv:2610.27915•Oct 21, 2026•0 citations
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} gate set, the protocol queries a 2n×2n sparse matrix with s non-zero elements at a circuit depth of O(log⁡(ns)) , utilizing O(n2s) 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(n) . Moreover, in our protocol, the subnormalization, a scaled factor that influences the measurement probability of ancillary qubits, is minimized to ∑l=0s0|Al| , where s0 denotes the number of classifications in the dictionary and Al 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.
Block encoding is a successful technique used in several powerful quantum algorithms. In this work we provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure. The proposed methodology is based on the linear combination of unitaries (LCU) framework and on an efficient unitary operator used to project the complex exponential at a frequency ωωω multiplied by the computational basis into its real and imaginary components. We demonstrate a distinct computational advantage with a O(poly(n))\mathcal{O}(\text{poly}(n))O(poly(n)) gate complexity, where nnn is the number of qubits, in the worst-case scenario used for banded matrices, and O(n)\mathcal{O}(n)O(n) when dealing with a simple diagonal matrix, compared to the exponential scaling of general-purpose methods for dense matrices. Various applications for the presented methodology are discussed in the context of solving differential problems such as the advection-diffusion-reaction (ADR) dynamics, using quantum algorithms with optimal scaling, e.g., quantum singular value transformation (QSVT). Numerical results are used to validate the analytical formulation.
Quantum circuits naturally implement unitary operations on input quantum states. However, non-unitary operations can also be implemented through "block encodings", where additional ancilla qubits are introduced and later measured. While block encoding underlies a host of well-established theoretical applications, its implementation in practice has been prohibitively expensive for current quantum hardware. In this paper, we present practical and explicit block encoding circuits implementing matrix polynomial transformations of a target matrix. With standard approaches, block-encoding a degree-d matrix polynomial requires a circuit depth scaling as d times the depth for block-encoding the original matrix alone. By leveraging the recently introduced Fast One-Qubit Controlled Select Linear Combination of Unitaries (FOQCS-LCU) framework, we show that the additional circuit-depth overhead required for encoding matrix polynomials can be reduced to scale linearly in d with no dependence on system size or the cost of block encoding the original matrix. Moreover, we demonstrate that the FOQCS-LCU circuits and their associated matrix polynomial transformations can be controlled with negligible overhead, enabling efficient applications such as Hadamard tests. Finally, we provide explicit hardware-efficient circuits for representative non-unitary operators, namely quantum spin models, together with detailed non-asymptotic gate counts and circuit depths.
Abstract How to efficiently encode classical data is a fundamental task in quantum computing. While many existing works treat classical data encoding as a black box in oracle-based quantum algorithms, their explicit constructions are crucial for the efficiency of practical algorithm implementations. Here, we unveil the mystery of the classical data encoding black box and study the Clifford + T complexity in constructing several typical quantum access models. For general matrices (even including sparse ones), we prove that sparse-access input models and block-encoding both require nearly linear circuit complexities relative to the matrix dimension. We also give construction protocols achieving near-optimal gate complexities. On the other hand, the construction becomes efficient with respect to the data qubit when the matrix is a linear combination of polynomial terms of efficiently implementable unitaries. As a typical example, we propose improved block-encoding when these unitaries are Pauli strings. Our protocols are built upon improved quantum state preparation and a select oracle for Pauli strings, which hold independent values. Our access model constructions provide considerable flexibility, allowing for tunable ancillary qubit numbers and offering corresponding space-time trade-offs.
Quantum block encoding (QBE) is a crucial step in the development of most quantum algorithms, as it provides an embedding of a given matrix into a suitable larger unitary matrix. Historically, the development of efficient techniques for QBE has mostly focused on sparse matrices; less effort has been devoted to data-sparse (e.g., rank-structured) matrices. In this work we examine a particular case of rank structure, namely, one-pair semiseparable matrices. We present a new block encoding approach that relies on a suitable factorization of the given matrix as the product of triangular and diagonal factors. To encode the matrix, the algorithm needs 2log⁡(N)+72\log(N)+72log(N)+7 ancillary qubits. Assuming that the data input oracles can be implemented with polylogarithmic depth, or that a QRAM input model is available, our proposed method requires O(polylog(N))\mathcal{O}({\rm polylog} (N))O(polylog(N)) time and has an error of O(N2)\mathcal{O}(N^2)O(N2), where NNN is the matrix size.
We present a novel framework for Linear Combination of Unitaries (LCU)-style decomposition tailored to structured sparse matrices, which frequently arise in the numerical solution of partial differential equations (PDEs). While LCU is a foundational primitive in both variational and fault-tolerant quantum algorithms, conventional approaches based on the Pauli basis can require a number of terms that scales quadratically with matrix size. We introduce the Sigma basis, a compact set of simple, non-unitary operators that can better capture sparsity and structure, enabling decompositions with only polylogarithmic scaling in the number of terms. We develop both numerical and semi-analytical methods for computing Sigma basis decompositions of arbitrary matrices. Given this new basis is comprised of non-unitary operators, we leverage the concept of unitary completion to design efficient quantum circuits for evaluating observables in variational quantum algorithms and for constructing block encodings in fault-tolerant quantum algorithms. We compare our method to related techniques like unitary dilation, and demonstrate its effectiveness through several PDE examples, showing exponential improvements in decomposition size while retaining circuit efficiency.
Unstructured meshes are widely used in modelling and simulation in Computational Fluid Dynamics (CFD) due to their geometric flexibility. However, they require an efficient block encoding circuit describing the system. Here, we present a new block encoding methodology for unstructured mesh solvers based on decomposing the system matrix into a sum of 1-sparse matrices. This block encoding is engineered to reduce subnormalisation even in the absence of structure by hiding the contribution of large matrix elements behind others. We investigate three methods of 1-sparse decomposition. Our circuit constructions can optionally take advantage of limited matrix bandwidth and repeated values. For example we consider digitisation (reduced precision), where the number of multiplexed rotation gates is equal to the number of non-unique matrix entries. We evaluate our methodologies using 2D and 3D CFD matrices for unstructured aerofoil meshes, structured cavity, and duct meshes, with and without matrix preconditioning. Our results show that we are able to achieve a block encoding with a near constant subnormalisation factor as the number of matrix preconditioning infill levels increases. This significantly reduces the subnormalised condition number and, in one case, reduces the degree of the QSP polynomial approximation to 1/x1/x1/x by 100,000. Reduced precision digitisation is shown to become more effective as the number of preconditioning infill levels is increased and, in one case, reduces the number of multiplexed rotations from 2,785,576 to 546 whilst maintaining an infidelity of 2.6×10−52.6\times10^{-5}2.6×10−5 relative to the classical solution. The effect of digitisation on QSVT solutions is demonstrated using 2D and 3D unstructured mesh aerofoil cases. Due to its flexibility and automatic applicability, we believe our 1-sparse decomposition block encoding can offer benefits to other quantum applications.