Query-optimal quantum simulation of Lindblad evolution

Simulating open quantum systems, governed by the Lindblad equation, is a fundamental task for quantum computers with applications in optimization, scientific computing, and state preparation. Previous algorithms for general Lindblad simulation typically exhibited a multiplicative dependence on the evolution time and precision, informally O(t polylog(1/ε)). This paper investigates whether this multiplicative scaling is an intrinsic limitation or if it can be reduced to the additive scaling O(t + polylog(1/ε)) characteristic of Hamiltonian simulation.

The authors employ the transducer framework, a technique previously used to achieve optimal query complexity in Hamiltonian simulation. By constructing a local dissipative transducer that implements a first-order approximation to the Lindblad channel, they compose these steps into a global transducer. To handle the resulting catalyst-removal error, they utilize a linear combination of unitaries (LCU) over reuse circuits of varying lengths. This construction allows for the cancellation of errors while maintaining the desired query-optimal scaling.

The paper establishes that the multiplicative dependence on evolution time in general Lindblad simulation is not fundamental. The proposed algorithm achieves additive query complexity in the block-encoding model, matching the lower bounds known for Hamiltonian simulation. This result holds for general Lindbladians without requiring specific restrictions on the jump operators or the total jump rate. The authors also extend this framework to time-dependent Lindbladian dynamics.

Efficient Lindblad simulation is a critical primitive for various quantum algorithms, including Gibbs state preparation and solving linear differential equations. By resolving the query complexity gap, this work provides a definitive answer to the fundamental limits of oracle access for open quantum system simulation. It also provides a clear roadmap for future research, identifying the remaining challenge of achieving optimal gate complexity alongside this optimal query complexity.