Abstract Density matrix exponentiation (DME) is a quantum algorithm that processes multiple copies of a program state σ to realize the Hamiltonian evolution e − i σ t . Wave matrix Lindbladization (WML) similarly processes multiple copies of a program state ψ L in order to realize a Lindbladian evolution. Both algorithms are prototypical sample-based quantum algorithms and can be used for various quantum information processing tasks, including quantum principal component analysis, Hamiltonian simulation, and Lindbladian simulation. In this work, we present detailed sample complexity analyses for DME and sample-based Hamiltonian simulation, as well as for WML and sample-based Lindbladian simulation. In particular, we prove that the sample complexity of DME is no larger than 4 t 2 / ε , where t is the desired evolution time and ɛ is the desired imprecision level, as quantified by the normalized diamond distance. We also establish a fundamental lower bound on the sample complexity of sample-based Hamiltonian simulation, which matches our DME sample complexity bound up to a constant multiplicative factor, thereby proving that DME is optimal for sample-based Hamiltonian simulation. Additionally, we prove that the sample complexity of WML is no larger than 3 t 2 d 2 / ε , where d is the dimension of the space on which the Lindblad operator acts nontrivially, and we prove a lower bound of 10 − 4 t 2 / ε on the sample complexity of sample-based Lindbladian simulation. These results prove that WML is optimal for sample-based Lindbladian simulation whenever the Lindblad operator acts nontrivially on a constant-sized system. Finally, we point out that the DME sample complexity analysis in Kimmel et al(2017 npj Quantum Inf. 3 13) and the WML sample complexity analysis in Patel and Wilde (2023 Open Syst. Inf. Dyn. 30 2350010) appear to be incomplete, highlighting the need for the results presented here.
Abstract Density matrix exponentiation (DME) is a quantum algorithm that processes multiple copies of a program state σ to realize the Hamiltonian evolution e − i σ t . Wave matrix Lindbladization (WML) similarly processes multiple copies of a program state ψ L in order to realize a Lindbladian evolution. Both algorithms are prototypical sample-based quantum algorithms and can be used for various quantum information processing tasks, including quantum principal component analysis, Hamiltonian simulation, and Lindbladian simulation. In this work, we present detailed sample complexity analyses for DME and sample-based Hamiltonian simulation, as well as for WML and sample-based Lindbladian simulation. In particular, we prove that the sample complexity of DME is no larger than 4 t 2 / ε , where t is the desired evolution time and ɛ is the desired imprecision level, as quantified by the normalized diamond distance. We also establish a fundamental lower bound on the sample complexity of sample-based Hamiltonian simulation, which matches our DME sample complexity bound up to a constant multiplicative factor, thereby proving that DME is optimal for sample-based Hamiltonian simulation. Additionally, we prove that the sample complexity of WML is no larger than 3 t 2 d 2 / ε , where d is the dimension of the space on which the Lindblad operator acts nontrivially, and we prove a lower bound of 10 − 4 t 2 / ε on the sample complexity of sample-based Lindbladian simulation. These results prove that WML is optimal for sample-based Lindbladian simulation whenever the Lindblad operator acts nontrivially on a constant-sized system. Finally, we point out that the DME sample complexity analysis in Kimmel et al(2017 npj Quantum Inf. 3 13) and the WML sample complexity analysis in Patel and Wilde (2023 Open Syst. Inf. Dyn. 30 2350010) appear to be incomplete, highlighting the need for the results presented here.
We establish improved sample-complexity bounds for sample-based Lindbladian simulation based on the Wave Matrix Lindbladization (WML) algorithm. For a jump operator L with dimension d, we derive an explicit non-asymptotic sample complexity bound nd∗(t,ε)≤(82d+3)∥L∥∞2(εt2), holding for simulation time t and error ε. This refines the dimension dependence of the best previously known bound, O(d2t2/ε), from [Go et al., Quantum Sci. Tech. 10, 045058 (2025)]. Remarkably, we show that this dimensional overhead can be entirely avoided when ∥L∥∞2=O(1/d), a condition satisfied with high probability for random Lindblad operators, yielding a typical-case sample complexity of O(t2/ε). On the other hand, in the worst case, we show that WML necessarily requires Ω(dt2/ε) samples by constructing an explicit example with a rank-one Lindblad operator. Our results reveal a sharp dichotomy between typical and adversarial sample complexities in Lindbladian simulation, thereby strengthening the theoretical foundations of sample-based quantum algorithms.
In this paper, we investigate the problem of simulating open system dynamics governed by the well-known Lindblad master equation. In our prequel paper [Patel and Wilde, Open Sys. & Info. Dyn., 30:2350010 (2023)], we introduced an input model in which Lindblad operators are encoded into pure quantum states, called program states, and we also introduced a method, called wave matrix Lindbladization, for simulating Lindbladian evolution by means of interacting the system of interest with these program states. Therein, we focused on a simple case in which the Lindbladian consists of only one Lindblad operator and a Hamiltonian. Here, we extend the method to simulating general Lindbladians and other cases in which a Lindblad operator is expressed as a linear combination or a polynomial of the operators encoded into the program states. We propose quantum algorithms for all these cases and also investigate their sample complexity, i.e., the number of program states needed to simulate a given Lindbladian evolution approximately. Finally, we demonstrate that our quantum algorithms provide an efficient route for simulating Lindbladian evolution relative to full tomography of encoded operators, by proving that the sample complexity for tomography is dependent on the dimension of the system, whereas the sample complexity of wave matrix Lindbladization is dimension independent.
Density Matrix Exponentiation is a technique for simulating Hamiltonian dynamics when the Hamiltonian to be simulated is available as a quantum state. In this paper, we present a natural analogue to this technique, for simulating Markovian dynamics governed by the well known Lindblad master equation. For this purpose, we first propose an input model in which a Lindblad operator [Formula: see text] is encoded into a quantum state [Formula: see text]. Then, given access to [Formula: see text] copies of the state [Formula: see text], the task is to simulate the corresponding Markovian dynamics for time [Formula: see text]. We propose a quantum algorithm for this task, called Wave Matrix Lindbladization, and we also investigate its sample complexity. We show that our algorithm uses [Formula: see text] samples of [Formula: see text] to achieve the target dynamics, with an approximation error of [Formula: see text].
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.
We give a quantum algorithm for Lindbladian simulation given a block encoding of the Hamiltonian H and a projected unitary encoding of the stacked jump operator B=∑k=1m∣k⟩⊗Lk, with normalization factors αH and αB, respectively. For evolution time t, set τ=(αH+αB2)t. The algorithm approximates the evolution channel to diamond-norm error ε using O(τ+log(e+log(1/ε)/τ)log(1/ε)) oracle queries, matching the query lower bound for Hamiltonian simulation. The number of additional one- and two-qubit gates is linear in the query complexity up to polylogarithmic factors. The query- and gate-complexity bounds extend to Lipschitz-continuous time-dependent Lindbladians under coherent time-indexed oracle access. Our construction uses a one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst. We bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels. The gate implementation combines a compressed Kraus-label representation, which stores only the positions and values of the nonzero labels, with the rotation factorization of Chen et al.
Abstract We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [ Nat. Phys. , 10(9):631–633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states.