Kvantalgoritmide kiirendamine eelarvutusega

Taasavaldanud Platon

järgijaid: 0

Kvantalgoritmide kiirendamine PlatoBlockchaini eelarvutusandmetega. Vertikaalne otsing. Ai.

William J. Huggins ja Jarrod R. McClean

Google Quantum AI, Veneetsia, CA, USA

Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.

Abstraktne

Reaalmaailma andmetöötlusrakendused võivad olla äärmiselt ajatundlikud. Oleks väärtuslik, kui suudaksime selliseid ülesandeid kiirendada, tehes osa töödest enne tähtaega. Sellest ajendatuna pakume välja kvantalgoritmide kulumudeli, mis võimaldab kvanteelarvutusi; st polünoomilise arvu “tasuta” arvutuste jaoks enne, kui algoritmi sisend on täielikult määratletud, ja meetodid selle ärakasutamiseks. Analüüsime kahte ühikute perekonda, mida on selles kulumudelis asümptootiliselt efektiivsem rakendada kui standardses. Esimene kvanteelarvutuse näide, mis põhineb tihedusmaatriksi eksponentsimisel, võib teatud tingimustel pakkuda eksponentsiaalset eelist. Teises näites kasutatakse värava teleportatsiooni varianti, et saavutada ruutväärtuse eelis võrreldes unitaaride otsese rakendamisega. Need näited vihjavad, et kvanteelarvutus võib pakkuda kvanteelise otsimiseks uut areeni.

► BibTeX-i andmed

