Złożoność próbkowania (w przybliżeniu) transformaty Fouriera funkcji boolowskiej

17

Jedną rzeczą, którą komputery kwantowe mogą zrobić (być może nawet z tylko BPP + obwody kwantowe głębokości logarytmicznej), jest przybliżenie próbki transformaty Fouriera funkcji logicznej wartościowej w P.±1

Tutaj i poniżej, kiedy mówię o próbkowaniu transformaty Fouriera, mam na myśli wybranie x zgodnie z . (Znormalizowane w razie potrzeby i w przybliżeniu).|f^(x)|2

Czy możemy opisać klasę złożoności, którą możemy nazwać P-FOURIER SAMPLING, przybliżonych próbkowania funkcji boolowskich P? Czy są problemy, które są kompletne dla tej klasy?

Biorąc pod uwagę klasę X funkcji boolowskich, co można powiedzieć o złożoności obliczeniowej, którą możemy nazwać SAMPLING-X przybliżenia próbkowania transformaty Fouriera funkcji w X. (Przypuszczam, że jeśli X jest BQP, to X-SAMPLING jest wciąż w mocy komputerów kwantowych).

Jakie są przykłady X, gdzie SAMPLING-X jest w P? Czy istnieją ciekawe przykłady, w których SAMPLING-X jest trudny do NP?

Istnieje kilka wariantów tego problemu, które mogą być również interesujące. Po stronie Fouriera zamiast próby przybliżonej możemy mówić o problemie decyzyjnym włączonym (probabilistycznie) przez przybliżone próbkowanie. Po stronie pierwotnej możemy zacząć od klasy X rozkładów prawdopodobieństwa i zapytać, jaka jest zależność między zdolnością do w przybliżeniu próbkowania rozkładu D w X a w przybliżeniu próbkowania (znormalizowanej) transformaty Fouriera.

Krótko mówiąc, co wiadomo na temat tego pytania.

Aktualizacja: Martin Schwarz wskazał, że jeśli wszystkie same współczynniki Fouriera są skoncentrowane tylko na wielomianowej liczbie wpisów, możliwe jest w BPP przybliżenie tych dużych współczynników (a tym samym również w przybliżeniu próbki). To sięga do Goldreich-Levin, i Kushilevitz-Mansour. Czy istnieją ciekawe klasy funkcji, w których istnieje probabilistyczny algorytm wielomianowy do przybliżonego próbkowania strony Fouriera, w którym współczynniki Fouriera są rozłożone na więcej niż wielomianowo wiele współczynników?

Dodano później: Pozwól mi wspomnieć o kilku konkretnych problemach.

1) Jak trudno jest w przybliżeniu próbkować transformatę Fouriera funkcji boolowskich w P.

a) Jednym pytaniem, które Scott Aaronson wspomniał w komentarzu poniżej, jest wykazanie, że nie ma tego w BPP. Lub coś słabszego w tym sensie, że jeśli to zadanie jest w BPP, następuje pewne załamanie. (Szkot przypuszcza, że ​​tak jest.)

b) Innym pytaniem jest wykazanie, że zadanie to jest trudne w odniesieniu do niektórych klas złożoności opartych na kwantach. Na przykład, aby pokazać, że jeśli możesz wykonać to zadanie, możesz rozwiązać problemy decyzyjne w BPP wspomaganym komputerami kwantowymi o głębokości dziennika lub coś podobnego.

2) Jakie są klasy funkcji boolowskich, tak że w przybliżeniu próbkowanie ich transformaty Fourlera znajduje się w P. Wiemy, że dzieje się tak, gdy współczynniki Fouriera koncentrują się na wielomianach o wielu współczynnikach, ale wydaje się to bardzo ograniczone.

3) Czy istnieje jakaś klasa złożoności X wysoko w PH, którą maszyna X może w przybliżeniu próbkować transformatę Fouriera każdej funkcji, którą maszyna X może obliczyć.

4) Byłem szczególnie zainteresowany problemem próbkowania transformaty Fouriera zdarzenia krzyżowania w celu perkolacji na siatce sześciokątnej n przez n.

cc.complexity-theory quantum-computing pr.probability randomized-algorithms sample-complexity Gil Kalai
źródło
2
Gil, na wypadek, gdyby cię to interesowało: zanim Alex Arkhipov i ja rozpoczęliśmy pracę nad BosonSampling, „oryginalną” rzeczą, którą chciałem udowodnić, było to, że przybliżony problem próbkowania Fouriera - tj. Dokładnie ten problem, który opisujesz - nie jest w BPP, chyba że załamie się hierarchia wielomianowa. Niestety, nie byłem w stanie tego udowodnić ani nawet uzyskać dobrych dowodów na to, co zmotywowało nas do przeniesienia uwagi na bozony i stałe „solidnie # P-pełne”. Chciałbym jednak teraz powtórzyć moje przypuszczenie, że przybliżenie próbkowania Fouriera jest trudne, zakładając, że PH jest nieskończone. :-)
Scott Aaronson
Dzięki, Scott, to jest bardzo interesujące. Wspomnę twoją hipotezę wraz z kilkoma innymi w następnej edycji pytania.
Gil Kalai
BTW, Scott, czy argument za pomocą stałych nie pokazuje, że BOSONSAMPLING w BPP oznacza załamanie PH działa również w przypadku próbkowania Fouriera?
Gil Kalai,
Gil: Tak, w przypadku algorytmów dokładnego próbkowania przechodzi dokładnie ten sam argument. Ale w przypadku algorytmów przybliżonego próbkowania nie jestem pewien: należałoby uwierzyć, że przybliżone obliczanie współczynników Fouriera powinno być średnio P-całkowite, podobnie jak ja i Arkhipov przypuszczaliśmy, że aproksymacja stałej stałej macierzy Gaussa powinna wynosić # Średnio P-kompletne.
Scott Aaronson

Odpowiedzi:

9

Kushilevitz-Mansour algorytmu uczenia Nawiązanie teorią, że gdy f ( x ) jest w przybliżeniu rzadki, a więc nie tylko O ( P O Lfa^(x)O(poly(n))Ω(1/poly(n))bP.P.Kushilevitz-Mansour mówił tylko o transformacjach Fouriera nad , ale znane są uogólnienia na FT nad ogólnymi skończonymi grupami abelowymi (patrz np . Teza Akavii ).Z2)

Ω(2)n/2))

Martin Schwarz
źródło
Dzięki, Martin! Przypuszczam, że nie wiadomo, jak trudno jest próbkować z transformaty Fouriet nawet funkcji AC ^ 0, prawda? (W przypadku głębokości-2 przypuszczenie Mansoura zapewnia, że ​​jest wielomianowe (z randomizacją).
Gil Kalai