Quantum Realization of the Finite Element Method
arXiv:2403.19512 · doi:10.1090/mcom/4137
Abstract
This paper presents a quantum algorithm for the solution of prototypical second-order linear elliptic partial differential equations discretized by -linear finite elements on Cartesian grids of a bounded -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 with an optimal complexity of order up to logarithmic terms, significantly improving over existing approaches. Notably, this approach does not rely on regularity of the solution and achieves quantum advantage over classical solvers 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.
Updated version contains experiments on real quantum hardware and clarifications in Theorem 6.5. Article accepted in Mathematics of Computation
References in corpus (24)
- Quantum algorithm for solving linear systems of equations
- Efficient classical simulation of slightly entangled quantum computations
- Quantum fingerprinting
- Quantum Error Correction for Beginners
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Quantum Error Mitigation
- Hamiltonian simulation with nearly optimal dependence on all parameters
- A Race Track Trapped-Ion Quantum Processor
- Preconditioned quantum linear system algorithm
- High-order quantum algorithm for solving linear differential equations
- Amplitude estimation without phase estimation
- Quantum algorithm for linear differential equations with exponentially improved dependence on precision
- Quantum algorithms and the finite element method
- Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
- Quantum algorithm and circuit design solving the Poisson equation
- High-precision quantum algorithms for partial differential equations
- Quantum spectral methods for differential equations
- Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
- Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
- Quantum simulation of partial differential equations via Schrodingerisation: technical details
- Quantum Circulant Preconditioner for Linear System of Equations
- Towards Quantum Computational Mechanics
- Quantum Circuits for partial differential equations via Schrödingerisation
- Variational quantum algorithm for generalized eigenvalue problems and its application to the finite element method