Quantum systems arising in solid state physics, chemistry and biology invariably interact with their environment, and need to me modelled as open systems. While the theory of Markovian open quantum systems has been extensively developed, their non-Markovian generalization remains less well understood. In this talk, I will first review quantum stochastic calculus which provides a mathematically rigorous description of a unitary group generating Markovian sub-system dynamics. From a physical standpoint, this description formalizes a model with a delta-function memory kernel - I will propose a generalization of this description to non-Markovian open quantum systems described by memory kernels describable as complex-valued tempered radon measures, and rigorously establish the well definition of the resulting dynamics. I will also show a systematic construction of a Markovian dilation of these systems with the error between the Markovian dilation and the exact non-Markovian dynamics growing only polynomially with time. Finally, I will consider the non-Markovian many-body quantum systems with n qubits and show that there is a poly(1/eps, n) quantum algorithm which approximates the state of the n qubits with epsilon trace distance error, thus placing dynamics of non-Markovian many-body systems in the BQP complexity class.