Accelerazione degli algoritmi quantistici con il precalcolo

Accelerazione degli algoritmi quantistici con il precalcolo

Accelerazione degli algoritmi quantistici con la data intelligence PlatoBlockchain precalcolata. Ricerca verticale. Ai.

William J. Huggins e Jarrod R. McClean

Google Quantum AI, Venezia, California, Stati Uniti

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

Le applicazioni informatiche nel mondo reale possono essere estremamente sensibili al tempo. Sarebbe utile se potessimo accelerare tali compiti eseguendo parte del lavoro in anticipo. Motivati ​​da ciò, proponiamo un modello di costo per algoritmi quantistici che consenta il precalcolo quantistico; cioè, per una quantità polinomiale di calcolo “gratuito” prima che l'input di un algoritmo sia completamente specificato e i metodi per trarne vantaggio. Analizziamo due famiglie di unitari che sono asintoticamente più efficienti da implementare in questo modello di costo rispetto a quello standard. Il primo esempio di precalcolo quantistico, basato sull’esponenziazione della matrice di densità, potrebbe offrire un vantaggio esponenziale in determinate condizioni. Il secondo esempio utilizza una variante del teletrasporto del cancello per ottenere un vantaggio quadratico rispetto all'implementazione diretta degli unitari. Questi esempi suggeriscono che il precalcolo quantistico può offrire una nuova arena in cui cercare un vantaggio quantistico.

► dati BibTeX

► Riferimenti

, S. Aaronson. Limitazioni della consulenza quantistica e della comunicazione unidirezionale. Negli Atti. 19a conferenza annuale dell'IEEE sulla complessità computazionale, 2004, pagine 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/​ccc.2004.1313854.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

, Scott Aaronson e Andris Ambainis. Forrelazione. In Atti del quarantasettesimo simposio annuale ACM sulla teoria dell'informatica, STOC '15, pagine 307–316, New York, NY, USA, 14 giugno 2015. ACM. ISBN 9781450335362/​10.1145.
https: / / doi.org/ 10.1145 / 2746539.2746547 mila

, Scott Aaronson e Guy N. Rothblum. Misura delicata degli stati quantistici e privacy differenziale. 18 aprile 2019. URL http://​/​arxiv.org/​abs/​1904.08747.
arXiv: 1904.08747

, Ryan Babbush, Jarrod R. McClean, Michael Newman, Craig Gidney, Sergio Boixo e Hartmut Neven. Concentrati oltre le accelerazioni quadratiche per un vantaggio quantistico con correzione degli errori. PRX quantum, 2 (1): 010103, 29 marzo 2021. ISSN 2691-3399. 10.1103/​prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

, Daniel J Bernstein e Tanja Lange. Fessure non uniformi nel calcestruzzo: il potere del precalcolo libero. In Advances in Cryptology – ASIACRYPT 2013, Dispense di informatica, pagine 321–340. Springer Berlin Heidelberg, Berlino, Heidelberg, 2013. ISBN 9783642420443,9783642420450. 10.1007/​978-3-642-42045-0_17.
https:/​/​doi.org/​10.1007/​978-3-642-42045-0_17

, Dominic W Berry, Craig Gidney, Mario Motta, Jarrod R McClean e Ryan Babbush. Qubitizzazione della chimica quantistica su base arbitraria sfruttando la scarsità e la fattorizzazione di basso rango. 6 febbraio 2019. URL https://​/​doi.org/​10.22331/​q-2019-12-02-208.
https:/​/​doi.org/​10.22331/​q-2019-12-02-208

, Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe e Seth Lloyd. Apprendimento automatico quantistico. Natura, 549 (7671): 195–202, settembre 2017. ISSN 0028-0836,1476-4687. 10.1038/​natura23474.
https: / / doi.org/ 10.1038 / nature23474

, Sergey Bravyi e Alexei Kitaev. Calcolo quantistico universale con porte Clifford ideali e ancillari rumorosi. Fis. Rev. A, 71 (2): 022316, 22 febbraio 2005. ISSN 1050-2947,1094-1622. 10.1103/​physreva.71.022316.
https: / / doi.org/ 10.1103 / physreva.71.022316

, Sergej Bravyi e Dmitri Maslov. I circuiti privi di Hadamard espongono la struttura del gruppo di Clifford. IEEE Trans. Inf. Teoria, 67 (7): 4546–4563, luglio 2021. ISSN 0018-9448,1557-9654. 10.1109/​tit.2021.3081415.
https: / / doi.org/ 10.1109 / tit.2021.3081415

