Zephyrnet-logo

Hamiltoniaanse dynamiek benaderen met de Nyström-methode

Datum:

Alessandro Rudi1, Leonard Wossnig2,3, Carlo Ciliberto2, Andrea Rocchetto2,4,5, Massimiliano Pontil6, en Simone Severini2

1INRIA – Sierra projectteam, Parijs, Frankrijk
2Afdeling informatica, University College London, Londen, Verenigd Koninkrijk
3Rahko Ltd., Londen, Verenigd Koninkrijk
4Afdeling Computerwetenschappen, Universiteit van Texas in Austin, Austin, Verenigde Staten
5Afdeling Computerwetenschappen, Universiteit van Oxford, Oxford, Verenigd Koninkrijk
6Computationele statistiek en machine learning, IIT, Genua, Italië

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

Het simuleren van de tijdevolutie van kwantummechanische systemen is BQP-moeilijk en zal naar verwachting een van de belangrijkste toepassingen van kwantumcomputers zijn. We beschouwen klassieke algoritmen voor de benadering van Hamiltoniaanse dynamica met behulp van subsampling-methoden van gerandomiseerde numerieke lineaire algebra. We leiden een simulatietechniek af waarvan de looptijd polynoom schaalt in het aantal qubits en de Frobenius-norm van de Hamiltoniaan. Als onmiddellijke toepassing laten we zien dat op monsters gebaseerde kwantumsimulatie, een soort evolutie waarbij de Hamiltoniaan een dichtheidsmatrix is, efficiënt klassiek kan worden gesimuleerd onder specifieke structurele omstandigheden. Onze belangrijkste technische bijdrage is een gerandomiseerd algoritme voor het benaderen van exponentiële hermitische matrixen. Het bewijs maakt gebruik van een lage rang, symmetrische benadering via de Nyström-methode. Onze resultaten suggereren dat er onder sterke bemonsteringsaannames klassieke polylogaritmische tijdsimulaties van kwantumberekeningen bestaan.

► BibTeX-gegevens

► Referenties

[1] Aharonov en 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 en Peller "Operator Lipschitz-functies" Russian Mathematical Surveys 71, 605 (2016).
https://​/​doi.org/​10.1070/​RM9729

[3] Belabbas en Wolfe "Fast low-rank approximation for covariantiematrices" 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 en Wolfe "Over schaarse representaties van lineaire operatoren en de benadering van matrixproducten" 42e jaarlijkse conferentie over informatiewetenschappen en systemen 258-263 (2008).
https: / / doi.org/ 10.1109 / CISS.2008.4558532

[5] Berry, Childs en Kothari, "Hamiltoniaanse simulatie met bijna optimale afhankelijkheid van alle 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 en Lloyd, "Quantum machine learning" Nature 549, 195 (2017).
https: / / doi.org/ 10.1038 / nature23474

[7] Bravyi, Browne, Calpin, Campbell, Gosset en Howard, "Simulatie van kwantumcircuits door ontbindingen van lage stabilisatoren" arXiv preprint arXiv: 1808.00128 (2018).
https:/​/​doi.org/​10.22331/​q-2019-09-02-181

[8] Chia, Gilyén, Li, Lin, Tang en Wang, "Sampling-based sublinear low-rank matrix aritmetic framework for dequantizing quantum machine learning" arXiv preprint arXiv:1910.06151 (2019).

[9] Childs en Kothari "Sparse Hamiltonians simuleren met sterontbindingen" 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 en Wiebe "Hamiltoniaanse simulatie met behulp van lineaire combinaties van unitaire bewerkingen" Quantum Info. Bereken. 12, 901-924 (2012).
https: / / doi.org/ 10.5555 / 2481569.2481570

[11] Childs, Cleve, Deotto, Farhi, Gutmann en 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 en Wossnig, "Quantum machine learning: een klassiek perspectief" Proc. R Soc. A 474, 20170551 (2018).
https: / / doi.org/ 10.1098 / rspa.2017.0551

[13] Drineas, Kannan en Mahoney, "Fast Monte Carlo-algoritmen voor matrices I: benadering van matrixvermenigvuldiging" SIAM Journal on Computing 36, 132-157 (2006).
https: / / doi.org/ 10.1137 / S0097539704442684

[14] Drineas, Kannan en Mahoney, "Fast Monte Carlo-algoritmen voor matrices II: berekening van een lage benadering van een matrix" SIAM Journal on computing 36, 158-183 (2006).
https: / / doi.org/ 10.1137 / S0097539704442696

[15] Drineas en Mahoney "Over de Nyström-methode voor het benaderen van een grammatrix voor verbeterd kernelgebaseerd leren" J. Mach. Leren. Res. 6, 2153-2175 (2005).
https: / / doi.org/ 10.5555 / 1046920.1194916

