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:2610.27915

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

Leigh Lapworth, Jarrett Smalley, Christoph Sünderhauf

quant-phSubmitted Oct 20, 2026• Announced Oct 21, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
35 pages, 21 figures

Related papers

Preconditioned block encodings for quantum linear systems

Leigh B. Lapworth, Christoph Sünderhauf

Abstract Quantum linear system solvers like the quantum singular value transformation (QSVT) require a block encoding of the system matrix A within a unitary operator UA . Unfortunately, block encoding often results in significant subnormalisation and increase in the matrix’s effective condition number κ, affecting the efficiency of solvers. Matrix preconditioning is a well-established classical technique to reduce κ by multiplying A by a preconditioner P. Here, we study quantum preconditioning for block encodings. We consider four preconditioners and two encoding approaches: (a) separately encoding A and its preconditioner P, followed by quantum multiplication, and (b) classically multiplying A and P before encoding the product in U PA . Their impact on subnormalisation factors and condition number κ are analysed using practical matrices from computational fluid dynamics (CFD). Our results show that (a) quantum multiplication introduces excessive subnormalisation factors, negating improvements in κ. We study preamplified quantum multiplication to reduce subnormalisation. Conversely, we see that (b) encoding of the classical product can significantly improve the effective condition number using the sparse approximate inverse preconditioner with infill. Further, we introduce a new matrix filtering technique that reduces the circuit depth without adversely affecting the matrix solution. We apply these methods to reduce the number of QSVT phase factors by a factor of 25 for an example CFD matrix of size 1024 × 1024.

arXiv:2502.20908•Quantum Science and Technology•Oct 3, 2025•1 citation

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

Evaluation of block encoding for sparse matrix inversion using QSVT

Leigh B. Lapworth

Three block encoding methods are evaluated for solving linear systems of equations using QSVT (Quantum Singular Value Transformation). These are ARCSIN, FABLE and PREPARE-SELECT. The performance of the encoders is evaluated using a suite of 30 test cases including 1D, 2D and 3D Laplacians and 2D CFD matrices. A subset of cases is used to characterise how the degree of the polynomial approximation to $1/x$ influences the performance of QSVT. The results are used to guide the evaluation of QSVT as the linear solver in hybrid non-linear pressure correction and coupled implicit CFD solvers. The performance of QSVT is shown to be resilient to polynomial approximation errors. For both CFD solvers, error tolerances of $10^{-2}$ are more than sufficient in most cases and in some cases $10^{-1}$ is sufficient. The pressure correction solver allows subnormalised condition numbers, $κ_s$, as low as half the theoretical values to be used, reducing the number of phase factors needed. PREPARE-SELECT encoding relies on a unitary decomposition, e.g. Pauli strings, that has significant classical preprocessing costs. Both ARCSIN and FABLE have much lower costs, particularly for coupled solvers. However, their subnormalisation factors, which are based on the rank of the matrix, can be many times higher than PREPARE-SELECT leading to more phase factors being needed. For both the pressure correction and coupled CFD calculations, QSVT is more stable than previous HHL results due to the polynomial approximation errors only affecting long wavelength CFD errors. Given that lowering $κ_s$ increases the success probability, optimising the performance of QSVT within a CFD code is a function of the number QSVT phase factors, the number of non-linear iterations and the number of shots. Although phase factor files can be reused, the time taken to generate them impedes scaling QSVT to larger test cases.

arXiv:2402.17529•Feb 27, 2024•1 citation

A QSVT-Based Quantum Jacobi Algorithm for Linear Systems with Application to the Poisson Equation

Louisa M. Piskol, Thorsten Grahs, Stefan Langer +1 more

Many computational fluid dynamics (CFD) algorithms solve partial differential equations by discretization, resulting in large and sparse systems of linear equations. While iterative methods are widely used to solve these systems classically, most existing quantum linear system solvers target the solution through matrix inversion rather than approximating it using an iterative procedure. In this work, we develop a quantum implementation of the Jacobi method based on quantum singular value transformation (QSVT). By reformulating the Jacobi iteration as a polynomial transformation of a block-encoded operator, the algorithm requires only a constant ancilla overhead with respect to the number of iterations while maintaining a circuit depth that scales linearly with the iteration number. We demonstrate the algorithm for one- and two-dimensional Poisson problems, including the pressure Poisson equation arising in Chorin's projection method for the lid-driven cavity flow. The proposed algorithm provides a promising building block for future quantum implementations of multigrid methods and preconditioning techniques, bringing quantum algorithms closer to established CFD solution strategies.

quant-pharXiv:2609.24266•Sep 22, 2026•0 citations

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

Chunlin Yang, Zexian Li, Hongmei Yao +3 more

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.

arXiv:2405.18007•Quantum•Jul 22, 2025•4 citations

Block-encoding structured matrices for data input in quantum computing

Christoph Sünderhauf, Earl T. Campbell, Joan Camps

