Approximating Hamiltonian dynamics with the Nyström method

Abstract

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.

arXiv commentv2: 22 pages, fixed typos in Eq.27 and 28 + other minor changes to the presentation of the results; v3 final version accepted to Quantum; v4 DOIs added in order to comply with Quantum requirements

References in corpus (21)

• Quantum Machine Learning
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Quantum support vector machine for big data classification
• Efficient simulation of one-dimensional quantum many-body systems
• Quantum principal component analysis
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Time-dependent variational principle for quantum lattices
• Exponential algorithmic speedup by quantum walk
• User-friendly tail bounds for sums of random matrices
• Quantum machine learning: a classical perspective
• Sketching as a Tool for Numerical Linear Algebra
• Hamiltonian simulation with nearly optimal dependence on all parameters
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Prediction by linear regression on a quantum computer
• A quantum-inspired classical algorithm for recommendation systems
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Simulating sparse Hamiltonians with star decompositions
• Hamiltonian Simulation with Optimal Sample Complexity
• Operator Lipschitz Functions
• On sparse representations of linear operators and the approximation of matrix products
• Matrix product states and the quantum max-flow/min-cut conjectures

Cited by in corpus (2)

• Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
• Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture