We describe a quantum algorithm for preparing states that encode solutions of nonhomogeneous linear partial differential equations. The algorithm is a continuous-variable version of matrix inversion: it efficiently inverts differential operators that are polynomials in the variables and their partial derivatives. The output is a quantum state whose wave function is proportional to a specific solution of the nonhomogeneous differential equation, which can be measured to reveal features of the solution. The algorithm consists of three stages: preparing fixed resource states in ancillary systems, performing Hamiltonian simulation, and measuring the ancilla systems. The algorithm can be carried out using standard methods for gate decompositions, but we improve this in two ways. First, we show that for a wide class of differential operators, it is possible to derive exact decompositions for the gates employed in Hamiltonian simulation. This avoids the need for costly commutator approximations, reducing gate counts by orders of magnitude. Additionally, we employ methods from machine learning to find explicit circuits that prepare the required resource states. We conclude by studying two example applications of the algorithm: solving Poisson's equation in electrostatics and performing one-dimensional integration.
We describe a quantum algorithm for preparing states that encode solutions of nonhomogeneous linear partial differential equations. The algorithm is a continuous-variable version of matrix inversion: it efficiently inverts differential operators that are polynomials in the variables and their partial derivatives. The output is a quantum state whose wave function is proportional to a specific solution of the nonhomogeneous differential equation, which can be measured to reveal features of the solution. The algorithm consists of three stages: preparing fixed resource states in ancillary systems, performing Hamiltonian simulation, and measuring the ancilla systems. The algorithm can be carried out using standard methods for gate decompositions, but we improve this in two ways. First, we show that for a wide class of differential operators, it is possible to derive exact decompositions for the gates employed in Hamiltonian simulation. This avoids the need for costly commutator approximations, reducing gate counts by orders of magnitude. Additionally, we employ methods from machine learning to find explicit circuits that prepare the required resource states. We conclude by studying two example applications of the algorithm: solving Poisson's equation in electrostatics and performing one-dimensional integration.
Recently, J. M. Arrazola et al. [Phys. Rev. A 100, 032306 (2019)] proposed a quantum algorithm for solving nonhomogeneous linear partial differential equations of the form $A\ensuremath{\psi}(\mathbf{r})=f(\mathbf{r})$. Its nonhomogeneous solution is obtained by inverting the operator $\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{A}$ along with the preparation and measurement of special ancillary modes. In this work we suggest modifications in its structure to reduce the costs of preparing the initial ancillary states and improve the precision of the algorithm for semidefinite operators. These achievements enable easier experimental implementation of the quantum algorithm.
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.
Many computational fluid dynamics (CFD) algorithms solve partial differential equations by discretization, resulting in large and sparse systems of linear equations. While iterative methods are widely used to solve these systems classically, most existing quantum linear system solvers target the solution through matrix inversion rather than approximating it using an iterative procedure. In this work, we develop a quantum implementation of the Jacobi method based on quantum singular value transformation (QSVT). By reformulating the Jacobi iteration as a polynomial transformation of a block-encoded operator, the algorithm requires only a constant ancilla overhead with respect to the number of iterations while maintaining a circuit depth that scales linearly with the iteration number. We demonstrate the algorithm for one- and two-dimensional Poisson problems, including the pressure Poisson equation arising in Chorin's projection method for the lid-driven cavity flow. The proposed algorithm provides a promising building block for future quantum implementations of multigrid methods and preconditioning techniques, bringing quantum algorithms closer to established CFD solution strategies.
Partial differential equations (PDEs) are crucial for modeling various physical phenomena such as heat transfer, fluid flow, and electromagnetic waves. In computer-aided engineering (CAE), the ability to handle fine resolutions and large computational models is essential for improving product performance and reducing development costs. However, solving large-scale PDEs, particularly for systems with spatially varying material properties, poses significant computational challenges. In this paper, we propose a quantum algorithm for solving second-order linear PDEs of nonconservative systems with spatially varying parameters, using the linear combination of the Hamiltonian simulation (LCHS) method. Our approach transforms those PDEs into ordinary differential equations represented by qubit operators, through spatial discretization using the finite-difference method. Then, we provide an algorithm that efficiently constructs the operator corresponding to the spatially varying parameters of PDEs via a logic minimization technique, which reduces the number of terms and subsequently the circuit depth. We also develop a scalable method for realizing a quantum circuit for LCHS, using a tensor-network-based technique, specifically a matrix product state (MPS). We validate our method with applications to the acoustic equation with spatially varying parameters and the dissipative heat equation. Our approach includes a detailed recipe for constructing quantum circuits for PDEs, leveraging efficient encoding of spatially varying parameters of PDEs and scalable implementation of LCHS, which we believe marks a significant step towards advancing quantum computing's role in solving practical engineering problems.
In numerical approaches to solving differential equations on a lattice, a representation of the derivative operator that correctly matches the continuum behaviour of functions of momentum up to the band limit must be non-local. We present the construction of efficient linear-combination-of-unitaries (LCU)-based block-encodings for the first-order derivative and Laplacian operators in the non-local N=2n-dimensional SLAC representation. We use state-preparation techniques designed for smoothly decaying functions to prepare the dense LCU amplitudes with high success probability and low gate cost. Furthermore, we demonstrate how Shannon wavelet transforms can be applied to these block-encodings to obtain multiscale representations of the SLAC derivative operators. We then show how to apply a diagonal preconditioner that reduces the condition number of these matrices in the multiscale wavelet basis to a small constant. This enables the solution of partial differential equations (PDEs) with SLAC-discretised derivative operators on a finite lattice using the quantum linear solving algorithm (QLSA). For a d-dimensional PDE, after projection away from the nullspace, the resulting quantum linear-system algorithm has overall gate complexity O(dn3α(k)log(1/ε)), where α(k) is the subnormalisation factor of the order-k SLAC block-encoding and ε denotes the algorithmic approximation error.