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.
 Dorit Aharonov and Amnon 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).
 Mohamed-Ali Belabbas and Patrick J Wolfe ``Fast low-rank approximation for covariance matrices'' 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 2007. 293–296 (2007).
 Mohamed-Ali Belabbas and Patrick J Wolfe ``On sparse representations of linear operators and the approximation of matrix products'' 42nd Annual Conference on Information Sciences and Systems 258–263 (2008).
 Dominic W Berry, Andrew M Childs, and Robin Kothari, ``Hamiltonian simulation with nearly optimal dependence on all parameters'' IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) 792–809 (2015).
 Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard, ``Simulation of quantum circuits by low-rank stabilizer decompositions'' arXiv preprint arXiv:1808.00128 (2018).
 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 preprint arXiv:1910.06151 (2019).
 Andrew M. Childs and Robin Kothari ``Simulating Sparse Hamiltonians with Star Decompositions'' Proceedings of the 5th Conference on Theory of Quantum Computation, Communication, and Cryptography 94–103 (2011).
 Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman, ``Exponential Algorithmic Speedup by a Quantum Walk'' Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing 59–68 (2003).
 Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig, ``Quantum machine learning: a classical perspective'' Proc. R. Soc. A 474, 20170551 (2018).
 Petros Drineas, Ravi Kannan, and Michael W Mahoney, ``Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication'' SIAM Journal on Computing 36, 132–157 (2006).
 Petros Drineas, Ravi Kannan, and Michael W Mahoney, ``Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix'' SIAM Journal on computing 36, 158–183 (2006).
 Petros Drineas and Michael W. Mahoney ``On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning'' J. Mach. Learn. Res. 6, 2153–2175 (2005).
 Petros Drineas and Michael W Mahoney ``Lectures on randomized numerical linear algebra'' The Mathematics of Data 25, 1 (2018).
 Charless Fowlkes, Serge Belongie, Fan Chung, and Jitendra Malik, ``Spectral Grouping Using the Nyström Method'' IEEE Trans. Pattern Anal. Mach. Intell. 26, 214–225 (2004).
 Jutho Haegeman, J Ignacio Cirac, Tobias J Osborne, Iztok Pižorn, Henri Verschelde, and Frank Verstraete, ``Time-dependent variational principle for quantum lattices'' Physical review letters 107, 070601 (2011).
 Daniel Hsu ``Weighted sampling of outer products'' arXiv preprint arXiv: 1410.4429 (2014).
 Cupjin Huang, Michael Newman, and Mario Szegedy, ``Explicit lower bounds on strong quantum simulation'' arXiv preprint arXiv:1804.10368 (2018).
 Bjarni Jónsson, Bela Bauer, and Giuseppe Carleo, ``Neural-network states for the classical simulation of quantum computing'' arXiv preprint arXiv:1808.05232 (2018).
 Iordanis Kerenidis and Anupam Prakash ``Quantum recommendation systems'' arXiv preprint arXiv:1603.08675 (2016).
 Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J Yoder, ``Hamiltonian simulation with optimal sample complexity'' npj Quantum Information 3, 13 (2017).
 Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar, ``On Sampling-Based Approximate Spectral Decomposition'' Proceedings of the 26th Annual International Conference on Machine Learning 553–560 (2009).
 Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar, ``Sampling methods for the Nyström method'' Journal of Machine Learning Research 13, 981–1006 (2012).
 Mu Li, James T. Kwok, and Bao-Liang Lu, ``Making Large-Scale Nyström Approximation Possible'' Proceedings of the 27th International Conference on International Conference on Machine Learning 631–638 (2010).
 Guang Hao Lowand Isaac L Chuang ``Hamiltonian Simulation by Uniform Spectral Amplification'' arXiv preprint arXiv:1707.05391 (2017).
 Lester Mackey, Ameet Talwalkar, and Michael I. Jordan, ``Divide-and-Conquer Matrix Factorization'' Proceedings of the 24th International Conference on Neural Information Processing Systems 1134–1142 (2011).
 Awad H Al-Mohyand Nicholas J Higham ``A new scaling and squaring algorithm for the matrix exponential'' SIAM Journal on Matrix Analysis and Applications 31, 970–989 (2009).
 Awad H Al-Mohyand Nicholas J Higham ``Computing the action of the matrix exponential, with an application to exponential integrators'' SIAM journal on scientific computing 33, 488–511 (2011).
 Ritsuo Nakamoto ``A norm inequality for Hermitian operators'' The American mathematical monthly 110, 238 (2003).
 Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. 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).
 Román Orús ``A practical introduction to tensor networks: Matrix product states and projected entangled pair states'' Annals of Physics 349, 117–158 (2014).
 Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd, ``Quantum support vector machine for big data classification'' Physical review letters 113, 130503 (2014).
 Patrick Rebentrost, Maria Schuld, Leonard Wossnig, Francesco Petruccione, and Seth Lloyd, ``Quantum gradient descent and Newton's method for constrained polynomial optimization'' New Journal of Physics 21, 073023 (2019).
 Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco, ``Less is More: Nyström Computational Regularization'' Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1 1657–1665 (2015).
 Alessandro Rudi, Raffaello Camoriano, and Lorenzo Rosasco, ``Less is More: Nyström Computational Regularization'' arXiv preprint arXiv:1507.04717 (2015).
 Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione, ``Prediction by linear regression on a quantum computer'' Physical Review A 94, 022342 (2016).
 Martin Schwarz and Maarten Van den Nest ``Simulating quantum circuits with sparse output distributions'' arXiv preprint arXiv:1310.6749 (2013).
 Daniel A. Spielman and Shang-Hua 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).
 Masuo 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).
 Ameet Talwalkar, Sanjiv Kumar, and Henry Rowley, ``Large-scale manifold learning'' IEEE Conference on Computer Vision and Pattern Recognition 1–8 (2008).
 Ewin Tang ``A Quantum-Inspired Classical Algorithm for Recommendation Systems'' Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 217–228 (2019).
 Hale F Trotter ``On the product of semi-groups of operators'' Proceedings of the American Mathematical Society 10, 545–551 (1959).
 Maarten Van Den Nest ``Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond'' Quantum Information & Computation 10, 258–271 (2010).
 Frank Verstraete, Juan J Garcia-Ripoll, and Juan Ignacio Cirac, ``Matrix product density operators: Simulation of finite-temperature and dissipative systems'' Physical review letters 93, 207204 (2004).
 Frank Verstraete, Valentin Murg, and J Ignacio Cirac, ``Matrix product states, projected entangled pair states, and variational renormalization group methods for quantum spin systems'' Advances in Physics 57, 143–224 (2008).
 Christopher K. I. Williams and Matthias Seeger ``Using the Nyström Method to Speed Up Kernel Machines'' Advances in Neural Information Processing Systems 13 682–688 (2001).
 CKI. Williams, CE. Rasmussen, A. Schwaighofer, and V. Tresp, ``Observations on the Nyström Method for Gaussian Process Prediction'' report (2002).
 Kai Zhang and James T Kwok ``Clustered Nyström method for large scale manifold learning and dimension reduction'' IEEE Transactions on Neural Networks 21, 1576–1587 (2010).
 Kai Zhang, Ivor W. Tsang, and James T. 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 Principal Component Analysis Only Achieves an Exponential Speedup Because of Its State Preparation Assumptions", arXiv:1811.00414, Physical Review Letters 127 6, 060503 (2021).
 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.
 Aram W. Harrow, "Small quantum computers and large classical data sets", arXiv:2004.00026.
 Juan A. Acebron, "A Monte Carlo method for computing the action of a matrix exponential on a vector", arXiv:1904.12759.
The above citations are from Crossref's cited-by service (last updated successfully 2022-01-23 14:21:44) and SAO/NASA ADS (last updated successfully 2022-01-23 14:21:45). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.