[16] Drineas en Mahoney "Lezingen over gerandomiseerde numerieke lineaire algebra" The Mathematics of Data 25, 1 (2018).

[17] Drineas, Mahoney, Muthukrishnan en Sarlós, "Faster Least Squares Approximation" Numer. Wiskunde. 117, 219-249 (2011).
https:/​/​doi.org/​10.1007/​s00211-010-0331-6

[18] Fowlkes, Belongie, Chung en Malik, "Spectrale groepering met behulp van de Nyström-methode" IEEE Trans. Patroon anaal. Mach. Intel. 26, 214-225 (2004).
https: / / doi.org/ 10.1109 / TPAMI.2004.1262185

[19] Frieze, Kannan en Vempala, "Snelle Monte-Carlo-algoritmen voor het vinden van laaggeplaatste benaderingen" J. ACM 51, 1025-1041 (2004).
https: / / doi.org/ 10.1145 / 1039488.1039494

[20] Haegeman, Cirac, Osborne, Pižorn, Verschelde en Verstraete, "Tijdsafhankelijk variatieprincipe voor kwantumroosters" Physical review letters 107, 070601 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.107.070601

[21] Higham "De schaal- en kwadratuurmethode voor de matrix exponentieel herzien" 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 "Gewogen bemonstering van uitwendige producten" arXiv preprint arXiv: 1410.4429 (2014).

[24] Huang, Newman en Szegedy, "Expliciete ondergrenzen voor sterke kwantumsimulatie" arXiv preprint arXiv: 1804.10368 (2018).

[25] Jónsson, Bauer en Carleo, "Neural-netwerktoestanden voor de klassieke simulatie van quantum computing" arXiv preprint arXiv: 1808.05232 (2018).

[26] Kerenidis en Prakash "Quantum aanbevelingssystemen" arXiv preprint arXiv: 1603.08675 (2016).

[27] Kimmel, Lin, Low, Ozols en Yoder, "Hamiltoniaanse simulatie met optimale monstercomplexiteit" npj Quantum Information 3, 13 (2017).
https:/​/​doi.org/​10.1038/​s41534-017-0013-7

[28] Kumar, Mohri en Talwalkar, ‘On Sampling-Based Approximate Spectral Decomposition’ Proceedings van de
26e jaarlijkse internationale conferentie over machinaal leren 553-560 (2009).
https: / / doi.org/ 10.1145 / 1553374.1553446

[29] Kumar, Mohri en Talwalkar, "Bemonsteringsmethoden voor de Nyström-methode" Journal of Machine Learning Research 13, 981-1006 (2012).
https: / / doi.org/ 10.5555 / 2188385.2343678

[30] Li, Kwok en Lu, "Grootschalige Nyström-benadering mogelijk maken" 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 en Rebentrost, "Quantum principal component analysis" Nature Physics 10, 631 (2014).
https: / / doi.org/ 10.1038 / nphys3029

[33] Lowand Chuang "Hamiltoniaanse simulatie door uniforme spectrale versterking" arXiv voordruk arXiv: 1707.05391 (2017).

[34] Mackey, Talwalkar en Jordan, "Verdeel-en-heers-matrixfactorisatie" Proceedings of the 24th International Conference on Neural Information Processing Systems 1134-1142 (2011).
https: / / doi.org/ 10.5555 / 2986459.2986586

[35] Mahoney "Gerandomiseerde algoritmen voor matrices en gegevens" Foundations and Trends® 3, 123-224 (2011).
https: / / doi.org/ 10.1561 / 2200000035

[36] Mathias "Approximation of matrix-valued functions" SIAM-tijdschrift over matrixanalyse en toepassingen 14, 1061-1063 (1993).
https: / / doi.org/ 10.1137 / 0614070

[37] Al-Mohyand Higham "Een nieuw schaal- en kwadratuuralgoritme voor de exponentiële matrix" SIAM Journal on Matrix Analysis and Applications 31, 970-989 (2009).
https: / / doi.org/ 10.1137 / 09074721X

[38] Al-Mohyand Higham "De actie van de exponentiële matrix berekenen, met een toepassing op exponentiële integrators", SIAM-tijdschrift over wetenschappelijk computergebruik 33, 488-511 (2011).
https: / / doi.org/ 10.1137 / 100788860

[39] Nakamoto "Een normongelijkheid voor Hermitische operatoren" Het Amerikaanse wiskundige maandblad 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 en Vishnoi, "Het benaderen van de exponentiële, de Lanczos-methode en een Õ(m)-tijd spectraal algoritme voor gebalanceerde 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 "Een praktische inleiding tot tensornetwerken: matrixproducttoestanden en geprojecteerde verstrengelde paartoestanden" Annals of Physics 349, 117-158 (2014).
https: / / doi.org/ 10.1016 / j.aop.2014.06.013

