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

Evaluation of block encoding for sparse matrix inversion using QSVT

Leigh B. Lapworth

Published Feb 27, 2024• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2402.17529

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

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

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

Spectrally Corrected Polynomial Approximation for Quantum Singular Value Transformation

Krishnan Suresh

Quantum Singular Value Transformation (QSVT) provides a unified framework for applying polynomial functions to the singular values of a block-encoded matrix. QSVT prepares a state proportional to $\bA^{-1}\bb$ with circuit depth $O(d\cdot\mathrm{polylog}(N))$, where $d$ is the polynomial degree of the $1/x$ approximation and $N$ is the size of $\bA$. Current polynomial approximation methods are over the continuous interval $[a,1]$, giving $d = O(\sqrt{\kap}\log(1/\varepsilon))$, and make no use of any properties of $\bA$. We observe here that QSVT solution accuracy depends only on the polynomial accuracy at the eigenvalues of $\bA$. When all $N$ eigenvalues are known exactly, a pure spectral polynomial $p_{S}$ can interpolate $1/x$ at these eigenvalues and achieve unit fidelity at reduced degree. But its practical applicability is limited. To address this, we propose a spectral correction that exploits prior knowledge of $K$ eigenvalues of $\bA$. Given any base polynomial $p_0$, such as Remez, of degree $d_0$, a $K\times K$ linear system enforces exact interpolation of $1/x$ only at these $K$ eigenvalues without increasing $d_0$. The spectrally corrected polynomial $p_{SC}$ preserves the continuous error profile between eigenvalues and inherits the parity of $p_0$. QSVT experiments on the 1D Poisson equation demonstrate up to a $5\times$ reduction in circuit depth relative to the base polynomial, at unit fidelity and improved compliance error. The correction is agnostic to the choice of base polynomial and robust to eigenvalue perturbations up to $10\%$ relative error. Extension to the 2D Poisson equation suggests that correcting a small fraction of the spectrum may suffice to achieve fidelity above $0.999$.

quant-pharXiv:2603.03998•Mar 5, 2026•0 citations

L-QLES: Sparse Laplacian generator for evaluating Quantum Linear Equation Solvers

Leigh B. Lapworth

L-QLES is an open source python code for generating 1D, 2D and 3D Laplacian operators and associated Poisson equations and their classical solutions. Its goal is to provide quantum algorithm developers with a flexible test case framework where features of industrial applications can be incorporated without the need for end-user domain knowledge or reliance on inflexible one-off industry supplied matrix sets. A sample set of 1, 2, and 3 dimensional Laplacians are suggested and used to compare the performance of the Prepare-Select and FABLE block encoding techniques. Results show that large matrices are not needed to investigate industrial characteristics. A matrix with a condition number of 17,000 can be encoded using 13 qubits. L-QLES has also been produced to enable algorithm developers to investigate and optimise both the classical and quantum aspects of the inevitable hybrid nature of quantum linear equation solvers. Prepare-Select encoding that takes over an hour of classical preprocessing time to decompose a 4,096x4,096 matrix into Pauli strings can be can investigated using L-QLES matrices. Similarly, row-column query oracles that have success probabilities $\le 10^{-7}$ for the same matrix can be investigated.

arXiv:2402.12266•Feb 19, 2024•0 citations

Measurement schemes for quantum linear equation solvers

Andrew Patterson, Leigh B. Lapworth

Abstract Solving computational fluid dynamics (CFD) problems requires the inversion of a linear system of equations, which can be done using a quantum algorithm for matrix inversion (Gilyén et al 2019 Proc. 51st Annual ACM SIGACT Symp. on Theory of Computing 193–204). However, the number of shots required to measure the output of the system can be prohibitive and remove any advantage obtained by quantum computing. In this work we propose a scheme for measuring the output of a quantum singular value transform (QSVT) matrix inversion algorithm specifically for the CFD use case. We use a quantum signal processing based amplitude estimation algorithm (Rall and Fuller 2023 Quantum 7 937) and show how it can be combined with the QSVT matrix inversion algorithm. We perform a detailed resource estimation of the amount of computational resources required for a single iteration of amplitude estimation, and compare the costs of amplitude estimation with the cost of not doing amplitude estimation and measuring the whole wavefunction. We also propose a measurement scheme to reduce the number of amplitudes measured in the CFD example by focussing on large amplitudes only. We simulate the whole CFD loop, finding that thus measuring only a small number of the total amplitudes in the output vector still results in an acceptable level of overall error.

