Quantum realization of the finite element method

This paper presents a quantum algorithm for the solution of prototypical second-order linear elliptic partial differential equations discretized by <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -linear finite elements on Cartesian grids of a bounded <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="monospace t monospace o monospace l"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="monospace">t</mml:mi> <mml:mi mathvariant="monospace">o</mml:mi> <mml:mi mathvariant="monospace">l</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathtt {tol}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with an optimal complexity of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="monospace t monospace o monospace l Superscript negative 1"> <mml:semantics> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="monospace">t</mml:mi> <mml:mi mathvariant="monospace">o</mml:mi> <mml:mi mathvariant="monospace">l</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:annotation encoding="application/x-tex">\mathtt {tol}^{-1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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.