Kvantumalgoritmusok gyorsítása előszámítással

Újra kiadta Platón

Követő: 0

Kvantumalgoritmusok gyorsítása előre kiszámított PlatoBlockchain adatintelligenciával. Függőleges keresés. Ai.

William J. Huggins és Jarrod R. McClean

Google Quantum AI, Velence, CA, USA

Érdekesnek találja ezt a cikket, vagy szeretne megvitatni? Scite vagy hagyjon megjegyzést a SciRate-en.

Absztrakt

A számítástechnika valós alkalmazásai rendkívül időérzékenyek lehetnek. Értékes lenne, ha az ilyen feladatokat felgyorsítanánk, ha a munka egy részét idő előtt elvégeznénk. Ezen motiválva olyan költségmodellt javasolunk a kvantumalgoritmusokhoz, amelyek lehetővé teszik a kvantum-előszámítást; azaz egy polinomiális mennyiségű „szabad” számításhoz, mielőtt az algoritmus bemenete teljesen meghatározásra kerül, és módszerek annak kihasználására. Két unitárius családot elemezünk, amelyek aszimptotikusan hatékonyabban valósíthatók meg ebben a költségmodellben, mint a standard modellben. A kvantum-előszámítás első példája, amely a sűrűségmátrix hatványozásán alapul, bizonyos feltételek mellett exponenciális előnyt kínálhat. A második példa a kaputeleportáció egy változatát használja, hogy négyzetes előnyt érjen el az unitáriusok közvetlen megvalósításához képest. Ezek a példák arra utalnak, hogy a kvantum-előszámítás új színteret kínálhat a kvantumelőny megszerzésére.

► BibTeX adatok

