Podstawowe podprogramy kwantowe: znajdowanie wielu zaznaczonych elementów i sumowanie liczb

Podstawowe podprogramy kwantowe: znajdowanie wielu zaznaczonych elementów i sumowanie liczb

Znacznik czasu: 14 marca 2024 9:40
Podstawowe podprogramy kwantowe: znajdowanie wielu zaznaczonych elementów i sumowanie liczb PlatoBlockchain Data Intelligence. Wyszukiwanie pionowe. AI.

Jorana van Apeldoorna1, Sandera Griblinga2, Harolda Nieuwboera3

1IViR i QuSoft, Uniwersytet w Amsterdamie, Holandia
2Katedra Ekonometrii i Badań Operacyjnych, Uniwersytet w Tilburgu, Tilburg, Holandia
3Korteweg–de Vries Institute for Mathematics and QuSoft, Uniwersytet w Amsterdamie, Holandia oraz Wydział Informatyki, Ruhr University Bochum, Niemcy i Wydział Nauk Matematycznych, Uniwersytet w Kopenhadze, Dania

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

Abstrakcyjny

Pokazujemy, jak znaleźć wszystkie zaznaczone $k$ elementy na liście o rozmiarze $N$ przy użyciu optymalnej liczby $O(sqrt{N k})$ zapytań kwantowych i jedynie narzutu polilogarytmicznego w złożoności bramki, w ustawieniu gdzie jeden ma małą pamięć kwantową. Poprzednie algorytmy albo generowały narzut wynoszący $k$ w złożoności bramki, albo miały dodatkowy współczynnik $log(k)$ w złożoności zapytania.
Następnie rozważamy problem znalezienia multiplikatywnego przybliżenia $delta$ $s = suma_{i=1}^N v_i$ gdzie $v=(v_i) w [0,1]^N$, biorąc pod uwagę dostęp zapytania kwantowego do binarny opis $v$. Podajemy algorytm, który to robi z prawdopodobieństwem co najmniej 1-rho$, używając zapytań kwantowych $O(sqrt{N log(1/rho) / delta})$ (przy łagodnych założeniach dotyczących $rho$). To kwadratowo poprawia zależność od $1/delta$ i $log(1/rho)$ w porównaniu z prostym zastosowaniem estymacji amplitudy. Aby uzyskać lepszą zależność $log(1/rho)$ używamy pierwszego wyniku.

► Dane BibTeX

► Referencje

[1] Srinivasan Arunachalam i Ronald de Wolf. Optymalizacja liczby bramek w poszukiwaniu kwantowym. Informacje kwantowe. Comput., 17(3-4):251–261, 2017. doi:10.26421/​qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] José A. Adell i P. Jodrá. Dokładne odległości Kołmogorowa i całkowitego zróżnicowania pomiędzy niektórymi znanymi rozkładami dyskretnymi. Journal of Inequalities and Applications, 2006(1):1–8, 2006. doi:10.1155/​JIA/​2006/​64307.
https://​/​doi.org/​10.1155/​JIA/​2006/​64307

[3] Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter i Ronald de Wolf. Algorytmy kwantowe skalowania i równoważenia macierzy. W Proceedings of 48th International Colloquium on Automata, Languages, and Programming (ICALP'21), tom 198, strony 110:1–110:17, 2021. arXiv:2011.12823, doi:10.4230/​LIPIcs.ICALP.2021.110.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arXiv: 2011.12823

[4] Scotta Aaronsona i Patricka Ralla. Liczenie przybliżone kwantowo, uproszczone. W Sympozjum na temat prostoty w algorytmach, strony 24–32, 2020. doi:10.1137/​1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[5] Michel Boyer, Gilles Brassard, Peter Høyer i Alain Tapp. Ścisłe ograniczenia w poszukiwaniach kwantowych. Fortschritte der Physik, 46 (4–5): 493–505, 1998. Wcześniejsza wersja w Physcomp'96. arXiv:quant-ph/​9605034.
arXiv: quant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf i Christof Zalka. Granice algorytmów kwantowych o małym i zerowym błędzie. W 40. dorocznym sympozjum na temat podstaw informatyki (FOCS'99), strony 358–368. Towarzystwo Komputerowe IEEE, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca i Alain Tapp. Wzmocnienie i estymacja amplitudy kwantowej. W Quantum Computation and Quantum Information: A Millennium Volume, tom 305 Contemporary Mathematics, strony 53–74. Amerykańskie Towarzystwo Matematyczne, 2002. doi:10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[8] Richarda Brenta i Paula Zimmermanna. Nowoczesna arytmetyka komputerowa, tom 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even i Oded Goldreich. Dolne granice algorytmów próbkowania do szacowania średniej. Listy dotyczące przetwarzania informacji, 53(1):17–25, styczeń 1995. doi:10.1016/​0020-0190(94)00171-T.
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

[10] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini i Leonard Wossnig. Kwantowe uczenie maszynowe: perspektywa klasyczna. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, styczeń 2018. doi:10.1098/​rspa.2017.0551.
https: / / doi.org/ 10.1098 / rspa.2017.0551

[11] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest i Clifford Stein. Wprowadzenie do algorytmów. MIT Press, wydanie 4, 2022.

[12] P. Diaconis i D. Freedman. Skończone sekwencje wymienne. The Annals of Probability, 8(4):745–764, 1980. URL: https://​/​www.jstor.org/​stable/​2242823.
https: / / www.jstor.org/ stable / 2242823

[13] Christopha Dürra i Petera Høyera. Kwantowy algorytm znajdowania minimum, 1996. doi:10.48550/​arXiv.quant-ph/​9607014.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: quant-ph / 9607014

[14] Christoph Dürr, Mark Heiligman, Peter Høyer i Mehdi Mhalla. Złożoność zapytań kwantowych niektórych problemów grafowych. SIAM Journal on Computing, 35(6):1310–1328, styczeń 2006. doi:10.1137/​050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] Paula Daguma, Richarda Karpa, Michaela Luby’ego i Sheldona Rossa. Optymalny algorytm estymacji Monte Carlo. SIAM Journal on Computing, 29(5):1484–1496, styczeń 2000. doi:10.1137/​S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd i Lorenzo Maccone. Kwantowa pamięć o dostępie swobodnym. Physical Review Letters, 100(16), kwiecień 2008. doi:10.1103/​physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] Sandera Griblinga i Harolda Nieuwboera. Ulepszone dolne i górne granice kwantowe skalowania macierzy. W Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS'22), tom 219, strony 35:1–35:23, 2022. arXiv:2109.15282, doi:10.4230/​LIPIcs.STACS.2022.35.
https: // doi.org/ 10.4230 / LIPIcs.STACS.2022.35
arXiv: 2109.15282

