Pospeševanje kvantnih algoritmov s predračunom

Ponovno objavil Platon

Spremljevalci: 0

Pospeševanje kvantnih algoritmov s predračunanjem PlatoBlockchain Data Intelligence. Navpično iskanje. Ai.

William J. Huggins in Jarrod R. McClean

Google Quantum AI, Benetke, CA, ZDA

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Uporabe računalništva v resničnem svetu so lahko izjemno časovno občutljive. Dragoceno bi bilo, če bi lahko takšne naloge pospešili tako, da bi nekaj dela opravili pred časom. Na podlagi tega predlagamo model stroškov za kvantne algoritme, ki omogoča kvantno predračunavanje; tj. za polinomsko količino "brezplačnega" računanja, preden je vnos v algoritem v celoti določen, in metode za njegovo izkoriščanje. Analiziramo dve družini enot, ki sta asimptotično bolj učinkoviti za implementacijo v tem stroškovnem modelu kot v standardnem. Prvi primer kvantnega predračunanja, ki temelji na potenciranju matrike gostote, bi lahko ponudil eksponentno prednost pod določenimi pogoji. Drugi primer uporablja različico teleportacije vrat za doseganje kvadratne prednosti v primerjavi z neposredno implementacijo unitarjev. Ti primeri namigujejo, da lahko kvantno predračunavanje ponudi novo areno, v kateri lahko iščemo kvantno prednost.

► BibTeX podatki

