Kvanttialgoritmien kiihtyvyys esilaskennan avulla

Julkaissut Platon

seuraajia: 0

Kvanttialgoritmien kiihdytys PlatoBlockchain-tiedon esilaskennan avulla. Pystysuuntainen haku. Ai.

William J. Huggins ja Jarrod R. McClean

Google Quantum AI, Venetsia, CA, USA

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Reaalimaailman tietojenkäsittelysovellukset voivat olla erittäin aikaherkkiä. Olisi arvokasta, jos voisimme nopeuttaa tällaisia tehtäviä suorittamalla osan töistä etukäteen. Tämän motivoituneena ehdotamme kvanttialgoritmeille kustannusmallia, joka mahdollistaa kvanttiesilaskennan; eli polynomiselle määrälle "vapaata" laskentaa ennen kuin algoritmin syöte on täysin määritelty, ja menetelmät sen hyödyntämiseksi. Analysoimme kahta yksikköperhettä, jotka on asymptoottisesti tehokkaampi toteuttaa tässä kustannusmallissa kuin vakiomallissa. Ensimmäinen esimerkki kvanttiesilaskennasta, joka perustuu tiheysmatriisin eksponentioon, voisi tarjota eksponentiaalisen edun tietyissä olosuhteissa. Toisessa esimerkissä käytetään portin teleportaation varianttia neliöllisen edun saavuttamiseksi verrattuna unitaarien toteuttamiseen suoraan. Nämä esimerkit vihjaavat, että kvanttiesilaskenta voi tarjota uuden areenan kvanttietujen etsimiselle.

► BibTeX-tiedot

