Shock-capturing quantum algorithm for the advection equation

Quantum computing algorithms have shown promise for performing physics simulations faster than classical computers can. We develop a quantum algorithm for solving the 1-dimensional advection equation with periodic boundary condition using a first-order upwind scheme, which can capture discontinuities in the wave envelope. We embed the non-unitary upwind scheme using Linear Combinations of Unitaries (LCUs), introducing a small, bounded probability of failure. We also develop an efficient quantum gate decomposition of the upwind unitary that achieves exponential speed up. That is, at each time step, our algorithm performs the advection using log(N) qubits and gates, where N is the number of data points, as opposed to a classical computer which costs O(N). For well-resolved envelopes, we also develop a method to recover the unknown quantum state when LCUs fail. Our algorithm can be used as a module for many physics simulations that involve advection.