1INRIA – Sierra project team, Paris, France
2Bilgisayar Bilimleri Bölümü, University College London, Londra, Birleşik Krallık
3Rahko Ltd., London, United Kingdom
4Department of Computer Science, University of Texas at Austin, Austin, United States
5Department of Computer Science, University of Oxford, Oxford, United Kingdom
6Computational Statistics and Machine Learning, IIT, Genoa, Italy
Bu makaleyi ilginç mi buldunuz yoksa tartışmak mı istiyorsunuz? SciRate'e çığlık at veya yorum bırak.
Özet
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.
► BibTeX verileri
► Referanslar
[1] 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).
https: / / doi.org/ 10.1145 / 780542.780546
[2] Aleksandrov and Peller “Operator Lipschitz functions” Russian Mathematical Surveys 71, 605 (2016).
https://doi.org/10.1070/RM9729
[3] 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).
https://doi.org/10.1109/CAMSAP.2007.4498023
[4] 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).
https: / / doi.org/ 10.1109 / CISS.2008.4558532
[5] 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).
https: / / doi.org/ 10.1109 / FOCS.2015.54
[6] Biamonte, Wittek, Pancotti, Rebentrost, Wiebe, and Lloyd, “Quantum machine learning” Nature 549, 195 (2017).
https: / / doi.org/ 10.1038 / nature23474
[7] Bravyi, Browne, Calpin, Campbell, Gosset, and Howard, “Simulation of quantum circuits by low-rank stabilizer decompositions” arXiv preprint arXiv:1808.00128 (2018).
https://doi.org/10.22331/q-2019-09-02-181
[8] 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).
[9] 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).
https://doi.org/10.1007/978-3-642-18073-6_8
[10] Childs and Wiebe “Hamiltonian Simulation Using Linear Combinations of Unitary Operations” Quantum Info. Comput. 12, 901-924 (2012).
https: / / doi.org/ 10.5555 / 2481569.2481570
[11] 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).
https: / / doi.org/ 10.1145 / 780542.780552
[12] Ciliberto, Herbster, Ialongo, Pontil, Rocchetto, Severini, and Wossnig, “Quantum machine learning: a classical perspective” Proc. R. Soc. A 474, 20170551 (2018).
https: / / doi.org/ 10.1098 / rspa.2017.0551
[13] Drineas, Kannan, and Mahoney, “Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication” SIAM Journal on Computing 36, 132-157 (2006).
https: / / doi.org/ 10.1137 / S0097539704442684
[14] 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).
https: / / doi.org/ 10.1137 / S0097539704442696
[15] 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).
https: / / doi.org/ 10.5555 / 1046920.1194916
[16] Drineas and Mahoney “Lectures on randomized numerical linear algebra” The Mathematics of Data 25, 1 (2018).
[17] Drineas, Mahoney, Muthukrishnan, and Sarlós, “Faster Least Squares Approximation” Numer. Math. 117, 219-249 (2011).
https://doi.org/10.1007/s00211-010-0331-6
[18] Fowlkes, Belongie, Chung, and Malik, “Spectral Grouping Using the Nyström Method” IEEE Trans. Pattern Anal. Mach. Intell. 26, 214-225 (2004).
https: / / doi.org/ 10.1109 / TPAMI.2004.1262185
[19] Frieze, Kannan, and Vempala, “Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations” J. ACM 51, 1025-1041 (2004).
https: / / doi.org/ 10.1145 / 1039488.1039494
[20] Haegeman, Cirac, Osborne, Pižorn, Verschelde, and Verstraete, “Time-dependent variational principle for quantum lattices” Physical review letters 107, 070601 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.107.070601
[21] Higham “The Scaling and Squaring Method for the Matrix Exponential Revisited” SIAM J. Matrix Anal. Appl. 26, 1179-1193 (2005).
https: / / doi.org/ 10.1137 / 04061101X
[22] Higham “The Scaling and Squaring Method for the Matrix Exponential Revisited” SIAM Rev. 51, 747-764 (2009).
https: / / doi.org/ 10.1137 / 090768539
[23] Hsu “Weighted sampling of outer products” arXiv preprint arXiv: 1410.4429 (2014).
[24] Huang, Newman, and Szegedy, “Explicit lower bounds on strong quantum simulation” arXiv preprint arXiv:1804.10368 (2018).
[25] Jónsson, Bauer, and Carleo, “Neural-network states for the classical simulation of quantum computing” arXiv preprint arXiv:1808.05232 (2018).
[26] Kerenidis and Prakash “Quantum recommendation systems” arXiv preprint arXiv:1603.08675 (2016).
[27] Kimmel, Lin, Low, Ozols, and Yoder, “Hamiltonian simulation with optimal sample complexity” npj Quantum Information 3, 13 (2017).
https://doi.org/10.1038/s41534-017-0013-7
[28] Kumar, Mohri, and Talwalkar, “On Sampling-Based Approximate Spectral Decomposition” Proceedings of the
26th Annual International Conference on Machine Learning 553-560 (2009).
https: / / doi.org/ 10.1145 / 1553374.1553446
[29] Kumar, Mohri, and Talwalkar, “Sampling methods for the Nyström method” Journal of Machine Learning Research 13, 981-1006 (2012).
https: / / doi.org/ 10.5555 / 2188385.2343678
[30] 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).
https: / / doi.org/ 10.5555 / 3104322.3104403
[31] Lloyd “Universal Quantum Simulators” Science 273, 1073-1078 (1996).
https: / / doi.org/ 10.1126 / science.273.5278.1073
[32] Lloyd, Mohseni, and Rebentrost, “Quantum principal component analysis” Nature Physics 10, 631 (2014).
https: / / doi.org/ 10.1038 / nphys3029
[33] Lowand Chuang “Hamiltonian Simulation by Uniform Spectral Amplification” arXiv preprint arXiv:1707.05391 (2017).
[34] Mackey, Talwalkar, and Jordan, “Divide-and-Conquer Matrix Factorization” Proceedings of the 24th International Conference on Neural Information Processing Systems 1134-1142 (2011).
https: / / doi.org/ 10.5555 / 2986459.2986586
[35] Mahoney “Randomized algorithms for matrices and data” Foundations and Trends® 3, 123-224 (2011).
https: / / doi.org/ 10.1561 / 2200000035
[36] Mathias “Approximation of matrix-valued functions” SIAM journal on matrix analysis and applications 14, 1061-1063 (1993).
https: / / doi.org/ 10.1137 / 0614070
[37] Al-Mohyand Higham “A new scaling and squaring algorithm for the matrix exponential” SIAM Journal on Matrix Analysis and Applications 31, 970-989 (2009).
https: / / doi.org/ 10.1137 / 09074721X
[38] 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).
https: / / doi.org/ 10.1137 / 100788860
[39] Nakamoto “A norm inequality for Hermitian operators” The American mathematical monthly 110, 238 (2003).
https: / / doi.org/ 10.1080 / 00029890.2003.11919961
[40] Nyström “Über die praktische Auflösung von Integralgleichungen mit Anwendungen auf Randwertaufgaben” Acta Mathematica 54, 185-204 (1930).
https: / / doi.org/ 10.1007 / BF02547521
[41] 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).
https: / / doi.org/ 10.1145 / 2213977.2214080
[42] Orús “A practical introduction to tensor networks: Matrix product states and projected entangled pair states” Annals of Physics 349, 117-158 (2014).
https: / / doi.org/ 10.1016 / j.aop.2014.06.013
[43] Rebentrost, Mohseni, and Lloyd, “Quantum support vector machine for big data classification” Physical review letters 113, 130503 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503
[44] Rebentrost, Schuld, Wossnig, Petruccione, and Lloyd, “Quantum gradient descent and Newton’s method for constrained polynomial optimization” New Journal of Physics 21, 073023 (2019).
https://doi.org/10.1088/1367-2630/ab2a9e
[45] 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).
https: / / doi.org/ 10.5555 / 2969239.2969424
[46] Rudi, Camoriano, and Rosasco, “Less is More: Nyström Computational Regularization” arXiv preprint arXiv:1507.04717 (2015).
[47] Schuld, Sinayskiy, and Petruccione, “Prediction by linear regression on a quantum computer” Physical Review A 94, 022342 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.94.022342
[48] Schwarz and Nest “Simulating quantum circuits with sparse output distributions” arXiv preprint arXiv:1310.6749 (2013).
[49] 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).
https: / / doi.org/ 10.1145 / 1007352.1007372
[50] Spielman and Teng “Spectral sparsification of graphs” SIAM Journal on Computing 40, 981-1025 (2011).
https: / / doi.org/ 10.1137 / 08074489X
[51] 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).
https: / / doi.org/ 10.1007 / BF01609348
[52] Talwalkar, Kumar, and Rowley, “Large-scale manifold learning” IEEE Conference on Computer Vision and Pattern Recognition 1-8 (2008).
https: / / doi.org/ 10.1109 / CVPR.2008.4587670
[53] Tang “A Quantum-Inspired Classical Algorithm for Recommendation Systems” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 217-228 (2019).
https: / / doi.org/ 10.1145 / 3313276.3316310
[54] Tropp “User-Friendly Tail Bounds for Sums of Random Matrices” Found. Comput. Math. 12, 389-434 (2012).
HTTPS: / / doi.org/ 10.1007 / s10208-011-9099-z
[55] Trotter “On the product of semi-groups of operators” Proceedings of the American Mathematical Society 10, 545-551 (1959).
https://doi.org/10.1090/S0002-9939-1959-0108732-6
[56] Van Den Nest “Classical simulation of quantum computation, the Gottesman” Quantum Information & Computation 10, 258-271 (2010).
https: / / doi.org/ 10.5555 / 2011350.2011356
[57] Verstraete, Garcia-Ripoll, and Cirac, “Matrix product density operators: Simulation of finite-temperature and dissipative systems” Physical review letters 93, 207204 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.93.207204
[58] 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).
https: / / doi.org/ 10.1063 / 1.5026985
[59] Vidal “Efficient Simulation of One-Dimensional Quantum Many-Body Systems” Phys. Rev. Lett. 93, 040502 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.93.040502
[60] Williams and Seeger “Using the Nyström Method to Speed Up Kernel Machines” Advances in Neural Information Processing Systems 13 682-688 (2001).
https: / / doi.org/ 10.5555 / 3008751.3008847
[61] Williams, Rasmussen, Schwaighofer, and Tresp, “Observations on the Nyström Method for Gaussian Process Prediction” report (2002).
[62] Woodruff “Sketching as a tool for numerical linear algebra” Foundations and Trends® 10, 1-157 (2014).
https: / / doi.org/ 10.1561 / 0400000060
[63] Zhang and Kwok “Clustered Nyström method for large scale manifold learning and dimension reduction” IEEE Transactions on Neural Networks 21, 1576-1587 (2010).
https: / / doi.org/ 10.1109 / TNN.2010.2064786
[64] 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).
https: / / doi.org/ 10.1145 / 1390156.1390311
Alıntılama
[1] Ewin Tang, “Quantum-inspired classical algorithms for principal component analysis and supervised clustering”, arXiv: 1811.00414.
[2] Juan A. Acebron, “A Monte Carlo method for computing the action of a matrix exponential on a vector”, arXiv: 1904.12759.
[3] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang ve Chunhao Wang, "Kuantum makine öğreniminin nicelikselleştirilmesi için örnekleme tabanlı alt doğrusal düşük dereceli matris aritmetik çerçevesi", arXiv: 1910.06151.
Yukarıdaki alıntılar SAO / NASA REKLAMLARI (son başarıyla 2020-02-20 15:40:36) güncellendi. Tüm yayıncılar uygun ve eksiksiz alıntı verisi sağlamadığından liste eksik olabilir.
Getirilemedi Alıntılanan veriler son girişim sırasında 2020-02-20 15:40:34: Crossref'ten 10.22331 / q-2020-02-20-234 için belirtilen veriler getirilemedi. DOI yakın zamanda kaydedildiyse bu normaldir.
Bu Makale, Quantum'da Creative Commons Atıf 4.0 Uluslararası (CC BY 4.0) lisans. Telif hakkı, yazarlar veya kurumları gibi orijinal telif hakkı sahiplerine aittir.
Kaynak: https://quantum-journal.org/papers/q-2020-02-20-234/