@artikkeli{Huggins2024kiihtyvä kvantti, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, otsikko {Acceler Q}kvantti {A}lgoritmit, joissa on {P}uudelleenlaskenta}, kirjoittaja = {Huggins, William J. ja McClean, Jarrod R.}, lehti = {{Kvantti}}, issn = {2521-327X}, kustantaja = {{ Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volyymi = {8}, sivut = {1264}, kuukausi = helmikuu, vuosi = {2024} }

► Viitteet

[1] S Aaronson. Kvanttineuvonnan ja yksisuuntaisen viestinnän rajoitukset. Proceedingsissa. 19th IEEE Annual Conference on Computational Complexity, 2004, sivut 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. Forrelaatio. Teoksessa Proceedings of the 15. vuotuinen ACM-symposium on Theory of Computing, STOC '307, sivut 316–14, New York, NY, USA, 2015. kesäkuuta 9781450335362. ACM. ISBN 10.1145. 2746539.2746547/XNUMX.
https: / / doi.org/ 10.1145 / +2746539.2746547

[3] Scott Aaronson ja Guy N Rothblum. Hellävarainen kvanttitilojen ja differentiaalisen yksityisyyden mittaus. 18. huhtikuuta 2019. URL-osoite http:///arxiv.org/abs/1904.08747.
arXiv: 1904.08747

[4] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo ja Hartmut Neven. Keskity neliöllisen nopeutuksen ulkopuolelle saadaksesi virhekorjatun kvanttiedun. PRX quantum, 2 (1): 010103, 29. maaliskuuta 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Daniel J Bernstein ja Tanja Lange. Epätasaiset halkeamat betonissa: Vapaan esilaskennan teho. Julkaisussa Advances in Cryptology – ASIACRYPT 2013, Tietojenkäsittelytieteen luentomuistiinpanot, sivut 321–340. Springer Berlin Heidelberg, Berliini, 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. Satunnaisen perustavan kvanttikemian qubitisointi hyödyntäen harvalukuisuutta ja matalaluokkaista tekijöitä. 6. helmikuuta 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. Kvanttikoneoppiminen. Nature, 549 (7671): 195–202, syyskuu 2017. ISSN 0028-0836,1476, 4687-10.1038. 23474/luontoXNUMX.
https: / / doi.org/ 10.1038 / nature23474

[8] Sergei Bravyi ja Aleksei Kitaev. Universaali kvanttilaskenta ihanteellisilla Clifford-porteilla ja meluisilla lisälaitteilla. Phys. Rev. A, 71 (2): 022316, 22. helmikuuta 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. Hadamard-vapaat piirit paljastavat clifford-ryhmän rakenteen. IEEE Trans. Inf. Theory, 67 (7): 4546–4563, heinäkuu 2021. ISSN 0018-9448,1557, 9654-10.1109. 2021.3081415/tit.XNUMX.
https: / / doi.org/ 10.1109 / tit.2021.3081415

[10] Earl T Campbell ja Joe O'Gorman. Tehokas maagisen tilan lähestymistapa pieniin kulmiin. 14. maaliskuuta 2016. URL-osoite 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. Eksponentiaaliset erot oppimisen välillä kvanttimuistilla ja ilman. Vuonna 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, helmikuu 2022. 10.1109/focs52979.2021.00063.
https:///doi.org/10.1109/focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari ja Rolando D Somma. Kvanttialgoritmi lineaarisille yhtälöjärjestelmille, joilla on eksponentiaalisesti parempi riippuvuus tarkkuudesta. SIAM J. Comput., 46 (6): 1920–1950, 1. tammikuuta 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. Nopeampi kvanttikemian simulointi vikasietoisissa kvanttitietokoneissa. New J. Phys., 14 (11): 115023, 27. marraskuuta 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. Optimaalinen skaalaus kvanttilineaaristen järjestelmien ratkaisija diskreetin adiabaattisen lauseen avulla. PRX quantum, 3 (4): 040303, 7. lokakuuta 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. Dekvantisoinnin ja kvanttiedun tarkasteleminen oppimistehtävissä. 1. joulukuuta 2021. URL-osoite http:///arxiv.org/abs/2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman ja Anirudh Krishna. Diagonaaliset portit Cliffordin hierarkiassa. Phys. Rev. A, 95 (1), 26. tammikuuta 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. Kvanttilikimääräinen optimointialgoritmi. 14. marraskuuta 2014. URL-osoite http:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

[18] Austin G Fowler. Aikaoptimaalinen kvanttilaskenta. 17. lokakuuta 2012. URL-osoite http:///arxiv.org/abs/1210.4626.
arXiv: 1210.4626

[19] Sevag Gharibian ja François Le Gall. Kvanttisingulaarisen arvon muunnoksen dekvantisointi: kovuus ja sovellukset kvanttikemiaan ja kvantti-PCP-oletuksiin. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, sivut 19–32, New York, NY, USA, 9. kesäkuuta 2022. ACM. ISBN 9781450392648. 10.1145/3519935.3519991.
https: / / doi.org/ 10.1145 / +3519935.3519991

[20] Craig Gidney ja Martin Ekerå. Kuinka kertoa 2048-bittiset RSA-kokonaisluvut 8 tunnissa käyttämällä 20 miljoonaa meluisaa kubittia. Quantum, 5 (433): 433, 15. huhtikuuta 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. Pintakoodilaskelmien joustava asettelu AutoCCZ-tilojen avulla. 21. toukokuuta 2019. URL-osoite http:///arxiv.org/abs/1905.08916.
arXiv: 1905.08916

[22] András Gilyén ja Alexander Poremba. Parannetut kvanttialgoritmit tarkkuuden estimointiin. 29. maaliskuuta 2022. URL-osoite http:///arxiv.org/abs/2203.15993.
arXiv: 2203.15993

[23] Daniel Gottesman ja Isaac L Chuang. Kvanttiteleportaatio on universaali laskennallinen primitiivi. 2. elokuuta 1999. URL https:///doi.org/10.1038/46503.
https: / / doi.org/ 10.1038 / +46503

[24] Leo Grady ja Ali Kemal Sinop. Nopea likimääräinen satunnaiskävelijöiden segmentointi ominaisvektorien esilaskentaa käyttämällä. Vuonna 2008 IEEE Conference on Computer Vision and Pattern Recognition, sivut 1–8. IEEE, kesäkuu 2008. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https: / / doi.org/ 10.1109 / cvpr.2008.4587487

[25] Rakastan K Groveria. Nopea kvanttimekaaninen algoritmi tietokantahakuun. Teoksessa Proceedings of the 96th century ACM symposium on Theory of Computing – STOC '96, STOC '212, sivut 219–1996, New York, New York, USA, 9780897917858. ACM Press. ISBN 10.1145. 237814.237866/XNUMX.
https: / / doi.org/ 10.1145 / +237814.237866

[26] Aram W Harrow, Avinatan Hassidim ja Seth Lloyd. Kvanttialgoritmi lineaarisille yhtälöjärjestelmille. Phys. Rev. Lett., 103 (15): 150502, 9. lokakuuta 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. Kvanttietu kokeista oppimisessa. Science, 376 (6598): 1182–1186, 10. kesäkuuta 2022. ISSN 0036-8075,1095, 9203-10.1126. 7293/science.abnXNUMX.
https:///doi.org/10.1126/science.abn7293

[28] Cody Jones. Tislausprotokollat Fourier-tiloihin kvanttilaskennassa. 12. maaliskuuta 2013. URL-osoite http:///arxiv.org/abs/1303.3066.
arXiv: 1303.3066

[29] John Kallaugher. Kvanttietu luonnollisessa suoratoisto-ongelmassa. Vuonna 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), sivut 897–908. IEEE, helmikuu 2022. 10.1109/focs52979.2021.00091.
https:///doi.org/10.1109/focs52979.2021.00091

