Nauka kwantowego PAC

tło

Funkcje w to PAC poznawalny w quasipolomomialnym czasie z klasycznym algorytmem, który wymaga O ( 2 l o g ( n ) O ( d ) ) losowo wybranych zapytań do poznania obwodu o głębokości d [1]. Jeśli nie ma algorytmu faktoryzacji 2 n o ( 1 ), jest to optymalne [2]. Oczywiście na komputerze kwantowym wiemy, jak to uwzględnić, więc ta dolna granica nie pomaga. Co więcej, optymalny klasyczny algorytm wykorzystuje widmo Fouriera funkcji, krzycząc „kwantuj mnie!”$AC^0$$O(2^{log(n)^{O(d)}})$$2^{n^{o(1)}}$

[1] N. Linial, Y. Mansour i N. Nisan. [1993] „Obwody o stałej głębokości, transformata Fouriera i zdolność uczenia się”, Journal of ACM 40 (3): 607-620.

[2] M. Kharitonov. [1993] „Twardość kryptograficzna uczenia specyficznego dla dystrybucji”, Proceedings of ACM STOC'93, s. 372–381.

W rzeczywistości 6 lat temu Scott Aaronson umieścił uczenie się jako jednego ze swoich dziesięciu pół-wielkich wyzwań dla teorii obliczeń kwantowych .$AC^0$

Pytanie

Moje pytanie jest trzykrotne:

1) Czy istnieją przykłady rodzin funkcji naturalnych, których komputery kwantowe mogą się nauczyć szybciej niż klasyczne komputery przy założeniach kryptograficznych?

$AC^0$$TC^0$

$TC^0$$TC^0$

Strzelę do twojego pierwszego pytania:

Czy istnieją przykłady rodzin funkcji naturalnych, których komputery kwantowe mogą się nauczyć szybciej niż klasyczne komputery przy założeniach kryptograficznych?

Zależy to od dokładnego modelu i zminimalizowanego zasobu. Jedną z opcji jest porównanie złożoności próbki (do uczenia PAC niezależnego od dystrybucji) standardowego modelu klasycznego z modelem kwantowym, który otrzymuje próbki kwantowe (tj. Zamiast losowego wejścia i odpowiedniej wartości funkcji, zapewnia się algorytm z kwantową superpozycją nad wartościami wejściowymi i ich funkcjami). W tym ustawieniu kwantowe uczenie się PAC i klasyczne uczenie się PAC są w zasadzie równoważne. Klasyczna górna granica złożoności próbki i kwantowa dolna granica złożoności próbki są prawie takie same, jak pokazano w następującej sekwencji dokumentów:

[1] R. Servedio i S. Gortler, „Równoważności i separacje między kwantową a klasyczną uczeniem się”, SIAM Journal on Computing, vol. 02138, s. 1–26, 2004.

[2] A. Atici i R. Servedio, „Poprawione granice kwantowych algorytmów uczenia się”, Quantum Information Processing, s. 1–18, 2005.

[3] C. Zhang, „Poprawiona dolna granica złożoności zapytań dla kwantowego uczenia się PAC”, Information Processing Letters, vol. 111, nr 1, s. 40–45, grudzień 2010 r.

$O(n^{\log n})$

[4] N. Bshouty i J. Jackson, „Uczenie się DNF nad rozkładem równomiernym za pomocą kwantowej przykładowej wyroczni”, SIAM Journal on Computing, vol. 28, nr 3, s. 1136–1153, 1998.

[5] J. Jackson, C. Tamon i T. Yamakami, „Znowu uczono się kwantowej DNF”, Computing and Combinatorics, str. 595–604, 2002.

[6] A. Atıcı i R. Servedio, „Algorytmy kwantowe do uczenia się i testowania juntas”, Quantum Information Processing, vol. 6, nr 5, ss. 323–348, wrzesień 2007.

Z drugiej strony, jeśli interesuje Cię tylko standardowy klasyczny model PAC, wykorzystując obliczenia kwantowe jako narzędzie do przetwarzania końcowego (tj. Bez próbek kwantowych), to Servedio i Gortler [1] zauważyli, że istnieje klasa koncepcji Kearnsowi i Valiantowi, którzy nie mogą być klasycznie nauczeni PAC przy założeniu twardości faktorowania liczb całkowitych Blum, ale mogą być kwantowo nauczeni PAC za pomocą algorytmu Shora.

Sytuacja w modelu dokładnej nauki Angluin poprzez zapytania o członkostwo jest nieco podobna. Zapytania kwantowe mogą jedynie przyspieszyć wielomian pod względem złożoności zapytań. Występuje jednak gwałtowne przyspieszenie złożoności czasu przy założeniu istnienia funkcji jednokierunkowych [1].

Nie mam pojęcia o drugim pytaniu. Z przyjemnością też o tym usłyszę.

Z pewnością nie jest to pełna odpowiedź na twoje pytanie, ale mam nadzieję, że pomoże w pierwszej części. Wydaje się, że istnieje duże zainteresowanie wykorzystaniem algorytmów kwantowych do identyfikacji nieznanych wyroczni. Jednym z przykładów jest niedawny artykuł Floessa, Anderssona i Hillery'ego ( arXiv: 1006.1423 ), który dostosowuje algorytm Bernsteina-Vazirani do identyfikowania funkcji boolowskich, które zależą tylko od niewielkiego podzbioru zmiennych wejściowych (juntas). Używają tego podejścia do określania funkcji wyroczni dla wielomianów niskiego stopnia (wyraźnie dotyczą przypadków liniowych, kwadratowych i sześciennych).