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 ( nlogn)
[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ę.