Przyspieszanie algorytmów kwantowych za pomocą obliczeń wstępnych

Przyspieszanie algorytmów kwantowych za pomocą obliczeń wstępnych

Przyspieszanie algorytmów kwantowych za pomocą obliczeń wstępnych PlatoBlockchain Data Intelligence. Wyszukiwanie pionowe. AI.

Williama J. Hugginsa i Jarroda R. McCleana

Google Quantum AI, Wenecja, Kalifornia, USA

Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.

Abstrakcyjny

Rzeczywiste zastosowania obliczeniowe mogą być niezwykle wrażliwe na czas. Byłoby cenne, gdybyśmy mogli przyspieszyć takie zadania, wykonując część prac wcześniej. Motywowani tym proponujemy model kosztów algorytmów kwantowych, który umożliwia wstępne obliczenia kwantowe; tj. dla wielomianowej ilości „swobodnych” obliczeń przed pełnym określeniem danych wejściowych algorytmu oraz metod ich wykorzystania. Analizujemy dwie rodziny unitarne, które są asymptotycznie bardziej efektywne do wdrożenia w tym modelu kosztów niż w modelu standardowym. Pierwszy przykład wstępnych obliczeń kwantowych, oparty na potęgowaniu macierzy gęstości, może w pewnych warunkach zapewnić wykładniczą przewagę. Drugi przykład wykorzystuje wariant teleportacji bramowej, aby osiągnąć przewagę kwadratową w porównaniu z bezpośrednim wdrożeniem unitarności. Przykłady te wskazują, że wstępne obliczenia kwantowe mogą zaoferować nową dziedzinę poszukiwania przewagi kwantowej.

► Dane BibTeX

► Referencje

[1] S. Aaronsona. Ograniczenia doradztwa kwantowego i komunikacji jednokierunkowej. W Postępowaniu. 19. doroczna konferencja IEEE na temat złożoności obliczeniowej, 2004, strony 320–332. IEEE, 2004. ISBN 9780769521206. 10.1109/​ccc.2004.1313854.
https: / / doi.org/ 10.1109 / ccc.2004.1313854

[2] Scotta Aaronsona i Andrisa Ambainisa. Forrelacja. W materiałach z czterdziestego siódmego dorocznego sympozjum ACM na temat teorii informatyki, STOC '15, strony 307–316, Nowy Jork, NY, USA, 14 czerwca 2015 r. ACM. ISBN 9781450335362. 10.1145/​2746539.2746547.
https: / / doi.org/ 10.1145 / 2746539.2746547

[3] Scotta Aaronsona i Guya N. Rothbluma. Delikatny pomiar stanów kwantowych i prywatności różnicowej. 18 kwietnia 2019 r. Adres 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. Skoncentruj się poza kwadratowymi przyspieszeniami, aby uzyskać przewagę kwantową skorygowaną o błędy. PRX quantum, 2 (1): 010103, 29 marca 2021 r. ISSN 2691-3399. 10.1103/​prxquantum.2.010103.
https: / / doi.org/ 10.1103 / prxquantum.2.010103

[5] Daniela J. Bernsteina i Tanji Lange. Nierównomierne pęknięcia w betonie: Moc swobodnych obliczeń wstępnych. W Advances in Cryptology – ASIACRYPT 2013, Notatki z wykładów z informatyki, strony 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. Qubityzacja dowolnej podstawy chemii kwantowej z wykorzystaniem rzadkości i faktoryzacji niskiego rzędu. 6 lutego 2019. Adres 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. Kwantowe uczenie maszynowe. Nature, 549 (7671): 195–202, wrzesień 2017. ISSN 0028-0836,1476-4687. 10.1038/​natura23474.
https: / / doi.org/ 10.1038 / nature23474

[8] Siergiej Bravyi i Aleksiej Kitajew. Uniwersalne obliczenia kwantowe z idealnymi bramkami klifowymi i hałaśliwymi ancillasami. Fiz. Rev. A, 71 (2): 022316, 22 lutego 2005. ISSN 1050-2947,1094-1622. 10.1103/​physreva.71.022316.
https: / / doi.org/ 10.1103 / physreva.71.022316

