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

Quantum Domain Decomposition for Preconditioning the Finite Element Method

Elise Fressart, Michel Nowak, Nicole Spillane

math.NAquant-phSubmitted May 25, 2026• Announced May 26, 2026• 0 citations
arXivHTMLPDF

Abstract

Even in cases where quantum linear solvers provide significant speedup compared to their classical counterparts, their performance depends on some of the same parameters. In particular, the condition number of the matrix which is to be inverted is a decisive parameter. A well known classical, and now quantum, remedy is to precondition the linear system $A x = b$ by premultiplying it by a matrix $H$ in such a way that the condition number of $HA$ is significantly smaller than the condition number of $A$. In this work, we focus on a family of preconditioners called domain decomposition. First, we prove that it is feasible to apply quantum domain decomposition. We provide upper bounds for the block-encoding parameters of the Poisson problem discretized by the finite element method and preconditioned by the two-level Additive Schwarz preconditioner (one of the most fundamental domain decomposition techniques). From these bounds, we deduce the complexity of the quantum linear system solver. Second, we focus on a particular choice of local solver within the domain decomposition preconditioner by applying recent work by [Deiml and Peterseim, \textit{Math. Comput.}, 2025] on the Bramble--Pasciak--Xu (BPX) preconditioner. Finally, we provide details on how the operators are implemented.

Related papers

Quantum realization of the finite element method

M. Deiml, Daniel Peterseim

This paper presents a quantum algorithm for the solution of prototypical second-order linear elliptic partial differential equations discretized by d d -linear finite elements on Cartesian grids of a bounded d d -dimensional domain. An essential step in the construction is a BPX preconditioner, which transforms the linear system into a sufficiently well-conditioned one, making it amenable to quantum computation. We provide a constructive proof demonstrating that, for any fixed dimension, our quantum algorithm can compute suitable functionals of the solution to a given tolerance t o l \mathtt {tol} with an optimal complexity of order t o l − 1 \mathtt {tol}^{-1} up to logarithmic terms, significantly improving over existing approaches. Notably, this approach does not rely on the regularity of the solution and achieves a quantum advantage over classical solvers already in two dimensions, whereas prior quantum methods required at least four dimensions for asymptotic benefits. We further detail the design and implementation of a quantum circuit capable of executing our algorithm, present simulator results, and report numerical experiments on current quantum hardware, confirming the feasibility of preconditioned finite element methods for near-term quantum computing.

arXiv:2403.19512•Mathematics of Computation•Aug 14, 2025•3 citations

Quantum preconditioning method for finite difference discretizations of the Poisson equation via Schrödingerization

Shi Jin, Nana Liu, Chuwen Ma +1 more

We present a quantum preconditioning framework for solving linear systems arising from a finite difference discretization of the Poisson equation. It is based on the combination of the Schrödingerization technique \cite{JLY22b,JLYPRL24} and the BPX multilevel preconditioner in order to achieve near-optimal complexity. The Schrödingerization technique transforms linear partial and ordinary differential equations into Schrödinger-type systems with unitary evolution in one higher dimension, making them suitable for quantum simulation. A key contribution is a structure-aware construction of the block-encoding for the symmetrically preconditioned matrix $A_S = S^\top A S$, where $A$ is the stiffness matrix and $S$ encodes the BPX preconditioner in factored form. By establishing a novel commuting identity, we avoid the unfavorable normalization scaling that would otherwise arise from naive multiplication of block-encodings. This yields an exact block-encoding of $A_S$ with normalization $\mathcal{O}(d^2(L+1))$, where $d$ is the spatial dimension and $L$ is the number of levels. Combined with the Schrödingerization-based Hamiltonian simulation, the overall quantum algorithm achieves a query complexity of $\mathcal{O}\big(\mathrm{poly}(d)\varepsilon^{-1} \mathrm{polylog}(\varepsilon^{-1}) \big)$ for estimating linear functionals of the solution to a given tolerance $\varepsilon$.

arXiv:2505.06866•May 11, 2025•0 citations

Pauli-structured preconditioning for quantum linear system solvers

Hantao Nie, Zhijian Lai, Dong An

Preconditioning is a fundamental technique for accelerating classical linear system solvers, and understanding when its benefits persist in quantum linear system (QLS) solvers is important for assessing the practical resource requirements of quantum linear algebra. In QLS algorithms, however, the potential advantage of preconditioning may be offset by the normalization overhead incurred by composing separate block-encodings of the system matrix and the preconditioner, as observed in recent work. This limitation leaves open whether additional algebraic structure can make preconditioning effective in quantum access models. Motivated by this question, we show that Pauli-structured representations of both the system matrix and the preconditioner allow the preconditioned operator to be accessed through regrouped Pauli expansions. In this setting, algebraic regrouping of Pauli products can reduce the Pauli coefficient weight of the preconditioned operator, thereby altering the normalization parameters relevant to quantum algorithms. We derive explicit size and coefficient-weight bounds for the regrouped Pauli representations, and we trace their consequences for both direct block-encoding constructions and randomized Pauli linear system solvers. These results identify when Pauli-structured preconditioning can reduce the effective complexity parameters of QLS algorithms, rather than merely improving the classical condition number. Numerical experiments on a finite-dimensional synthetic benchmark show reductions in norm-aware direct block-encoding diagnostics and in the randomized QLS per-sample depth proxy.