[18] Marta de Graafa i Ronalda de Wolfa. O kwantowych wersjach zasady Yao. W 19. Sympozjum teoretycznych aspektów informatyki (STACS'02), tom 2285 Notatek z wykładów z informatyki, strony 347–358, Berlin, Heidelberg, 2002. Springer. doi:10.1007/​3-540-45841-7_28.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

[19] Lov K. Grover. Szybki algorytm mechaniki kwantowej do przeszukiwania baz danych. W Proceedings of 38th Annual ACM Symposium on Theory of Computing (STOC'96), strony 212–219, 1996. arXiv:quant-ph/​9605043, doi:10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: quant-ph / 9605043

[20] Lov K. Grover. Telekomputacja kwantowa, 1997. Memorandum techniczne Bell Labs ITD97-31630F. doi:10.48550/​arXiv.quant-ph/​9704012.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: quant-ph / 9704012

[21] Lov K. Grover. Struktura szybkich algorytmów mechaniki kwantowej. W Proceedings of the trzydzieste Annual ACM Symposium on the Theory of Computing (STOC'98), strony 53–62, 1998. arXiv:quant-ph/​9711043, doi:10.1145/​276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712
arXiv: quant-ph / 9711043

[22] Yassine Hamoudi. Kwantowy estymator średniej subgaussowskiej. W 29. dorocznym europejskim sympozjum na temat algorytmów (ESA 2021), tom 204 Leibniz International Proceedings in Informatics (LIPIcs), strony 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https://​/​doi.org/​10.4230/​LIPics.ESA.2021.50

[23] Svantego Jansona. Ograniczenia ogonowe dla sum zmiennych geometrycznych i wykładniczych. Statystyki i listy prawdopodobieństwa, 135:1–6, 2018. doi:10.1016/​j.spl.2017.11.017.
https://​/​doi.org/​10.1016/​j.spl.2017.11.017

[24] Donalda Ervina Knutha. Sztuka programowania komputerowego, tom III. Addison-Wesley, wydanie 2, 1998. Adres URL: https://​/​www.worldcat.org/​oclc/​312994415.
https://​/​www.worldcat.org/​oclc/​312994415

[25] Robin Kothari i Ryan O'Donnell. Średnie oszacowanie, jeśli masz kod źródłowy; lub kwantowe metody Monte Carlo. W materiałach z dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych 2023 (SODA'23), strony 1186–1215, 2023. doi:10.1137/​1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen i Isaac L. Chuang. Obliczenia kwantowe i informacje kwantowe. Cambridge University Press, 2002.

[27] Ashwina Nayaka i Felixa Wu. Złożoność zapytania kwantowego w zakresie aproksymacji mediany i powiązanych statystyk. W materiałach z 31. dorocznego sympozjum ACM SIGACT na temat teorii informatyki (STOC'99), strony 384–393, 1999. arXiv:quant-ph/​9804066, doi:10.1145/​301250.301349.
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: quant-ph / 9804066

[28] B. Roosa. Przybliżenie dwumianowe do rozkładu dwumianowego Poissona: rozwinięcie Krawtchouka. Teoria prawdopodobieństwa i jej zastosowania, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

[29] Roberta M. Younga. 75.9 Stała Eulera. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/​3620251.
https: / / doi.org/ 10.2307 / 3620251

Cytowany przez

Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.

Znak czasu:

Więcej z Dziennik kwantowy