  Digital quantum simulation on quantum systems require algorithms that can be
implemented using finite quantum resources. Recent studies have demonstrated
digital quantum simulation of open quantum systems on Noisy Intermediate-Scale
Quantum (NISQ) devices. In this work, we develop quantum circuits for optimal
simulation of Markovian and Non-Markovian open quantum systems. The circuits
use ancilla qubits to simulate the environment, and memory effects are induced
by storing information about the system on extra qubits. We simulate the
amplitude damping channel and dephasing channel as examples of the framework
and infer (Non-)Markovianity from the (non-)monotonic behaviour of the
dynamics. Further, we develop a method to optimize simulations by decomposing
complex open quantum dynamics into smaller parts, that can be simulated using a
small number of qubits. We show that this optimization reduces quantum space
complexity from $O(l)$ to $O(1)$ for simulating the environment.