[43] Rebentrost, Mohseni en Lloyd, "Quantum-ondersteuningsvectormachine voor classificatie van big data" Fysieke beoordelingsbrieven 113, 130503 (2014).
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503

[44] Rebentrost, Schuld, Wossnig, Petruccione en Lloyd, "Kwantumgradiëntafdaling en Newtons methode voor beperkte polynoomoptimalisatie" New Journal of Physics 21, 073023 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab2a9e

[45] Rudi, Camoriano en 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 en Rosasco, "Less is More: Nyström Computational Regularization" arXiv preprint arXiv:1507.04717 (2015).

[47] Schuld, Sinayskiy en Petruccione, "Voorspelling door lineaire regressie op een kwantumcomputer" Physical Review A 94, 022342 (2016).
https: / / doi.org/ 10.1103 / PhysRevA.94.022342

[48] Schwarz en Nest "Kwantumcircuits simuleren met schaarse uitvoerdistributies" arXiv preprint arXiv: 1310.6749 (2013).

[49] Spielman en 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 en Teng "Spectrale sparsificatie van grafieken" SIAM Journal on Computing 40, 981-1025 (2011).
https: / / doi.org/ 10.1137 / 08074489X

[51] Suzuki "Gegeneraliseerde Trotter's formule en systematische benaderingen van exponentiële operatoren en innerlijke afleidingen met toepassingen op veellichamenproblemen" Communications in Mathematical Physics 51, 183-190 (1976).
https: / / doi.org/ 10.1007 / BF01609348

[52] Talwalkar, Kumar en Rowley, "Grootschalig veelvoudig leren" IEEE-conferentie over computervisie en patroonherkenning 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 "Gebruiksvriendelijke staartgrenzen voor sommen van willekeurige matrices" gevonden. Bereken. Wiskunde. 12, 389-434 (2012).
https: / / doi.org/ 10.1007 / s10208-011-9099-z

[55] Trotter "Over het product van semi-groepen operatoren" Proceedings of the American Mathematical Society 10, 545-551 (1959).
https:/​/​doi.org/​10.1090/​S0002-9939-1959-0108732-6

[56] Van Den Nest "Klassieke simulatie van kwantumberekening, de Gottesman" Quantum Information & Computation 10, 258-271 (2010).
https: / / doi.org/ 10.5555 / 2011350.2011356

[57] Verstraete, Garcia-Ripoll en 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 en Cirac, "Matrixproducttoestanden, geprojecteerde verstrengelde paartoestanden en variatierenormalisatiegroepmethoden voor kwantumspinsystemen" 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. Eerwaarde Lett. 93, 040502 (2004).
https: / / doi.org/ 10.1103 / PhysRevLett.93.040502

[60] Williams en Seeger "De Nyström-methode gebruiken om kernelmachines te versnellen" Vooruitgang in neurale informatieverwerkingssystemen 13 682-688 (2001).
https: / / doi.org/ 10.5555 / 3008751.3008847

[61] Williams, Rasmussen, Schwaighofer en Tresp, rapport "Observations on the Nyström Method for Gaussian Process Prediction" (2002).

[62] Woodruff "Schetsen als hulpmiddel voor numerieke lineaire algebra" Foundations and Trends® 10, 1-157 (2014).
https: / / doi.org/ 10.1561 / 0400000060

[63] Zhang en Kwok "Clustered Nyström-methode voor grootschalig veelvoudig leren en dimensiereductie" IEEE Transactions on Neural Networks 21, 1576-1587 (2010).
https://​/​doi.org/​10.1109/​TNN.2010.2064786

[64] Zhang, Tsang en Kwok, "Verbeterde 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

Geciteerd door

[1] Ewin Tang, "Quantum-geïnspireerde klassieke algoritmen voor analyse van hoofdcomponenten en gesuperviseerde clustering", arXiv: 1811.00414.

[2] Juan A. Acebron, "Een Monte Carlo-methode voor het berekenen van de actie van een exponentiële matrix op een vector", arXiv: 1904.12759.

[3] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang en Chunhao Wang, "Sampling-gebaseerd sublineair low-rank matrix rekenkundig kader voor dekwantisering van kwantummachinaal leren", arXiv: 1910.06151.

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2020-02-20 15:40:36). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

Kon niet ophalen Door Crossref geciteerde gegevens tijdens laatste poging 2020-02-20 15:40:34: kon niet geciteerde gegevens voor 10.22331 / q-2020-02-20-234 niet ophalen van Crossref. Dit is normaal als de DOI recent is geregistreerd.

Bron: https://quantum-journal.org/papers/q-2020-02-20-234/

spot_img

Laatste intelligentie

spot_img