@artikkel{Huggins2024akceleratingquantum, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, pealkiri {Acceler = {Acceler Q}kvant {A}lgoritmid {P}ümberarvutusega}, autor = {Huggins, William J. ja McClean, Jarrod R.}, ajakiri = {{Kvant}}, issn = {2521-327X}, väljaandja = {{ Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, maht = {8}, lehekülge = {1264}, kuu = veebruar, aasta = {2024} }

► Viited

[1] S Aaronson. Kvantnõustamise ja ühesuunalise suhtluse piirangud. In Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004, lk 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/ccc.2004.1313854.
https:///doi.org/10.1109/ccc.2004.1313854

[2] Scott Aaronson ja Andris Ambainis. Forrelatsioon. Väljaandes Proceedings of the 15. aastane ACM sümpoosion on Theory of Computing, STOC '307, lk 316–14, New York, NY, USA, 2015. juuni 9781450335362. ACM. ISBN 10.1145. 2746539.2746547/XNUMX.
https:///doi.org/10.1145/2746539.2746547

[3] Scott Aaronson ja Guy N Rothblum. Kvantolekute ja diferentsiaalse privaatsuse õrn mõõtmine. 18. aprill 2019. URL http:///arxiv.org/abs/1904.08747.
arXiv: 1904.08747

[4] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo ja Hartmut Neven. Veakorrigeeritud kvanteelise saavutamiseks keskenduge kaugemale ruutkiirusest. PRX quantum, 2 (1): 010103, 29. märts 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https:///doi.org/10.1103/prxquantum.2.010103

[5] Daniel J Bernstein ja Tanja Lange. Ebaühtlased praod betoonis: vaba eelarvutuse võimsus. Raamatus Advances in Cryptology – ASIACRYPT 2013, Loengukonspektid arvutiteaduses, lk 321–340. Springer Berlin Heidelberg, Berliin, 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 ja Ryan Babbush. Suvalise baaskvantkeemia qubitiseerimine, mis võimendab hõredust ja madala astme faktoriseerimist. 6. veebruar 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 ja Seth Lloyd. Kvantmasinaõpe. Nature, 549 (7671): 195–202, september 2017. ISSN 0028-0836,1476-4687. 10.1038/loodus23474.
https:///doi.org/10.1038/nature23474

[8] Sergei Bravyi ja Aleksei Kitaev. Universaalne kvantarvutus ideaalsete Cliffordi väravate ja mürarikaste lisaseadmetega. Phys. Rev. A, 71 (2): 022316, 22. veebruar 2005. ISSN 1050-2947,1094-1622. 10.1103/physreva.71.022316.
https:///doi.org/10.1103/physreva.71.022316

[9] Sergei Bravyi ja Dmitri Maslov. Hadamardivabad ahelad paljastavad cliffordi rühma struktuuri. IEEE Trans. Info Theory, 67 (7): 4546–4563, juuli 2021. ISSN 0018-9448,1557-9654. 10.1109/tit.2021.3081415.
https:///doi.org/10.1109/tit.2021.3081415

[10] Earl T Campbell ja Joe O'Gorman. Tõhus maagilise oleku lähenemine väikeste nurkade pöördetele. 14. märts 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 ja Jerry Li. Eksponentsiaalne eraldus kvantmäluga ja ilma õppimise vahel. 2021. aastal toimub IEEE 62. iga-aastane arvutiteaduse aluste sümpoosion (FOCS). IEEE, veebruar 2022. 10.1109/focs52979.2021.00063.
https:///doi.org/10.1109/focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari ja Rolando D Somma. Kvantalgoritm lineaarvõrrandisüsteemide jaoks, millel on eksponentsiaalselt paranenud sõltuvus täpsusest. SIAM J. Comput., 46 (6): 1920–1950, 1. jaanuar 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 ja Yoshihisa Yamamoto. Kiirem kvantkeemia simulatsioon tõrketaluvusega kvantarvutites. 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 ja Dominic W Berry. Optimaalne skaleerimise kvantlineaarsete süsteemide lahendaja diskreetse adiabaatilise teoreemi kaudu. PRX quantum, 3 (4): 040303, 7. oktoober 2022. ISSN 2691-3399. 10.1103/prxquantum.3.040303.
https:///doi.org/10.1103/prxquantum.3.040303

[15] Jordan Cotler, Hsin-Yuan Huang ja Jarrod R McClean. Dekvantimise ja kvanteelise uuesti läbivaatamine õppeülesannetes. 1. detsember 2021. URL http:///arxiv.org/abs/2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman ja Anirudh Krishna. Diagonaalväravad Cliffordi hierarhias. Phys. Rev. A, 95 (1), 26. jaanuar 2017. ISSN 2469-9926,2469-9934. 10.1103/physreva.95.012329.
https:///doi.org/10.1103/physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone ja Sam Gutmann. Kvantligikaudne optimeerimisalgoritm. 14. november 2014. URL http:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

[18] Austin G Fowler. Ajaoptimaalne kvantarvutus. 17. oktoober 2012. URL http:///arxiv.org/abs/1210.4626.
arXiv: 1210.4626

[19] Sevag Gharibian ja François Le Gall. Kvant-ainsuse väärtuse teisenduse dekvantiseerimine: kõvadus ja rakendused kvantkeemias ning kvant-PCP oletus. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, lk 19–32, New York, NY, USA, 9. juuni 2022. ACM. ISBN 9781450392648. 10.1145/3519935.3519991.
https:///doi.org/10.1145/3519935.3519991

[20] Craig Gidney ja Martin Ekerå. Kuidas faktoreerida 2048-bitised RSA-täisarvud 8 tunni jooksul, kasutades 20 miljonit mürarikast kubitti. Quantum, 5 (433): 433, 15. aprill 2021. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[21] Craig Gidney ja Austin G Fowler. Pinnakoodide arvutuste paindlik paigutus, kasutades AutoCCZ olekuid. 21. mai 2019. URL http:///arxiv.org/abs/1905.08916.
arXiv: 1905.08916

[22] András Gilyén ja Alexander Poremba. Täiustatud kvantalgoritmid täpsuse hindamiseks. 29. märts 2022. URL http:///arxiv.org/abs/2203.15993.
arXiv: 2203.15993

[23] Daniel Gottesman ja Isaac L Chuang. Kvantteleportatsioon on universaalne arvutuslik primitiiv. 2. august 1999. URL https:///doi.org/10.1038/46503.
https:///doi.org/10.1038/46503

[24] Leo Grady ja Ali Kemal Sinop. Kiire ligikaudne juhusliku kõndija segmenteerimine, kasutades omavektori eelarvutust. 2008. aastal IEEE arvutinägemise ja mustrite tuvastamise konverents, lk 1–8. IEEE, juuni 2008. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https:///doi.org/10.1109/cvpr.2008.4587487

[25] Lov K Grover. Kiire kvantmehaaniline algoritm andmebaasi otsimiseks. Kahekümne kaheksanda iga-aastase ACM-i andmetöötlusteooria sümpoosioni toimetistes – STOC '96, STOC '96, lk 212–219, New York, New York, USA, 1996. ACM Press. ISBN 9780897917858. 10.1145/237814.237866.
https:///doi.org/10.1145/237814.237866

[26] Aram W Harrow, Avinatan Hassidim ja Seth Lloyd. Lineaarsete võrrandisüsteemide kvantalgoritm. Phys. Rev. Lett., 103 (15): 150502, 9. oktoober 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 ja Jarrod R McClean. Kvantieelis katsetest õppimisel. Science, 376 (6598): 1182–1186, 10. juuni 2022. ISSN 0036-8075,1095, 9203-10.1126. 7293/science.abnXNUMX.
https:///doi.org/10.1126/science.abn7293

[28] Cody Jones. Destilleerimisprotokollid Fourier olekute jaoks kvantarvutuses. 12. märts 2013. URL http:///arxiv.org/abs/1303.3066.
arXiv: 1303.3066

[29] John Kallaugher. Kvantieelis loomuliku voogesituse probleemi jaoks. 2021. aastal IEEE 62. iga-aastane arvutiteaduse aluste sümpoosion (FOCS), lk 897–908. IEEE, veebruar 2022. 10.1109/focs52979.2021.00091.
https:///doi.org/10.1109/focs52979.2021.00091

[30] Richard M Karp ja Richard J Lipton. Mõned seosed ebaühtlaste ja ühtsete keerukusklasside vahel. Kaheteistkümnenda aastaarvutusteooria ACM-i sümpoosioni toimetistes – STOC '80, STOC '80, lk 302–309, New York, New York, USA, 28. aprill 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 ja Theodore J Yoder. Hamiltoni simulatsioon valimi optimaalse keerukusega. Npj Quantum Inf., 3 (1): 1–7, 30. märts 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. Kvant- ja klassikalise võrguruumi keerukuse eksponentsiaalne eraldamine. Kaheksateistkümnenda iga-aastase ACM-i sümpoosioni toimingutes algoritmide ja arhitektuuride paralleelsusest, SPAA '06, lk 67–73, New York, NY, USA, 30. juuli 2006. ACM. ISBN 9781595934529. 10.1145/1148109.1148119.
https:///doi.org/10.1145/1148109.1148119

[33] Lin Lin ja Yu Tong. Optimaalne polünoomipõhine kvantomaseisundi filtreerimine, mida saab kasutada kvantlineaarsete süsteemide lahendamisel. 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. Maagiline destilleerimine: mitte nii kulukas, kui arvate. Quantum, 3 (205): 205, 2. detsember 2019a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[35] Daniel Litinski. Pinnakoodide mäng: laiaulatuslik kvantarvutus võreoperatsiooniga. Quantum, 3 (128): 128, 5. märts 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 ja Patrick Rebentrost. Kvantpõhikomponendi analüüs. Nat. Phys., 10 (9): 631–633, 27. september 2014. ISSN 1745-2473,1745, 2481-10.1038. 3029/nphysXNUMX.
https:///doi.org/10.1038/nphys3029

[37] John M. Martyn, Zane M Rossi, Andrew K Tan ja Isaac L Chuang. Suur kvantalgoritmide ühendamine. PRX quantum, 2 (4): 040203, 3. detsember 2021. ISSN 2691-3399. 10.1103/prxquantum.2.040203.
https:///doi.org/10.1103/prxquantum.2.040203

[38] Iman Marvian ja Seth Lloyd. Universaalne kvantemulaator. 8. juuni 2016. URL http:///arxiv.org/abs/1606.02734.
arXiv: 1606.02734

[39] F Motzoi, parlamendiliige Kaicher ja FK Wilhelm. Kvant-mitmekehaliste operaatorite lineaarsed ja logaritmilised ajakompositsioonid. Phys. Rev. Lett., 119 (16): 160503, 20. oktoober 2017. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.119.160503.
https:///doi.org/10.1103/PhysRevLett.119.160503

[40] Michael A Nielsen. Optiline kvantarvutus klastri olekute abil. Phys. Rev. Lett., 93 (4): 040503, 23. juuli 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 ja K Birgitta Whaley. Üldised vahetusvõrgud lähiajalise kvantarvutuse jaoks. 13. mai 2019. URL http:///arxiv.org/abs/1905.05118.
arXiv: 1905.05118

[42] Paul Pham ja Krysta M Svore. 2D lähima naabri kvantarhitektuur polülogaritmilise sügavuse arvestamiseks. 27. juuli 2012. URL http:///arxiv.org/abs/1207.6655.
arXiv: 1207.6655

[43] R Raussendorf ja HJ Briegel. Ühesuunaline kvantarvuti. Phys. Rev. Lett., 86 (22): 5188–5191, 28. mai 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 ja Ryan Babbush. Veataluvusega kvantheuristika koostamine kombinatoorseks optimeerimiseks. 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 ja Michael J Bremner. Ajaliselt struktureerimata kvantarvutus. Proc. matemaatika. Phys. Eng. Sci., 465 (2105): 1413–1439, 8. mai 2009. ISSN 1364-5021,1471, 2946-10.1098. 2008.0443/rspa.XNUMX.
https:///doi.org/10.1098/rspa.2008.0443

[46] Peter-Pike Sloan, Jan Kautz ja John Snyder. Eelarvutatud kiirguse ülekanne reaalajas renderdamiseks dünaamilistes madala sagedusega valgustuskeskkondades. Arvutigraafika ja interaktiivsete tehnikate 29. aastakonverentsi toimetistes SIGGRAPH '02, lk 527–536, New York, NY, USA, 1. juuli 2002. ACM. ISBN 9781581135213. 10.1145/566570.566612.
https:///doi.org/10.1145/566570.566612

[47] James E Smith. Haru ennustusstrateegiate uuring. 25 aasta jooksul rahvusvahelisel arvutiarhitektuuri sümpoosionil (valitud paberid), ISCA '98, lk 202–215, New York, NY, USA, 1. august 1998. ACM. ISBN 9781581130584. 10.1145/285930.285980.
https:///doi.org/10.1145/285930.285980

[48] Rolando D Somma ja Yiğit Subaşı. Kvantseisundi kontrollimise keerukus kvantlineaarsete süsteemide probleemis. PRX quantum, 2 (1): 010315, 27. jaanuar 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https:///doi.org/10.1103/prxquantum.2.010315

[49] Barbara M Terhal. Kvantmälude kvantveaparandus. Rev. Mod. Phys., 87 (2): 307–346, 7. aprill 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 ja Isaac L Chuang. Kvantloogika värava ehitamise metoodika. Phys. Rev. A, 62 (5), 18. oktoober 2000. ISSN 1050-2947,1094-1622. 10.1103/physreva.62.052316.
https:///doi.org/10.1103/physreva.62.052316

Viidatud

[1] Dar Gilboa ja Jarrod R. McClean, „Eksponentsiaalne kvantkommunikatsiooni eelis hajutatud õppes”, arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost ja Mikel Sanz, „Kvantilähedane kloonimise abil tihedusmaatriksi eksponentsiatsioon”, arXiv: 2311.11751, (2023).

Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2024-02-22 13:13:08). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.

Ei saanud tuua Ristviide viidatud andmete alusel viimase katse ajal 2024-02-22 13:13:06: 10.22331/q-2024-02-22-1264 viidatud andmeid ei saanud Crossrefist tuua. See on normaalne, kui DOI registreeriti hiljuti.

See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.

SEO-põhise sisu ja PR-levi. Võimenduge juba täna.
PlatoData.Network Vertikaalne generatiivne Ai. Jõustage ennast. Juurdepääs siia.
PlatoAiStream. Web3 luure. Täiustatud teadmised. Juurdepääs siia.
PlatoESG. Süsinik, CleanTech, Energia, Keskkond päikeseenergia, Jäätmekäitluse. Juurdepääs siia.
PlatoTervis. Biotehnoloogia ja kliiniliste uuringute luureandmed. Juurdepääs siia.
Allikas: https://quantum-journal.org/papers/q-2024-02-22-1264/

Ajatempel: Veebruar 22, 2024

Ajatempel: Juuni 1, 2023

Kvantalgoritmide kiirendamine eelarvutusega

Taasavaldanud Platon

Abstraktne

► BibTeX-i andmed

► Viited

Viidatud

Veel alates Quantum Journal

Perceval: Tarkvaraplatvorm diskreetse muutuva fotoonilise kvantarvutuse jaoks

Universaalsed kvantahelad kvantkeemia jaoks

Efektiivne versus Floqueti teooria Kerri parameetrilise ostsillaatori jaoks

Ruumi ja aja kvantkanalite ahelad

Energiasäästu ja fluktuatsiooniteoreem ei ühildu kvanttööga

Ostsillaatorite optimaalne kodeerimine rohkemateks ostsillaatoriteks

Tundmatute kvantmõõtmiste diskrimineerimine ja sertifitseerimine

Tähtsuse valim stohhastiliste kvantsimulatsioonide jaoks

Kvantsõnumi edastamise algoritm optimaalseks ja tõhusaks dekodeerimiseks

Skaleeritav ja paindlik klassikaline varitomograafia tensorvõrkudega

Meist

Vertikaalne otsing ja Ai

Platvorm

Püsi ühenduses

konto