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$ .

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 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.