Ograniczanie luki między kwantową a deterministyczną złożonością zapytań

Chociaż znane są wykładnicze separacje między złożonością kwantowych zapytań o ograniczonym ograniczeniu ( $Q(f)$ ) a złożonością deterministycznych zapytań ( $D(f)$ ) lub złożonością losowych zapytań o ograniczonym ograniczeniu ( $R(f)$ ), dotyczą one tylko niektórych funkcji częściowych. Jeśli funkcje cząstkowe mają jakieś specjalne struktury , są one również wielomianowo powiązane z $D(f) = O(Q(f)^9))$ . Jednak najbardziej martwię się o funkcje całkowite.

W klasycznej pracy wykazano, że $D(f)$ jest ograniczone przez $O(Q(f)^6)$ dla funkcji całkowitych, $O(Q(f)^4)$ dla funkcji sumy monotonicznej i $O(Q(f)^2)$ dla symetryczne funkcje sumaryczne. Jednakże, nie jest większa niż kwadratowe rozdzielania znane są ten rodzaj działania (to oddzielenie uzyskuje się przez $OR$na przykład). O ile rozumiem, większość ludzi przypuszcza, że ​​dla funkcji całkowitych mamy $D(f) = O(Q(f)^2)$ . W jakich warunkach udowodniono tę hipotezę (poza funkcjami symetrycznymi)? Jakie są najlepsze obecne ograniczenia złożoności drzewa decyzyjnego pod względem złożoności kwantowych zapytań dla wszystkich funkcji?

O ile mi wiadomo, ogólne granice, które określasz, są zasadniczo najlepiej znane. Zmiana wzoru lekko Midrijanis został pokazany związaną że , gdzie Q E ( f ) jest dokładny skomplikowania zapytanie kwantową F ; istnieją również ściślejsze granice znane w kategoriach błędu jednostronnego (patrz sekcja 6 tego dokumentu ).$D(f) = O(Q_E(f))^3$$Q_E(f)$$f$

Jeśli chodzi o bardziej szczegółowe, ale wciąż ogólne, klasy funkcji, istnieje artykuł Barnuma i Saksa, który pokazuje, że wszystkie funkcje jednorazowego odczytu zmiennych mają kwantową złożoność kwerend Ω ( $n$.$\Omega(\sqrt{n})$

Chociaż postęp ten był ograniczony, nastąpił znaczny postęp w ograniczaniu złożoności kwantowej kwerendy określonych funkcji; zobacz tę recenzję, aby poznać szczegóły (lub np. najnowszy artykuł Reichardta, który dowodzi, że najbardziej ogólna wersja granicy „przeciwnika” charakteryzuje złożoność kwantowych zapytań).

Podoba mi się odpowiedź Ashleya Montanaro, ale pomyślałem, że dołączę także zestaw funkcji, dla których znana jest hipoteza.

Zestaw funkcji, który jest często przedmiotem zainteresowania, to funkcje ze stałymi rozmiarami 1-certyfikatów. Ta klasa problemów obejmuje takie rzeczy, jak , odmienność, kolizja, wyszukiwanie trójkątów i wiele innych problemów (nie w rodzinie HSP), dla których wykazano, że mają separacje złożoności zapytań.$OR$

$f$$D(f) = O(Q(f)^2)$

Detale:

$x$$S \subseteq \{1,...,n\}$$y$$(\forall i \in S \quad y_i = x_i) \rightarrow f(y) = f(x)$$C_x(f)$$x$f ( x ) = $C_1(f) = \max_{x | f(x) = 1} C_x(f)$$f(x) = 0$

Możesz pokazać, że . Następnie można użyć algorytmu przedstawionego w Buhrman i de Wolfa badania , aby pokazać, że:$Q(f) \geq \sqrt{bs(f)} \geq 2C_0(f)/2^{C_1(f)} + 1$$D(f) \leq C_1(f)bs(f) \leq C_0(f)C_1(f)$

Jeśli ograniczymy uwagę do właściwości wykresu, możemy udowodnić nieco ulepszone granice w porównaniu z ogólnymi granicami, o których wspominasz:

W klasycznej pracy wykazano, że jest ograniczone przez dla funkcji sumarycznych, dla funkcji sumy monotonicznej i dla symetrycznych funkcji sumarycznych.O ( Q ( f ) 6 ) O ( Q ( f ) 4 ) O ( Q ( f ) 2$D(f)$$O(Q(f)^6)$$O(Q(f)^4)$$O(Q(f)^2)$

Po pierwsze, myślę, że ograniczenie 6. mocy można poprawić do 4. mocy właściwości wykresu. Wynika to z [1], gdzie pokazują, że jakakolwiek właściwość graf ma złożoność zapytania co najmniej , gdzie jest wielkością wejściową, która jest kwadratowa w liczbie wierzchołków. Oczywiście klasyczny złożoność zapytania jest co najwyżej .N $\Omega(N^{1/4})$$N$$N$

Czwarty limit mocy dla sumarycznych funkcji monotonicznych można poprawić do trzeciej mocy dla właściwości wykresu monotonicznego. Wynika to z niepublikowanej obserwacji Yao i Santha (wspomnianych w [2]), że wszystkie właściwości grafów monotonicznych mają złożoność kwantowych zapytań .$\Omega(N^{1/3}\log^{1/6}N)$

[1] Sun, X .; Yao, AC .; Shengyu Zhang, „Właściwości wykresu i funkcje kołowe: jak niska może być złożoność kwantowych zapytań?”, „Złożoność obliczeniowa, 2004. Postępowanie. 19. Doroczna konferencja IEEE, vol., Nr, str. 286,293, 21–24 czerwca 2004 r. Doi: 10.1109 / CCC.2004.1313851

[2] Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2005), „Algorytmy kwantowe dla problemu trójkąta”, Materiały szesnastego dorocznego sympozjum ACM-SIAM na temat algorytmów dyskretnych, Vancouver, Kolumbia Brytyjska: Society for Industrial and Applied Mathematics, s. 1109–1117, arXiv: quant -ph / 0310134.

W 2015 r. Poczyniono znaczne postępy w tej kwestii.

Po pierwsze, w arXiv: 1506,04719 [cs.CC] , autorzy poprawiły kwadratowego rozdzielania pokazując funkcji całkowitej z$f$

Z drugiej strony, w arXiv: 1512.04016 [quant-ph] wykazano, że kwadratowa zależność między kwantową a deterministyczną złożonością zapytania zachodzi, gdy dziedzina funkcji jest bardzo mała.