Fourier extensions for block encoding matrix functions

Fourier extensions express functions as a linear combination of complex exponentials. They approximate the target non-periodic function on a sub-interval of a larger periodic domain. This allows the non-periodic function to be approximated with exponential convergence by a Fourier series [2]. This approach can be complemented with Sobolev regularisation to exploit the redundancy of the basis to minimise subnormalisation for a given target error. When applying the Fourier extension to Hermitian matrix inputs, it becomes a linear combination of unitary operators [1] that recover the target function. For example, using f(x) = x results in an exponentially convergent linear combination of unitaries decomposition. By using f(x) = e^x or f(x) = 1/x, the method can be used to solve partial differential equations or to invert matrices. 

The approach decomposes arbitrary matrix functions into a linear combination of Hamiltonian simulations. We have validated the approach through statevector simulations of solving the heat equation using three different methodologies. Firstly, explicit time marching expresses the problem as a matrix multiplication problem; using f(x) = x prepares an exponentially convergent linear combination of unitaries of the time-marching operator. On the other hand, using implicit time marching expresses a time step as a matrix inversion problem, where we use f(x) = 1/x to perform this inversion. Finally, using a Fourier extension of f(x) = e^x allows us to evolve the dynamics directly in a single shot. The results show exponential convergence up to the target error, followed by a reduction in the subnormalisation of the block encoding to the near-optimal value of the spectral norm of the target operator. 

Linear combination of unitaries is arguably the most popular approach for constructing block encodings of non-unitary operators. However, a major challenge has been the identification of suitable decompositions of the intended operator into a linear combinations of unitaries. Existing general methods result in a major trade-off between the accuracy of the block, and its amplitude. The proposed approach, based on Sobolev regularised Fourier extensions, decouples the block accuracy from its amplitude. Since it has exponential convergence, matrix multiplication, inversion, or exponentiation problems using the approach generally improve exponentially over their classical counterparts. The implementation of the specific Hamiltonian simulations remains application dependent, but we show how this can be done for the problem of lossy mechanical wave propagation described by the damped wave equation.