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:2403.19512 · Mathematics of Computation

Quantum realization of the finite element method

M. Deiml, Daniel Peterseim

Published Aug 14, 2025• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1090/mcom/4137

Related papers

A Quantum Algorithm for the Finite Element Method

Ahmad M. Alkadri, Tyler Kharazi, K. Birgitta Whaley +1 more

The finite element method (FEM) is a cornerstone numerical technique for solving partial differential equations (PDEs). Here, we present $\textbf{Qu-FEM}$, a fault-tolerant era quantum algorithm for the finite element method. In contrast to other quantum PDE solvers, Qu-FEM preserves the geometric flexibility of FEM by introducing two new primitives, the unit of interaction and the local-to-global indicator matrix, which enable the assembly of global finite element arrays with a constant-size linear combination of unitaries. We study the modified Poisson equation as an elliptic problem of interest, and provide explicit circuits for Qu-FEM in Cartesian domains. For problems with constant coefficients, our algorithm admits block-encodings of global arrays that require only $\tilde{\mathcal{O}}\left(d^2 p^2 n\right)$ Clifford+$T$ gates for $d$-dimensional, order-$p$ tensor product elements on grids with $2^n$ degrees of freedom in each dimension, where $n$ is the number of qubits representing the $N=2^n$ discrete grid points. For problems with spatially varying coefficients, we perform numerical integration directly on the quantum computer to assemble global arrays and force vectors. Dirichlet boundary conditions are enforced via the method of Lagrange multipliers, eliminating the need to modify the block-encodings that emerge from the assembly procedure. This work presents a framework for extending the geometric flexibility of quantum PDE solvers while preserving the possibility of a quantum advantage.

arXiv:2510.18150•Oct 20, 2025•0 citations

Quantum Domain Decomposition for Preconditioning the Finite Element Method

Elise Fressart, Michel Nowak, Nicole Spillane

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.

math.NACross-listedarXiv:2605.26090•May 26, 2026•0 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

High-precision quantum algorithms for partial differential equations

Andrew M. Childs, Jin-Peng Liu, Aaron Ostrander

Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity p o l y ( 1 / ϵ ) , where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be p o l y ( d , log ⁡ ( 1 / ϵ ) ) , where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.

arXiv:2002.07868•Quantum•Nov 10, 2021•154 citations

A Variational Quantum Linear Solver Application to Discrete Finite-Element Methods

Corey Jason Trahan, Mark Loveland, Noah A. Davis +1 more

Finite-element methods are industry standards for finding numerical solutions to partial differential equations. However, the application scale remains pivotal to the practical use of these methods, even for modern-day supercomputers. Large, multi-scale applications, for example, can be limited by their requirement of prohibitively large linear system solutions. It is therefore worthwhile to investigate whether near-term quantum algorithms have the potential for offering any kind of advantage over classical linear solvers. In this study, we investigate the recently proposed variational quantum linear solver (VQLS) for discrete solutions to partial differential equations. This method was found to scale polylogarithmically with the linear system size, and the method can be implemented using shallow quantum circuits on noisy intermediate-scale quantum (NISQ) computers. Herein, we utilize the hybrid VQLS to solve both the steady Poisson equation and the time-dependent heat and wave equations.

Entropy•Mar 28, 2023•33 citations

A structure-aware construction of quantum BPX preconditioners for Q1 finite element discretizations of reaction-diffusion problems

Yin Yang, Yue Yu, Long Zhang

We present a structure-aware construction of quantum BPX preconditioners for Q1 finite element discretizations of constant-coefficient reaction--diffusion equations on the unit cube, including the Poisson equation. Building on existing quantum finite element and finite difference methods, we express the preconditioned operator through explicit one-dimensional maps, tensor products, and norm-preserving interlevel transfers. Symmetric preconditioning gives multilevel coefficients, and its favorable conditioning alone does not ensure efficient recovery of a state in the original finite element nodal basis. We instead use the local $L^2$-orthonormal basis underlying the construction as the output representation of the same finite element function. Its coefficient norm equals the continuous $L^2$ norm. Assuming direct access to the preconditioned right-hand side, we prepare this orthonormal coefficient state with a represented function error at most $\varepsilon$. The expected query complexity is \[ \mathcal{O}\!\Big(dL^3\frac{\|f\|_{L^2}}{\|u\|_{L^2}} \log\!\Big(2+\frac{L\|f\|_{L^2}}{\varepsilon}\Big)\Big), \] where $u$ is the exact solution, $f$ is the right-hand side, $d$ is the spatial dimension, and $L=\log_2(1/h)$ for mesh width $h$. The bound holds for $0<\varepsilon\le\|u\|_{L^2}/2$ and depends only polylogarithmically on mesh refinement for fixed continuous data. We also analyze linear-functional estimation and illustrate the construction and continuous error bounds with a one-dimensional UnitaryLab experiment.

