期刊
QUANTUM
卷 4, 期 -, 页码 -出版社
VEREIN FORDERUNG OPEN ACCESS PUBLIZIERENS QUANTENWISSENSCHAF
DOI: 10.22331/q-2020-02-20-234
关键词
-
资金
- EPSRC
- QinetiQ
- Royal Society
- National Natural Science Foundation of China
- US DOD [ARO-MURI W911NF-17-1-0304]
- UK MOD [ARO-MURI W911NF-17-1-0304]
- UK EPSRC under the Multidisciplinary University Research Initiative [ARO-MURI W911NF-17-1-0304]
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 Elamiltonian 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 Elamiltonian is a density matrix, can be efficiently classically simulated under specific structural conditions. Our main technical contribution is a, randomized algorithm for approxifnating Hermitian matrix exponentials. The proof leverages a low-rank, symmetric approximation via the Nystrom method. Our results suggest that under strong sampling assumptions there exist classical poly-logarithmic time simulations of quantum computations.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据