quant-pharXiv:2606.01733•Jun 2, 2026•0 citations

Variational Quantum Eigen-Decomposition Preconditioning Method for Solving Computational Mechanics Problems

Eunsik Choi, Jungin E. Kim, Yan Wang

Recently, quantum computing emerged as a paradigm for solving systems of linear equations.However, large condition numbers significantly increase the computational complexity of quantum linear equation solvers.In this work, a new quantum preconditioning approach called variational quantum eigen-decomposition (VQED) is proposed, where the preconditioner is defined as a weighted projector onto the subspace spanned by the eigenvectors of a matrix.A variational quantum algorithm with projection-based deflation is performed to calculate eigenvalueeigenvector pairs for constructing the preconditioner.The proposed VQED method is used with quantum singular value transformation to solve linear systems for mechanics examples.It is demonstrated that the VQED can reduce the condition numbers to as low as 1.03, which is a significant improvement over the original condition number.

Computer Science Research Notes•Jan 1, 2025•0 citations

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

Faster quantum linear system solver beyond the condition number

Alexander M. Dalzell, Jianqiang Li, Yuan Su

The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution $|x\rangle$ of linear system $Ax=| b \rangle$ to accuracy $ε$ with complexity independent of the condition number $κ=\lVert A^{-1}\rVert$. We focus on the standard input model where $A$ is accessed through a block encoding and $| b \rangle$ is prepared by a unitary. But we also introduce an affine dilation model that encodes $A$ and $| b \rangle$ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to $| b \rangle$ and $\operatorname{\mathbf{O}}\left(κ_{\mathrm{eff}}\operatorname{polylog}\left(\frac{κ_{\mathrm{eff}}}ε\right)\right)$ queries to $A$. We prove a family of upper bounds on the effective condition number, including $κ_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}$ for positive even integer $t$ and $κ_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}$ for positive odd $t$, overcoming the $κ$-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity $3\frac{\lVert A^{-1\dagger}|x\rangle\rVert}ε$ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.

