Akselererende kvantealgoritmer med forhåndsberegning

Publisert av Platon

Følgere: 0

Akselererer kvantealgoritmer med Precomputation PlatoBlockchain Data Intelligence. Vertikalt søk. Ai.

William J. Huggins og Jarrod R. McClean

Google Quantum AI, Venezia, CA, USA

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Real-world-applikasjoner for databehandling kan være ekstremt tidssensitive. Det ville vært verdifullt om vi kunne fremskynde slike oppgaver ved å utføre noe av arbeidet på forhånd. Motivert av dette foreslår vi en kostnadsmodell for kvantealgoritmer som tillater kvanteforberegning; dvs. for en polynom mengde "gratis" beregning før inndata til en algoritme er fullstendig spesifisert, og metoder for å dra nytte av det. Vi analyserer to familier av unitarer som er asymptotisk mer effektive å implementere i denne kostnadsmodellen enn i standardmodellen. Det første eksemplet på kvanteforberegning, basert på tetthetsmatriseeksponentiering, kan tilby en eksponentiell fordel under visse forhold. Det andre eksemplet bruker en variant av portteleportering for å oppnå en kvadratisk fordel sammenlignet med å implementere enhetsenhetene direkte. Disse eksemplene antyder at kvanteforberegning kan tilby en ny arena for å søke kvantefordeler.

► BibTeX-data

