Approximating Hamiltonian dynamics with the Nyström method
This addresses the challenge of quantum simulation for quantum computing applications, but it is incremental as it builds on existing subsampling methods with strong assumptions.
The paper tackles the problem of simulating quantum Hamiltonian dynamics classically by developing a randomized algorithm based on the Nyström method, achieving runtime scaling polynomially in qubits and Hamiltonian norm, and showing efficient classical simulation under specific conditions.
Simulating the time-evolution of quantum mechanical systems is BQP-hard and expected to be one of the foremost applications of quantum computers. We consider classical algorithms for the approximation of Hamiltonian dynamics using subsampling methods from randomized numerical linear algebra. We derive a simulation technique whose runtime scales polynomially in the number of qubits and the Frobenius norm of the Hamiltonian. As an immediate application, we 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. Our main technical contribution is a randomized algorithm for approximating Hermitian matrix exponentials. The proof leverages a low-rank, symmetric approximation via the Nyström method. Our results suggest that under strong sampling assumptions there exist classical poly-logarithmic time simulations of quantum computations.