quant-pharXiv:2607.07691•Jul 9, 2026•0 citations
Even in cases where quantum linear solvers provide significant speedup compared to their classical counterparts, their performance depends on some of the same parameters. In particular, the condition number of the matrix which is to be inverted is a decisive parameter. A well known classical, and now quantum, remedy is to precondition the linear system Ax=bA x = bAx=b by premultiplying it by a matrix HHH in such a way that the condition number of HAHAHA is significantly smaller than the condition number of AAA.
In this work, we focus on a family of preconditioners called domain decomposition. First, we prove that it is feasible to apply quantum domain decomposition. We provide upper bounds for the block-encoding parameters of the Poisson problem discretized by the finite element method and preconditioned by the two-level Additive Schwarz preconditioner (one of the most fundamental domain decomposition techniques). From these bounds, we deduce the complexity of the quantum linear system solver. Second, we focus on a particular choice of local solver within the domain decomposition preconditioner by applying recent work by [Deiml and Peterseim, \textit{Math. Comput.}, 2025] on the Bramble--Pasciak--Xu (BPX) preconditioner. Finally, we provide details on how the operators are implemented.
This paper presents a quantum algorithm for the solution of prototypical second-order linear elliptic partial differential equations discretized by d d -linear finite elements on Cartesian grids of a bounded d d -dimensional domain. An essential step in the construction is a BPX preconditioner, which transforms the linear system into a sufficiently well-conditioned one, making it amenable to quantum computation. We provide a constructive proof demonstrating that, for any fixed dimension, our quantum algorithm can compute suitable functionals of the solution to a given tolerance t o l \mathtt {tol} with an optimal complexity of order t o l − 1 \mathtt {tol}^{-1} up to logarithmic terms, significantly improving over existing approaches. Notably, this approach does not rely on the regularity of the solution and achieves a quantum advantage over classical solvers already in two dimensions, whereas prior quantum methods required at least four dimensions for asymptotic benefits. We further detail the design and implementation of a quantum circuit capable of executing our algorithm, present simulator results, and report numerical experiments on current quantum hardware, confirming the feasibility of preconditioned finite element methods for near-term quantum computing.
We present a quantum preconditioning framework for solving linear systems arising from a finite difference discretization of the Poisson equation. It is based on the combination of the Schrödingerization technique \cite{JLY22b,JLYPRL24} and the BPX multilevel preconditioner in order to achieve near-optimal complexity. The Schrödingerization technique transforms linear partial and ordinary differential equations into Schrödinger-type systems with unitary evolution in one higher dimension, making them suitable for quantum simulation. A key contribution is a structure-aware construction of the block-encoding for the symmetrically preconditioned matrix AS=S⊤ASA_S = S^\top A SAS​=S⊤AS, where AAA is the stiffness matrix and SSS encodes the BPX preconditioner in factored form. By establishing a novel commuting identity, we avoid the unfavorable normalization scaling that would otherwise arise from naive multiplication of block-encodings. This yields an exact block-encoding of ASA_SAS​ with normalization O(d2(L+1))\mathcal{O}(d^2(L+1))O(d2(L+1)), where ddd is the spatial dimension and LLL is the number of levels. Combined with the Schrödingerization-based Hamiltonian simulation, the overall quantum algorithm achieves a query complexity of O(poly(d)ε−1polylog(ε−1))\mathcal{O}\big(\mathrm{poly}(d)\varepsilon^{-1} \mathrm{polylog}(\varepsilon^{-1}) \big)O(poly(d)ε−1polylog(ε−1)) for estimating linear functionals of the solution to a given tolerance ε\varepsilonε.
Preconditioning is a fundamental technique for accelerating classical linear system solvers, and understanding when its benefits persist in quantum linear system (QLS) solvers is important for assessing the practical resource requirements of quantum linear algebra. In QLS algorithms, however, the potential advantage of preconditioning may be offset by the normalization overhead incurred by composing separate block-encodings of the system matrix and the preconditioner, as observed in recent work. This limitation leaves open whether additional algebraic structure can make preconditioning effective in quantum access models. Motivated by this question, we show that Pauli-structured representations of both the system matrix and the preconditioner allow the preconditioned operator to be accessed through regrouped Pauli expansions. In this setting, algebraic regrouping of Pauli products can reduce the Pauli coefficient weight of the preconditioned operator, thereby altering the normalization parameters relevant to quantum algorithms. We derive explicit size and coefficient-weight bounds for the regrouped Pauli representations, and we trace their consequences for both direct block-encoding constructions and randomized Pauli linear system solvers. These results identify when Pauli-structured preconditioning can reduce the effective complexity parameters of QLS algorithms, rather than merely improving the classical condition number. Numerical experiments on a finite-dimensional synthetic benchmark show reductions in norm-aware direct block-encoding diagnostics and in the randomized QLS per-sample depth proxy.
Recently, quantum computing emerged as a paradigm for solving systems of linear equations.However, large condition numbers significantly increase the computational complexity of quantum linear equation solvers.In this work, a new quantum preconditioning approach called variational quantum eigen-decomposition (VQED) is proposed, where the preconditioner is defined as a weighted projector onto the subspace spanned by the eigenvectors of a matrix.A variational quantum algorithm with projection-based deflation is performed to calculate eigenvalueeigenvector pairs for constructing the preconditioner.The proposed VQED method is used with quantum singular value transformation to solve linear systems for mechanics examples.It is demonstrated that the VQED can reduce the condition numbers to as low as 1.03, which is a significant improvement over the original condition number.
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.
The spectral condition number is a widely adopted measure of worst-case cost for quantum linear system solvers. Yet it can significantly overestimate the actual runtime for a typical problem instance. We present two quantum algorithms that produce the normalized solution ∣x⟩|x\rangle∣x⟩ of linear system Ax=∣b⟩Ax=| b \rangleAx=∣b⟩ to accuracy εεε with complexity independent of the condition number κ=∥A−1∥κ=\lVert A^{-1}\rVertκ=∥A−1∥. We focus on the standard input model where AAA is accessed through a block encoding and ∣b⟩| b \rangle∣b⟩ is prepared by a unitary. But we also introduce an affine dilation model that encodes AAA and ∣b⟩| b \rangle∣b⟩ jointly, allowing further refinements of the query complexity. Our truncation-based solver makes an optimal number of queries to ∣b⟩| b \rangle∣b⟩ and O⁡(κeffpolylog⁡(κeffε))\operatorname{\mathbf{O}}\left(κ_{\mathrm{eff}}\operatorname{polylog}\left(\frac{κ_{\mathrm{eff}}}ε\right)\right)O(κeff​polylog(εκeff​​)) queries to AAA. We prove a family of upper bounds on the effective condition number, including κeff≤∥(A†A)−t/2∣x⟩∥1/tε1/tκ_{\mathrm{eff}}\leq\frac{\lVert(A^\dagger A)^{-t/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}κeff​≤ε1/t∥(A†A)−t/2∣x⟩∥1/t​ for positive even integer ttt and κeff≤∥A−1†(A†A)−(t−1)/2∣x⟩∥1/tε1/tκ_{\mathrm{eff}}\leq\frac{\lVert A^{-1\dagger}(A^\dagger A)^{-(t-1)/2}|x\rangle\rVert^{1/t}}{ε^{1/t}}κeff​≤ε1/t∥A−1†(A†A)−(t−1)/2∣x⟩∥1/t​ for positive odd ttt, overcoming the κκκ-barrier. Our filtering-based solver is extremely simple with a favorable runtime prefactor. In particular, the solver has query complexity 3∥A−1†∣x⟩∥ε3\frac{\lVert A^{-1\dagger}|x\rangle\rVert}ε3ε∥A−1†∣x⟩∥​ to leading order when the solution norm is known. We then present a similarly simple solution norm estimator with the same asymptotic cost up to logarithmic factors. Our quantum linear system solvers thus substantially improve a recent algorithm of Li, enabling faster quantum linear system solving beyond the condition number.