We develop randomized quantum algorithms to simulate quantum collision models, also known as repeated interaction schemes, which provide a rich framework to model various open-system dynamics. The underlying technique involves composing time evolutions of simple Hamiltonians on a joint system environment space and intermittent tracing out of the environment degrees of freedom. This results in a unified framework where any near-term Hamiltonian simulation algorithm can be incorporated to implement an arbitrary number of such collisions on early fault-tolerant quantum computers. In particular, using the correspondence between Lindbladian evolution and completely positive trace-preserving maps arising out of memoryless collisions, we provide an end-to-end quantum algorithm for simulating Lindbladian dynamics. Finally, we also develop a framework to efficiently simulate an arbitrary number of memory retaining collisions, i.e., where environments interact, leading to non-Markovian dynamics. Overall, our methods can leverage quantum collision models for both Markovian and non-Markovian dynamics on early fault-tolerant quantum computers, shedding light on the advantages and limitations of this framework.