@article{Huggins2024acceleratingquantum, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, title = {Pospeševanje { Q}kvantni {A}lgoritmi s {P}ponovnim računanjem}, avtor = {Huggins, William J. in McClean, Jarrod R.}, revija = {{Quantum}}, issn = {2521-327X}, založnik = {{ Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, obseg = {8}, strani = {1264}, mesec = feb, leto = {2024} }

► Reference

[1] S Aaronson. Omejitve kvantnega svetovanja in enosmerne komunikacije. V zborniku. 19. letna konferenca IEEE o računalniški kompleksnosti, 2004, strani 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/ccc.2004.1313854.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

[2] Scott Aaronson in Andris Ambainis. Odnos. V zborniku sedeminštiridesetega letnega simpozija ACM o teoriji računalništva, STOC '15, strani 307–316, New York, NY, ZDA, 14. junij 2015. ACM. ISBN 9781450335362. 10.1145/2746539.2746547.
https: / / doi.org/ 10.1145 / 2746539.2746547

[3] Scott Aaronson in Guy N Rothblum. Nežno merjenje kvantnih stanj in diferencialne zasebnosti. 18. april 2019. URL http:///arxiv.org/abs/1904.08747.
arXiv: 1904.08747

[4] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo in Hartmut Neven. Osredotočite se na kvadratne pospeške za kvantno prednost s popravljenimi napakami. PRX quantum, 2 (1): 010103, 29. marec 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Daniel J Bernstein in Tanja Lange. Neenakomerne razpoke v betonu: Moč brezplačnega predizračunavanja. V Napredek v kriptologiji – ASIACRYPT 2013, zapiski predavanj iz računalništva, strani 321–340. Springer Berlin Heidelberg, Berlin, Heidelberg, 2013. ISBN 9783642420443,9783642420450. 10.1007/978-3-642-42045-0_17.
https://doi.org/10.1007/978-3-642-42045-0_17

[6] Dominic W Berry, Craig Gidney, Mario Motta, Jarrod R McClean in Ryan Babbush. Kbitizacija kvantne kemije s poljubno bazo, ki izkorišča redkost in faktorizacijo nizkega ranga. 6. februar 2019. URL https:///doi.org/10.22331/q-2019-12-02-208.
https://doi.org/10.22331/q-2019-12-02-208

[7] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe in Seth Lloyd. Kvantno strojno učenje. Narava, 549 (7671): 195–202, september 2017. ISSN 0028-0836,1476-4687. 10.1038/nature23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Sergej Bravi in Aleksej Kitajev. Univerzalno kvantno računanje z idealnimi cliffordovimi vrati in hrupnimi ancilami. Phys. Rev. A, 71 (2): 022316, 22. februar 2005. ISSN 1050-2947,1094-1622. 10.1103/physreva.71.022316.
https: / / doi.org/ 10.1103 / physreva.71.022316

[9] Sergej Bravi in Dmitrij Maslov. Vezja brez Hadamarda razkrivajo strukturo cliffordove skupine. IEEE Trans. Inf. Theory, 67 (7): 4546–4563, julij 2021. ISSN 0018-9448,1557-9654. 10.1109/tit.2021.3081415.
https: / / doi.org/ 10.1109 / tit.2021.3081415

[10] Earl T Campbell in Joe O'Gorman. Učinkovit pristop čarobnega stanja k rotacijam z majhnim kotom. 14. marec 2016. URL https:///doi.org/10.1088/2058-9565/1/1/015007.
https://doi.org/10.1088/2058-9565/1/1/015007

[11] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang in Jerry Li. Eksponentna ločevanja med učenjem s kvantnim spominom in brez njega. Leta 2021 na 62. letnem simpoziju IEEE o temeljih računalništva (FOCS). IEEE, februar 2022. 10.1109/focs52979.2021.00063.
https:///doi.org/10.1109/focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari in Rolando D Somma. Kvantni algoritem za sisteme linearnih enačb z eksponentno izboljšano odvisnostjo od natančnosti. SIAM J. Comput., 46 (6): 1920–1950, 1. januar 2017. ISSN 0097-5397. 10.1137/16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

[13] N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik in Yoshihisa Yamamoto. Hitrejša simulacija kvantne kemije na kvantnih računalnikih, odpornih na napake. New J. Phys., 14 (11): 115023, 27. november 2012. ISSN 1367-2630. 10.1088/1367-2630/14/11/115023.
https://doi.org/10.1088/1367-2630/14/11/115023

[14] Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush in Dominic W Berry. Reševalec kvantnih linearnih sistemov z optimalnim skaliranjem prek diskretnega adiabatnega izreka. PRX quantum, 3 (4): 040303, 7. oktober 2022. ISSN 2691-3399. 10.1103/prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

[15] Jordan Cotler, Hsin-Yuan Huang in Jarrod R McClean. Ponovna obravnava dekvantizacije in kvantne prednosti pri učnih nalogah. 1. december 2021. URL http:///arxiv.org/abs/2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman in Anirudh Krishna. Diagonalna vrata v cliffordovi hierarhiji. Phys. Rev. A, 95 (1), 26. januar 2017. ISSN 2469-9926,2469-9934. 10.1103/physreva.95.012329.
https: / / doi.org/ 10.1103 / physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone in Sam Gutmann. Algoritem kvantne približne optimizacije. 14. november 2014. URL http:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

[18] Austin G Fowler. Časovno optimalno kvantno računanje. 17. oktober 2012. URL http:///arxiv.org/abs/1210.4626.
arXiv: 1210.4626

[19] Sevag Gharibian in François Le Gall. Dekvantizacija kvantne transformacije singularne vrednosti: trdota in aplikacije v kvantni kemiji in domneva o kvantnem PCP. V zborniku 54. letnega simpozija ACM SIGACT o teoriji računalništva, STOC 2022, strani 19–32, New York, NY, ZDA, 9. junij 2022. ACM. ISBN 9781450392648. 10.1145/3519935.3519991.
https: / / doi.org/ 10.1145 / 3519935.3519991

[20] Craig Gidney in Martin Ekerå. Kako faktorizirati 2048-bitna cela števila RSA v 8 urah z uporabo 20 milijonov hrupnih kubitov. Quantum, 5 (433): 433, 15. april 2021. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[21] Craig Gidney in Austin G Fowler. Prilagodljiva postavitev izračunov površinske kode z uporabo stanj AutoCCZ. 21. maj 2019. URL http:///arxiv.org/abs/1905.08916.
arXiv: 1905.08916

[22] András Gilyén in Alexander Poremba. Izboljšani kvantni algoritmi za oceno natančnosti. 29. marec 2022. URL http:///arxiv.org/abs/2203.15993.
arXiv: 2203.15993

[23] Daniel Gottesman in Isaac L Chuang. Kvantna teleportacija je univerzalna računalniška primitiva. 2. avgust 1999. URL https:///doi.org/10.1038/46503.
https: / / doi.org/ 10.1038 / 46503

[24] Leo Grady in Ali Kemal Sinop. Hitra približna segmentacija naključnega sprehajalca z uporabo predizračunavanja lastnih vektorjev. Leta 2008 na konferenci IEEE o računalniškem vidu in prepoznavanju vzorcev, strani 1–8. IEEE, junij 2008. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https:///doi.org/10.1109/cvpr.2008.4587487

[25] Lov K Grover. Hiter kvantno mehanski algoritem za iskanje po bazi podatkov. V zborniku osemindvajsetega letnega simpozija ACM o teoriji računalništva – STOC '96, STOC '96, strani 212–219, New York, New York, ZDA, 1996. ACM Press. ISBN 9780897917858. 10.1145/237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866

[26] Aram W Harrow, Avinatan Hassidim in Seth Lloyd. Kvantni algoritem za linearne sisteme enačb. Phys. Rev. Lett., 103 (15): 150502, 9. oktober 2009. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

[27] Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill in Jarrod R McClean. Kvantna prednost učenja iz eksperimentov. Znanost, 376 (6598): 1182–1186, 10. junij 2022. ISSN 0036-8075,1095-9203. 10.1126/science.abn7293.
https:///doi.org/10.1126/science.abn7293

[28] Cody Jones. Protokoli destilacije za fourierjeva stanja v kvantnem računalništvu. 12. marec 2013. URL http:///arxiv.org/abs/1303.3066.
arXiv: 1303.3066

[29] John Kallaugher. Kvantna prednost za problem naravnega pretakanja. Leta 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), strani 897–908. IEEE, februar 2022. 10.1109/focs52979.2021.00091.
https:///doi.org/10.1109/focs52979.2021.00091

[30] Richard M Karp in Richard J Lipton. Nekatere povezave med neenotnimi in enotnimi kompleksnostnimi razredi. V zborniku dvanajstega letnega simpozija ACM o teoriji računalništva – STOC '80, STOC '80, strani 302–309, New York, New York, ZDA, 28. april 1980. ACM Press. ISBN 9780897910170. 10.1145/800141.804678.
https: / / doi.org/ 10.1145 / 800141.804678

[31] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols in Theodore J Yoder. Hamiltonova simulacija z optimalno kompleksnostjo vzorca. Npj Quantum Inf., 3 (1): 1–7, 30. marec 2017. ISSN 2056-6387,2056-6387. 10.1038/s41534-017-0013-7.
https://doi.org/10.1038/s41534-017-0013-7

[32] François Le Gall. Eksponentna ločitev kompleksnosti kvantnega in klasičnega spletnega prostora. V zborniku osemnajstega letnega simpozija ACM o paralelizmu v algoritmih in arhitekturah, SPAA '06, strani 67–73, New York, NY, ZDA, 30. julij 2006. ACM. ISBN 9781595934529. 10.1145/1148109.1148119.
https: / / doi.org/ 10.1145 / 1148109.1148119

[33] Lin Lin in Yu Tong. Optimalno filtriranje kvantnih lastnih stanj na osnovi polinoma z uporabo pri reševanju kvantnih linearnih sistemov. Quantum, 4 (361): 361, 11. november 2020. ISSN 2521-327X. 10.22331/q-2020-11-11-361.
https://doi.org/10.22331/q-2020-11-11-361

[34] Daniel Litinski. Čarobna destilacija: Ni tako drago, kot mislite. Quantum, 3 (205): 205, 2. december 2019a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[35] Daniel Litinski. Igra površinskih kod: kvantno računalništvo velikega obsega z mrežno kirurgijo. Quantum, 3 (128): 128, 5. marec 2019b. ISSN 2521-327X. 10.22331/q-2019-03-05-128.
https://doi.org/10.22331/q-2019-03-05-128

[36] Seth Lloyd, Masoud Mohseni in Patrick Rebentrost. Analiza kvantnih glavnih komponent. Nat. Phys., 10 (9): 631–633, 27. september 2014. ISSN 1745-2473,1745-2481. 10.1038/nphys3029.
https: / / doi.org/ 10.1038 / nphys3029

[37] John M Martyn, Zane M Rossi, Andrew K Tan in Isaac L Chuang. Velika združitev kvantnih algoritmov. PRX quantum, 2 (4): 040203, 3. december 2021. ISSN 2691-3399. 10.1103/prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Iman Marvian in Seth Lloyd. Univerzalni kvantni emulator. 8. junij 2016. URL http:///arxiv.org/abs/1606.02734.
arXiv: 1606.02734

[39] F Motzoi, MP Kaicher in FK Wilhelm. Linearne in logaritemske časovne kompozicije kvantnih večtelesnih operatorjev. Phys. Rev. Lett., 119 (16): 160503, 20. oktober 2017. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.119.160503.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

[40] Michael A Nielsen. Optično kvantno računanje z uporabo stanj grozda. Phys. Rev. Lett., 93 (4): 040503, 23. julij 2004. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.93.040503.
https: / / doi.org/ 10.1103 / PhysRevLett.93.040503

[41] Bryan O'Gorman, William J Huggins, Eleanor G Rieffel in K Birgitta Whaley. Splošna izmenjevalna omrežja za kratkoročno kvantno računalništvo. 13. maj 2019. URL http:///arxiv.org/abs/1905.05118.
arXiv: 1905.05118

[42] Paul Pham in Krysta M Svore. 2D kvantna arhitektura najbližjega soseda za faktoring polilogaritemske globine. 27. julij 2012. URL http:///arxiv.org/abs/1207.6655.
arXiv: 1207.6655

[43] R Raussendorf in HJ Briegel. Enosmerni kvantni računalnik. Phys. Rev. Lett., 86 (22): 5188–5191, 28. maj 2001. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.86.5188.
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

[44] Yuval R Sanders, Dominic W Berry, Pedro CS Costa, Louis W Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven in Ryan Babbush. Zbirka kvantnih hevristik, odpornih na napake, za kombinatorično optimizacijo. PRX quantum, 1 (2): 020312, 9. november 2020. ISSN 2691-3399. 10.1103/prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

[45] Dan Shepherd in Michael J Bremner. Časovno nestrukturirano kvantno računanje. Proc. matematika Phys. inž. Sci., 465 (2105): 1413–1439, 8. maj 2009. ISSN 1364-5021,1471-2946. 10.1098/rspa.2008.0443.
https: / / doi.org/ 10.1098 / rspa.2008.0443

[46] Peter-Pike Sloan, Jan Kautz in John Snyder. Vnaprej izračunan prenos sevanja za upodabljanje v realnem času v dinamičnih okoljih nizke frekvence osvetlitve. V zborniku 29. letne konference o računalniški grafiki in interaktivnih tehnikah, SIGGRAPH '02, strani 527–536, New York, NY, ZDA, 1. julij 2002. ACM. ISBN 9781581135213. 10.1145/566570.566612.
https: / / doi.org/ 10.1145 / 566570.566612

[47] James E Smith. Študija strategij napovedovanja vej. V 25 letih mednarodnega simpozija o računalniški arhitekturi (izbrani prispevki), ISCA '98, strani 202–215, New York, NY, ZDA, 1. avgust 1998. ACM. ISBN 9781581130584. 10.1145/285930.285980.
https: / / doi.org/ 10.1145 / 285930.285980

[48] Rolando D Somma in Yiğit Subaşı. Kompleksnost preverjanja kvantnega stanja v problemu kvantnih linearnih sistemov. PRX quantum, 2 (1): 010315, 27. januar 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Barbara M Terhal. Kvantna korekcija napak za kvantne spomine. Rev. Mod. Phys., 87 (2): 307–346, 7. april 2015. ISSN 0034-6861,1539-0756. 10.1103/revmodphys.87.307.
https: / / doi.org/ 10.1103 / revmodphys.87.307

[50] Xinlan Zhou, Debbie W Leung in Isaac L Chuang. Metodologija za konstrukcijo kvantnih logičnih vrat. Phys. Rev. A, 62 (5), 18. oktober 2000. ISSN 1050-2947,1094-1622. 10.1103/physreva.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Navedel

[1] Dar Gilboa in Jarrod R. McClean, »Eksponentna kvantna komunikacijska prednost pri porazdeljenem učenju«, arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost in Mikel Sanz, »Kvantno približno eksponentiranje matrike gostote s pomočjo kloniranja«, arXiv: 2311.11751, (2023).

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2024-02-22 13:13:08). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