[9] Siergiej Bravyi i Dmitrij Masłow. Obwody wolne od Hadamarda odsłaniają strukturę grupy klifowej. IEEE Trans. Inf. Teoria, 67 (7): 4546–4563, lipiec 2021 r. 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. Efektywne podejście do stanu magicznego przy obrotach pod małymi kątami. 14 marca 2016. Adres 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. Wykładnicze separacje między uczeniem się z pamięcią kwantową i bez niej. W 2021 r. odbędzie się 62. doroczne sympozjum IEEE na temat podstaw informatyki (FOCS). IEEE, luty 2022. 10.1109/​focs52979.2021.00063.
https://​/​doi.org/​10.1109/​focs52979.2021.00063

[12] Andrew M. Childs, Robin Kothari i Rolando D. Somma. Algorytm kwantowy dla układów równań liniowych z wykładniczo poprawioną zależnością od precyzji. SIAM J. Comput., 46 (6): 1920–1950, 1 stycznia 2017 r. 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. Szybsza symulacja chemii kwantowej na odpornych na uszkodzenia komputerach kwantowych. New J. Phys., 14 (11): 115023, 27 listopada 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. Rozwiązanie optymalnego skalowania kwantowych układów liniowych za pomocą dyskretnego twierdzenia adiabatycznego. PRX quantum, 3 (4): 040303, 7 października 2022 r. 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. Powrót do dekwantyzacji i przewagi kwantowej w zadaniach edukacyjnych. 1 grudnia 2021 r. Adres URL http://​/​arxiv.org/​abs/​2112.00811.
arXiv: 2112.00811

[16] Shawn X Cui, Daniel Gottesman i Anirudh Krishna. Bramy ukośne w hierarchii klifu. Fiz. Rev. A, 95 (1), 26 stycznia 2017 r. ISSN 2469-9926,2469-9934. 10.1103/​physreva.95.012329.
https: / / doi.org/ 10.1103 / physreva.95.012329

[17] Edwarda Farhiego, Jeffreya Goldstone’a i Sama Gutmanna. Algorytm optymalizacji przybliżonej kwantowo. 14 listopada 2014. Adres URL http://​/​arxiv.org/​abs/​1411.4028.
arXiv: 1411.4028

[18] Austina G. Fowlera. Optymalne czasowo obliczenia kwantowe. 17 października 2012. Adres URL http://​/​arxiv.org/​abs/​1210.4626.
arXiv: 1210.4626

[19] Sevaga Gharibiana i François Le Galla. Dekwantyzacja transformacji wartości osobliwej kwantowej: twardość i zastosowania w chemii kwantowej oraz hipoteza kwantowego PCP. W materiałach z 54. dorocznego sympozjum ACM SIGACT na temat teorii informatyki, STOC 2022, strony 19–32, Nowy Jork, NY, USA, 9 czerwca 2022 r. ACM. ISBN 9781450392648. 10.1145/​3519935.3519991.
https: / / doi.org/ 10.1145 / 3519935.3519991

[20] Craig Gidney i Martin Ekerå. Jak rozłożyć na czynniki 2048-bitowe liczby całkowite RSA w 8 godzin przy użyciu 20 milionów hałaśliwych kubitów. Quantum, 5 (433): 433, 15 kwietnia 2021 r. ISSN 2521-327X. 10.22331/​q-2021-04-15-433.
https:/​/​doi.org/​10.22331/​q-2021-04-15-433

[21] Craiga Gidneya i Austina G. Fowlera. Elastyczny układ obliczeń kodu powierzchni przy użyciu stanów AutoCCZ. 21 maja 2019. Adres URL http://​/​arxiv.org/​abs/​1905.08916.
arXiv: 1905.08916

[22] András Gilyén i Alexander Poremba. Ulepszone algorytmy kwantowe do estymacji wierności. 29 marca 2022. Adres URL http://​/​arxiv.org/​abs/​2203.15993.
arXiv: 2203.15993

[23] Daniela Gottesmana i Isaaca L Chuanga. Teleportacja kwantowa jest uniwersalnym prymitywem obliczeniowym. 2 sierpnia 1999. Adres URL https://​/​doi.org/​10.1038/​46503.
https: / / doi.org/ 10.1038 / 46503

[24] Leo Grady’ego i Ali Kemala Sinopa. Szybka przybliżona segmentacja chodzika losowego przy użyciu obliczeń wstępnych wektora własnego. W 2008 r. Konferencja IEEE na temat widzenia komputerowego i rozpoznawania wzorców, strony 1–8. IEEE, czerwiec 2008. ISBN 9781424422425. 10.1109/​cvpr.2008.4587487.
https: / / doi.org/ 10.1109 / cvpr.2008.4587487