The cost of data input can dominate the run-time of quantum algorithms. Here, we consider data input of arithmetically structured matrices via block encoding circuits, the input model for the quantum singular value transform and related algorithms. We demonstrate how to construct block encoding circuits based on an arithmetic description of the sparsity and pattern of repeated values of a matrix. We present schemes yielding different subnormalisations of the block encoding; a comparison shows that the best choice depends on the specific matrix. The resulting circuits reduce flag qubit number according to sparsity, and data loading cost according to repeated values, leading to an exponential improvement for certain matrices. We give examples of applying our block encoding schemes to a few families of matrices, including Toeplitz and tridiagonal matrices.

arXiv:2302.10949•Quantum•Jan 11, 2024•48 citations
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.
Abstract Quantum linear system solvers like the quantum singular value transformation (QSVT) require a block encoding of the system matrix A within a unitary operator UA . Unfortunately, block encoding often results in significant subnormalisation and increase in the matrix’s effective condition number κ, affecting the efficiency of solvers. Matrix preconditioning is a well-established classical technique to reduce κ by multiplying A by a preconditioner P. Here, we study quantum preconditioning for block encodings. We consider four preconditioners and two encoding approaches: (a) separately encoding A and its preconditioner P, followed by quantum multiplication, and (b) classically multiplying A and P before encoding the product in U PA . Their impact on subnormalisation factors and condition number κ are analysed using practical matrices from computational fluid dynamics (CFD). Our results show that (a) quantum multiplication introduces excessive subnormalisation factors, negating improvements in κ. We study preamplified quantum multiplication to reduce subnormalisation. Conversely, we see that (b) encoding of the classical product can significantly improve the effective condition number using the sparse approximate inverse preconditioner with infill. Further, we introduce a new matrix filtering technique that reduces the circuit depth without adversely affecting the matrix solution. We apply these methods to reduce the number of QSVT phase factors by a factor of 25 for an example CFD matrix of size 1024 × 1024.
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.
Three block encoding methods are evaluated for solving linear systems of equations using QSVT (Quantum Singular Value Transformation). These are ARCSIN, FABLE and PREPARE-SELECT. The performance of the encoders is evaluated using a suite of 30 test cases including 1D, 2D and 3D Laplacians and 2D CFD matrices. A subset of cases is used to characterise how the degree of the polynomial approximation to 1/x1/x1/x influences the performance of QSVT. The results are used to guide the evaluation of QSVT as the linear solver in hybrid non-linear pressure correction and coupled implicit CFD solvers. The performance of QSVT is shown to be resilient to polynomial approximation errors. For both CFD solvers, error tolerances of 10−210^{-2}10−2 are more than sufficient in most cases and in some cases 10−110^{-1}10−1 is sufficient. The pressure correction solver allows subnormalised condition numbers, κsκ_sκs​, as low as half the theoretical values to be used, reducing the number of phase factors needed. PREPARE-SELECT encoding relies on a unitary decomposition, e.g. Pauli strings, that has significant classical preprocessing costs. Both ARCSIN and FABLE have much lower costs, particularly for coupled solvers. However, their subnormalisation factors, which are based on the rank of the matrix, can be many times higher than PREPARE-SELECT leading to more phase factors being needed. For both the pressure correction and coupled CFD calculations, QSVT is more stable than previous HHL results due to the polynomial approximation errors only affecting long wavelength CFD errors. Given that lowering κsκ_sκs​ increases the success probability, optimising the performance of QSVT within a CFD code is a function of the number QSVT phase factors, the number of non-linear iterations and the number of shots. Although phase factor files can be reused, the time taken to generate them impedes scaling QSVT to larger test cases.
Many computational fluid dynamics (CFD) algorithms solve partial differential equations by discretization, resulting in large and sparse systems of linear equations. While iterative methods are widely used to solve these systems classically, most existing quantum linear system solvers target the solution through matrix inversion rather than approximating it using an iterative procedure. In this work, we develop a quantum implementation of the Jacobi method based on quantum singular value transformation (QSVT). By reformulating the Jacobi iteration as a polynomial transformation of a block-encoded operator, the algorithm requires only a constant ancilla overhead with respect to the number of iterations while maintaining a circuit depth that scales linearly with the iteration number. We demonstrate the algorithm for one- and two-dimensional Poisson problems, including the pressure Poisson equation arising in Chorin's projection method for the lid-driven cavity flow. The proposed algorithm provides a promising building block for future quantum implementations of multigrid methods and preconditioning techniques, bringing quantum algorithms closer to established CFD solution strategies.
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.
The cost of data input can dominate the run-time of quantum algorithms. Here, we consider data input of arithmetically structured matrices via block encoding circuits, the input model for the quantum singular value transform and related algorithms. We demonstrate how to construct block encoding circuits based on an arithmetic description of the sparsity and pattern of repeated values of a matrix. We present schemes yielding different subnormalisations of the block encoding; a comparison shows that the best choice depends on the specific matrix. The resulting circuits reduce flag qubit number according to sparsity, and data loading cost according to repeated values, leading to an exponential improvement for certain matrices. We give examples of applying our block encoding schemes to a few families of matrices, including Toeplitz and tridiagonal matrices.