@article{Huggins2024acceleratingquantum, doi = {10.22331/q-2024-02-22-1264}, url = {https://doi.org/10.22331/q-2024-02-22-1264}, tittel = {Accelerating Q}uantum {A}lgoritmer med {P}omregning}, forfatter = {Huggins, William J. og McClean, Jarrod R.}, journal = {{Quantum}}, issn = {2521-327X}, utgiver = {{ Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volum = {8}, sider = {1264}, måned = feb, år = {2024} }

► Referanser

[1] S Aaronson. Begrensninger for kvanterådgivning og enveiskommunikasjon. I Proceedings. 19th IEEE Annual Conference on Computational Complexity, 2004, side 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/ccc.2004.1313854.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

[2] Scott Aaronson og Andris Ambainis. For slektskap. I Proceedings of the førti-sjuende årlige ACM symposium on Theory of Computing, STOC '15, side 307–316, New York, NY, USA, 14. juni 2015. ACM. ISBN 9781450335362. 10.1145/2746539.2746547.
https: / / doi.org/ 10.1145 / 2746539.2746547

[3] Scott Aaronson og Guy N Rothblum. Skånsom måling av kvantetilstander og forskjellig personvern. 18. april 2019. URL http:///arxiv.org/abs/1904.08747.
arxiv: 1904.08747

[4] Ryan Babbush, Jarrod R McClean, Michael Newman, Craig Gidney, Sergio Boixo og Hartmut Neven. Fokuser utover kvadratiske speedups for feilkorrigert kvantefordel. PRX quantum, 2 (1): 010103, 29. mars 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Daniel J Bernstein og Tanja Lange. Uensartede sprekker i betongen: Kraften til fri forhåndsberegning. In Advances in Cryptology – ASIACRYPT 2013, Forelesningsnotater i informatikk, side 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 og Ryan Babbush. Qubitisering av vilkårlig basis kvantekjemi som utnytter sparsitet og lav rangfaktorisering. 6. februar 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 og Seth Lloyd. Kvantemaskinlæring. Nature, 549 (7671): 195–202, september 2017. ISSN 0028-0836,1476-4687. 10.1038/nature23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Sergey Bravyi og Alexei Kitaev. Universell kvanteberegning med ideelle clifford-porter og støyende ancillas. Phys. Rev. A, 71 (2): 022316, 22. februar 2005. ISSN 1050-2947,1094-1622. 10.1103/physreva.71.022316.
https: / / doi.org/ 10.1103 / physreva.71.022316

[9] Sergey Bravyi og Dmitri Maslov. Hadamard-frie kretsløp avslører strukturen til clifford-gruppen. IEEE Trans. Inf. Theory, 67 (7): 4546–4563, juli 2021. ISSN 0018-9448,1557-9654. 10.1109/tit.2021.3081415.
https: / / doi.org/ 10.1109 / tit.2021.3081415

[10] Earl T Campbell og Joe O'Gorman. En effektiv magisk tilnærming til små vinkelrotasjoner. 14. mars 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 og Jerry Li. Eksponentielle separasjoner mellom læring med og uten kvanteminne. I 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, februar 2022. 10.1109/focs52979.2021.00063.
https:///doi.org/10.1109/focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari og Rolando D Somma. Kvantealgoritme for systemer med lineære ligninger med eksponentielt forbedret avhengighet av presisjon. SIAM J. Comput., 46 (6): 1920–1950, 1. januar 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 og Yoshihisa Yamamoto. Raskere kvantekjemi simulering på feiltolerante kvantedatamaskiner. 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 og Dominic W Berry. Løser for optimal skalering av kvante-lineære systemer via diskret adiabatisk teorem. PRX quantum, 3 (4): 040303, 7. oktober 2022. ISSN 2691-3399. 10.1103/prxquantum.3.040303.
https: / / doi.org/ 10.1103 / prxquantum.3.040303

[15] Jordan Cotler, Hsin-Yuan Huang og Jarrod R McClean. Revisit avkvantisering og kvantefordel i læringsoppgaver. 1. desember 2021. URL http:///arxiv.org/abs/2112.00811.
arxiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman og Anirudh Krishna. Diagonale porter i clifford-hierarkiet. Phys. Rev. A, 95 (1), 26. januar 2017. ISSN 2469-9926,2469-9934. 10.1103/physreva.95.012329.
https: / / doi.org/ 10.1103 / physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone og Sam Gutmann. En omtrentlig kvanteoptimaliseringsalgoritme. 14. november 2014. URL http:///arxiv.org/abs/1411.4028.
arxiv: 1411.4028

[18] Austin G Fowler. Tidsoptimal kvanteberegning. 17. oktober 2012. URL http:///arxiv.org/abs/1210.4626.
arxiv: 1210.4626

[19] Sevag Gharibian og François Le Gall. Avkvantisering av kvantesingularverditransformasjonen: hardhet og anvendelser til kvantekjemi og kvante-PCP-formodningen. I Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, side 19–32, New York, NY, USA, 9. juni 2022. ACM. ISBN 9781450392648. 10.1145/3519935.3519991.
https: / / doi.org/ 10.1145 / 3519935.3519991

[20] Craig Gidney og Martin Ekerå. Hvordan faktorisere 2048-biters RSA-heltall på 8 timer ved å bruke 20 millioner støyende qubits. Quantum, 5 (433): 433, 15. april 2021. ISSN 2521-327X. 10.22331/q-2021-04-15-433.
https://doi.org/10.22331/q-2021-04-15-433

[21] Craig Gidney og Austin G Fowler. Fleksibel layout av overflatekodeberegninger ved hjelp av AutoCCZ-tilstander. 21. mai 2019. URL http:///arxiv.org/abs/1905.08916.
arxiv: 1905.08916

[22] András Gilyén og Alexander Poremba. Forbedrede kvantealgoritmer for troskapsestimering. 29. mars 2022. URL http:///arxiv.org/abs/2203.15993.
arxiv: 2203.15993

[23] Daniel Gottesman og Isaac L Chuang. Kvanteteleportering er en universell beregningsprimitiv. 2. august 1999. URL https:///doi.org/10.1038/46503.
https: / / doi.org/ 10.1038 / 46503

[24] Leo Grady og Ali Kemal Sinop. Rask tilnærmet tilfeldig walker-segmentering ved bruk av egenvektorforberegning. I 2008 IEEE Conference on Computer Vision and Pattern Recognition, side 1–8. IEEE, juni 2008. ISBN 9781424422425. 10.1109/cvpr.2008.4587487.
https:///doi.org/10.1109/cvpr.2008.4587487

[25] Kjærlighet K Grover. En rask kvantemekanisk algoritme for databasesøk. I Proceedings of the twenty-eightth annual ACM symposium on Theory of computing – STOC '96, STOC '96, side 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 og Seth Lloyd. Kvantealgoritme for lineære ligningssystemer. Phys. Rev. Lett., 103 (15): 150502, 9. oktober 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 og Jarrod R McClean. Kvantefordel ved å lære av eksperimenter. Science, 376 (6598): 1182–1186, 10. juni 2022. ISSN 0036-8075,1095-9203. 10.1126/science.abn7293.
https:///doi.org/10.1126/science.abn7293

[28] Cody Jones. Destillasjonsprotokoller for fouriertilstander i kvanteberegning. 12. mars 2013. URL http:///arxiv.org/abs/1303.3066.
arxiv: 1303.3066

[29] John Kallaugher. En kvantefordel for et naturlig strømmeproblem. I 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), side 897–908. IEEE, februar 2022. 10.1109/focs52979.2021.00091.
https:///doi.org/10.1109/focs52979.2021.00091

[30] Richard M Karp og Richard J Lipton. Noen sammenhenger mellom uensartede og ensartede kompleksitetsklasser. I Proceedings of the tolfth annual ACM symposium on Theory of computing – STOC '80, STOC '80, side 302–309, New York, New York, USA, 28. april 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 og Theodore J Yoder. Hamiltonsimulering med optimal prøvekompleksitet. Npj Quantum Inf., 3 (1): 1–7, 30. mars 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. Eksponentiell separasjon av kvante- og klassisk nettromkompleksitet. I Proceedings of the attenth annual ACM symposium on Parallelism in algorithms and architectures, SPAA '06, side 67–73, New York, NY, USA, 30. juli 2006. ACM. ISBN 9781595934529. 10.1145/1148109.1148119.
https: / / doi.org/ 10.1145 / 1148109.1148119

[33] Lin Lin og Yu Tong. Optimal polynombasert kvanteegentilstandsfiltrering med applikasjon for å løse kvantelineære systemer. 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. Magisk tilstandsdestillasjon: Ikke så kostbart som du tror. Quantum, 3 (205): 205, 2. desember 2019a. ISSN 2521-327X. 10.22331/q-2019-12-02-205.
https://doi.org/10.22331/q-2019-12-02-205

[35] Daniel Litinski. Et spill med overflatekoder: Storskala kvantedatabehandling med gitterkirurgi. Quantum, 3 (128): 128, 5. mars 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 og Patrick Rebentrost. Kvanteprinsippkomponentanalyse. Nat. Phys., 10 (9): 631–633, 27. september 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 og Isaac L Chuang. Storslått forening av kvantealgoritmer. PRX quantum, 2 (4): 040203, 3. desember 2021. ISSN 2691-3399. 10.1103/prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Iman Marvian og Seth Lloyd. Universell kvanteemulator. 8. juni 2016. URL http:///arxiv.org/abs/1606.02734.
arxiv: 1606.02734

[39] F Motzoi, MP Kaicher og FK Wilhelm. Lineære og logaritmiske tidssammensetninger av kvantemangekroppsoperatorer. Phys. Rev. Lett., 119 (16): 160503, 20. oktober 2017. ISSN 0031-9007,1079-7114. 10.1103/PhysRevLett.119.160503.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

[40] Michael A Nielsen. Optisk kvanteberegning ved bruk av klyngetilstander. Phys. Rev. Lett., 93 (4): 040503, 23. juli 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 og K Birgitta Whaley. Generaliserte byttenettverk for kortsiktig kvanteberegning. 13. mai 2019. URL http:///arxiv.org/abs/1905.05118.
arxiv: 1905.05118

[42] Paul Pham og Krysta M Svore. En 2D-kvantearkitektur for nærmeste nabo for faktorisering av polylogaritmisk dybde. 27. juli 2012. URL http:///arxiv.org/abs/1207.6655.
arxiv: 1207.6655

[43] R Raussendorf og HJ Briegel. En enveis kvantedatamaskin. 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 og Ryan Babbush. Sammenstilling av feiltolerante kvanteheuristikk for kombinatorisk optimalisering. 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 og Michael J Bremner. Tidsmessig ustrukturert kvanteberegning. Proc. Matte. Phys. Eng. 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 og John Snyder. Forhåndsberegnet utstrålingsoverføring for sanntidsgjengivelse i dynamiske, lavfrekvente lysmiljøer. I Proceedings of the 29th annual conference on Computer graphics and interactive techniques, SIGGRAPH '02, side 527–536, New York, NY, USA, 1. juli 2002. ACM. ISBN 9781581135213. 10.1145/566570.566612.
https: / / doi.org/ 10.1145 / 566570.566612

[47] James E Smith. En studie av grenprediksjonsstrategier. I 25 år av den internasjonale symposia om datamaskinarkitektur (utvalgte artikler), ISCA '98, side 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 og Yiğit Subaşı. Kompleksiteten til kvantetilstandsverifisering i problemet med kvantelineære system. PRX quantum, 2 (1): 010315, 27. januar 2021. ISSN 2691-3399. 10.1103/prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Barbara M Terhal. Kvantefeilkorreksjon for kvanteminner. Rev. Mod. Phys., 87 (2): 307–346, 7. april 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 og Isaac L Chuang. Metodikk for kvantelogikk-portkonstruksjon. Phys. Rev. A, 62 (5), 18. oktober 2000. ISSN 1050-2947,1094-1622. 10.1103/physreva.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Sitert av

[1] Dar Gilboa og 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 og Mikel Sanz, "Quantum approximated cloning-assisted density matrix exponentiation", arxiv: 2311.11751, (2023).

Sitatene ovenfor er fra SAO / NASA ADS (sist oppdatert vellykket 2024-02-22 13:13:08). Listen kan være ufullstendig fordi ikke alle utgivere gir passende og fullstendige sitasjonsdata.

Kunne ikke hente Crossref sitert av data under siste forsøk 2024-02-22 13:13:06: Kunne ikke hente siterte data for 10.22331 / q-2024-02-22-1264 fra Crossref. Dette er normalt hvis DOI nylig ble registrert.

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

SEO-drevet innhold og PR-distribusjon. Bli forsterket i dag.
PlatoData.Network Vertical Generative Ai. Styrk deg selv. Tilgang her.
PlatoAiStream. Web3 Intelligence. Kunnskap forsterket. Tilgang her.
PlatoESG. Karbon, CleanTech, Energi, Miljø, Solenergi, Avfallshåndtering. Tilgang her.
PlatoHelse. Bioteknologisk og klinisk etterretning. Tilgang her.
kilde: https://quantum-journal.org/papers/q-2024-02-22-1264/

Tidstempel: Februar 22, 2024

Tidstempel: Juni 1, 2023

Akselererer kvantealgoritmer med forhåndsberegning

Publisert av Platon

Abstrakt

► BibTeX-data

► Referanser

Sitert av

Mer fra Kvantejournal

Perceval: En programvareplattform for diskret variabel fotonisk kvanteberegning

Universelle kvantekretser for kvantekjemi

Effektiv versus Floquet-teori for Kerr parametriske oscillatoren

Kretser av rom og tid kvantekanaler

Energisparing og fluktuasjonsteorem er uforenlige for kvantearbeid

Optimal koding av oscillatorer til flere oscillatorer

Diskriminering og sertifisering av ukjente kvantemålinger

Viktighetsprøvetaking for stokastiske kvantesimuleringer

Kvantemeldingsoverføringsalgoritme for optimal og effektiv dekoding

Skalerbar og fleksibel klassisk skyggetomografi med tensornettverk

Om Oss

Vertikal søk og Ai

Plattform

Hold kontakten

Logg inn