Sample-based Hamiltonian and Lindbladian simulation: Non-asymptotic analysis of sample complexity
Mark Wilde | Cornell University
Density matrix exponentiation (DME) is a quantum algorithm that processes multiple copies of a program state σ to realize the Hamiltonian evolution exp(−iσt). Wave matrix Lindbladization (WML) similarly processes multiple copies of a program state 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 4t^2/ε for evolution time t and error ε 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.
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.
Based on joint work with Byeongseon Go, Hyukjoon Kwon, Siheon Park and Dhrumil Patel.
Bio
Mark M. Wilde received the Ph.D. degree in electrical engineering from the University of Southern California, Los Angeles, California. He is an Associate Professor of Electrical and Computer Engineering at Cornell University. He is an IEEE Fellow, he is a recipient of the National Science Foundation Career Development Award, he is a co-recipient of the 2018 AHP-Birkhauser Prize, awarded to “the most remarkable contribution” published in the journal Annales Henri Poincare, and he is an Outstanding Referee of the American Physical Society. His current research interests are in quantum Shannon theory, quantum computation, quantum optical communication, quantum computational complexity theory, and quantum error correction.
Location
QNC 1201