Jaka jest złożoność odróżnienia prawdziwego widma Fouriera od fałszywego?

$PH$ urządzenie ma dostęp oracle losowej logicznej funkcji $f:\{0,1\}^n \to \{ -1,1 \}$ , a dwa Fouriera widma $g$ i $h$ .

Widma Fouriera funkcji $f$ są zdefiniowane jako $F:\{0,1\}^n \to R$ :

$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left( s\cdot x \mod\ 2 \right) f(x)$

Jedno z $g$ lub $h$ to prawdziwe widma Fouriera $f$ a drugie to tylko fałszywe widma Fouriera należące do nieznanej losowej funkcji boolowskiej.

Nie jest to trudne do wykazania, że $PH$ maszyny, nie mogą nawet w przybliżeniu $F(s)$ dla wszelkich $s$ .

Jaka jest złożoność zapytania przy podejmowaniu decyzji z dużym prawdopodobieństwem powodzenia, która z nich jest prawdziwa?

Interesujące jest to, mi, ponieważ w przypadku tego problemu nie jest $PH$ , to można wykazać, że istnieje względem ORACLE którym $BQP$ w nie podzbioru $PH$ .

— Mirmojtaba Gharibi
źródło

@Mirmojtaba: Chociaż znam problem i motywację, byłoby miło, gdybyś mógł edytować swoje pytanie i zdefiniować „widma Fouriera” i wyjaśnić motywację dla czytelników, którzy nie znają tego problemu (lub tylko używanej terminologii). W ten sposób możesz uzyskać więcej odpowiedzi od ludzi. Ponadto zwykle preferowane jest edytowanie pytania w celu dodania dodatkowych komentarzy zamiast zamieszczania ich w wątku komentarzy. (Aby czytelnicy musieli przeczytać tylko twoje pytanie, a nie komentarze).

— Robin Kothari,

Może źle zrozumiałem problem, ale wydaje się, że ten problem jest zbyt trudny. Jeśli g i h są bardzo blisko (powiedzmy, że różnią się tylko 1 bitem), w jaki sposób maszyna BQP decyduje, które z nich jest prawidłowym widmem Fouriera f? Czy dolna granica problemu wyszukiwania nie powinna oznaczać, że jest to trudne dla komputerów kwantowych?

— Robin Kothari,

Mam bardziej podstawowe pytanie. biorąc pod uwagę dowolną funkcję, czy łatwo jest stwierdzić, czy rzeczywiście jest to czteroliniowe spektrum funkcji boolowskiej?

— Suresh Venkat,

na marginesie, ponieważ czekał dwa dni przed crossspostingiem, a także po tym, jak tutaj nie otrzymałem odpowiedzi, myślę, że jest to w porządku. Zobacz także rozdzielczość osiągniętą tutaj: meta.cstheory.stackexchange.com/questions/673/…

— Suresh Venkat

Co to jest maszyna PH? W rzeczywistości wydaje się to nieistotne, jeśli interesuje Cię tylko złożoność zapytań, prawda? W tym przypadku problem wydaje się sprowadzać do prostego problemu algebry liniowej, co prawdopodobnie powoduje wykładniczą złożoność zapytań.

— domotorp

Odpowiedzi:

Przepraszam za spóźnienie - to wspaniałe pytanie! Jak już zauważyli inni, właśnie dlatego zadałem to pytanie w mojej pracy BQP vs. PH i dlaczego spędziłem 4 lub 5 miesięcy pracując nad tym bez powodzenia w 2008 roku. Jednym ze sposobów odpowiedzi na to pytanie byłoby udowodnienie znacznie bardziej ogólne stwierdzenie, które nazwałem „uogólnioną hipotezą liniowo-Nisanową” - ale niestety ta hipoteza okazała się fałszywa , przynajmniej dla obwodów o głębokości 3 i wyższych. (Nadal uważam, że jest to prawdopodobnie prawdą w przypadku obwodów o głębokości 2, które przynajmniej doprowadziłyby do separacji wyroczni między BQP i AM.) W przypadku nowszych pomysłów (najnowszych, o ile mi wiadomo) na temat separacji wyroczni między BQP i PH, zobacz ładny artykuł uzupełniający autorstwa Feffermana, Shaltiela, Umansa,

