Accelerarea algoritmilor cuantici cu precalcul

Republicat de Platon

Urmaritori: 0

Accelerarea algoritmilor cuantici cu precalcul PlatoBlockchain Data Intelligence. Căutare verticală. Ai.

William J. Huggins și Jarrod R. McClean

Google Quantum AI, Veneția, CA, SUA

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Aplicațiile de calcul din lumea reală pot fi extrem de sensibile la timp. Ar fi valoros dacă am putea accelera astfel de sarcini realizând o parte din muncă din timp. Motivați de aceasta, propunem un model de cost pentru algoritmii cuantici care permite precalcularea cuantică; adică, pentru o cantitate polinomială de calcul „liber” înainte ca intrarea unui algoritm să fie complet specificată și metode pentru a profita de aceasta. Analizăm două familii de unitare care sunt asimptotic mai eficiente de implementat în acest model de cost decât în cel standard. Primul exemplu de precalcul cuantic, bazat pe exponențiarea matricei de densitate, ar putea oferi un avantaj exponențial în anumite condiții. Cel de-al doilea exemplu folosește o variantă de teleportare pe poartă pentru a obține un avantaj pătratic în comparație cu implementarea directă a unităților. Aceste exemple sugerează că precalcularea cuantică poate oferi o nouă arenă în care să caute avantaje cuantice.

► Date BibTeX

