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• 30 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•9 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•1 citation

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•16 citations

Quantum algorithms and the finite element method

Ashley Montanaro, Sam Pallister

The finite element method is used to approximately solve boundary value problems for differential equations. The method discretizes the parameter space and finds an approximate solution by solving a large system of linear equations. Here we investigate the extent to which the finite element method can be accelerated using an efficient quantum algorithm for solving linear equations. We consider the representative general question of approximately computing a linear functional of the solution to a boundary value problem and compare the quantum algorithm's theoretical performance with that of a standard classical algorithm---the conjugate gradient method. Prior work claimed that the quantum algorithm could be exponentially faster but did not determine the overall classical and quantum run times required to achieve a predetermined solution accuracy. Taking this into account, we find that the quantum algorithm can achieve a polynomial speedup, the extent of which grows with the dimension of the partial differential equation. In addition, we give evidence that no improvement of the quantum algorithm can lead to a superpolynomial speedup when the dimension is fixed and the solution satisfies certain smoothness properties.

arXiv:1512.05903•Physical Review A•Mar 17, 2016•231 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•219 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•43 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ε.
The finite element method is used to approximately solve boundary value problems for differential equations. The method discretizes the parameter space and finds an approximate solution by solving a large system of linear equations. Here we investigate the extent to which the finite element method can be accelerated using an efficient quantum algorithm for solving linear equations. We consider the representative general question of approximately computing a linear functional of the solution to a boundary value problem and compare the quantum algorithm's theoretical performance with that of a standard classical algorithm---the conjugate gradient method. Prior work claimed that the quantum algorithm could be exponentially faster but did not determine the overall classical and quantum run times required to achieve a predetermined solution accuracy. Taking this into account, we find that the quantum algorithm can achieve a polynomial speedup, the extent of which grows with the dimension of the partial differential equation. In addition, we give evidence that no improvement of the quantum algorithm can lead to a superpolynomial speedup when the dimension is fixed and the solution satisfies certain smoothness properties.
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.