arXiv:2610.06987•Oct 4, 2026•0 citations
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.
The finite element method (FEM) is a cornerstone numerical technique for solving partial differential equations (PDEs). Here, we present Qu-FEM\textbf{Qu-FEM}Qu-FEM, a fault-tolerant era quantum algorithm for the finite element method. In contrast to other quantum PDE solvers, Qu-FEM preserves the geometric flexibility of FEM by introducing two new primitives, the unit of interaction and the local-to-global indicator matrix, which enable the assembly of global finite element arrays with a constant-size linear combination of unitaries. We study the modified Poisson equation as an elliptic problem of interest, and provide explicit circuits for Qu-FEM in Cartesian domains. For problems with constant coefficients, our algorithm admits block-encodings of global arrays that require only O~(d2p2n)\tilde{\mathcal{O}}\left(d^2 p^2 n\right)O~(d2p2n) Clifford+TTT gates for ddd-dimensional, order-ppp tensor product elements on grids with 2n2^n2n degrees of freedom in each dimension, where nnn is the number of qubits representing the N=2nN=2^nN=2n discrete grid points. For problems with spatially varying coefficients, we perform numerical integration directly on the quantum computer to assemble global arrays and force vectors. Dirichlet boundary conditions are enforced via the method of Lagrange multipliers, eliminating the need to modify the block-encodings that emerge from the assembly procedure. This work presents a framework for extending the geometric flexibility of quantum PDE solvers while preserving the possibility of a quantum advantage.
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.
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ε.
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity p o l y ( 1 / ϵ ) , where ϵ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be p o l y ( d , log ⁡ ( 1 / ϵ ) ) , where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.
Finite-element methods are industry standards for finding numerical solutions to partial differential equations. However, the application scale remains pivotal to the practical use of these methods, even for modern-day supercomputers. Large, multi-scale applications, for example, can be limited by their requirement of prohibitively large linear system solutions. It is therefore worthwhile to investigate whether near-term quantum algorithms have the potential for offering any kind of advantage over classical linear solvers. In this study, we investigate the recently proposed variational quantum linear solver (VQLS) for discrete solutions to partial differential equations. This method was found to scale polylogarithmically with the linear system size, and the method can be implemented using shallow quantum circuits on noisy intermediate-scale quantum (NISQ) computers. Herein, we utilize the hybrid VQLS to solve both the steady Poisson equation and the time-dependent heat and wave equations.
We present a structure-aware construction of quantum BPX preconditioners for Q1 finite element discretizations of constant-coefficient reaction--diffusion equations on the unit cube, including the Poisson equation. Building on existing quantum finite element and finite difference methods, we express the preconditioned operator through explicit one-dimensional maps, tensor products, and norm-preserving interlevel transfers. Symmetric preconditioning gives multilevel coefficients, and its favorable conditioning alone does not ensure efficient recovery of a state in the original finite element nodal basis. We instead use the local L2L^2L2-orthonormal basis underlying the construction as the output representation of the same finite element function. Its coefficient norm equals the continuous L2L^2L2 norm. Assuming direct access to the preconditioned right-hand side, we prepare this orthonormal coefficient state with a represented function error at most ε\varepsilonε. The expected query complexity is O ⁣(dL3∥f∥L2∥u∥L2log⁡ ⁣(2+L∥f∥L2ε)), \mathcal{O}\!\Big(dL^3\frac{\|f\|_{L^2}}{\|u\|_{L^2}} \log\!\Big(2+\frac{L\|f\|_{L^2}}{\varepsilon}\Big)\Big), O(dL3∥u∥L2​∥f∥L2​​log(2+εL∥f∥L2​​)), where uuu is the exact solution, fff is the right-hand side, ddd is the spatial dimension, and L=log⁡2(1/h)L=\log_2(1/h)L=log2​(1/h) for mesh width hhh. The bound holds for 0<ε≤∥u∥L2/20<\varepsilon\le\|u\|_{L^2}/20<ε≤∥u∥L2​/2 and depends only polylogarithmically on mesh refinement for fixed continuous data. We also analyze linear-functional estimation and illustrate the construction and continuous error bounds with a one-dimensional UnitaryLab experiment.