Schrodingerization based quantum algorithms for the time-fractional heat equation

We develop a quantum algorithm for solving high-dimensional time-fractional heat equations. By applying the dimension extension technique from [FKW23], the $d+1$-dimensional time-fractional equation is reformulated as a local partial differential equation in $d+2$ dimensions. Through discretization along both the extended and spatial domains, a stable system of ordinary differential equations is obtained by a simple change of variables. We propose a quantum algorithm for the resulting semi-discrete problem using the Schrodingerization approach from [JLY24a,JLY23,JL24a]. The Schrodingerization technique transforms general linear partial and ordinary differential equations into Schrodinger-type systems--with unitary evolution, making them suitable for quantum simulation. This is accomplished via the warped phase transformation, which maps the equation into a higher-dimensional space. We provide detailed implementations of this method and conduct a comprehensive complexity analysis, demonstrating up to exponential advantage--with respect to the inverse of the mesh size in high dimensions~--~compared to its classical counterparts. Specifically, to compute the solution to time T, while the classical method requires at least O(Nₜ d h-(d+0.5)) matrix-vector multiplications, where Nₜ is the number of time steps (which is, for example, O(Tdh⁻²) for the forward Euler method), our quantum algorithms requires O(T²d⁴ h⁻⁸) queries to the block-encoding input models, with the quantum complexity being independent of the dimension d in terms of the inverse mesh size h⁻¹. Numerical experiments are performed to validate our formulation.