, Earl T. Campbell e Joe O'Gorman. Un approccio efficiente allo stato magico per rotazioni di piccoli angoli. 14 marzo 2016. URL https://​/​doi.org/​10.1088/​2058-9565/​1/​1/​015007.
https:/​/​doi.org/​10.1088/​2058-9565/​1/​1/​015007

, Sitan Chen, Jordan Cotler, Hsin-Yuan Huang e Jerry Li. Separazioni esponenziali tra apprendimento con e senza memoria quantistica. Nel 2021 si terrà il 62° Simposio annuale dell'IEEE sui fondamenti dell'informatica (FOCS). IEEE, febbraio 2022. 10.1109/​focs52979.2021.00063.
https://​/​doi.org/​10.1109/​focs52979.2021.00063

, Andrew M. Childs, Robin Kothari e Rolando D. Somma. Algoritmo quantistico per sistemi di equazioni lineari con dipendenza dalla precisione esponenzialmente migliorata. SIAM J. Comput., 46 (6): 1920–1950, 1 gennaio 2017. ISSN 0097-5397. 10.1137/​16M1087072.
https: / / doi.org/ 10.1137 / 16M1087072

, N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik e Yoshihisa Yamamoto. Simulazione più rapida della chimica quantistica su computer quantistici tolleranti ai guasti. New J. Phys., 14 (11): 115023, 27 novembre 2012. ISSN 1367-2630. 10.1088/​1367-2630/​14/​11/​115023.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​11/​115023

, Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush e Dominic W Berry. Risolutore di sistemi lineari quantistici con scalabilità ottimale tramite teorema adiabatico discreto. PRX quantum, 3 (4): 040303, 7 ottobre 2022. ISSN 2691-3399. 10.1103/​prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

, Jordan Cotler, Hsin-Yuan Huang e Jarrod R. McClean. Rivisitare la dequantizzazione e il vantaggio quantistico nei compiti di apprendimento. 1 dicembre 2021. URL http://​/​arxiv.org/​abs/​2112.00811.
arXiv: 2112.00811

, Shawn X Cui, Daniel Gottesman e Anirudh Krishna. Porte diagonali nella gerarchia di Clifford. Fis. Rev. A, 95 (1), 26 gennaio 2017. ISSN 2469-9926,2469-9934. 10.1103/​physreva.95.012329.
https: / / doi.org/ 10.1103 / physreva.95.012329

, Edward Farhi, Jeffrey Goldstone e Sam Gutmann. Un algoritmo di ottimizzazione quantistica approssimata. 14 novembre 2014. URL http://​/​arxiv.org/​abs/​1411.4028.
arXiv: 1411.4028

, Austin G. Fowler. Calcolo quantistico ottimale in termini di tempo. 17 ottobre 2012. URL http://​/​arxiv.org/​abs/​1210.4626.
arXiv: 1210.4626

, Sevag Gharibian e François Le Gall. Dequantizzazione della trasformazione quantistica del valore singolare: durezza e applicazioni alla chimica quantistica e alla congettura del PCP quantistico. In Atti del 54° Simposio annuale ACM SIGACT sulla teoria dell'informatica, STOC 2022, pagine 19–32, New York, NY, USA, 9 giugno 2022. ACM. ISBN 9781450392648/​10.1145.
https: / / doi.org/ 10.1145 / 3519935.3519991 mila

, Craig Gidney e Martin Ekerå. Come fattorizzare interi RSA a 2048 bit in 8 ore utilizzando 20 milioni di qubit rumorosi. Quantum, 5 (433): 433, 15 aprile 2021. ISSN 2521-327X. 10.22331/​q-2021-04-15-433.
https:/​/​doi.org/​10.22331/​q-2021-04-15-433

, Craig Gidney e Austin G. Fowler. Layout flessibile dei calcoli del codice di superficie utilizzando gli stati AutoCCZ. 21 maggio 2019. URL http://​/​arxiv.org/​abs/​1905.08916.
arXiv: 1905.08916

, András Gilyén e Alexander Poremba. Algoritmi quantistici migliorati per la stima della fedeltà. 29 marzo 2022. URL http://​/​arxiv.org/​abs/​2203.15993.
arXiv: 2203.15993

, Daniel Gottesman e Isaac L. Chuang. Il teletrasporto quantistico è una primitiva computazionale universale. 2 agosto 1999. URL https://​/​doi.org/​10.1038/​46503.
https: / / doi.org/ 10.1038 / 46503 mila

