Abstract

Simulating the time-evolution of quantum mechanical systems is BQP -hard and expected to be one of the foremost applications of quantum computers. During this talk I will present a method to approximate Hamiltonian dynamics using subsampling methods from randomized numerical linear algebra and propose conditions for the efficient approximation of state vectors evolving under a given Hamiltonian. As an immediate application, I will show that sample based quantum simulation, a type of evolution where the Hamiltonian is a density matrix, can be efficiently classically simulated under specific structural conditions. The main technical contribution of our method is a randomized algorithm for approximating Hermitian matrix exponentials. The proof leverages the Nyström method to obtain low-rank approximations of the Hamiltonian, a tool commonly used in the statistical machine learning literature.

The talk is based on joint work with Carlo Ciliberto, Massimiliano Pontil, Alessandro Rudi, Simone Severini and Leonard Wossnig