arXiv:2609.26372
Lattice Lindbladian simulation by patching and merging
Kaoru Mizuta
Abstract
Simulating the dynamics of dissipative quantum many-body systems governed by local Lindbladians is a fundamental task in quantum computation. While the near-optimal gate count has been achieved for Hamiltonian simulation, comparable results for Lindbladian simulation remain elusive. In this work, we develop quantum algorithms for lattice Lindbladians by exploiting their locality. First, we consider sparsely dissipative systems, in which the dissipation is sparsely located, including boundary-driven systems. We establish a near-optimal quantum algorithm for their dynamics with gate count $O(Nt \, \mathrm{polylog}(Nt/\varepsilon))$, where $N$ is the system size, $t$ is the evolution time, and $\varepsilon$ is the allowable error. We then consider generic lattice Lindbladians with finite-range interactions and dissipation, and develop an algorithm for simulating time-evolved observables with gate count $O((Nt)^{4/3} \, \mathrm{polylog}(Nt/\varepsilon))$ per sample with the sampling complexity $Θ(\varepsilon^{-2})$. The gate count has the smallest known dependence on the system size among algorithms retaining polylogarithmic dependence on $1/\varepsilon$. Our algorithms are based on two techniques that exploit locality: patching and merging. Patching decomposes dissipative dynamics into dynamics on subsystems with exponentially small error, generalizing a key idea underlying the Haah-Hastings-Kothari-Low algorithm for near-optimal Hamiltonian simulation. Merging absorbs reversed dissipative dynamics into other parts of the evolution, substantially reducing the overhead associated with quasi-probabilistic sampling. These results demonstrate that locality can be fully exploited to achieve fast quantum simulation of dissipative many-body dynamics, opening the way to applications such as predicting nonequilibrium phenomena and preparing desirable quantum states.
AI Summary
The paper asks how locality can reduce the elementary-gate cost of simulating lattice Lindbladians, given that backward dissipative evolution prevents a direct extension of near-optimal Hamiltonian-simulation algorithms. It considers bounded-strength, finite-range generators, primarily on one-dimensional qubit lattices. For sparsely dissipative systems, it constructs a channel approximating $e^{\mathcal L t}$ in diamond norm to error $\varepsilon$ using $O(Nt\,\mathrm{polylog}(Nt/\varepsilon))$ gates. Dissipative regions must have diameter $o(\log N)$ and separation $\omega(\log N)$, with $t$ and $1/\varepsilon$ polynomially bounded in $N$. This class includes one-dimensional boundary-driven systems. For generic one-dimensional lattice Lindbladians, it estimates bounded-observable expectation values using $O((Nt)^{4/3}\,\mathrm{polylog}(Nt/\varepsilon))$ gates per sample and $\Theta(\varepsilon^{-2})$ samples, rather than preparing the evolved state. The construction establishes a dissipative patching bound: over sufficiently short constant time, an overlapping-subsystem decomposition has diamond-norm error at most $e^{-R/\xi}$ for overlap width $R$ and interaction range $\xi$. Sparse dissipation permits overlaps whose reversed evolution is unitary. For generic dissipation, symmetric “merging” combines reversed and forward evolution into a physical boundary evolution plus a correction of Pauli norm $O(\tau^3)$. Quasi-probability sampling and optimized block sizes control the accumulated overhead. The generic algorithm improves on the stated $\widetilde O(N^2t)$ gate bound only for $t\lesssim N^2$. State-preparation and measurement-basis costs are excluded. Higher-dimensional extensions have worse exponents, and near-linear gate complexity for generic dissipative dynamics remains open.
AI tools were used to assist with proofreading, checking references to prior work, and identifying potential issues in the mathematical definitions and proofs.
Central claim may not hold: The abstract's generic Õ((Nt)^(4/3)) gate bound is established only for one-dimensional lattices; the paper states the weaker bound Õ((Nt)^(3/2−1/(4d+2))) in dimension d>1. The abstract omits the polynomial bounds on t and 1/ε required by the sparse-dissipation theorem to ensure that its logarithmic overlap blocks fit between dissipative domains.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 41 pages, 7 figures, 1 Table