Efficient and fail-safe quantum algorithm for the transport equation

Abstract

In this paper we present a scalable algorithm for fault-tolerant quantum computers for solving the transport equation in two and three spatial dimensions for variable grid sizes and discrete velocities, where the object walls are aligned with the Cartesian grid, the relative difference of velocities in each dimension is bounded by 1 and the total simulated time is dependent on the discrete velocities chosen. We provide detailed descriptions and complexity analyses of all steps of our quantum transport method (QTM) and present numerical results for 2D flows generated in Qiskit as a proof of concept. Our QTM is based on a novel streaming approach which leads to a reduction in the amount of CNOT gates required in comparison to state-of-the-art quantum streaming methods. As a second highlight of this paper we present a novel object encoding method, that reduces the complexity of the amount of CNOT gates required to encode walls, which now becomes independent of the size of the wall. Finally we present a novel quantum encoding of the particles' discrete velocities that enables a linear speed-up in the costs of reflecting the velocity of a particle, which now becomes independent of the amount of velocities encoded. Our main contribution consists of a detailed description of a fail-safe implementation of a quantum algorithm for the reflection step of the transport equation that can be readily implemented on a physical quantum computer. This fail-safe implementation allows for a variety of initial conditions and particle velocities and leads to physically correct particle flow behavior around the walls, edges and corners of obstacles. Combining these results we present a novel and fail-safe quantum algorithm for the transport equation that can be used for a multitude of flow configurations and leads to physically correct behavior. We finally show that our approach only requires O(n_wn_g²+dn_t^vn_vmax²) CNOT gates, which is quadratic in the amount of qubits necessary to encode the grid and the amount of qubits necessary to encode the discrete velocities in a single spatial dimension. This complexity result makes our approach superior to state-of-the-art approaches known in the literature.