Pridobitve ni bilo mogoče Crossref citirani podatki med zadnjim poskusom 2024-02-22 13:13:06: Citiranih podatkov za 10.22331 / q-2024-02-22-1264 od Crossrefa ni bilo mogoče pridobiti. To je normalno, če je bil DOI registriran pred kratkim.

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.

Distribucija vsebine in PR s pomočjo SEO. Okrepite se še danes.
PlatoData.Network Vertical Generative Ai. Opolnomočite se. Dostopite tukaj.
PlatoAiStream. Web3 Intelligence. Razširjeno znanje. Dostopite tukaj.
PlatoESG. Ogljik, CleanTech, Energija, Okolje, sončna energija, Ravnanje z odpadki. Dostopite tukaj.
PlatoHealth. Obveščanje o biotehnologiji in kliničnih preskušanjih. Dostopite tukaj.
vir: https://quantum-journal.org/papers/q-2024-02-22-1264/

Časovni žig: Februar 22, 2024

Časovni žig: Junij 1, 2023

Pospeševanje kvantnih algoritmov s predračunom

Ponovno objavil Platon

Minimalizem

► BibTeX podatki

► Reference

Navedel

Več od Quantum Journal

Perceval: programska platforma za diskretno spremenljivo fotonsko kvantno računalništvo

Univerzalna kvantna vezja za kvantno kemijo

Efektivna proti Floquetovi teoriji za Kerrov parametrični oscilator

Vezja prostorskih in časovnih kvantnih kanalov

Ohranjanje energije in fluktuacijski izrek sta nezdružljiva za kvantno delo

Optimalno kodiranje oscilatorjev v več oscilatorjev

Razločevanje in certificiranje neznanih kvantnih meritev

Vzorčenje pomembnosti za stohastične kvantne simulacije

Kvantni algoritem za posredovanje sporočil za optimalno in učinkovito dekodiranje

Razširljiva in prilagodljiva klasična senčna tomografija s tenzorskimi omrežji

O nas

Navpično iskanje in Ai

Platforma

Ostanite povezani

Račun