@article{Huggins2024acceleratingquantum, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, titlu = {Accelerare { Q}uantum {A}lgoritmi cu {P}recalculare}, autor = {Huggins, William J. și McClean, Jarrod R.}, jurnal = {{Quantum}}, issn = {2521-327X}, editor = {{ Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volum = {8}, pagini = {1264}, luna = februarie, an = {2024} }

► Referințe

[1] S Aaronson. Limitările consilierii cuantice și ale comunicării unidirecționale. În Proceedings. A 19-a conferință anuală IEEE privind complexitatea computațională, 2004, paginile 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/ccc.2004.1313854.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

[2] Scott Aaronson și Andris Ambainis. Pentru relație. În Proceedings of the fourty-15th annual ACM symposium on Theory of Computing, STOC '307, paginile 316–14, New York, NY, SUA, 2015 iunie 9781450335362. ACM. ISBN 10.1145. 2746539.2746547/XNUMX.
https: / / doi.org/ 10.1145 / 2746539.2746547

[3] Scott Aaronson și Guy N Rothblum. Măsurarea blândă a stărilor cuantice și a confidențialității diferențiale. 18 aprilie 2019. URL http:///arxiv.org/abs/1904.08747.
arXiv: 1904.08747

[4] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo și Hartmut Neven. Concentrați-vă dincolo de accelerarea pătratică pentru avantajul cuantic corectat de erori. PRX quantum, 2 (1): 010103, 29 martie 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Daniel J Bernstein și Tanja Lange. Fisuri neuniforme în beton: puterea de precalcul liber. În Advances in Cryptology – ASIACRYPT 2013, Note de curs în informatică, paginile 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 și Ryan Babbush. Qubitizarea chimiei cuantice bazate pe bază arbitrară, folosind dispersitatea și factorizarea de rang scăzut. 6 februarie 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 și Seth Lloyd. Învățare automată cuantică. Nature, 549 (7671): 195–202, septembrie 2017. ISSN 0028-0836,1476-4687. 10.1038/nature23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Serghei Bravyi și Alexei Kitaev. Calcul cuantic universal cu porți Clifford ideale și ancillari zgomotoase. Fiz. Rev. A, 71 (2): 022316, 22 februarie 2005. ISSN 1050-2947,1094-1622. 10.1103/physreva.71.022316.
https: / / doi.org/ 10.1103 / physreva.71.022316

[9] Serghei Bravyi și Dmitri Maslov. Circuitele fără Hadamard expun structura grupului Clifford. IEEE Trans. Inf. Theory, 67 (7): 4546–4563, iulie 2021. ISSN 0018-9448,1557-9654. 10.1109/tit.2021.3081415.
https: / / doi.org/ 10.1109 / tit.2021.3081415

[10] Earl T Campbell și Joe O'Gorman. O abordare eficientă a stării magice a rotațiilor cu unghi mici. 14 martie 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 și Jerry Li. Separări exponențiale între învățarea cu și fără memorie cuantică. În 2021, cel de-al 62-lea simpozion anual IEEE privind fundamentele informaticii (FOCS). IEEE, februarie 2022. 10.1109/focs52979.2021.00063.
https:///doi.org/10.1109/focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari și Rolando D Somma. Algoritm cuantic pentru sisteme de ecuații liniare cu dependență îmbunătățită exponențial de precizie. SIAM J. Comput., 46 (6): 1920–1950, 1 ianuarie 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 și Yoshihisa Yamamoto. Simulare mai rapidă a chimiei cuantice pe calculatoare cuantice tolerante la erori. New J. Phys., 14 (11): 115023, 27 noiembrie 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 și Dominic W Berry. Rezolvator de sisteme liniare cuantice cu scalare optimă prin teorema adiabatică discretă. PRX quantum, 3 (4): 040303, 7 octombrie 2022. ISSN 2691-3399. 10.1103/prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

[15] Jordan Cotler, Hsin-Yuan Huang și Jarrod R McClean. Revizuirea decuantizării și a avantajului cuantic în sarcinile de învățare. 1 decembrie 2021. URL http:///arxiv.org/abs/2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman și Anirudh Krishna. Porți diagonale în ierarhia Clifford. Fiz. Rev. A, 95 (1), 26 ianuarie 2017. ISSN 2469-9926,2469-9934. 10.1103/physreva.95.012329.
https: / / doi.org/ 10.1103 / physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone și Sam Gutmann. Un algoritm de optimizare cuantică aproximativă. 14 noiembrie 2014. URL http:///arxiv.org/abs/1411.4028.
arXiv: 1411.4028

[18] Austin G Fowler. Calcul cuantic optim în timp. 17 octombrie 2012. URL http:///arxiv.org/abs/1210.4626.
arXiv: 1210.4626

[19] Sevag Gharibian și François Le Gall. Decuantizarea transformării valorii singulare cuantice: duritate și aplicații la chimia cuantică și conjectura PCP cuantică. În Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, paginile 19–32, New York, NY, SUA, 9 iunie 2022. ACM. ISBN 9781450392648. 10.1145/3519935.3519991.
https: / / doi.org/ 10.1145 / 3519935.3519991

[20] Craig Gidney și Martin Ekerå. Cum să factorizezi numere întregi RSA de 2048 de biți în 8 ore folosind 20 de milioane de qubiți zgomotoși. Quantum, 5 (433): 433, 15 aprilie 2021. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[21] Craig Gidney și Austin G Fowler. Dispunerea flexibilă a calculelor codurilor de suprafață folosind stările AutoCCZ. 21 mai 2019. URL http:///arxiv.org/abs/1905.08916.
arXiv: 1905.08916

[22] András Gilyén și Alexander Poremba. Algoritmi cuantici îmbunătățiți pentru estimarea fidelității. 29 martie 2022. URL http:///arxiv.org/abs/2203.15993.
arXiv: 2203.15993

[23] Daniel Gottesman și Isaac L Chuang. Teleportarea cuantică este o primitivă computațională universală. 2 august 1999. URL https:///doi.org/10.1038/46503.
https: / / doi.org/ 10.1038 / 46503

[24] Leo Grady și Ali Kemal Sinop. Segmentare rapidă aproximativă aleatoare a mersului folosind precalcularea vectorului propriu. În 2008 IEEE Conference on Computer Vision and Pattern Recognition, paginile 1–8. IEEE, iunie 2008. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https: / / doi.org/ 10.1109 / cvpr.2008.4587487

[25] Iubitor K Grover. Un algoritm mecanic cuantic rapid pentru căutarea în baze de date. În Proceedings of the twoty-96th annual ACM symposium on Theory of computing – STOC '96, STOC '212, pages 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 și Seth Lloyd. Algoritm cuantic pentru sisteme liniare de ecuații. Fiz. Rev. Lett., 103 (15): 150502, 9 octombrie 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 și Jarrod R McClean. Avantaj cuantic în învățarea din experimente. Science, 376 (6598): 1182–1186, 10 iunie 2022. ISSN 0036-8075,1095-9203. 10.1126/science.abn7293.
https:///doi.org/10.1126/science.abn7293

[28] Cody Jones. Protocoale de distilare pentru stările Fourier în calculul cuantic. 12 martie 2013. URL http:///arxiv.org/abs/1303.3066.
arXiv: 1303.3066

[29] John Kallaugher. Un avantaj cuantic pentru o problemă naturală de streaming. În 2021, cel de-al 62-lea simpozion anual IEEE privind fundamentele informaticii (FOCS), paginile 897–908. IEEE, februarie 2022. 10.1109/focs52979.2021.00091.
https:///doi.org/10.1109/focs52979.2021.00091

[30] Richard M Karp și Richard J Lipton. Câteva conexiuni între clasele de complexitate neuniforme și uniforme. În Proceedings of the 80th annual ACM symposium on Theory of computing – STOC '80, STOC '302, pages 309–28, New York, New York, USA, 1980 April 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 și Theodore J Yoder. Simulare hamiltoniană cu complexitate optimă a eșantionului. Npj Quantum Inf., 3 (1): 1–7, 30 martie 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. Separarea exponențială a complexității spațiului online cuantic și clasic. În Proceedings of the 06th annual ACM symposium on Parallelism in algorithms and architectures, SPAA '67, paginile 73–30, New York, NY, SUA, 2006 iulie 9781595934529. ACM. ISBN 10.1145. 1148109.1148119/XNUMX.
https: / / doi.org/ 10.1145 / 1148109.1148119

[33] Lin Lin și Yu Tong. Filtrarea optimă a stărilor proprii cuantice bazată pe polinomii cu aplicație la rezolvarea sistemelor liniare cuantice. Quantum, 4 (361): 361, 11 noiembrie 2020. ISSN 2521-327X. 10.22331/q-2020-11-11-361.
https://doi.org/10.22331/q-2020-11-11-361

[34] Daniel Litinski. Distilarea în stare magică: nu atât de costisitoare pe cât crezi. Quantum, 3 (205): 205, 2 decembrie 2019a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[35] Daniel Litinski. Un joc de coduri de suprafață: calcul cuantic la scară largă cu chirurgie latice. Quantum, 3 (128): 128, 5 martie 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 și Patrick Rebentrost. Analiza componentelor principale cuantice. Nat. Phys., 10 (9): 631–633, 27 septembrie 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 și Isaac L Chuang. Marea unificare a algoritmilor cuantici. PRX quantum, 2 (4): 040203, 3 decembrie 2021. ISSN 2691-3399. 10.1103/prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Iman Marvian și Seth Lloyd. Emulator cuantic universal. 8 iunie 2016. URL http:///arxiv.org/abs/1606.02734.
arXiv: 1606.02734

[39] F Motzoi, MP Kaicher și FK Wilhelm. Compozițiile de timp liniare și logaritmice ale operatorilor cuantici cu mai multe corpuri. Fiz. Rev. Lett., 119 (16): 160503, 20 octombrie 2017. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.119.160503.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

[40] Michael A Nielsen. Calcul cuantic optic folosind stări cluster. Fiz. Rev. Lett., 93 (4): 040503, 23 iulie 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 și K Birgitta Whaley. Rețele de schimb generalizate pentru calculul cuantic pe termen scurt. 13 mai 2019. URL http:///arxiv.org/abs/1905.05118.
arXiv: 1905.05118

[42] Paul Pham și Krysta M Svore. O arhitectură cuantică 2D cu cel mai apropiat vecin pentru factorizarea profunzimii polilogaritmice. 27 iulie 2012. URL http:///arxiv.org/abs/1207.6655.
arXiv: 1207.6655

[43] R Raussendorf și HJ Briegel. Un computer cuantic cu sens unic. Fiz. 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 și Ryan Babbush. Compilare de euristici cuantice tolerante la erori pentru optimizarea combinatorie. PRX quantum, 1 (2): 020312, 9 noiembrie 2020. ISSN 2691-3399. 10.1103/prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

[45] Dan Shepherd și Michael J Bremner. Calcul cuantic nestructurat temporal. Proc. Matematică. Fiz. ing. Sci., 465 (2105): 1413–1439, 8 mai 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 și John Snyder. Transfer de radiație precalculat pentru redare în timp real în medii de iluminare dinamice, cu frecvență joasă. În Proceedings of the 29th annual Conference on Computer graphics and interactive techniques, SIGGRAPH '02, paginile 527–536, New York, NY, SUA, 1 iulie 2002. ACM. ISBN 9781581135213. 10.1145/566570.566612.
https: / / doi.org/ 10.1145 / 566570.566612

[47] James E Smith. Un studiu al strategiilor de predicție a ramurilor. În 25 de ani de simpozioane internaționale de arhitectură a calculatoarelor (lucrări selectate), ISCA '98, paginile 202–215, New York, NY, SUA, 1 august 1998. ACM. ISBN 9781581130584. 10.1145/285930.285980.
https: / / doi.org/ 10.1145 / 285930.285980

[48] Rolando D Somma şi Yiğit Subaşı. Complexitatea verificării stării cuantice în problema sistemelor liniare cuantice. PRX quantum, 2 (1): 010315, 27 ianuarie 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Barbara M Terhal. Corectarea erorilor cuantice pentru memoriile cuantice. Rev. Mod. Phys., 87 (2): 307–346, 7 aprilie 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 și Isaac L Chuang. Metodologie pentru construcția unei porți logice cuantice. Fiz. Rev. A, 62 (5), 18 octombrie 2000. ISSN 1050-2947,1094-1622. 10.1103/physreva.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Citat de

[1] Dar Gilboa și 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 și Mikel Sanz, „Quantum approximated cloning-assisted density matrix exponentiation”, arXiv: 2311.11751, (2023).

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2024-02-22 13:13:08). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

Nu a putut să aducă Date citate încrucișate în ultima încercare 2024-02-22 13:13:06: Nu s-au putut prelua date citate pentru 10.22331 / q-2024-02-22-1264 de la Crossref. Acest lucru este normal dacă DOI a fost înregistrat recent.

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Distribuție de conținut bazat pe SEO și PR. Amplifică-te astăzi.
PlatoData.Network Vertical Generative Ai. Împuterniciți-vă. Accesați Aici.
PlatoAiStream. Web3 Intelligence. Cunoștințe amplificate. Accesați Aici.
PlatoESG. carbon, CleanTech, Energie, Mediu inconjurator, Solar, Managementul deșeurilor. Accesați Aici.
PlatoHealth. Biotehnologie și Inteligență pentru studii clinice. Accesați Aici.
Sursa: https://quantum-journal.org/papers/q-2024-02-22-1264/

Timestamp-ul: 22 Februarie 2024

Timestamp-ul: Iunie 1, 2023

Accelerarea algoritmilor cuantici cu precalcul

Republicat de Platon

Abstract

► Date BibTeX

► Referințe

Citat de

Mai mult de la Jurnalul cuantic

Perceval: O platformă software pentru calculul cuantic fotonic cu variabile discrete

Circuite cuantice universale pentru chimia cuantică

Teoria eficientă versus Floquet pentru oscilatorul parametric Kerr

Circuite ale canalelor cuantice spațiale și temporale

Conservarea energiei și teorema fluctuației sunt incompatibile cu munca cuantică

Codificarea optimă a oscilatorilor în mai multe oscilatoare

Discriminarea și certificarea măsurătorilor cuantice necunoscute

Eșantionarea importanței pentru simulările cuantice stocastice

Algoritm cuantic de transmitere a mesajelor pentru o decodare optimă și eficientă

Tomografie clasică în umbră scalabilă și flexibilă cu rețele tensoare

Despre noi

Căutare verticală și Ai

Platformă

Rămâneți conectat

Cont