[25] Kocham K. Grovera. Szybki algorytm mechaniki kwantowej do przeszukiwania baz danych. W materiałach z dwudziestego ósmego dorocznego sympozjum ACM na temat teorii informatyki – STOC '96, STOC '96, strony 212–219, Nowy Jork, Nowy Jork, USA, 1996. ACM Press. ISBN 9780897917858. 10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866

[26] Aram W. Harrow, Awinatan Hassidim i Seth Lloyd. Algorytm kwantowy dla liniowych układów równań. Fiz. Rev. Lett., 103 (15): 150502, 9 października 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. Przewaga kwantowa w uczeniu się na podstawie eksperymentów. Science, 376 (6598): 1182–1186, 10 czerwca 2022 r. ISSN 0036-8075,1095-9203. 10.1126/​science.abn7293.
https://​/​doi.org/​10.1126/​science.abn7293

[28] Cody'ego Jonesa. Protokoły destylacji stanów Fouriera w informatyce kwantowej. 12 marca 2013. Adres URL http://​/​arxiv.org/​abs/​1303.3066.
arXiv: 1303.3066

[29] Johna Kallaughera. Kwantowa przewaga w przypadku naturalnego problemu ze strumieniowaniem. W 2021 r. 62. doroczne sympozjum IEEE na temat podstaw informatyki (FOCS), strony 897–908. IEEE, luty 2022. 10.1109/​focs52979.2021.00091.
https://​/​doi.org/​10.1109/​focs52979.2021.00091

[30] Richarda M. Karpa i Richarda J. Liptona. Niektóre powiązania pomiędzy niejednorodnymi i jednolitymi klasami złożoności. W materiałach z dwunastego dorocznego sympozjum ACM na temat teorii informatyki - STOC '80, STOC '80, strony 302–309, Nowy Jork, Nowy Jork, USA, 28 kwietnia 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 i Theodore J. Yoder. Symulacja Hamiltona z optymalną złożonością próbki. Npj Quantum Inf., 3 (1): 1–7, 30 marca 2017 r. ISSN 2056-6387,2056-6387. 10.1038/​s41534-017-0013-7.
https:/​/​doi.org/​10.1038/​s41534-017-0013-7

[32] François Le Galla. Wykładnicza separacja złożoności przestrzeni kwantowej i klasycznej online. W materiałach z osiemnastego dorocznego sympozjum ACM na temat równoległości w algorytmach i architekturach, SPAA '06, strony 67–73, Nowy Jork, NY, USA, 30 lipca 2006 r. ACM. ISBN 9781595934529. 10.1145/​1148109.1148119.
https: / / doi.org/ 10.1145 / 1148109.1148119

[33] Lin Lin i Yu Tong. Optymalna wielomianowa filtracja kwantowych stanów własnych z zastosowaniem do rozwiązywania kwantowych układów liniowych. Quantum, 4 (361): 361, 11 listopada 2020 r. ISSN 2521-327X. 10.22331/​q-2020-11-11-361.
https:/​/​doi.org/​10.22331/​q-2020-11-11-361

[34] Daniel Litiński. Destylacja w stanie magicznym: nie tak kosztowna, jak myślisz. Quantum, 3 (205): 205, 2 grudnia 2019a. ISSN 2521-327X. 10.22331/​q-2019-12-02-205.
https:/​/​doi.org/​10.22331/​q-2019-12-02-205

[35] Daniel Litiński. Gra w kody powierzchniowe: wielkoskalowe obliczenia kwantowe z chirurgią sieciową. Quantum, 3 (128): 128, 5 marca 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. Kwantowa analiza głównych składowych. Nat. Fiz., 10 (9): 631–633, 27 września 2014 r. 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. Wielka unifikacja algorytmów kwantowych. PRX quantum, 2 (4): 040203, 3 grudnia 2021 r. ISSN 2691-3399. 10.1103/​prxquantum.2.040203.
https: / / doi.org/ 10.1103 / prxquantum.2.040203

[38] Iman Marvian i Seth Lloyd. Uniwersalny emulator kwantowy. 8 czerwca 2016. Adres URL http://​/​arxiv.org/​abs/​1606.02734.
arXiv: 1606.02734

[39] F. Motzoi, poseł Kaicher i F.K. Wilhelm. Liniowe i logarytmiczne składy czasu kwantowych operatorów wielu ciał. Fiz. Rev. Lett., 119 (16): 160503, 20 października 2017 r. ISSN 0031-9007,1079-7114. 10.1103/​PhysRevLett.119.160503.
https: / / doi.org/ 10.1103 / PhysRevLett.119.160503

