We develop a quantum algorithm to solve a type of linear reaction-diffusion equation, the neutron diffusion (generalized) k-eigenvalue problem that establishes nuclear criticality. The algorithm handles an equation with piecewise constant coefficients, describing a problem in a heterogeneous medium. We apply uniform finite elements and show that the quantum algorithm provides significant polynomial end-to-end speedup over classical uniform finite element methods in the cases tested, although nonuniform classical methods can perform much better than uniform ones. Our work leverages recent advances in quantum linear systems--fast inversion and quantum preconditioning--and uses Hamiltonian simulation as a subroutine. Our results suggest that quantum algorithms may provide speedups for heterogeneous PDEs, though the extent of this advantage over the fastest classical algorithm depends on the effectiveness of other classical approaches such as nonuniform or adaptive meshing for a given problem instance.
We develop a quantum algorithm to solve a type of linear reaction-diffusion equation, the neutron diffusion (generalized) k-eigenvalue problem that establishes nuclear criticality. The algorithm handles an equation with piecewise constant coefficients, describing a problem in a heterogeneous medium. We apply uniform finite elements and show that the quantum algorithm provides significant polynomial end-to-end speedup over classical uniform finite element methods in the cases tested, although nonuniform classical methods can perform much better than uniform ones. Our work leverages recent advances in quantum linear systems--fast inversion and quantum preconditioning--and uses Hamiltonian simulation as a subroutine. Our results suggest that quantum algorithms may provide speedups for heterogeneous PDEs, though the extent of this advantage over the fastest classical algorithm depends on the effectiveness of other classical approaches such as nonuniform or adaptive meshing for a given problem instance.
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.
Quantum computing is a rapidly advancing field, driven by the potential advantages derived from the unique properties of quantum entanglement. In particular, the exponential speedup of certain carefully designed algorithms, compared to their classical counterparts, promises to significantly enhance the numerical solution of a wide range of problems. This paper investigates the integration of quantum computing with the finite element method, focusing on singularly perturbed advection-diffusion-reaction problems. We introduce a novel finite element scheme that combines classical and quantum algorithms. In this approach, the primary mesh adaptation loop is managed by a classical computer, while a specific stabilization procedure is executed on a quantum computer. This procedure leverages the Harrow-Hassidim-Lloyd algorithm in conjunction with the swap test to estimate the value of a linear functional, which constitutes a substantial portion of the computational workload. We demonstrate that this hybrid approach effectively eliminates parasitic oscillations in the finite element approximation, even at the early stages of the adaptation process. This leads to a significant improvement in the quality of intermediate finite element solutions. As a result, our scheme offers more efficient feedback with reduced computational costs for researchers using the method to investigate physical phenomena. To support the scheme, we prove special explicit a posteriori error estimates. Possible benefits of the proposed finite element scheme are analyzed using the numerical comparison with the typical adaptive scheme.
This thesis describes quantum algorithms for Hamiltonian simulation, ordinary differential equations (ODEs), and partial differential equations (PDEs). Product formulas are used to simulate Hamiltonians which can be expressed as a sum of terms which can each be simulated individually. By simulating each of these terms in sequence, the net effect approximately simulates the total Hamiltonian. We find that the error of product formulas can be improved by randomizing over the order in which the Hamiltonian terms are simulated. We prove that this approach is asymptotically better than ordinary product formulas and present numerical comparisons for small numbers of qubits. The ODE algorithm applies to the initial value problem for time-independent first order linear ODEs. We approximate the propagator of the ODE by a truncated Taylor series, and we encode the initial value problem in a large linear system. We solve this linear system with a quantum linear system algorithm (QLSA) whose output we perform a post-selective measurement on. The resulting state encodes the solution to the initial value problem. We prove that our algorithm is asymptotically optimal with respect to several system parameters. The PDE algorithms apply the finite difference method (FDM) to Poisson's equation, the wave equation, and the Klein-Gordon equation. We use high order FDM approximations of the Laplacian operator to develop linear systems for Poisson's equation in cubic volumes under periodic, Neumann, and Dirichlet boundary conditions. Using QLSAs, we output states encoding solutions to Poisson's equation. We prove that our algorithm is exponentially faster with respect to the spatial dimension than analogous classical algorithms. We also consider how high order Laplacian approximations can be used for simulating the wave and Klein-Gordon equations. We consider under what conditions it suffices to use Hamiltonian simulation for time evolution, and we propose an algorithm for these cases that uses QLSAs for state preparation and post-processing.
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.
Quantum computing promises a theoretical computational advantage for solving certain problems, thus it holds significant academic and commercial interest. This thesis begins by reviewing established quantum algorithms and their applications. Then I expand this set to demonstrate quantum computational advantage for solving the drift-diffusion equation, a computationally intensive problem with applications in finance, modelling, and manufacturing. First, I introduce a complexity analysis for four classical algorithms designed to solve the multi-dimensional drift-diffusion equation. I then present four quantum algorithms, leveraging a quantum linear system solver, a quantum Hamiltonian simulation, a quantum random walk, and the quantum Fourier transform. By comparing the complexities of these methods to their classical counterparts, I find that diagonalisation via the quantum Fourier transform offers a quantum computational advantage for solving linear partial differential equations at a fixed final time. I employ a multidimensional amplitude estimation process to extract the full probability distribution from the quantum computer. Finally, I compare the circuit depths for five gate sets to implement a quantum algorithm solving the drift-diffusion equation in two spatial dimensions. This uses the diagonalisation by the quantum Fourier transform algorithm. The gate sets are: an unconstrained gate set, TK1 gate set from Quantinuum, the native gate sets of IBM Heron and IonQ, and Fujitsu’s space-time efficient analog rotation (STAR) gate set. This analysis covers a set of illustrative scenarios using up to 22 qubits. I find that while scaling with spatial resolution aligns with theoretical predictions in one dimension, scaling with spatial dimension is less efficient than theorised due to overhead from block encoding. Finally, using the STAR gate set, I find that even minimal problem instances exceed the operational limits of current quantum hardware. We find that for a test scenario using 22 logical qubits, requires 1 × 106 logical operations, assuming full connectivity.