Poprawiona złożoność zapytań kwantowych na łatwiejszych danych wejściowych

Poprawiona złożoność zapytań kwantowych na łatwiejszych danych wejściowych

Znacznik czasu: 8 kwietnia 2024 11:29

Noela T. Andersona1, Jay-U Chung1, Shelby Kimmel1, Da-Yeon Koh2i Xiaohan Ye1,3

1Middlebury College, Middlebury, VT, USA
2Williams College w Williamstown, MA, USA
3Uniwersytet Browna w Providence, RI, USA

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

Abstrakcyjny

Algorytmy programu o rozpiętości kwantowej do oceny funkcji czasami zmniejszają złożoność zapytań, gdy obiecano, że dane wejściowe mają określoną strukturę. Projektujemy zmodyfikowany algorytm programu rozpiętości, aby pokazać, że te ulepszenia utrzymują się nawet bez obietnic z wyprzedzeniem, i rozszerzamy to podejście na bardziej ogólny problem konwersji stanu. Jako aplikacja udowadniamy wykładnicze i superwielomianowe zalety kwantowe w średniej złożoności zapytań dla kilku problemów wyszukiwania, uogólniając metodę Montanaro's Search with Advice [Montanaro, TQC 2010].

Większa złożoność zapytań kwantowych na łatwiejszych danych wejściowych Inteligencja danych PlatoBlockchain. Wyszukiwanie pionowe. AI.

Wyróżniony obraz: Drzewo decyzyjne użyte do stworzenia jednego z naszych algorytmów.

Popularne podsumowanie

Oczekujemy, że algorytmy kwantowe, podobnie jak algorytmy klasyczne, powinny działać szybciej przy łatwiejszych danych wejściowych. Na przykład, jeśli szukasz elementu na nieuporządkowanej liście i istnieje wiele kopii tego elementu, spodziewalibyśmy się, że algorytm kwantowy powinien w tej sytuacji działać szybciej w porównaniu do sytuacji, gdy jest tylko jeden zaznaczony element, nawet bez wiedzy liczbę elementów docelowych z wyprzedzeniem. Rzeczywiście, w przypadku problemu wyszukiwania wiadomo, jak uzyskać taką przewagę na łatwiejszych danych wejściowych. Jednak uogólnienie tego pomysłu na problemy wykraczające poza wyszukiwanie jest trudne, gdy nie ma oczywistego sposobu na oznaczenie, czy obliczenia trwały wystarczająco długo. Modyfikujemy kilka popularnych struktur algorytmicznych w modelu zapytań, aby utworzyć flagi ostrzegające nas, czy obliczenia trwały wystarczająco długo, co pozwala nam wcześniej zakończyć algorytm na łatwiejszych danych wejściowych, bez wcześniejszej wiedzy, czy instancja jest łatwa, czy trudna. Jako aplikacja, biorąc pod uwagę rozkład zarówno łatwych, jak i twardych danych wejściowych problemu, możemy analizować średnią złożoność zapytania. Pokazujemy, że pewne rozkłady danych wejściowych do problemów wyszukiwania dają duże średnie korzyści w zapytaniach kwantowych w porównaniu z klasycznymi algorytmami.

► Dane BibTeX

► Referencje

[1] Andrisa Ambainisa i Ronalda de Wolfa. Złożoność zapytań kwantowych w średnim przypadku. Journal of Physics A: Mathematical and General, 34(35):6741, 2001. doi:10.1088/​0305-4470/​34/​35/​302.
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​302

[2] Dorit Aharonov. Obliczenia kwantowe. Roczne recenzje fizyki obliczeniowej VI, strony 259–346, 1999. doi:10.1142/​9789812815569_0007.
https: / / doi.org/ 10.1142 / 9789812815569_0007

[3] Michel Boyer, Gilles Brassard, Peter Høyer i Alain Tapp. Ścisłe granice poszukiwań kwantowych. Fortschritte der Physik, 46(4-5):493–505, 1998. 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

[4] Aleksandr Biełows. Programy rozszerzające dla funkcji z certyfikatami o stałym rozmiarze 1: Rozszerzone streszczenie. W materiałach z czterdziestego czwartego dorocznego sympozjum ACM na temat teorii informatyki, STOC '12, strony 77–84, 2012. doi:10.1145/​2213977.2213985.
https: / / doi.org/ 10.1145 / 2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca i Alain Tapp. Wzmocnienie i estymacja amplitudy kwantowej. W obliczeniach i informacjach kwantowych, tom 305 Contemp. Matematyka, strony 53–74. Amera. Matematyka. Soc., Providence, RI, 2002. doi:10.1090/​conm/​305/​05215.
https: / / doi.org/ 10.1090 / conm / 305/05215

[6] Gilles Brassard, Peter Høyer i Alain Tapp. Liczenie kwantowe. W Automata, Languages ​​and Programming, strony 820–831, 1998. doi:10.1007/​BFb0055105.
https: // doi.org/ 10.1007 / BFb0055105

[7] Aleksandrs Belovs i Ben W. Reichardt. Programy rozpiętościowe i algorytmy kwantowe do wykrywania połączeń stowych i pazurów. Notatki z wykładów z informatyki, 7501 LNCS:193–204, 2012. doi:10.1007/​978-3-642-33090-2_18.
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_18