[40] Michaela Nielsena. Optyczne obliczenia kwantowe z wykorzystaniem stanów skupień. Fiz. Rev. Lett., 93 (4): 040503, 23 lipca 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. Uogólnione sieci wymiany dla krótkoterminowych obliczeń kwantowych. 13 maja 2019. Adres URL http://​/​arxiv.org/​abs/​1905.05118.
arXiv: 1905.05118

[42] Paul Pham i Krysta M. Svore. Dwuwymiarowa architektura kwantowa najbliższego sąsiada do rozkładu na czynniki głębi polilogarytmicznej. 2 lipca 27. Adres URL http://​/​arxiv.org/​abs/​2012.
arXiv: 1207.6655

[43] R Raussendorf i HJ Briegel. Jednokierunkowy komputer kwantowy. Fiz. Rev. Lett., 86 (22): 5188–5191, 28 maja 2001 r. 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. Kompilacja odpornych na błędy heurystyk kwantowych do optymalizacji kombinatorycznej. PRX quantum, 1 (2): 020312, 9 listopada 2020 r. ISSN 2691-3399. 10.1103/​prxquantum.1.020312.
https: / / doi.org/ 10.1103 / prxquantum.1.020312

[45] Dana Shepherda i Michaela J. Bremnera. Czasowo nieustrukturyzowane obliczenia kwantowe. Proc. Matematyka. Fiz. inż. Sci., 465 (2105): 1413–1439, 8 maja 2009. ISSN 1364-5021,1471-2946. 10.1098/​rspa.2008.0443.
https: / / doi.org/ 10.1098 / rspa.2008.0443

[46] Petera-Pike’a Sloana, Jana Kautza i Johna Snydera. Wstępnie obliczony transfer blasku do renderowania w czasie rzeczywistym w dynamicznych środowiskach oświetleniowych o niskiej częstotliwości. W materiałach z 29. dorocznej konferencji na temat grafiki komputerowej i technik interaktywnych, SIGGRAPH '02, strony 527–536, Nowy Jork, NY, USA, 1 lipca 2002 r. ACM. ISBN 9781581135213. 10.1145/​566570.566612.
https: / / doi.org/ 10.1145 / 566570.566612

[47] Jamesa E Smitha. Badanie strategii przewidywania gałęzi. W 25-lecie międzynarodowych sympozjów na temat architektury komputerów (wybrane artykuły), ISCA '98, s. 202–215, Nowy Jork, NY, USA, 1 sierpnia 1998 r. ACM. ISBN 9781581130584. 10.1145/​285930.285980.
https: / / doi.org/ 10.1145 / 285930.285980

[48] Rolando D Somma i Yiğit Subaşı. Złożoność weryfikacji stanu kwantowego w problematyce kwantowych układów liniowych. PRX quantum, 2 (1): 010315, 27 stycznia 2021 r. ISSN 2691-3399. 10.1103/​prxquantum.2.010315.
https: / / doi.org/ 10.1103 / prxquantum.2.010315

[49] Barbara M Terhal. Kwantowa korekcja błędów pamięci kwantowych. Wielebny Mod. Fiz., 87 (2): 307–346, 7 kwietnia 2015 r. 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. Metodologia budowy kwantowej bramki logicznej. Fiz. Rev. A, 62 (5), 18 października 2000. ISSN 1050-2947,1094-1622. 10.1103/​physreva.62.052316.
https: / / doi.org/ 10.1103 / physreva.62.052316

Cytowany przez

[1] Dar Gilboa i Jarrod R. McClean, „Wykładnicza przewaga komunikacji kwantowej w uczeniu rozproszonym”, arXiv: 2310.07136, (2023).

[2] Pablo Rodriguez-Grasa, Ruben Ibarrondo, Javier Gonzalez-Conde, Yue Ban, Patrick Rebentrost i Mikel Sanz, „Quantum przybliżone potęgowanie macierzy gęstości wspomaganej klonowaniem”, arXiv: 2311.11751, (2023).

Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2024-02-22 13:13:08). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.

Nie można pobrać Przywołane przez Crossref dane podczas ostatniej próby 2024-02-22 13:13:06: Nie można pobrać cytowanych danych dla 10.22331 / q-2024-02-22-1264 z Crossref. Jest to normalne, jeśli DOI zostało niedawno zarejestrowane.

Znak czasu:

Więcej z Dziennik kwantowy