Accelerera kvantalgoritmer med förberäkning

Accelerera kvantalgoritmer med förberäkning

Accelerera kvantalgoritmer med Precomputation PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

William J. Huggins och Jarrod R. McClean

Google Quantum AI, Venedig, CA, USA

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Verkliga tillämpningar av datorer kan vara extremt tidskänsliga. Det skulle vara värdefullt om vi kunde påskynda sådana uppgifter genom att utföra en del av arbetet i förväg. Motiverade av detta föreslår vi en kostnadsmodell för kvantalgoritmer som tillåter kvantförberäkning; dvs för en polynommängd av "fri" beräkning innan indata till en algoritm är helt specificerad, och metoder för att dra nytta av den. Vi analyserar två familjer av unitarer som är asymptotiskt mer effektiva att implementera i denna kostnadsmodell än i standardmodellen. Det första exemplet på kvantförberäkning, baserat på densitetsmatrisexponentiering, skulle kunna erbjuda en exponentiell fördel under vissa förhållanden. Det andra exemplet använder en variant av gate-teleportering för att uppnå en kvadratisk fördel jämfört med att implementera unitarerna direkt. Dessa exempel antyder att kvantförberäkning kan erbjuda en ny arena där man kan söka kvantfördelar.

► BibTeX-data

► Referenser

[1] S Aaronson. Begränsningar av kvantrådgivning och envägskommunikation. I Proceedings. 19:e IEEE Annual Conference on Computational Complexity, 2004, sidorna 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/​ccc.2004.1313854.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

[2] Scott Aaronson och Andris Ambainis. För släktskap. I Proceedings of the fyrtiosjunde årliga ACM symposium on Theory of Computing, STOC '15, sid 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 och Guy N Rothblum. Skonsam mätning av kvanttillstånd och differentiell integritet. 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 och Hartmut Neven. Fokusera bortom kvadratiska hastigheter för felkorrigerad kvantfördel. 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 och Tanja Lange. Ojämna sprickor i betongen: Kraften i fri förberäkning. In Advances in Cryptology – ASIACRYPT 2013, Föreläsningsanteckningar i datavetenskap, sidorna 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 och Ryan Babbush. Qubitisering av godtycklig kvantkemi som utnyttjar sparsitet och låg rangfaktorisering. 6 februari 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 och Seth Lloyd. Kvantmaskininlärning. Nature, 549 (7671): 195–202, september 2017. ISSN 0028-0836,1476-4687. 10.1038/​nature23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Sergey Bravyi och Alexei Kitaev. Universell kvantberäkning med idealiska clifford-grindar och bullriga anslutningar. Phys. Rev. A, 71 (2): 022316, 22 februari 2005. ISSN 1050-2947,1094-1622. 10.1103/​physreva.71.022316.
https: / ⠀ </ ⠀ <doi.org/†<10.1103 / ⠀ <physreva.71.022316

[9] Sergey Bravyi och Dmitri Maslov. Hadamard-fria kretsar exponerar strukturen hos cliffordgruppen. 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 och Joe O'Gorman. Ett effektivt magiskt tillstånd för små vinkelrotationer. 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 och Jerry Li. Exponentiella separationer mellan inlärning med och utan kvantminne. 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE, februari 2022. 10.1109/​focs52979.2021.00063.
https://​/​doi.org/​10.1109/​focs52979.2021.00063

[12] Andrew M Childs, Robin Kothari och Rolando D Somma. Kvantalgoritm för system av linjära ekvationer med exponentiellt förbättrat beroende av precision. SIAM J. Comput., 46 (6): 1920–1950, 1 januari 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 och Yoshihisa Yamamoto. Snabbare kvantkemi simulering på feltoleranta kvantdatorer. 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 och Dominic W Berry. Optimal skalning av kvantlinjärsystemslösare 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 och Jarrod R McClean. Återbesök avkvantisering och kvantfördelar i inlärningsuppgifter. 1 december 2021. URL http://​/​arxiv.org/​abs/​2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman och Anirudh Krishna. Diagonala grindar i cliffordhierarkin. Phys. Rev. A, 95 (1), 26 januari 2017. ISSN 2469-9926,2469-9934. 10.1103/​physreva.95.012329.
https: / ⠀ </ ⠀ <doi.org/†<10.1103 / ⠀ <physreva.95.012329

[17] Edward Farhi, Jeffrey Goldstone och Sam Gutmann. En ungefärlig kvantoptimeringsalgoritm. 14 november 2014. URL http://​/​arxiv.org/​abs/​1411.4028.
arXiv: 1411.4028

[18] Austin G Fowler. Tidsoptimal kvantberäkning. 17 oktober 2012. URL http://​/​arxiv.org/​abs/​1210.4626.
arXiv: 1210.4626

[19] Sevag Gharibian och François Le Gall. Avkvantisering av kvantsingularvärdetransformationen: hårdhet och tillämpningar för kvantkemi och kvant-PCP-förmodan. I Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, sidorna 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 och Martin Ekerå. Hur man faktorisera 2048 bitars RSA-heltal på 8 timmar med 20 miljoner brusiga 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 och Austin G Fowler. Flexibel layout av ytkodsberäkningar med AutoCCZ-tillstånd. 21 maj 2019. URL http://​/​arxiv.org/​abs/​1905.08916.
arXiv: 1905.08916

[22] András Gilyén och Alexander Poremba. Förbättrade kvantalgoritmer för trohetsuppskattning. 29 mars 2022. URL http://​/​arxiv.org/​abs/​2203.15993.
arXiv: 2203.15993