, Leo Grady e Ali Kemal Sinop. Segmentazione rapida e approssimativa dei camminatori casuali utilizzando il precalcolo degli autovettori. Nel 2008 Conferenza IEEE sulla visione artificiale e il riconoscimento dei modelli, pagine 1–8. IEEE, giugno 2008. ISBN 9781424422425. 10.1109/​cvpr.2008.4587487.
https: / / doi.org/ 10.1109 / cvpr.2008.4587487

, Lov K Grover. Un algoritmo veloce di meccanica quantistica per la ricerca nei database. In Atti del ventottesimo simposio annuale ACM sulla teoria dell'informatica - STOC '96, STOC '96, pagine 212–219, New York, New York, USA, 1996. ACM Press. ISBN 9780897917858/​10.1145.
https: / / doi.org/ 10.1145 / 237814.237866 mila

, Aram W Harrow, Avinatan Hassidim e Seth Lloyd. Algoritmo quantistico per sistemi lineari di equazioni. Fis. Rev. Lett., 103 (15): 150502, 9 ottobre 2009. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.103.150502.
https: / / doi.org/ 10.1103 / PhysRevLett.103.150502

, Hsin-Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hartmut Neven, Ryan Babbush, Richard Kueng, John Preskill e Jarrod R McClean. Vantaggio quantistico nell’imparare dagli esperimenti. Science, 376 (6598): 1182–1186, 10 giugno 2022. ISSN 0036-8075,1095-9203. 10.1126/​science.abn7293.
https://​/​doi.org/​10.1126/​science.abn7293

, Cody Jones. Protocolli di distillazione per stati di Fourier nell'informatica quantistica. 12 marzo 2013. URL http://​/​arxiv.org/​abs/​1303.3066.
arXiv: 1303.3066

, John Kallaugher. Un vantaggio quantistico per un problema di streaming naturale. Nel 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pagine 897–908. IEEE, febbraio 2022. 10.1109/​focs52979.2021.00091.
https://​/​doi.org/​10.1109/​focs52979.2021.00091

, Richard M Karp e Richard J Lipton. Alcune connessioni tra classi di complessità non uniforme e uniforme. In Atti del dodicesimo simposio annuale ACM sulla teoria dell'informatica - STOC '80, STOC '80, pagine 302–309, New York, New York, USA, 28 aprile 1980. ACM Press. ISBN 9780897910170/​10.1145.
https: / / doi.org/ 10.1145 / 800141.804678 mila

, Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols e Theodore J Yoder. Simulazione hamiltoniana con complessità campionaria ottimale. Npj Quantum Inf., 3 (1): 1–7, 30 marzo 2017. ISSN 2056-6387,2056-6387. 10.1038/​s41534-017-0013-7.
https:/​/​doi.org/​10.1038/​s41534-017-0013-7

, François Le Gall. Separazione esponenziale della complessità dello spazio online quantistico e classico. In Atti del diciottesimo simposio annuale ACM sul parallelismo negli algoritmi e nelle architetture, SPAA '06, pagine 67–73, New York, NY, USA, 30 luglio 2006. ACM. ISBN 9781595934529/​10.1145.
https: / / doi.org/ 10.1145 / 1148109.1148119 mila

, Lin Lin e Yu Tong. Filtraggio ottimale degli autostati quantistici basato su polinomi con applicazione alla risoluzione di sistemi lineari quantistici. Quantum, 4 (361): 361, 11 novembre 2020. ISSN 2521-327X. 10.22331/​q-2020-11-11-361.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361

, Daniele Litinski. Distillazione allo stato magico: non così costosa come pensi. Quantum, 3 (205): 205, 2 dicembre 2019a. ISSN 2521-327X. 10.22331/​q-2019-12-02-205.
https:/​/​doi.org/​10.22331/​q-2019-12-02-205

, Daniele Litinski. Un gioco di codici di superficie: calcolo quantistico su larga scala con chirurgia del reticolo. Quantum, 3 (128): 128, 5 marzo 2019b. ISSN 2521-327X. 10.22331/​q-2019-03-05-128.
https:/​/​doi.org/​10.22331/​q-2019-03-05-128

, Seth Lloyd, Masoud Mohseni e Patrick Rebentrost. Analisi delle componenti principali quantistiche. Naz. Phys., 10 (9): 631–633, 27 settembre 2014. ISSN 1745-2473,1745-2481. 10.1038/​nphys3029.
https: / / doi.org/ 10.1038 / nphys3029

, John M Martyn, Zane M Rossi, Andrew K Tan e Isaac L Chuang. Grande unificazione degli algoritmi quantistici. PRX quantum, 2 (4): 040203, 3 dicembre 2021. ISSN 2691-3399. 10.1103/​prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

, Iman Marvian e Seth Lloyd. Emulatore quantistico universale. 8 giugno 2016. URL http://​/​arxiv.org/​abs/​1606.02734.
arXiv: 1606.02734

