Exponentially accurate randomized quantum simulation of open quantum systems with low ancilla overhead

We present a novel quantum algorithm for simulating open quantum systems governed by the Lindblad equation, achieving significant improvements in space complexity while maintaining efficient time complexity. Our method employs an efficient decomposition of non-unitary dynamics and randomized circuit generation, resulting

in a substantial reduction in ancilla qubit requirements compared to previous state-of-the-art algorithms. The key innovation lies in our techniques to expand non-unitary operations in the vectorized form into quantum operations on quantum circuits using only a constant number of ancilla qubits. This is achieved through a Taylor series expansion of the non-unitary propagator with vectorization, which ensures efficient time complexity, and by employment of new techniques with Oblivious Amplitude Amplification for non-isometry and cancellation of the implementation error. Our algorithm achieves a maximal circuit depth of O(t² log(1/ε)), where t is the simulation time, and ε is the simulation error. We provide a rigorous error analysis and complexity bounds for our method. Furthermore, we demonstrate the algorithm’s effectiveness through numerical simulations of a two-level system with a damping channel, showing excellent agreement with exact solutions. This work represents a significant step towards making open quantum system simulations more feasible on near-term quantum devices, particularly in the early era of fault-tolerant quantum computing where qubit resources are limited.