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.
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.
In recent years, quantum linear system algorithms have been applied to partial differential equations (PDEs), particularly in high-dimensional settings, demonstrating an exponential speedup in dimension. Concurrently, randomized and quantum-inspired classical linear solvers have emerged, showing computational complexity comparable to their quantum counterparts in many application areas. In this paper, we investigate the applicability of these quantum-inspired classical algorithms to PDEs. We provide both upper and lower bounds on their computational complexity, proving that these methods cannot achieve exponential speedup in dimension for discretizations of high-dimensional Poisson problems. Our theoretical findings definitively demonstrate that quantum-inspired classical algorithms are not competitive with quantum algorithms for solving PDEs, confirming that quantum methods retain a significant advantage for high-dimensional problems.
Abstract The radial basis function (RBF) method is widely used for the numerical solution of the Poisson problem in high dimension, where the approximate solution can be found by solving a large system of linear equations. We demonstrate that the RBF method can be accelerated on a quantum computer by using an efficient quantum algorithm for linear equations. We compare the theoretical performance of our quantum algorithm with that of a standard classical algorithm, and find that the quantum algorithm can achieve a polynomial speedup.
Structural mechanics is commonly modeled by (systems of) partial differential equations (PDEs). Except for very simple cases where analytical solutions exist, the use of numerical methods is required to find approximate solutions. However, for many problems of practical interest, the computational cost of classical numerical solvers running on classical, that is, silicon-based computer hardware, becomes prohibitive. Quantum computing, though still in its infancy, holds the promise of enabling a new generation of algorithms that can execute the most cost-demanding parts of PDE solvers up to exponentially faster than classical methods, at least theoretically. Also, increasing research and availability of quantum computing hardware spurs the hope of scientists and engineers to start using quantum computers for solving PDE problems much faster than classically possible. This work reviews the contributions that deal with the application of quantum algorithms to solve PDEs in structural mechanics. The aim is not only to discuss the theoretical possibility and extent of advantage for a given PDE, boundary conditions and input/output to the solver, but also to examine the hardware requirements of the methods proposed in literature.
Quantum computers have the potential to solve some complex problems much faster than classical equivalents. Significant research efforts are aimed at determining which algorithms give which advantages for different use-cases. An application where quantum computers can possibly bring great advantages is solving (partial) differential equations, which has a broad set of applications, for instance in wave-propagation models. Few differential equations admit an analytical solution. For most heuristic methods are required to approximate a solution. Well-known heuristic techniques include the finite element and finite difference method, where the considered space is partitioned and systems of linear equations resulting from this partitioning need to be solved. Quantum computing puts forward new methods to solve these systems of linear equations and hence these differential equations. First, the HHL algorithm gives an efficient way to solve a linear system of equations. The HHL algorithm comes with drawbacks, but in this specific use-case some of these objections might be circumvented. Quantum computers furthermore offer the variational approach: an optimization-based path to solving differential equations. With this approach, the devices might even ‘learn’ the noise patterns emerging in present day quantum computers and compensate for it. In this work we revisit quantum methods for solving partial differential equations and consider how well they work in solving differential equations in practice. We also discuss possible caveats and bottlenecks of the approaches.
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.
Quantum methods for solving partial differential equations (PDEs) generally fall into a few general categories, each leveraging different quantum mechanisms to achieve potential speedups. One well-known approach is the quantum linear system solver, epitomized by the Harrow-Hassidim-Lloyd (HHL) algorithm, which uses phase estimation and eigenvalue inversion to solve large, sparse linear systems arising from discretized linear PDEs [1]. This method can yield exponential improvements over classical solvers under certain conditions (mostly when the matrix is well-conditioned and sparse). More recent developments, such as Quantum Singular Value Transformation (QSVT), provide a framework for matrix inversion in a more flexible way, often improving on the cost and error dependence of earlier solvers [2]. Time-dependent PDEs can be tackled via Hamiltonian simulations. The Trotter-Suzuki method decomposes the exponential of a Hamiltonian into products of exponentials of simpler sub-Hamiltonians, allowing a piecewise approximation of continuous dynamics [3]. Continuous-time quantum walks, which treat a PDE operator as a Hamiltonian that governs the walk, similarly simulate processes like diffusion or wave propagation on discretized grids or graphs [4]. Beyond direct simulation, variational quantum algorithms have emerged as a promising route in the noisy intermediate-scale quantum era. These approaches encode the PDE solution as a parameterized quantum state and optimize the parameters via classical feedback, thereby minimizing a cost function tied to the PDE residual or energy functional [5]. Quantum annealing or adiabatic methods, meanwhile, can solve optimization problems derived from PDE constraints by adiabatically evolving a simple initial Hamiltonian to the final problem Hamiltonian and staying in the system's ground state [3]. In our study, we implement a new parameterized quantum model, specifically designed to solve large linear systems on quantum hardware. This model is less deep and computationally faster than the proposed one in [5], reducing the complexity and speeding up convergence times. Such improvements are particularly valuable in cases where classical algorithms may fail due to the problem's size or complexity. Ongoing research is focusing on generalized quantum models that can be adapted to practical PDE problems for solving large electromagnetic problems where classical computers can fail.