1Inštitut za matematiko Alfréda Rényija
2Adobe Research
3Univerza v Washingtonu
Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.
Minimalizem
Podajamo klasičen algoritem za linearno regresijo, ki je analogen algoritmu inverzije kvantne matrike [Harrow, Hassidim in Lloyd, Physical Review Letters'09] za matrike nizkega ranga [Wossnig, Zhao in Prakash, Physical Review Letters'18], ko vhodna matrika $A$ je shranjena v podatkovni strukturi, ki se uporablja za pripravo stanja na podlagi QRAM-a.
Namreč, predpostavimo, da imamo $A v mathbb{C}^{mtimes n}$ z minimalno neničelno singularno vrednostjo $sigma$, ki podpira nekatere učinkovite poizvedbe glede vzorčenja pomembnosti norme $ell_2$, skupaj z $b v mathbb {C}^m$. Potem za nekaj $x v mathbb{C}^n$, ki izpolnjuje $|x – A^+b| leq varepsilon|A^+b|$, lahko izpišemo meritev $|xrangle$ v računski osnovi in izpišemo vnos $x$ s klasičnimi algoritmi, ki delujejo v $tilde{mathcal{O}}big(frac{ |A|_{mathrm{F}}^6|A|^6}{sigma^{12}varepsilon^4}big)$ in $tilda{mathcal{O}}big(frac{|A|_{mathrm {F}}^6|A|^2}{sigma^8varepsilon^4}velik)$ čas oz. To izboljša prejšnje "kvantno navdihnjene" algoritme v tej smeri raziskav za vsaj faktor $frac{|A|^{16}}{sigma^{16}varepsilon^2}$ [Chia, Gilyén, Li, Lin, Tang in Wang, STOC'20]. Posledično pokažemo, da lahko kvantni računalniki dosežejo največ faktor 12 pospeška za linearno regresijo v tej nastavitvi strukture podatkov QRAM in povezanih nastavitvah. Naše delo uporablja tehnike od skiciranja algoritmov in optimizacije do kvantno navdihnjene literature. Za razliko od prejšnjih del je to obetavna pot, ki bi lahko vodila do izvedljivih implementacij klasične regresije v kvantno navdihnjenih nastavitvah za primerjavo s prihodnjimi kvantnimi računalniki.
Predstavljena slika: računska kompleksnost prejšnjega najboljšega algoritma za kvantno navdahnjeno linearno regresijo (kot je opisano v povzetku), avtorjev Chia, Gilyén, Li, Lin, Tang, Wang, skupaj s kompleksnostjo algoritma, doseženega v tem delu. Oba algoritma delujeta v splošnejših nastavitvah (predhodno delo je mogoče uporabiti za bolj robusten pojem regresije in to delo podpira regularizacijo), vendar omejitev na to nastavitev ne vpliva bistveno na primerjavo.
Priljubljen povzetek
► BibTeX podatki
► Reference
[1] John Preskill. "Kvantno računalništvo v dobi NISQ in pozneje". Quantum 2, 79 (2018). arXiv:1801.00862.
https://doi.org/10.22331/q-2018-08-06-79
arXiv: 1801.00862
[2] Andrew M Childs. “Reševanje enačb s simulacijo”. Nature Physics 5, 861–861 (2009).
https: / / doi.org/ 10.1038 / nphys1473
[3] Scott Aaronson. "Preberite drobni tisk". Nature Physics 11, 291–293 (2015).
https: / / doi.org/ 10.1038 / nphys3272
[4] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe in Seth Lloyd. "Kvantno strojno učenje". Narava 549, 195–202 (2017). arXiv:1611.09347.
https: / / doi.org/ 10.1038 / nature23474
arXiv: 1611.09347
[5] Aram W. Harrow, Avinatan Hassidim in Seth Lloyd. “Kvantni algoritem za linearne sisteme enačb”. Physical Review Letters 103, 150502 (2009). arXiv:0811.3171.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502
arXiv: 0811.3171
[6] András Gilyén, Yuan Su, Guang Hao Low in Nathan Wiebe. "Kvantna singularna transformacija vrednosti in več: Eksponentne izboljšave za kvantno matrično aritmetiko". V zborniku 51. simpozija ACM o teoriji računalništva (STOC). Strani 193–204. (2019). arXiv:1806.01838.
https: / / doi.org/ 10.1145 / 3313276.3316366
arXiv: 1806.01838
[7] Vittorio Giovannetti, Seth Lloyd in Lorenzo Maccone. "Kvantni pomnilnik z naključnim dostopom". Physical Review Letters 100, 160501 (2008). arXiv:0708.1879.
https: / / doi.org/ 10.1103 / PhysRevLett.100.160501
arXiv: 0708.1879
[8] Anupam Prakash. “Kvantni algoritmi za linearno algebro in strojno učenje”. doktorsko delo. Kalifornijska univerza v Berkeleyju. (2014). url: www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-211.pdf.
https:///www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-211.pdf
[9] Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang in Chunhao Wang. "Sublinearni nizkorangirani matrični aritmetični okvir za dekvantizacijo kvantnega strojnega učenja, ki temelji na vzorčenju". V zborniku 52. simpozija ACM o teoriji računalništva (STOC). Stran 387–400. (2020). arXiv:1910.06151.
https: / / doi.org/ 10.1145 / 3357713.3384314
arXiv: 1910.06151
[10] Iordanis Kerenidis in Anupam Prakash. "Kvantni sistemi priporočil". V zborniku 8. konference o inovacijah v teoretični računalniški znanosti (ITCS). Strani 49:1–49:21. (2017). arXiv:1603.08675.
https: / / doi.org/ 10.4230 / LIPIcs.ITCS.2017.49
arXiv: 1603.08675
[11] Ewin Tang. "Kvantno navdihnjen klasični algoritem za priporočilne sisteme". V zborniku 51. simpozija ACM o teoriji računalništva (STOC). Strani 217–228. (2019). arXiv:1807.04271.
https: / / doi.org/ 10.1145 / 3313276.3316310
arXiv: 1807.04271
[12] Iordanis Kerenidis, Jonas Landman, Alessandro Luongo in Anupam Prakash. “q-means: kvantni algoritem za nenadzorovano strojno učenje”. V Napredek v sistemih za obdelavo nevronskih informacij. Letnik 32. (2019). arXiv:1812.03584.
arXiv: 1812.03584
[13] Iordanis Kerenidis in Anupam Prakash. "Kvantni gradientni spust za linearne sisteme in najmanjše kvadrate". Physical Review A 101, 022316 (2020). arXiv:1704.04992.
https: / / doi.org/ 10.1103 / PhysRevA.101.022316
arXiv: 1704.04992
[14] Danial Dervovic, Mark Herbster, Peter Mountney, Simone Severini, Naïri Usher in Leonard Wossnig. »Algoritmi kvantnih linearnih sistemov: primer« (2018). arXiv:1802.08227.
arXiv: 1802.08227
[15] Leonard Wossnig, Zhikuan Zhao in Anupam Prakash. “Algoritem kvantnega linearnega sistema za goste matrike”. Physical Review Letters 120, 050502 (2018). arXiv:1704.06174.
https: / / doi.org/ 10.1103 / PhysRevLett.120.050502
arXiv: 1704.06174
[16] Patrick Rebentrost, Masoud Mohseni in Seth Lloyd. "Kvantni podporni vektorski stroj za klasifikacijo velikih podatkov". Physical Review Letters 113, 130503 (2014). arXiv:1307.0471.
https: / / doi.org/ 10.1103 / PhysRevLett.113.130503
arXiv: 1307.0471
[17] Shantanav Chakraborty, András Gilyén in Stacey Jeffery. "Moč blokovno kodiranih matričnih moči: izboljšane regresijske tehnike prek hitrejše Hamiltonove simulacije". V zborniku 46. mednarodnega kolokvija o avtomatih, jezikih in programiranju (ICALP). Strani 33:1–33:14. (2019). arXiv:1804.01973.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2019.33
arXiv: 1804.01973
[18] Nai-Hui Chia, András Gilyén, Han-Hsuan Lin, Seth Lloyd, Ewin Tang in Chunhao Wang. “Kvantno navdihnjeni algoritmi za reševanje sistemov linearnih enačb nizkega ranga z logaritemsko odvisnostjo od dimenzije”. V zborniku 31. mednarodnega simpozija o algoritmih in računanju (ISAAC). Strani 47:1–47:17. (2020). arXiv:1811.04852 in 1811.04909 (združeno).
https:///doi.org/10.4230/LIPIcs.ISAAC.2020.47
arXiv:1811.04852 in 1811.04909
(združeno)
[19] Juan Miguel Arrazola, Alain Delgado, Bhaskar Roy Bardhan in Seth Lloyd. "Kvantno navdihnjeni algoritmi v praksi". Quantum 4, 307 (2020). arXiv:1905.10415.
https://doi.org/10.22331/q-2020-08-13-307
arXiv: 1905.10415
[20] Ewin Tang. "Analiza kvantne glavne komponente doseže samo eksponentno pospešitev zaradi svojih predpostavk o pripravi stanja." Physical Review Letters 127, 060503 (2021). arXiv:1811.00414.
https: / / doi.org/ 10.1103 / PhysRevLett.127.060503
arXiv: 1811.00414
[21] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini in Leonard Wossnig. "Kvantno strojno učenje: klasična perspektiva". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 474, 20170551 (2018). arXiv:1707.08561.
https: / / doi.org/ 10.1098 / rspa.2017.0551
arXiv: 1707.08561
[22] Srinivasan Arunachalam, Vlad Gheorghiu, Tomas Jochym-O'Connor, Michele Mosca in Priyaa Varshinee Srinivasan. "O robustnosti kvantnega RAM-a bucket brigade". New Journal of Physics 17, 123010 (2015). arXiv:1502.03450.
https://doi.org/10.1088/1367-2630/17/12/123010
arXiv: 1502.03450
[23] Neha Gupta in Aaron Sidford. "Izkoriščanje numerične redkosti za učinkovito učenje: hitrejše izračunavanje lastnih vektorjev in regresija". V Napredek v sistemih za obdelavo nevronskih informacij. Strani 5269–5278. (2018). arXiv:1811.10866.
arXiv: 1811.10866
[24] Yair Carmon, Yujia Jin, Aaron Sidford in Kevin Tian. "Koordinatne metode za matrične igre". Leta 2020 na 61. letnem simpoziju IEEE o temeljih računalništva (FOCS). Strani 283–293. IEEE (2020). arXiv:2009.08447.
https:///doi.org/10.1109/focs46700.2020.00035
arXiv: 2009.08447
[25] Sébastien Bubeck. "Konveksna optimizacija: Algoritmi in kompleksnost". Temelji in trendi v strojnem učenju 8, 231–357 (2015). arXiv:1405.4980.
https: / / doi.org/ 10.1561 / 2200000050
arXiv: 1405.4980
[26] Roy Frostig, Rong Ge, Sham Kakade in Aaron Sidford. »Neregulariziranje: približna proksimalna točka in hitrejši stohastični algoritmi za empirično zmanjšanje tveganja«. Na mednarodni konferenci o strojnem učenju. Strani 2540–2548. (2015). arXiv:1506.07512.
arXiv: 1506.07512
[27] Francis Bach in Eric Moulines. “Neasimptotična analiza stohastičnih aproksimacijskih algoritmov za strojno učenje”. V Napredek v sistemih za obdelavo nevronskih informacij. Strani 451–459. (2011). url: http:///papers.nips.cc/paper/4316-non-asymptotic-analysis-of-stochastic-approximation-algorithms-for-machine-learning.pdf.
http:///papers.nips.cc/paper/4316-non-asymptotic-analysis-of-stochastic-approximation-algorithms-for-machine-learning.pdf
[28] András Gilyén, Seth Lloyd in Ewin Tang. »Kvantno navdahnjena stohastična regresija nizkega ranga z logaritemsko odvisnostjo od dimenzije« (2018). arXiv:1811.04909.
arXiv: 1811.04909
[29] Nai-Hui Chia, Han-Hsuan Lin in Chunhao Wang. »Kvantno navdihnjeni sublinearni klasični algoritmi za reševanje linearnih sistemov nizkega ranga« (2018). arXiv:1811.04852.
arXiv: 1811.04852
[30] David P. Woodruff. “Skiciranje kot orodje za numerično linearno algebro”. Osnove in trendi v teoretični računalniški znanosti 10, 1–157 (2014).
https: / / doi.org/ 10.1561 / 0400000060
[31] Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, Honghao Lin in David P. Woodruff. »Kvantno navdihnjeni algoritmi iz randomizirane numerične linearne algebre« (2020). arXiv:2011.04125.
arXiv: 2011.04125
[32] Changpeng Shao in Ashley Montanaro. »Hitrejši kvantno navdihnjeni algoritmi za reševanje linearnih sistemov« (2021). arXiv:2103.10309.
arXiv: 2103.10309
[33] Thomas Strohmer in Roman Vershynin. "Naključni Kaczmarzov algoritem z eksponentno konvergenco". Journal of Fourier Analysis and Applications 15, 262–278 (2008). arXiv:math/0702226.
https://doi.org/10.1007/s00041-008-9030-4
arXiv: matematika / 0702226
[34] Deanna Needell, Nathan Srebro in Rachel Ward. "Stohastični gradientni spust, uteženo vzorčenje in randomizirani Kaczmarzov algoritem". Matematično programiranje 155, 549–573 (2015). arXiv:1310.5715.
https://doi.org/10.1007/s10107-015-0864-7
arXiv: 1310.5715
[35] Petros Drineas, Ravi Kannan in Michael W Mahoney. “Hitri algoritmi Monte Carlo za matrike II: Računanje približka nizkega ranga matriki”. SIAM Journal on Computing 36, 158–183 (2006).
https: / / doi.org/ 10.1137 / S0097539704442696
Navedel
[1] Quynh T. Nguyen, Bobak T. Kiani in Seth Lloyd, "Kvantni algoritem za gosta jedra in jedra polnega ranga z uporabo hierarhičnih matric", arXiv: 2201.11329.
[2] Benjamin A. Cordier, Nicolas PD Sawaya, Gian G. Guerreschi in Shannon K. McWeeney, "Biologija in medicina v pokrajini kvantnih prednosti", arXiv: 2112.00760.
[3] Adam Bouland, Wim van Dam, Hamed Joorati, Iordanis Kerenidis in Anupam Prakash, "Obeti in izzivi kvantnih financ", arXiv: 2011.06492.
[4] Amirhossein Nourbakhsh, Mark Nicholas Jones, Kaur Kristjuhan, Deborah Carberry, Jay Karon, Christian Beenfeldt, Kyarash Shahriari, Martin P. Andersson, Mojgan A. Jadidi in Seyed Soheil Mansouri, »Kvantno računalništvo: osnove, trendi in perspektive za Kemijski in biokemični inženirji« arXiv: 2201.02823.
[5] Shantanav Chakraborty, Aditya Morolia in Anurudh Peduri, »Kvantno regularizirani najmanjši kvadrati«, arXiv: 2206.13143.
[6] Bujiao Wu, Maharshi Ray, Liming Zhao, Xiaoming Sun in Patrick Rebentrost, "Kvantno-klasični algoritmi za poševne linearne sisteme z optimiziranim Hadamardovim testom", Fizični pregled A 103 4, 042422 (2021).
[7] Xiao-Ming Zhang, Tongyang Li in Xiao Yuan, "Priprava kvantnega stanja z optimalno globino vezja: izvedbe in aplikacije", arXiv: 2201.11495.
[8] Changpeng Shao in Ashley Montanaro, "Hitrejši kvantno navdihnjeni algoritmi za reševanje linearnih sistemov", arXiv: 2103.10309.
[9] Patrick Rall, "Hitrejši koherentni kvantni algoritmi za oceno faze, energije in amplitude", arXiv: 2103.09717.
[10] Armando Bellante, Alessandro Luongo in Stefano Zanero, "Kvantni algoritmi za predstavitev in analizo podatkov", arXiv: 2104.08987.
[11] Iordanis Kerenidis in Anupam Prakash, "Kvantno strojno učenje s podprostorskimi stanji", arXiv: 2202.00054.
[12] Chenyi Zhang, Jiaqi Leng in Tongyang Li, "Kvantni algoritmi za pobeg iz sedla", arXiv: 2007.10253.
[13] Daniel Chen, Yekun Xu, Betis Baheri, Samuel A. Stein, Chuan Bi, Ying Mao, Qiang Quan in Shuai Xu, »Kvantno navdihnjen klasični algoritem za analizo počasnih funkcij«, arXiv: 2012.00824.
[14] Sevag Gharibian in François Le Gall, »Dekvantiziranje kvantne singularne transformacije vrednosti: trdota in aplikacije v kvantni kemiji in kvantni PCP domnevi«, arXiv: 2111.09079.
[15] Kazuya Kaneko, Koichi Miyamoto, Naoyuki Takeda in Kazuyoshi Yoshino, "Linearna regresija s kvantno oceno amplitude in njena razširitev na konveksno optimizacijo", Fizični pregled A 104 2, 022430 (2021).
[16] Ebrahim Ardeshir-Larijani, "Parametrizirana kompleksnost kvantno navdihnjenih algoritmov", arXiv: 2112.11686.
[17] Franco D. Albareti, Thomas Ankenbrand, Denis Bieri, Esther Hänggi, Damian Lötscher, Stefan Stettler in Marcel Schöngens, "Strukturirana raziskava kvantnega računalništva za finančno industrijo", arXiv: 2204.10026.
Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2022-07-21 14:20:36). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.
On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2022-07-21 14:20:34).
Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.