@cikk{Huggins2024acceleratingquantum, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, cím = {Accelerating Q}uantum {A}lgoritmusok {P}újraszámítással}, szerző = {Huggins, William J. és McClean, Jarrod R.}, folyóirat = {{Quantum}}, issn = {2521-327X}, kiadó = {{ Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, kötet = {8}, oldalak = {1264}, hónap = február, év = {2024} }

► Referenciák

[1] S Aaronson. A kvantumtanácsadás és az egyirányú kommunikáció korlátai. In Proceedings. 19. IEEE Annual Conference on Computational Complexity, 2004, 320–332. oldal. IEEE, 2004. ISBN 9780769521206. 10.1109/ccc.2004.1313854.
https:///doi.org/10.1109/ccc.2004.1313854

[2] Scott Aaronson és Andris Ambainis. Forrelation. In Proceedings of the negyvenhetedik éves ACM szimpózium a számítástudomány elméletéről, STOC '15, 307–316. oldal, New York, NY, USA, 14. június 2015. ACM. ISBN 9781450335362. 10.1145/2746539.2746547.
https:///doi.org/10.1145/2746539.2746547

[3] Scott Aaronson és Guy N Rothblum. A kvantumállapotok és a differenciális adatvédelem finom mérése. 18. április 2019. URL http:///arxiv.org/abs/1904.08747.
arXiv: 1904.08747

[4] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo és Hartmut Neven. Összpontosítson a négyzetes gyorsításokon túl a hibajavított kvantumelőny érdekében. PRX quantum, 2 (1): 010103, 29. március 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https:///doi.org/10.1103/prxquantum.2.010103

[5] Daniel J Bernstein és Tanja Lange. Nem egyenletes repedések a betonban: A szabad előszámítás ereje. In Advances in Cryptology – ASIACRYPT 2013, Lecture notes in Computer Science, 321–340. oldal. 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 és Ryan Babbush. Tetszőleges bázisú kvantumkémia qubitizálása, kihasználva a ritkaságot és az alacsony rangú faktorizációt. 6. február 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 és Seth Lloyd. Kvantumgépi tanulás. Nature, 549 (7671): 195–202, 2017. szeptember. ISSN 0028-0836,1476-4687. 10.1038/természet23474.
https:///doi.org/10.1038/nature23474

[8] Szergej Bravyi és Alekszej Kitaev. Univerzális kvantumszámítás ideális Clifford-kapukkal és zajos segédelemekkel. Phys. Rev. A, 71 (2): 022316, 22. február 2005. ISSN 1050-2947,1094-1622. 10.1103/physreva.71.022316.
https:///doi.org/10.1103/physreva.71.022316

[9] Szergej Bravyi és Dmitrij Maszlov. A Hadamard-mentes áramkörök feltárják a clifford-csoport szerkezetét. IEEE Trans. Inf. Theory, 67 (7): 4546–4563, 2021. július. ISSN 0018-9448,1557-9654. 10.1109/tit.2021.3081415.
https:///doi.org/10.1109/tit.2021.3081415

[10] Earl T Campbell és Joe O'Gorman. Hatékony mágikus állapot megközelítés kis szögű elforgatásokhoz. 14. március 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 és Jerry Li. A kvantummemóriával és anélkül történő tanulás exponenciális szétválasztása. 2021-ben az IEEE 62. éves szimpóziuma a számítástechnika alapjairól (FOCS). IEEE, 2022. február. 10.1109/focs52979.2021.00063.
https:///doi.org/10.1109/focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari és Rolando D Somma. Kvantumalgoritmus lineáris egyenletrendszerekhez, exponenciálisan javított pontosságfüggőséggel. SIAM J. Comput., 46 (6): 1920–1950, 1. január 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 és Yoshihisa Yamamoto. Gyorsabb kvantumkémiai szimuláció hibatűrő kvantumszámítógépeken. 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 és Dominic W Berry. Optimális skálázási kvantumlineáris rendszerek megoldója diszkrét adiabatikus tételen keresztül. PRX quantum, 3 (4): 040303, 7. október 2022. ISSN 2691-3399. 10.1103/prxquantum.3.040303.
https:///doi.org/10.1103/prxquantum.3.040303

[15] Jordan Cotler, Hsin-Yuan Huang és Jarrod R McClean. A dekvantálás és a kvantumelőny újragondolása a tanulási feladatokban. 1. december 2021. URL http:///arxiv.org/abs/2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman és Anirudh Krishna. Átlós kapuk a cliffordi hierarchiában. Phys. Rev. A, 95 (1), 26. január 2017. ISSN 2469-9926,2469-9934. 10.1103/physreva.95.012329.
https:///doi.org/10.1103/physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone és Sam Gutmann. Egy kvantumközelítő optimalizálási algoritmus. 14. november 2014. URL http:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

[18] Austin G Fowler. Idő-optimális kvantumszámítás. 17. október 2012. URL http:///arxiv.org/abs/1210.4626.
arXiv: 1210.4626

[19] Sevag Gharibian és François Le Gall. A kvantum szinguláris érték transzformáció dekvantálása: keménység és alkalmazások a kvantumkémiában és a kvantum PCP sejtésben. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, 19–32. oldal, New York, NY, USA, 9. június 2022. ACM. ISBN 9781450392648. 10.1145/3519935.3519991.
https:///doi.org/10.1145/3519935.3519991

[20] Craig Gidney és Martin Ekerå. Hogyan lehet 2048 bites RSA egész számokat faktorálni 8 óra alatt 20 millió zajos qubit használatával. Quantum, 5 (433): 433, 15. április 2021. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[21] Craig Gidney és Austin G Fowler. A felületi kódszámítások rugalmas elrendezése az AutoCCZ állapotok használatával. 21. május 2019. URL http:///arxiv.org/abs/1905.08916.
arXiv: 1905.08916

[22] Gilyén András és Poremba Sándor. Továbbfejlesztett kvantum-algoritmusok a hűségbecsléshez. 29. március 2022. URL http:///arxiv.org/abs/2203.15993.
arXiv: 2203.15993

[23] Daniel Gottesman és Isaac L Chuang. A kvantumteleportáció egy univerzális számítási primitív. 2. augusztus 1999. URL https:///doi.org/10.1038/46503.
https:///doi.org/10.1038/46503

[24] Leo Grady és Ali Kemal Sinop. Gyors közelítő véletlen sétáló szegmentálás sajátvektor-előszámítással. 2008-ban IEEE konferencia a számítógépes látásról és mintafelismerésről, 1–8. oldal. IEEE, 2008. június. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https:///doi.org/10.1109/cvpr.2008.4587487

[25] Szeretem K Grover. Gyors kvantummechanikai algoritmus adatbázis-kereséshez. In Proceedings of the huszonnyolcadik éves ACM szimpózium a számítástudomány elméletéről – STOC '96, STOC '96, 212–219. oldal, 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 és Seth Lloyd. Kvantumalgoritmus lineáris egyenletrendszerekhez. Phys. Rev. Lett., 103 (15): 150502, 9. október 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 és Jarrod R McClean. Kvantumelőny a kísérletekből való tanulásban. Science, 376 (6598): 1182–1186, 10. június 2022. ISSN 0036-8075,1095, 9203-10.1126. 7293/science.abnXNUMX.
https:///doi.org/10.1126/science.abn7293

[28] Cody Jones. Desztillációs protokollok Fourier-állapotokhoz a kvantumszámításban. 12. március 2013. URL http:///arxiv.org/abs/1303.3066.
arXiv: 1303.3066

[29] John Kallaugher. Kvantumelőny természetes streamelési probléma esetén. 2021-ben az IEEE 62. éves szimpóziuma a számítástechnika alapjairól (FOCS), 897–908. oldal. IEEE, 2022. február. 10.1109/focs52979.2021.00091.
https:///doi.org/10.1109/focs52979.2021.00091

[30] Richard M Karp és Richard J Lipton. Néhány kapcsolat a nem egyforma és az egységes komplexitási osztályok között. In Proceedings of the tizenkettedik éves ACM szimpózium a számítástudomány elméletéről – STOC '80, STOC '80, 302–309. oldal, New York, New York, USA, 28. április 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 és Theodore J Yoder. Hamilton szimuláció optimális mintakomplexitással. Npj Quantum Inf., 3 (1): 1–7, 30. március 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. A kvantum és a klasszikus online tér összetettségének exponenciális szétválasztása. In Proceedings of the XVIII éves ACM szimpózium az algoritmusok és architektúrák párhuzamosságáról, SPAA '06, 67–73. oldal, New York, NY, USA, 30. július 2006. ACM. ISBN 9781595934529. 10.1145/1148109.1148119.
https:///doi.org/10.1145/1148109.1148119

[33] Lin Lin és Yu Tong. Optimális polinom alapú kvantum-sajátállapot-szűrés kvantumlineáris rendszerek megoldására. 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. Mágikus állapotú lepárlás: Nem olyan költséges, mint gondolná. Quantum, 3 (205): 205, 2. december 2019.a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[35] Daniel Litinski. Felületi kódok játéka: Nagyszabású kvantumszámítás rácsműtéttel. Quantum, 3 (128): 128, 5. március 2019. b. 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 és Patrick Rebentrost. Kvantum főkomponens elemzés. Nat. Phys., 10 (9): 631–633, 27. szeptember 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 és Isaac L Chuang. A kvantum algoritmusok nagy egyesítése. 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 és Seth Lloyd. Univerzális kvantum emulátor. 8. június 2016. URL http:///arxiv.org/abs/1606.02734.
arXiv: 1606.02734

[39] F Motzoi, Kaicher képviselő és FK Wilhelm. Kvantum soktestes operátorok lineáris és logaritmikus időösszetételei. Phys. Rev. Lett., 119 (16): 160503, 20. október 2017. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.119.160503.
https:///doi.org/10.1103/PhysRevLett.119.160503

[40] Michael A Nielsen. Optikai kvantumszámítás klaszterállapotok felhasználásával. Phys. Rev. Lett., 93 (4): 040503, 23. július 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 és K Birgitta Whaley. Általánosított swap hálózatok rövid távú kvantumszámításhoz. 13. május 2019. URL http:///arxiv.org/abs/1905.05118.
arXiv: 1905.05118

[42] Paul Pham és Krysta M Svore. Egy 2D legközelebbi szomszéd kvantumarchitektúra a polilogaritmikus mélység figyelembevételéhez. 27. július 2012. URL http:///arxiv.org/abs/1207.6655.
arXiv: 1207.6655

[43] R Raussendorf és HJ Briegel. Egyirányú kvantumszámítógép. Phys. Rev. Lett., 86 (22): 5188–5191, 28. május 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 és Ryan Babbush. Hibatűrő kvantumheurisztika összeállítása kombinatorikus optimalizáláshoz. 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 és Michael J Bremner. Időben strukturálatlan kvantumszámítás. Proc. Math. Phys. Eng. Sci., 465 (2105): 1413–1439, 8. május 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 és John Snyder. Előre kiszámított sugárzás átvitel a valós idejű megjelenítéshez dinamikus, alacsony frekvenciájú világítási környezetben. In Proceedings of the 29. éves konferencia a számítógépes grafikáról és az interaktív technikákról, SIGGRAPH '02, 527–536. oldal, New York, NY, USA, 1. július 2002. ACM. ISBN 9781581135213. 10.1145/566570.566612.
https:///doi.org/10.1145/566570.566612

[47] James E Smith. Tanulmány az ágazati előrejelzési stratégiákról. A számítógép-architektúráról szóló nemzetközi szimpózium 25 évében (válogatott cikkek), ISCA '98, 202–215. oldal, New York, NY, USA, 1. augusztus 1998. ACM. ISBN 9781581130584. 10.1145/285930.285980.
https:///doi.org/10.1145/285930.285980

[48] Rolando D Somma és Yiğit Subaşı. A kvantumállapot-ellenőrzés összetettsége a kvantumlineáris rendszerek problémájában. PRX quantum, 2 (1): 010315, 27. január 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https:///doi.org/10.1103/prxquantum.2.010315

[49] Barbara M Terhal. Kvantumhiba-javítás kvantum memóriákhoz. Rev. Mod. Phys., 87 (2): 307–346, 7. április 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 és Isaac L Chuang. Módszertan kvantumlogikai kapu szerkesztéséhez. Phys. Rev. A, 62 (5), 18. október 2000. ISSN 1050-2947,1094-1622. 10.1103/physreva.62.052316.
https:///doi.org/10.1103/physreva.62.052316

Idézi

[1] Dar Gilboa és Jarrod R. McClean, „Exponenciális kvantumkommunikációs előny az elosztott tanulásban”, arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost és Mikel Sanz, „Kvantum közelítő klónozással segített sűrűségmátrix hatványozása”, arXiv: 2311.11751, (2023).

A fenti idézetek innen származnak SAO/NASA HIRDETÉSEK (utolsó sikeres frissítés: 2024-02-22 13:13:08). Előfordulhat, hogy a lista hiányos, mivel nem minden kiadó ad megfelelő és teljes hivatkozási adatokat.

Nem sikerült lekérni Az adatok által hivatkozott kereszthivatkozás utolsó próbálkozáskor 2024-02-22 13:13:06: Nem sikerült lekérni a 10.22331/q-2024-02-22-1264 hivatkozás által hivatkozott adatokat a Crossref-től. Ez normális, ha a DOI-t nemrég regisztrálták.

Ez a tanulmány a Quantumban jelent meg Creative Commons Nevezd meg 4.0 International (CC BY 4.0) engedély. A szerzői jog az eredeti szerzői jog tulajdonosainál marad, például a szerzőknél vagy intézményeiknél.

SEO által támogatott tartalom és PR terjesztés. Erősödjön még ma.
PlatoData.Network Vertical Generative Ai. Erősítse meg magát. Hozzáférés itt.
PlatoAiStream. Web3 Intelligence. Felerősített tudás. Hozzáférés itt.
PlatoESG. Carbon, CleanTech, Energia, Környezet, Nap, Hulladékgazdálkodás. Hozzáférés itt.
PlatoHealth. Biotechnológiai és klinikai vizsgálatok intelligencia. Hozzáférés itt.
Forrás: https://quantum-journal.org/papers/q-2024-02-22-1264/

Időbélyeg: Február 22, 2024

Időbélyeg: 1. június 2023.

Kvantumalgoritmusok gyorsítása előszámítással

Újra kiadta Platón

Absztrakt

► BibTeX adatok

► Referenciák

Idézi

Még több Quantum Journal

Perceval: Szoftverplatform a diszkrét változó fotonikus kvantumszámításhoz

Univerzális kvantumáramkörök a kvantumkémiához

Hatékony versus Floquet elmélet a Kerr parametrikus oszcillátorhoz

Tér és idő kvantumcsatornáinak áramkörei

Az energiamegmaradás és a fluktuációs tétel nem kompatibilis a kvantummunkával

Az oszcillátorok optimális kódolása több oszcillátorba

Ismeretlen kvantummérések diszkriminációja és hitelesítése

Fontossági mintavétel sztochasztikus kvantumszimulációkhoz

Kvantum üzenettovábbítási algoritmus az optimális és hatékony dekódoláshoz

Skálázható és rugalmas klasszikus árnyéktomográfia Tensor hálózatokkal

Rólunk

Vertical Search & Ai

Emelvény

Maradjon kapcsolatban

Fiók