Near-optimal quantum simulation of lattice Lindbladian dynamics

Technical Summary: Near-optimal quantum simulation of lattice Lindbladian dynamics

Problem Statement
The paper addresses the challenge of simulating the time evolution of open quantum systems described by geometrically local Lindbladians on a lattice of $N$ qudits. While efficient algorithms exist for closed systems (Hamiltonian dynamics), such as the Haah-Hastings-Kothari-Low (HHKL) algorithm which achieves near-optimal scaling of $O(Nt \text{ polylog}(Nt/\varepsilon))$, extending these techniques to Lindbladian dynamics has been obstructed by the irreversibility of dissipative evolution. Existing methods for Lindbladians either scale unfavorably with system size $N$ or rely on non-Markovian approximations that perform poorly near the Markovian limit. The central question posed is whether a quantum algorithm exists that simulates lattice Lindbladians with a gate cost that is quasilinear in $Nt$ and polylogarithmic in the inverse error $1/\varepsilon$.

Methodology
The authors propose a three-step algorithmic framework that generalizes the HHKL approach to open systems:

1. Dilation to Unitary Dynamics:
   The authors first express the non-unitary Lindblad dynamics as the reduced dynamics of a larger, unitary system-environment interaction. Using the theory of Quantum Stochastic Calculus, the Lindbladian is dilated into a Hamiltonian $H(t)$ acting on the system and an ancillary bosonic Fock space (environment). The environment is initially in the vacuum state, and the system's dynamics are recovered by tracing out the environment after unitary evolution. This step allows the use of unitary evolution techniques, including backward time evolution, which are essential for the splitting strategy but impossible for direct Lindbladian simulation.

2. Lieb-Robinson Splitting for Unbounded Hamiltonians:
   The core of the HHKL algorithm relies on Lieb-Robinson bounds to split global time evolution into local patches. However, the dilated Hamiltonian involves unbounded bosonic operators. To overcome this, the authors utilize a generalized Lieb-Robinson bound (adapted from Ref. [TYR24]) that applies to specific operator spaces ($S_K$) where the environment state is constrained by the number of excitations. They prove that for states with a bounded number of overlapping time intervals (and thus bounded excitations), the unbounded annihilation and creation operators behave effectively as bounded operators. This enables a decomposition of the global unitary $U(t,s)$ into a sequence of local forward and backward evolutions on overlapping spatial blocks, with an error that decays exponentially with the block size $l$.

3. Digitization and Compression (Collision Model):
   The continuous bosonic environment is digitized using a "collision model" approach, where the environment is represented by a chain of ancillary qubits interacting with the system in discrete time steps.

   • Truncation: A critical insight is that the number of excitations emitted into the environment during time $t$ is bounded with exponential tails. The authors truncate the Hilbert space of the ancillas to a subspace containing at most $n_c$ excitations.
   • Excitation-Location Representation: Instead of simulating the full exponential dimension of the truncated space, the authors employ a compressed "excitation-location" representation. This encodes the state of the ancillas by storing the sorted list of positions of the excited qubits. This representation requires only $O(n_c \log T)$ qubits, where $T$ is the number of time steps.
   • Efficient Simulation: Using block-encoding techniques and quantum signal processing, the authors construct efficient circuits to simulate the evolution within this compressed subspace. They prove that the gate complexity scales polylogarithmically with the number of time steps, avoiding the polynomial scaling in $N$ that typically arises from discretizing continuous bosonic fields.

Key Results
The main result (Theorem 2.1) states that for a lattice of $N$ qudits evolving under a geometrically local Lindbladian for time $t$ to a diamond-norm error $\varepsilon$:

• The dynamics can be approximated by a quantum circuit with geometrically local gates.
• The gate count scales as $O(Nt \text{ polylog}(Nt/\varepsilon))$.
• The circuit depth scales as $O(t \text{ polylog}(Nt/\varepsilon))$.
• The algorithm requires $O(\text{polylog}(Nt/\varepsilon))$ ancillary qubits per site.

This performance matches the asymptotic scaling of the HHKL algorithm for Hamiltonian simulation, effectively closing the gap between closed and open system simulation complexities for local lattice models.

Significance and Claims
The paper claims to provide the first quantum algorithm that achieves essentially optimal scaling for simulating lattice Lindbladians, resolving the open question of whether such an algorithm exists. By leveraging the irreversibility of Lindbladian dynamics through a dilation strategy and managing the resulting unbounded operators via excitation truncation, the authors demonstrate that the "cost" of irreversibility does not preclude near-optimal simulation efficiency.

The authors further discuss the theoretical implications for mixed-state phase equivalence. They establish that a geometrically local Lindbladian evolution can be approximated by a shallow circuit of local quantum channels, rigorously connecting continuous-time dissipative dynamics with discrete-time local channel descriptions. The paper notes that while the algorithm uses $O(t \text{ polylog})$ ancillas in total, the final channel admits a Stinespring dilation with only $O(1)$ ancillas per site, leaving open the question of whether an algorithm with both optimal gate complexity and minimal ancilla resources exists.

The work extends to higher-dimensional lattices and time-dependent local terms, maintaining the same asymptotic complexity under standard smoothness assumptions. The authors acknowledge that while their result is optimal up to polylogarithmic factors, establishing a strict lower bound of $\Omega(Nt)$ for purely dissipative local dynamics remains an open challenge.