arXiv:2411.00723•Quantum Science and Technology•Mar 5, 2025•2 citations
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.
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.
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.
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.
Quantum Singular Value Transformation (QSVT) provides a unified framework for applying polynomial functions to the singular values of a block-encoded matrix. QSVT prepares a state proportional to $\bA^{-1}\bb$ with circuit depth O(d⋅polylog(N))O(d\cdot\mathrm{polylog}(N))O(d⋅polylog(N)), where ddd is the polynomial degree of the 1/x1/x1/x approximation and NNN is the size of $\bA$. Current polynomial approximation methods are over the continuous interval [a,1][a,1][a,1], giving $d = O(\sqrt{\kap}\log(1/\varepsilon))$, and make no use of any properties of $\bA$. We observe here that QSVT solution accuracy depends only on the polynomial accuracy at the eigenvalues of $\bA$. When all NNN eigenvalues are known exactly, a pure spectral polynomial pSp_{S}pS​ can interpolate 1/x1/x1/x at these eigenvalues and achieve unit fidelity at reduced degree. But its practical applicability is limited. To address this, we propose a spectral correction that exploits prior knowledge of KKK eigenvalues of $\bA$. Given any base polynomial p0p_0p0​, such as Remez, of degree d0d_0d0​, a K×KK\times KK×K linear system enforces exact interpolation of 1/x1/x1/x only at these KKK eigenvalues without increasing d0d_0d0​. The spectrally corrected polynomial pSCp_{SC}pSC​ preserves the continuous error profile between eigenvalues and inherits the parity of p0p_0p0​. QSVT experiments on the 1D Poisson equation demonstrate up to a 5×5\times5× reduction in circuit depth relative to the base polynomial, at unit fidelity and improved compliance error. The correction is agnostic to the choice of base polynomial and robust to eigenvalue perturbations up to 10%10\%10% relative error. Extension to the 2D Poisson equation suggests that correcting a small fraction of the spectrum may suffice to achieve fidelity above 0.9990.9990.999.
L-QLES is an open source python code for generating 1D, 2D and 3D Laplacian operators and associated Poisson equations and their classical solutions. Its goal is to provide quantum algorithm developers with a flexible test case framework where features of industrial applications can be incorporated without the need for end-user domain knowledge or reliance on inflexible one-off industry supplied matrix sets. A sample set of 1, 2, and 3 dimensional Laplacians are suggested and used to compare the performance of the Prepare-Select and FABLE block encoding techniques. Results show that large matrices are not needed to investigate industrial characteristics. A matrix with a condition number of 17,000 can be encoded using 13 qubits. L-QLES has also been produced to enable algorithm developers to investigate and optimise both the classical and quantum aspects of the inevitable hybrid nature of quantum linear equation solvers. Prepare-Select encoding that takes over an hour of classical preprocessing time to decompose a 4,096x4,096 matrix into Pauli strings can be can investigated using L-QLES matrices. Similarly, row-column query oracles that have success probabilities ≤10−7\le 10^{-7}≤10−7 for the same matrix can be investigated.
Abstract Solving computational fluid dynamics (CFD) problems requires the inversion of a linear system of equations, which can be done using a quantum algorithm for matrix inversion (Gilyén et al 2019 Proc. 51st Annual ACM SIGACT Symp. on Theory of Computing 193–204). However, the number of shots required to measure the output of the system can be prohibitive and remove any advantage obtained by quantum computing. In this work we propose a scheme for measuring the output of a quantum singular value transform (QSVT) matrix inversion algorithm specifically for the CFD use case. We use a quantum signal processing based amplitude estimation algorithm (Rall and Fuller 2023 Quantum 7 937) and show how it can be combined with the QSVT matrix inversion algorithm. We perform a detailed resource estimation of the amount of computational resources required for a single iteration of amplitude estimation, and compare the costs of amplitude estimation with the cost of not doing amplitude estimation and measuring the whole wavefunction. We also propose a measurement scheme to reduce the number of amplitudes measured in the CFD example by focussing on large amplitudes only. We simulate the whole CFD loop, finding that thus measuring only a small number of the total amplitudes in the output vector still results in an acceptable level of overall error.