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.
 Aharonov and Ta-Shma “Adiabatic Quantum State Generation and Statistical Zero Knowledge” Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing 20-29 (2003).
 Belabbas and Wolfe “Fast low-rank approximation for covariance matrices” 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2007. 293-296 (2007).
 Belabbas and Wolfe “On sparse representations of linear operators and the approximation of matrix products” 42nd Annual Conference on Information Sciences and Systems 258-263 (2008).
 Berry, Childs, and Kothari, “Hamiltonian simulation with nearly optimal dependence on all parameters” IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) 792-809 (2015).
 Bravyi, Browne, Calpin, Campbell, Gosset, and Howard, “Simulation of quantum circuits by low-rank stabilizer decompositions” arXiv preprint arXiv:1808.00128 (2018).
 Chia, Gilyén, Li, Lin, Tang, and Wang, “Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning” arXiv preprint arXiv:1910.06151 (2019).
 Childs and Kothari “Simulating Sparse Hamiltonians with Star Decompositions” Proceedings of the 5th Conference on Theory of Quantum Computation, Communication, and Cryptography 94-103 (2011).
 Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman, “Exponential Algorithmic Speedup by a Quantum Walk” Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing 59-68 (2003).
 Ciliberto, Herbster, Ialongo, Pontil, Rocchetto, Severini, and Wossnig, “Quantum machine learning: a classical perspective” Proc. R. Soc. A 474, 20170551 (2018).
 Drineas, Kannan, and Mahoney, “Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication” SIAM Journal on Computing 36, 132-157 (2006).
 Drineas, Kannan, and Mahoney, “Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix” SIAM Journal on computing 36, 158-183 (2006).
 Drineas and Mahoney “On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning” J. Mach. Learn. Res. 6, 2153-2175 (2005).
 Drineas and Mahoney “Lectures on randomized numerical linear algebra” The Mathematics of Data 25, 1 (2018).
 Haegeman, Cirac, Osborne, Pižorn, Verschelde, and Verstraete, “Time-dependent variational principle for quantum lattices” Physical review letters 107, 070601 (2011).
 Hsu “Weighted sampling of outer products” arXiv preprint arXiv: 1410.4429 (2014).
 Huang, Newman, and Szegedy, “Explicit lower bounds on strong quantum simulation” arXiv preprint arXiv:1804.10368 (2018).
 Jónsson, Bauer, and Carleo, “Neural-network states for the classical simulation of quantum computing” arXiv preprint arXiv:1808.05232 (2018).
 Kerenidis and Prakash “Quantum recommendation systems” arXiv preprint arXiv:1603.08675 (2016).
 Kumar, Mohri, and Talwalkar, “On Sampling-Based Approximate Spectral Decomposition” Proceedings of the 26th Annual International Conference on Machine Learning 553-560 (2009).
 Li, Kwok, and Lu, “Making Large-Scale Nyström Approximation Possible” Proceedings of the 27th International Conference on International Conference on Machine Learning 631-638 (2010).
 Lowand Chuang “Hamiltonian Simulation by Uniform Spectral Amplification” arXiv preprint arXiv:1707.05391 (2017).
 Mackey, Talwalkar, and Jordan, “Divide-and-Conquer Matrix Factorization” Proceedings of the 24th International Conference on Neural Information Processing Systems 1134-1142 (2011).
 Al-Mohyand Higham “Computing the action of the matrix exponential, with an application to exponential integrators” SIAM journal on scientific computing 33, 488-511 (2011).
 Nakamoto “A norm inequality for Hermitian operators” The American mathematical monthly 110, 238 (2003).
 Orecchia, Sachdeva, and Vishnoi, “Approximating the Exponential, the Lanczos Method and an Õ(m)-Time Spectral Algorithm for Balanced Separator” Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing 1141-1160 (2012).
 Rebentrost, Mohseni, and Lloyd, “Quantum support vector machine for big data classification” Physical review letters 113, 130503 (2014).
 Rebentrost, Schuld, Wossnig, Petruccione, and Lloyd, “Quantum gradient descent and Newton’s method for constrained polynomial optimization” New Journal of Physics 21, 073023 (2019).
 Rudi, Camoriano, and Rosasco, “Less is More: Nyström Computational Regularization” Proceedings of the 28th International Conference on Neural Information Processing Systems – Volume 1 1657-1665 (2015).
 Rudi, Camoriano, and Rosasco, “Less is More: Nyström Computational Regularization” arXiv preprint arXiv:1507.04717 (2015).
 Schwarz and Nest “Simulating quantum circuits with sparse output distributions” arXiv preprint arXiv:1310.6749 (2013).
 Spielman and Teng “Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems” Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing 81-90 (2004).
 Suzuki “Generalized Trotter’s formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems” Communications in Mathematical Physics 51, 183-190 (1976).
 Tang “A Quantum-Inspired Classical Algorithm for Recommendation Systems” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 217-228 (2019).
 Trotter “On the product of semi-groups of operators” Proceedings of the American Mathematical Society 10, 545-551 (1959).
 Verstraete, Garcia-Ripoll, and Cirac, “Matrix product density operators: Simulation of finite-temperature and dissipative systems” Physical review letters 93, 207204 (2004).
 Verstraete, Murg, and Cirac, “Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems” Advances in Physics 57, 143-224 (2008).
 Williams, Rasmussen, Schwaighofer, and Tresp, “Observations on the Nyström Method for Gaussian Process Prediction” report (2002).
 Zhang and Kwok “Clustered Nyström method for large scale manifold learning and dimension reduction” IEEE Transactions on Neural Networks 21, 1576-1587 (2010).
 Zhang, Tsang, and Kwok, “Improved Nyström Low-Rank Approximation and Error Analysis” Proceedings of the 25th International Conference on Machine Learning 1232-1239 (2008).
 Ewin Tang, “Quantum-inspired classical algorithms for principal component analysis and supervised clustering”, arXiv:1811.00414.
 Juan A. Acebron, “A Monte Carlo method for computing the action of a matrix exponential on a vector”, arXiv:1904.12759.
 Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang, “Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning”, arXiv:1910.06151.
The above citations are from SAO/NASA ADS (last updated successfully 2020-02-20 15:40:36). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2020-02-20 15:40:34: Could not fetch cited-by data for 10.22331/q-2020-02-20-234 from Crossref. This is normal if the DOI was registered recently.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.