, F Motzoi, MP Kaicher e FK Wilhelm. Composizioni temporali lineari e logaritmiche di operatori quantistici a molti corpi. Fis. Rev. Lett., 119 (16): 160503, 20 ottobre 2017. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.119.160503.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

, Michael A Nielsen. Calcolo quantistico ottico utilizzando stati di cluster. Fis. Rev. Lett., 93 (4): 040503, 23 luglio 2004. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.93.040503.
https: / / doi.org/ 10.1103 / PhysRevLett.93.040503

, Bryan O'Gorman, William J Huggins, Eleanor G Rieffel e K Birgitta Whaley. Reti di scambio generalizzate per l'informatica quantistica a breve termine. 13 maggio 2019. URL http://​/​arxiv.org/​abs/​1905.05118.
arXiv: 1905.05118

, Paul Pham e Krysta M Svore. Un'architettura quantistica 2D del vicino più vicino per la fattorizzazione della profondità polilogaritmica. 27 luglio 2012. URL http://​/​arxiv.org/​abs/​1207.6655.
arXiv: 1207.6655

, R Raussendorf e HJ Briegel. Un computer quantistico unidirezionale. Fis. Rev. Lett., 86 (22): 5188–5191, 28 maggio 2001. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.86.5188.
https: / / doi.org/ 10.1103 / PhysRevLett.86.5188

, Yuval R Sanders, Dominic W Berry, Pedro CS Costa, Louis W Tessler, Nathan Wiebe, Craig Gidney, Hartmut Neven e Ryan Babbush. Compilazione di euristiche quantistiche tolleranti agli errori per l'ottimizzazione combinatoria. PRX quantum, 1 (2): 020312, 9 novembre 2020. ISSN 2691-3399. 10.1103/​prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

, Dan Shepherd e Michael J Bremner. Calcolo quantistico temporalmente non strutturato. Proc. Matematica. Fis. L'Ing. Sci., 465 (2105): 1413–1439, 8 maggio 2009. ISSN 1364-5021,1471-2946. 10.1098/​rspa.2008.0443.
https: / / doi.org/ 10.1098 / rspa.2008.0443

, Peter-Pike Sloan, Jan Kautz e John Snyder. Trasferimento della radianza precalcolato per il rendering in tempo reale in ambienti di illuminazione dinamici e a bassa frequenza. In Atti della 29a conferenza annuale sulla computer grafica e le tecniche interattive, SIGGRAPH '02, pagine 527–536, New York, NY, USA, 1 luglio 2002. ACM. ISBN 9781581135213/​10.1145.
https: / / doi.org/ 10.1145 / 566570.566612 mila

, James E Smith. Uno studio sulle strategie di previsione dei rami. In 25 anni di simposi internazionali sull'architettura del computer (documenti selezionati), ISCA '98, pagine 202–215, New York, NY, USA, 1 agosto 1998. ACM. ISBN 9781581130584/​10.1145.
https: / / doi.org/ 10.1145 / 285930.285980 mila

, Rolando D Somma e Yiğit Subaşı. Complessità della verifica dello stato quantistico nel problema dei sistemi lineari quantistici. PRX quantum, 2 (1): 010315, 27 gennaio 2021. ISSN 2691-3399. 10.1103/​prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

, Barbara M. Terhal. Correzione degli errori quantistici per memorie quantistiche. Rev. Mod. Phys., 87 (2): 307–346, 7 aprile 2015. ISSN 0034-6861,1539-0756. 10.1103/​revmodphys.87.307.
https: / / doi.org/ 10.1103 / revmodphys.87.307

, Xinlan Zhou, Debbie W Leung e Isaac L Chuang. Metodologia per la costruzione di porte logiche quantistiche. Fis. Rev. A, 62 (5), 18 ottobre 2000. ISSN 1050-2947,1094-1622. 10.1103/​physreva.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Citato da

[1] Dar Gilboa e Jarrod R. McClean, "Vantaggio esponenziale della comunicazione quantistica nell'apprendimento distribuito", arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost e Mikel Sanz, "Esponenziazione della matrice di densità assistita da clonazione approssimata quantistica", arXiv: 2311.11751, (2023).

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2024-02-22 13:13:08). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

Impossibile recuperare Crossref citato da dati durante l'ultimo tentativo 2024-02-22 13:13:06: Impossibile recuperare i dati citati per 10.22331 / q-2024-02-22-1264 da Crossref. Questo è normale se il DOI è stato registrato di recente.

Timestamp:

Di più da Diario quantistico