We present an efficient algorithm for simulating open quantum systems dynamics described by the Lindblad master equation on quantum computers, addressing key challenges in the field. In contrast to existing approaches, our method achieves two significant advancements. First, we employ a repetition of unitary gates on a set of n system qubits and, remarkably, only a single ancillary bath qubit representing the environment. It follows that, for the typical case of m locality of the Lindblad operators, we reach an exponential improvement of the number of ancilla in terms of m and up to a polynomial improvement in ancilla overhead for large n with respect to other approaches. Although stochasticity is introduced, requiring multiple circuit realizations, the sampling overhead is independent of the system size. Second, we show that, under fixed accuracy conditions, our algorithm enables a reduction in the number of Trotter steps compared to other approaches, substantially decreasing circuit depth. These advancements hold particular significance for near-term quantum computers, where minimizing both width and depth is critical due to inherent noise in their dynamics.
