Using a map between the Lindbladian evolution of dephasing in free fermions and the time evolution of imaginary-interaction Fermi-Hubbard models in bipartite lattices, we present an efficient classical algorithm to solve the Schrödinger equation in these interacting systems. This algorithm leverages the recently discovered algorithm for simulating Lindbladian evolution by sampling mixed unitary channels (Wang et al arXiv:2601.06298). We comment on the expected classical complexity of the problem for general complex values of the parameters and discuss some applications.
Using a map between the Lindbladian evolution of dephasing in free fermions and the time evolution of imaginary-interaction Fermi-Hubbard models in bipartite lattices, we present an efficient classical algorithm to solve the Schrödinger equation in these interacting systems. This algorithm leverages the recently discovered algorithm for simulating Lindbladian evolution by sampling mixed unitary channels (Wang et al arXiv:2601.06298). We comment on the expected classical complexity of the problem for general complex values of the parameters and discuss some applications.
Noise and decoherence are ubiquitous in the dynamics of quantum systems coupled to an external environment. In the regime where environmental correlations decay rapidly, the evolution of a subsytem is well described by a Lindblad quantum master equation. In this work, we introduce a quantum algorithm for simulating unital Lindbladian dynamics by sampling unitary quantum channels without extra ancillas. Using ancillary qubits we show that this algorithm allows approximating general Lindbladians as well. For interacting dephasing Lindbladians coupling two subsystems, we develop a decoupling scheme that reduces the circuit complexity of the simulation. This is achieved by sampling from a time-correlated probability distribution - determined by the evolution of one subsystem, which specifies the stochastic circuit implemented on the complementary subsystem. We demonstrate our approach by studying a model of bosons coupled to fermions via dephasing, which naturally arises from anharmonic effects in an electron-phonon system coupled to a bath. Our method enables tracing out the bosonic degrees of freedom, reducing part of the dynamics to sampling an IQP circuit. The sampled bitstrings then define a corresponding fermionic problem, which in the non-interacting case can be solved efficiently classically. We comment on the computational complexity of this class of dissipative problems, using the known fact that sampling from IQP circuits is believed to be difficult classically.
We consider the natural generalization of the Schrödinger equation to Markovian open system dynamics: the so-called the Lindblad equation. We give a quantum algorithm for simulating the evolution of an n-qubit system for time t within precision ε. If the Lindbladian consists of poly(n) operators that can each be expressed as a linear combination of poly(n) tensor products of Pauli operators then the gate cost of our algorithm is O(tpolylog(t/ε)poly(n)). We also obtain similar bounds for the cases where the Lindbladian consists of local operators, and where the Lindbladian consists of sparse operators. This is remarkable in light of evidence that we provide indicating that the above efficiency is impossible to attain by first expressing Lindblad evolution as Schrödinger evolution on a larger system and tracing out the ancillary system: the cost of such a \textit{reduction} incurs an efficiency overhead of O(t2/ε) even before the Hamiltonian evolution simulation begins. Instead, the approach of our algorithm is to use a novel variation of the "linear combinations of unitaries" construction that pertains to channels.
We consider the task of simulating the real-time dynamics of weakly interacting fermionic systems. In particular, we focus on computing the expectation value of a local observable A at time t. By analyzing the convergence of the perturbative expansion in the interaction strength λ for the Heisenberg-picture observable, we propose a polynomial-time algorithm for estimating this expectation value in the weakly interacting regime λ∣t∣2D+1=O(1), when the Hamiltonian is geometrically local on a D-dimensional lattice. Importantly, this condition is independent of the system size. If the goal is instead to approximate the time-evolved observable in normalized Frobenius norm, we extend the convergence regime to λ∣t∣=O(1) with quasi-polynomial runtime. When the non-interacting part exhibits Anderson localization, our polynomial-time algorithm can be extended up to λ∣t∣=O(1), modulo polylogarithmic factors. Our algorithm brings together ideas from continuous-time QMC, diagrammatic QMC, and Majorana Propagation, but with a new Heisenberg-picture operator-growth analysis that makes the sampling complexity rigorously controllable. This leads to provably efficient classical algorithms in regimes where the interaction is weak enough that the sampling variance remains bounded independently of system size. Together, these results identify broad regimes in which weak interactions, locality, and localization can be leveraged to make real-time fermionic dynamics classically tractable.
Recently, there have been several advancements in quantum algorithms for Gibbs sampling. These algorithms simulate the dynamics generated by an artificial Lindbladian, which is meticulously constructed to obey a detailed-balance condition with the Gibbs state of interest, ensuring it is a stationary point of the evolution, while simultaneously having efficiently implementable time steps. The overall complexity then depends primarily on the mixing time of the Lindbladian, which can vary drastically, but which has been previously bounded in the regime of high enough temperatures [Rouzé et al. arXiv:2403.12691 and arXiv:2411.04885]. In this work, we calculate the spectral gap of the Lindbladian for free fermions using third quantisation, and also prove a logarithmic bound on its mixing time by analysing corresponding covariance matrices. Then we prove a constant gap of the perturbed Lindbladian corresponding to interacting fermions up to some maximal coupling strength. This is achieved by using theorems about stability of the gap for lattice fermions. Our methods apply at any constant temperature and independently of the system size. The gap then provides an upper bound on the mixing time, and hence on the overall complexity of the quantum algorithm, proving that the purified Gibbs state of weakly interacting (quasi-)local fermionic systems of any dimension can be prepared in O(n3polylog(1/ε)) time on O(n) qubits, where n denotes the size of the system and ε the desired accuracy. As an application, we explain how to calculate partition functions for the considered systems. We provide exact numerical simulations for small system sizes supporting the theory and also identify different suitable jump operators and filter functions for the sought-after regime of intermediate coupling in the Fermi-Hubbard model.
Abstract The Lindblad equation generalizes the Schrödinger equation to quantum systems that undergo dissipative dynamics. The quantum simulation of Lindbladian dynamics is therefore non-unitary, preventing a naive application of state-of-the-art quantum algorithms. Here, we make use of an approximate correspondence between Lindbladian dynamics and evolution based on repeated interaction (RI) CPTP maps to write down a Hamiltonian formulation of the Lindblad dynamics and derive a rigorous error bound on the master equation. Specifically, we show that the number of interactions needed to simulate the Liouvillian e t L within error ε scales in most physical scenarios as ν ∈ O ( t 2 ‖ L ‖ 1 → 1 2 / ϵ ) . This is significant because the error in the Lindbladian approximation to the dynamics is not explicitly bounded in existing quantum algorithms for open system simulations. We then provide quantum algorithms to simulate RI maps using an iterative qubitization approach and Trotter–Suzuki formulas, and specifically show that for iterative qubitization the number of operations needed to simulate the dynamics (for a fixed value of ν) scales as O ( α 0 t + ν log ( 1 / ϵ ) / log log ( 1 / ϵ ) ) in the limit where α 0 (the coefficient 1-norm for the system and bath Hamiltonians) asymptotically dominates over the corresponding factor for the interaction Hamiltonian, which is often the case in weak coupling. This scaling would appear to be optimal if the complexity of ν is not considered, which underscores the importance of considering the error in the Liouvillian that we reveal in this work.
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(Ntpolylog(Nt/ε)), where N is the system size, t is the evolution time, and ε 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/3polylog(Nt/ε)) per sample with the sampling complexity Θ(ε−2). The gate count has the smallest known dependence on the system size among algorithms retaining polylogarithmic dependence on 1/ε. 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.