[8] Aleksandrs Belovs i Ansis Rosmanis. Wąska dolna granica kwantowa dla przybliżonego liczenia w stanach kwantowych. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] Salmana Beigiego i Leili Taghavi. Przyspieszenie kwantowe w oparciu o klasyczne drzewa decyzyjne. Quantum, 4:241, 2020. doi:10.22331/​q-2020-03-02-241.
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[10] Aleksandrs Belovs i Duyal Yolcu. Bilet w jedną stronę do Las Vegas i kwantowego przeciwnika. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] Ryszard. Cleve, Artur. Ekert, Chiara Macchiavello i Michele Mosca. Algorytmy kwantowe ponownie. Proceedings of Royal Society of London. Seria A: Nauki matematyczne, fizyczne i inżynieryjne, 454(1969):339–354, 1998. doi:10.1098/​rspa.1998.0164.
https: / / doi.org/ 10.1098 / rspa.1998.0164

[12] Arjan Cornelissen, Stacey Jeffery, Maris Ozols i Alvaro Piedrafita. Programy rozpiętościowe i złożoność czasu kwantowego. W 45. Międzynarodowym Sympozjum na temat matematycznych podstaw informatyki (MFCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. doi:10.4230/​LIPIcs.MFCS.2020.26.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2020.26

[13] Chris Cade, Ashley Montanaro i Aleksandrs Belovs. Algorytmy kwantowe efektywne czasowo i przestrzennie do wykrywania cykli i testowania dwudzielności. Informacje i obliczenia kwantowe, 18 (1-2): 18–50, 2018.

[14] Kai DeLorenzo, Shelby Kimmel i R. Teal Witter. Zastosowania algorytmu kwantowego dla st-łączności. W 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), s. 6:1–6:14, 2019. doi:10.4230/​LIPIcs.TQC.2019.6.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2019.6

[15] Dmitry Grinko, Julien Gacon, Christa Zoufal i Stefan Woerner. Iteracyjna estymacja amplitudy kwantowej. npj Quantum Information, 7(1):52, marzec 2021. doi:10.1038/​s41534-021-00379-1.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] Lov K. Grover. Mechanika kwantowa pomaga w poszukiwaniu igły w stogu siana. Physical Review Letters, 79(2):325–328, 1997. doi:10.1103/​PhysRevLett.79.325.
https: / / doi.org/ 10.1103 / PhysRevLett.79.325

[17] Wassly’ego Hoeffdinga. Nierówności prawdopodobieństwa sum ograniczonych zmiennych losowych. Journal of the American Statistical Association, 58(301):13–30, 1963. doi:10.1080/​01621459.1963.10500830.
https: / / doi.org/ 10.1080 / 01621459.1963.10500830

[18] Tsuyoshi Ito i Stacey Jeffery. Przybliżone programy rozpiętości. Algorithmica, 81(6):2158–2195, 2019. doi:10.1007/​s00453-018-0527-1.
https:/​/​doi.org/​10.1007/​s00453-018-0527-1

[19] Michaela Jarreta, Stacey Jeffery, Shelby Kimmel i Alvaro Piedrafity. Algorytmy kwantowe dla łączności i problemów pokrewnych. W 26. dorocznym europejskim sympozjum na temat algorytmów (ESA 2018), s. 49:1–49:13, 2018. doi:10.4230/​LIPIcs.ESA.2018.49.
https://​/​doi.org/​10.4230/​LIPics.ESA.2018.49

[20] Aleksiej Y. Kitajew. Pomiary kwantowe i problem stabilizatora abelowego. 1995. arXiv:quant-ph/​9511026.
arXiv: quant-ph / 9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek i Mario Szegedy. Złożoność zapytania kwantowego konwersji stanu. W 2011 r. 52. doroczne sympozjum IEEE na temat podstaw informatyki, strony 344–353, 2011. doi:10.1109/​FOCS.2011.75.
https: / / doi.org/ 10.1109 / FOCS.2011.75

[22] Frédéric Magniez, Ashwin Nayak, Jérémie Roland i Miklos Santha. Szukaj za pomocą Quantum Walk. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/​090745854.
https: / / doi.org/ 10.1137 / 090745854

[23] Ashley Montanaro. Wyszukiwanie kwantowe z poradami. W konferencji na temat obliczeń kwantowych, komunikacji i kryptografii, strony 77–93. Springer, 2010. doi:10.1007/​978-3-642-18073-6_7.
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_7

[24] Bena W. Reichardta. Programy rozciągające i złożoność zapytań kwantowych: ogólna granica przeciwnika jest prawie ścisła dla każdej funkcji logicznej. 50. doroczne sympozjum IEEE na temat podstaw informatyki, strony 544–551, 2009. doi:10.1109/​FOCS.2009.55.
https: / / doi.org/ 10.1109 / FOCS.2009.55

[25] Bena W. Reichardta. Refleksje na temat algorytmów zapytań kwantowych. W materiałach z dorocznego sympozjum ACM-SIAM 2011 na temat algorytmów dyskretnych, Proceedings, strony 560–569. 2011. doi:10.1137/​1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44

[26] Leila Taghavi. Uproszczony algorytm kwantowy dla problemu identyfikacji wyroczni. Inteligencja maszyn kwantowych, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

Cytowany przez

[1] Stacey Jeffery, Shelby Kimmel i Alvaro Piedrafita, „Quantum Algorithm for Path-Edge Sampling”, arXiv: 2303.03319, (2023).

[2] Michael Czekanski, Shelby Kimmel i R. Teal Witter, „Robust and Space-Efficient Dual Adversary Quantum Query Algorithms”, arXiv: 2306.15040, (2023).

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

On Serwis cytowany przez Crossref nie znaleziono danych na temat cytowania prac (ostatnia próba 2024-04-11 15:45:17).

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