A quantum-based solver for the heat equation

Our numerical solution technique is based on finite differences or elements for the spatial discretization as well as the implicit Euler method for the time integration. In each time step, the implicit Euler method requires the solution of a linear system of equations. Since we want to avoid a sequantial time-stepping, we combine the single systems of equations resulting in a large linear system of equations for the whole space-time discretization. To solve this linear system of equations, there is a variety of quantum linear systems solvers (QLSS), which are listed in the survey article [1]. Here, we utilize a QSVT (Quantum Singular Value Transformation)-based solver [2], requiring a unitary block encoding [3] of the matrix obtained from the space-time discretization (space-time matrix). Due to the fact that the space-time matrix can be represented as a linear combination of tensor products of identity and shift operators, the block encoding of this matrix is constructed via a linear combination of elementary block encodings. For example, the block encodings of the lower/upper diagonals can be realized by shift operators and cyclic adders [4]. 

The proposed method is implemented using the high-level quantum programming language Eclipse Qrisp [5], leveraging its Block Encoding programming abstraction and Generalized Quantum Signal Processing library [6]. Qrisp has been developed by the Fraunhofer Institute FOKUS to facilitate the implementation of quantum algorithms based on concepts from classical programming languages [7]. Two concepts that have been adapted from classical programming are, e.g., the use of variables as well as the use of functions. To validate our quantum-based solver, we run small-scale simulations using the statevector simulator provided by Qrisp. We demonstrate the successful extraction of the solution for a one-dimensional heat equation, exhibiting high fidelity when compared to the classical solution of the linear system. Moreover, it is shown that macroscopic quantities such as the average of a solution can be determined with sufficient accuracy.

Besides the numerical simulations, we use the tools of Qrisp to perform a resource estimation, i.e., we show how the number of qubits, gates and the depth of the underlying circuits scale with the number of unknows of the space-time system. In particular, we estimate the Clifford + T-gate cost for the block encoding of the space-time matrix. While the space-time solver succeeds in mitigating exponentially decreasing success probabilities, the condition number of the space-time matrix still scales in case of standard finite differences and a one-dimensional heat equation with O(N_x^2), where N_x is the number of unknowns of the spatial discretization. This reveals a fundamental limitation for low-dimensional implementations: The query complexity for the QSVT-based solver scales as O(N_x^4 polylog(N_x))[8], and the query complexity of the (near-) optimal Dalzell solver scales as O(N_x^2) [9]. Denoting by N_t the number of time steps, it can be shown that classical linear solvers (such as the Thomas algorithm or multigrid methods) can solve the system using O(N_t N_x) floating point operations and O(N_t N_x^2) floating point operations in the case of one- and two-dimensional problems, respectively. Thus, there is no practical quantum advantage in these low-dimensional scenarios, if N_t and N_x are approximately of the same size. To circumvent this drawback preconditioners and further discretization methods, such as finite element methods with hierarchical bases [10], are considered. Moreover, our considerations reveal that a possible quantum advantage can be achieved by extending this method to problems with higher space dimensions.