[23] Daniel Gottesman och Isaac L Chuang. Kvantteleportation är en universell beräkningsprimitiv. 2 augusti 1999. URL https://​/​doi.org/​10.1038/​46503.
https: / / doi.org/ 10.1038 / 46503

[24] Leo Grady och Ali Kemal Sinop. Snabb approximativ slumpmässig walker-segmentering med egenvektorförberäkning. 2008 IEEE-konferens om datorseende och mönsterigenkänning, sidorna 1–8. IEEE, juni 2008. ISBN 9781424422425. 10.1109/​cvpr.2008.4587487.
https: / / doi.org/ 10.1109 / cvpr.2008.4587487

[25] Lov K Grover. En snabb kvantmekanisk algoritm för databassökning. I Proceedings av det tjugoåttonde årliga ACM-symposiet om Theory of computing – STOC '96, STOC '96, sidorna 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 och Seth Lloyd. Kvantalgoritm för linjära ekvationssystem. 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 och Jarrod R McClean. Kvantfördelar med att lära av experiment. 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. Destillationsprotokoll för fouriertillstånd i kvantberäkning. 12 mars 2013. URL http://​/​arxiv.org/​abs/​1303.3066.
arXiv: 1303.3066

[29] John Kallaugher. En kvantfördel för ett naturligt streamingproblem. År 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), sidorna 897–908. IEEE, februari 2022. 10.1109/​focs52979.2021.00091.
https://​/​doi.org/​10.1109/​focs52979.2021.00091

[30] Richard M Karp och Richard J Lipton. Vissa samband mellan olikformiga och enhetliga komplexitetsklasser. I Proceedings of the tolfth annual ACM symposium on Theory of computing – STOC '80, STOC '80, sid 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 och Theodore J Yoder. Hamiltonsimulering med optimal provkomplexitet. 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. Exponentiell separation av kvant och klassisk onlinerymds komplexitet. I Proceedings of the artonde årliga ACM-symposium om Parallelism in algorithms and architectures, SPAA '06, sid 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 och Yu Tong. Optimal polynombaserad kvantegentillståndsfiltrering med tillämpning för att lösa kvantlinjära system. 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 tillståndsdestillation: Inte så kostsamt som du tror. Quantum, 3 (205): 205, 2 december 2019a. ISSN 2521-327X. 10.22331/​q-2019-12-02-205.
https:/​/​doi.org/​10.22331/​q-2019-12-02-205

[35] Daniel Litinski. Ett spel med ytkoder: Storskalig kvantberäkning med gallerkirurgi. 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 och Patrick Rebentrost. Analys av kvantprincipalkomponenter. 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 och Isaac L Chuang. Stor förening av kvantalgoritmer. 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 och Seth Lloyd. Universell kvantemulator. 8 juni 2016. URL http://​/​arxiv.org/​abs/​1606.02734.
arXiv: 1606.02734

[39] F Motzoi, MP Kaicher och FK Wilhelm. Linjära och logaritmiska tidssammansättningar av kvantmångkroppsoperatorer. 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 kvantberäkning med hjälp av klustertillstånd. 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 och K Birgitta Whaley. Generaliserade swapnätverk för kvantberäkning på kort sikt. 13 maj 2019. URL http://​/​arxiv.org/​abs/​1905.05118.
arXiv: 1905.05118

[42] Paul Pham och Krysta M Svore. En 2D-kvantarkitektur för närmaste granne för faktorisering av polylogaritmiskt djup. 27 juli 2012. URL http://​/​arxiv.org/​abs/​1207.6655.
arXiv: 1207.6655

[43] R Raussendorf och HJ Briegel. En enkelriktad kvantdator. Phys. Rev Lett., 86 (22): 5188–5191, 28 maj 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 och Ryan Babbush. Sammanställning av feltoleranta kvantheuristik för kombinatorisk optimering. 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 och Michael J Bremner. Temporärt ostrukturerad kvantberäkning. Proc. Matematik. Phys. Eng. Sci., 465 (2105): 1413–1439, 8 maj 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 och John Snyder. Förberäknad radiansöverföring för realtidsrendering i dynamiska, lågfrekventa ljusmiljöer. I Proceedings of the 29th annual conference on Computer graphics and interactive techniques, SIGGRAPH '02, sid 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 grenprediktionsstrategier. Under 25 år av det internationella symposiet om datorarkitektur (utvalda artiklar), ISCA '98, sid 202–215, New York, NY, USA, 1 augusti 1998. ACM. ISBN 9781581130584. 10.1145/​285930.285980.
https: / / doi.org/ 10.1145 / 285930.285980

[48] Rolando D Somma och Yiğit Subaşı. Komplexiteten av kvanttillståndsverifiering i problemet med kvantlinjära system. PRX quantum, 2 (1): 010315, 27 januari 2021. ISSN 2691-3399. 10.1103/​prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Barbara M Terhal. Kvantfelskorrigering för kvantminnen. 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 och Isaac L Chuang. Metodik för konstruktion av kvantlogikgrind. 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

Citerad av

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

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2024-02-22 13:13:08). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

Det gick inte att hämta Crossref citerade data under senaste försöket 2024-02-22 13:13:06: Det gick inte att hämta citerade data för 10.22331 / q-2024-02-22-1264 från Crossref. Detta är normalt om DOI registrerades nyligen.

Tidsstämpel:

Mer från Quantum Journal