[30] Richard M Karp ja Richard J Lipton. Joitakin yhteyksiä epätasaisten ja yhtenäisten kompleksisuusluokkien välillä. Teoksessa Proceedings of the 80th century ACM symposium on Theory of Computing – STOC '80, STOC '302, sivut 309–28, New York, New York, USA, 1980. huhtikuuta 9780897910170. ACM Press. ISBN 10.1145. 800141.804678/XNUMX.
https: / / doi.org/ 10.1145 / +800141.804678

[31] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols ja Theodore J Yoder. Hamiltonin simulaatio optimaalisella näytteen monimutkaisuudella. Npj Quantum Inf., 3 (1): 1–7, 30. maaliskuuta 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. Kvantti- ja klassisen online-avaruuden monimutkaisuuden eksponentiaalinen erottelu. Julkaisussa Proceedings of the XVIII vuosittainen ACM-symposium on Parallelism in Algorithms and Archites, SPAA '06, sivut 67–73, New York, NY, USA, 30. heinäkuuta 2006. ACM. ISBN 9781595934529. 10.1145/1148109.1148119.
https: / / doi.org/ 10.1145 / +1148109.1148119

[33] Lin Lin ja Yu Tong. Optimaalinen polynomipohjainen kvanttiominaistilasuodatus, jota voidaan soveltaa kvanttilineaaristen järjestelmien ratkaisemiseen. Quantum, 4 (361): 361, 11. marraskuuta 2020. ISSN 2521-327X. 10.22331/q-2020-11-11-361.
https://doi.org/10.22331/q-2020-11-11-361

[34] Daniel Litinski. Maaginen tislaus: Ei niin kallista kuin luulet. Quantum, 3 (205): 205, 2. joulukuuta 2019a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[35] Daniel Litinski. Pintakoodien peli: Laajamittainen kvanttilaskenta hilaleikkauksella. Quantum, 3 (128): 128, 5. maaliskuuta 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. Kvanttipääkomponenttianalyysi. Nat. Phys., 10 (9): 631–633, 27. syyskuuta 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. Kvanttialgoritmien suuri yhdistäminen. PRX quantum, 2 (4): 040203, 3. joulukuuta 2021. ISSN 2691-3399. 10.1103/prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Iman Marvian ja Seth Lloyd. Universaali kvanttiemulaattori. 8. kesäkuuta 2016. URL-osoite http:///arxiv.org/abs/1606.02734.
arXiv: 1606.02734

[39] F Motzoi, kansanedustaja Kaicher ja FK Wilhelm. Kvanttimonikappaleoperaattoreiden lineaariset ja logaritmiset aikakoostumukset. Phys. Rev. Lett., 119 (16): 160503, 20. lokakuuta 2017. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.119.160503.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

[40] Michael A Nielsen. Optinen kvanttilaskenta käyttäen klusterin tiloja. Phys. Rev. Lett., 93 (4): 040503, 23. heinäkuuta 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. Yleistetyt swap-verkot lähiajan kvanttilaskentaan. 13. toukokuuta 2019. URL-osoite http:///arxiv.org/abs/1905.05118.
arXiv: 1905.05118

[42] Paul Pham ja Krysta M Svore. 2D lähin naapurin kvanttiarkkitehtuuri polylogaritmisen syvyyden huomioon ottamiseksi. 27. heinäkuuta 2012. URL-osoite http:///arxiv.org/abs/1207.6655.
arXiv: 1207.6655

[43] R Raussendorf ja HJ Briegel. Yksisuuntainen kvanttitietokone. Phys. Rev. Lett., 86 (22): 5188–5191, 28. toukokuuta 2001. ISSN 0031-9007,1079, 7114-10.1103. 86.5188/PhysRevLett.XNUMX.
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. Vikasietoisten kvanttiheuristien kokoaminen kombinatorista optimointia varten. PRX quantum, 1 (2): 020312, 9. marraskuuta 2020. ISSN 2691-3399. 10.1103/prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