— Scott Aaronson
źródło

czy powyższe stwierdzenie pytania Gharibi jest identyczne czy nieco inne? czy to Twoja relatywna wersja?

— dniu

To niewielki wariant, ale uważam, że nie jest trudno udowodnić, że jest równoważny. Po pierwsze, z pewnością, jeśli potrafisz rozwiązać sprawdzanie Fouriera, to możesz także rozwiązać problem Gharibi (po prostu uruchom algorytm FC osobno dla g i h). Z drugiej strony, jeśli potrafisz rozwiązać problem Gharibi, to biorąc pod uwagę instancję FC, nazwij drugą funkcję FC albo „g” lub „h” równomiernie losowo, i ustaw drugą z dwóch (odpowiednio h lub g) na funkcja losowa. Jeśli algorytm Gharibi zawsze wybiera oryginalną funkcję z instancji FC, jest to dowód, że instancja była raczej powiązana niż przypadkowa.

— Scott Aaronson,

Czy jest bardziej znany, gdy f jest w P?

— Gil Kalai

Gil: Niezupełnie! W BQP pojawia się problem z relatywną obietnicą, o którym nie wiemy, że jest w PH. Z pewnością można symulować „losowy” przypadek problemu z wyrocznią, zastępując f i g funkcjami pseudolosowymi (obliczonymi w czasie, który jest większym wielomianem niż dostępna maszyna PH). Najtrudniejsze jest to, w jaki sposób symulujesz „związany” przypadek problemu wyroczni (gdzie f jest bliskie transformacie Fouriera g)? Tj. W jaki sposób zapewniasz małe obwody dla takich f i g, które nie „oddają całej gry”? (Podobny problem występuje z problemem Simona.)

— Scott Aaronson

Scott Aaronson może być najlepszą osobą na świecie, która odpowie na to pytanie, być może będzie miał lepszą odpowiedź po opublikowaniu tego pytania. zaproponował oryginalny problem, na który to pytanie wydaje się być bardzo niewielkim wariantem, tak zwany problem sprawdzania Fouriera (więcej na ten temat w komentarzach). problem jest ściśle związany / prawie równoważny z oddzieleniem dwóch ważnych klas złożoności PH i BQP, co jest kluczowym otwartym problemem teorii złożoności QM i przypuszczalnie jest bardzo trudne. nie wydaje się, że wiele bezpośrednich / dalszych badań nad tym problemem zostało do tej pory przeprowadzonych przez kogokolwiek innego niż Aaronson, a może nawet on (ma najwyraźniej niewiele ponad 2 lata).

jednak tutaj jest co najmniej jeden artykuł autorstwa kogoś innego niż Aaronson, który koncentruje się / opiera się na przypuszczeniu / problemie z pewnymi nowymi wynikami.

Wykładnicze przyspieszenia są generyczne przez Fernando GSL Brandão i Michała Horodeckiego

W naszym artykule [4] uogólniamy problem sprawdzania Fouriera [1] i pokazujemy, że transformacja Fouriera, zarówno w definicji problemu, jak i rozwiązującym go algorytmie kwantowym, może zostać zastąpiona dużą klasą obwodów kwantowych. Obejmują one zarówno transformatę Fouriera nad dowolną (ewentualnie nie-abelową) grupą skończoną, jak i prawie każdy wystarczająco długi obwód kwantowy z naturalnego rozkładu na zbiorze obwodów kwantowych. Otrzymujemy wykładnicze separacje kwantowej i postselected klasyczne złożoność zapytań dla wszystkich takich obwodów.

— vzn
źródło

B Q P ⊈ P H

$BQP\nsubseteq PH$