Sample-based Hamiltonian and Lindbladian simulation: non-asymptotic analysis of sample complexity

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 4t2/ε, 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 3t2d2/ε, where d is the dimension of the space on which the Lindblad operator acts nontrivially, and we prove a lower bound of 10−4t2/ε 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.