Quantum Time Marching Algorithms for Simulating Linear Transport Problems

To address this, we introduce a novel approach for treating diffusion that maintains optimal success probabilities with linear scaling in time. The strategy employs the unitary decomposition into Pauli matrices (or their tensor products) to represent the time-marching operator for modeling heat conduction. This decomposition is then block-encoded using the Linear Combination of Unitaries (LCU) algorithm [5], providing additional degrees of freedom to neutralize the sub-normalization factors. As a result, the temporal evolution of the parabolic equation can be simulated in a time-marching approach without deficiencies in the success probabilities. Notably, the cumulative probability of success converges for steady-state solutions and depends only on the temporal distance between initial and final state, making this probability a problem intrinsic property.

To incorporate boundary conditions, the method of images associates the boundary type with odd (Dirichlet) or even (Neumann) reflections of the solution over the non-periodic dimension [4]. Using this domain decomposition technique, the boundaries are reconstructed from neighboring interior points. This enables the use of a discrete periodic operator while conserving the non-vanishing success probabilities of the time-marching method. An alternative algorithm is also presented for Neumann conditions, where the unitary decomposition of the bounded time-marching operator is directly applied to the LCU method, eliminating the need for spatial reflection.

The total number of qubits scales as  O(log2(N) + log2 (d) + d), where d is the spatial dimension and N the total number of sampling points, while the number of attempts required for a successful execution over a given time interval T is determined by the inverse of the cumulative success probability. Since the gate complexity grows linearly with the number of time steps and taking into account the stability limits of explicit approximation schemes, the implementation has a gate complexity of O((log2(N)+log2(d)+d) T N^(2/d)). In contrast, the complexity of classical algorithms scale as O(T N^((2+d)/d)). Comparing the exponent of these complexities, the factor 2/(2+d) indicates a polynomial speed up of the proposed quantum algorithm over classical algorithms.

The potential of the method is demonstrated by benchmarking two-dimensional state-vector simulations of the unsteady, non-periodic heat equation against classical second-order accurate central finite differences. The results for homogeneous Neumann, Dirichlet, and mixed boundaries demonstrate unequivocally the practical feasibility of the proposed method for implementation on a fault-tolerant QC with very high accuracy while maintaining optimal success probabilities with linear time scaling. Furthermore, the approach can be straightforwardly extended to arbitrary dimensions. The presented treatment of diffusive dynamics could be extended to implement additional non-unitary processes, while the application of the boundary approach to other initial-boundary value problems in structural, fluid, or quantum mechanics is worth exploring in future research.