Query-optimal quantum simulation of Lindblad evolution

Abstract:For the problem of simulating Lindblad evolution for time $t$ to precision $\epsilon$, Hamiltonian simulation provides an additive query lower bound, informally, $\Omega(t + \mathrm{polylog}(1/\epsilon))$. However, the best previously known algorithms for general Lindblad simulation achieve a multiplicative upper bound, informally, $\mathcal{O}(t\,\mathrm{polylog}(1/\epsilon))$, in gate complexity. It has remained open whether this multiplicative dependence is necessary. In this paper, we close the gap in query complexity by giving an algorithm with optimal additive dependence on evolution time and precision in the block-encoding model. Our approach uses the transducer framework to reduce the query cost of composing first-order approximations to the evolution channel, together with linear combinations of reuse circuits of different lengths to suppress catalyst-removal error. Although our additional gate complexity is higher than that of existing algorithms, our optimal query complexity resolves the question of how much oracle access is fundamentally necessary and identifies the remaining challenge to achieve the optimal gate complexity.

arXiv:2609.17490 [quant-ph]

(or arXiv:2609.17490v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.17490 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.