UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Approximating Hamiltonian dynamics with the Nyström method

Rudi, A; Wossnig, L; Ciliberto, C; Rocchetto, A; Pontil, M; Severini, S; (2020) Approximating Hamiltonian dynamics with the Nyström method. Quantum , 4 10.22331/q-2020-02-20-234. Green open access

[thumbnail of q-2020-02-20-234.pdf]
Preview
Text
q-2020-02-20-234.pdf - Accepted version

Download (709kB) | Preview

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.

Type: Article
Title: Approximating Hamiltonian dynamics with the Nyström method
Open access status: An open access version is available from UCL Discovery
DOI: 10.22331/q-2020-02-20-234
Publisher version: https://doi.org/10.22331/q-2020-02-20-234
Language: English
Additional information: This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license (https://creativecommons.org/licenses/by/4.0/).
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10092747
Downloads since deposit
26Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item