[45] Dan Shepherd ja Michael J Bremner. Ajallisesti strukturoimaton kvanttilaskenta. Proc. Matematiikka. Phys. Eng. Sci., 465 (2105): 1413–1439, 8. toukokuuta 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. Esilaskettu säteilyn siirto reaaliaikaiseen renderöintiin dynaamisissa, matalataajuisissa valaistusympäristöissä. Teoksessa Proceedings of the 29. vuotuinen tietokonegrafiikkaa ja interaktiivisia tekniikoita käsittelevä konferenssi, SIGGRAPH '02, sivut 527–536, New York, NY, USA, 1. heinäkuuta 2002. ACM. ISBN 9781581135213. 10.1145/566570.566612.
https: / / doi.org/ 10.1145 / +566570.566612

[47] James E Smith. Tutkimus haaran ennustestrategioista. 25 vuotta kansainvälisessä tietokonearkkitehtuuria käsittelevässä symposiumissa (valitut artikkelit), ISCA '98, sivut 202–215, New York, NY, USA, 1. elokuuta 1998. ACM. ISBN 9781581130584. 10.1145/285930.285980.
https: / / doi.org/ 10.1145 / +285930.285980

[48] Rolando D Somma ja Yiğit Subaşı. Kvanttitilan verifioinnin monimutkaisuus kvanttilineaaristen järjestelmien ongelmassa. PRX quantum, 2 (1): 010315, 27. tammikuuta 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Barbara M Terhal. Kvanttivirheen korjaus kvanttimuisteille. Rev. Mod. Phys., 87 (2): 307–346, 7. huhtikuuta 2015. ISSN 0034-6861,1539, 0756-10.1103. 87.307/revmodphys.XNUMX.
https: / / doi.org/ 10.1103 / revmodphys.87.307

[50] Xinlan Zhou, Debbie W Leung ja Isaac L Chuang. Metodologia kvanttilogiikkaportin rakentamiseen. Phys. Rev. A, 62 (5), 18. lokakuuta 2000. ISSN 1050-2947,1094-1622. 10.1103/physreva.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Viitattu

[1] Dar Gilboa ja Jarrod R. McClean, "Exponential Quantum Communication Advantage in Distributed Learning", arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost ja Mikel Sanz, "Quantum approksmoitu kloonausavusteinen tiheysmatriisin eksponentio", arXiv: 2311.11751, (2023).

Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2024-02-22 13:13:08). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.

Ei voitu noutaa Crossref siteeratut tiedot viimeisen yrityksen aikana 2024-02-22 13:13:06: Ei voitu noutaa viittauksia 10.22331 / q-2024-02-22-1264 mainittuihin tietoihin Crossrefiltä. Tämä on normaalia, jos DOI rekisteröitiin äskettäin.

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.

SEO-pohjainen sisällön ja PR-jakelu. Vahvista jo tänään.
PlatoData.Network Vertical Generatiivinen Ai. Vahvista itseäsi. Pääsy tästä.
PlatoAiStream. Web3 Intelligence. Tietoa laajennettu. Pääsy tästä.
PlatoESG. hiili, CleanTech, energia, ympäristö, Aurinko, Jätehuolto. Pääsy tästä.
PlatonHealth. Biotekniikan ja kliinisten kokeiden älykkyys. Pääsy tästä.
Lähde: https://quantum-journal.org/papers/q-2024-02-22-1264/

Aikaleima: Helmikuu 22, 2024

Aikaleima: Kesäkuu 1, 2023

Kiihdyttävä kvanttialgoritmi esilaskennan avulla

Julkaissut Platon

Abstrakti

► BibTeX-tiedot

► Viitteet

Viitattu

Lisää aiheesta Quantum Journal

Perceval: Software Platform for Discrete Variable Photonic Quantum Computing

Universaalit kvanttipiirit kvanttikemialle

Tehokas verrattuna Floquet-teoriaan Kerr-parametriselle oskillaattorille

Avaruuden ja ajan kvanttikanavat

Energiansäästö- ja fluktuaatiolauseet eivät ole yhteensopivia kvanttityössä

Optimaalinen oskillaattorien koodaus useammiksi oskillaattoriksi

Tuntemattomien kvantimittausten syrjintä ja sertifiointi

Tärkeysnäytteenotto stokastisille kvanttisimulaatioille

Kvanttiviestinvälitysalgoritmi optimaaliseen ja tehokkaaseen dekoodaukseen

Skaalautuva ja joustava klassinen varjotomografia Tensor Networksin avulla

Tietoa Meistä

Pystysuuntainen haku ja Ai

foorumi

Pysy yhteydessä

Tili