Jeśli P = BQP, oznacza to, że PSPACE (= IP) = AM?

Ostatnio Watrous i wsp. Udowodnili, że QIP (3) = PSPACE to niezwykły wynik. Był to dla mnie zaskakujący wynik, co wywołało u mnie myśl ...

Zastanawiałem się, czy komputery kwantowe mogłyby być skutecznie symulowane przez komputery klasyczne. Czy może to być PO PROSTU związane z podziałem między IP a AM? Mam na myśli to, że IP charakteryzuje się wielomianową liczbą rund klasycznej interakcji, podczas gdy AM ma 2 rundy klasycznej interakcji. Czy symulowanie obliczeń kwantowych może zmniejszyć interakcję IP z wielomianu do stałej wartości?

Świetne pytanie! Krótka odpowiedź: nie jest znana żadna implikacja taka jak ; ale to nie znaczy, że nie warto próbować udowodnić ...

Powiedziałbym jednak, że znalezienie takiej implikacji wydaje się mało prawdopodobne. Myślę, że przesłanie teorii kwantowej złożoności jest takie, że chociaż komputery kwantowe nie są wszechstronnym panaceum na rozwiązywanie trudnych problemów, mogą być w pewnych szczególnych okolicznościach znacznie mocniejsze niż klasyczne komputery.

Na przykład w złożoności zapytań algorytmy kwantowe mogą skutecznie rozwiązywać niektóre problemy, których klasyczne nie są w stanie, gdy obiecuje się, że dane wejściowe będą przestrzegane jakiejś ładnej globalnej struktury. Na przykład algorytm Shora opiera się na algorytmie umożliwiającym szybkie znalezienie nieznanego okresu funkcji, która ma być okresowa. Z drugiej strony kwantowe algorytmy kwerendy nie są o wiele silniejsze niż klasyczne do rozwiązywania problemów, w których nie zakłada się specjalnej struktury na wejściu. (Patrz Buhrman i de Wolfa badania na złożoność zapytań o ten ostatni punkt).

Podobnie myślę, że wyniki mówią nam, że nie interakcja jest nieoczekiwanie słaba (nawet jeśli P = B Q P ), ale że obliczenia kwantowe są nieoczekiwanie silne, szczególnie w kontekście interakcji z niepowiązanymi obliczeniowo dowodami.$\mathsf{QIP}(3) = \mathsf{QIP} = \mathsf{IP}$$\mathsf{P} = \mathsf{BQP}$

Zgadzam się z tym, co napisał Andy i chciałem, aby ta „odpowiedź” była komentarzem do jego odpowiedzi, ale najwyraźniej jest zbyt długa na komentarz…

W każdym razie pomocne może być powiedzenie czegoś więcej o tym, jaki aspekt obliczeń kwantowych (lub może informacja kwantowa) pozwala na udowodnienie ograniczenia PSPACE w QIP (3). Znane dowody tego ograniczenia nie wynikają ze zdolności weryfikatora do obliczania funkcji, które okazały się kwantowym obliczeniem czasu wielomianowego. Bardziej dokładnym wyjaśnieniem jest to, że dowody wykorzystują określone sposoby, w jakie łowca może manipulować splątanymi stanami kwantowymi, które dzieli z weryfikatorem. Gdyby łowca nie był w stanie manipulować informacją kwantową lub mógłby w magiczny sposób manipulować wspólnymi stanami splątanymi w sposób silniejszy niż pozwala na to teoria informacji kwantowej, dowody nie działałyby.

Tak więc, moim zdaniem, ograniczenie PSPACE w QIP (3) nie mówi nic o związku między AM a PSPACE.

Odpowiedzi Johna Watrousa i Andy'ego Druckera są doskonałe do zrozumienia niektórych związanych z tym problemów.

$P = BQP$$PH$$PSPACE \supseteq PH \supset\neq AM$

$IP = PSPACE$

[1] L. Fortnow i J. Rogers. Ograniczenia złożoności obliczeń kwantowych . Journal of Computer and System Sciences, 59 (2): 240-252, 1999. Wydanie specjalne dla wybranych artykułów z 13. Konferencji IEEE na temat złożoności obliczeniowej. Dostępne również tutaj .

Pozostałe odpowiedzi są doskonałe i nie ma to na celu zastąpienia ani zaprzeczenia żadnej z nich, a jedynie zaoferowanie pewnej intuicji, dlaczego P = BQP niekoniecznie oznacza równość między kwantowymi i klasycznymi interaktywnymi systemami dowodowymi (dla ustalonych rund itp.). Wiemy jednak teraz, że QIP = IP dzięki pracy Jaina, Ji, Upadhyay i Watrousa, więc z pewnością nie próbuję twierdzić, że takie równości nigdy się nie zdarzają.

Jeśli przyjmiemy, że P = BQP, dowiadujemy się tylko o tym, na jakie problemy decyzyjne można odpowiedzieć za pomocą modeli kwantowych i klasycznych. To nie jest to samo, co sugerowanie, że modele są w rzeczywistości takie same. Główna różnica polega na tym, że komputery kwantowe mogą przetwarzać stany w superpozycji, co oznacza, że ​​ich wejście i wyjście nie musi być ograniczone do stanów klasycznych. Jest to bardzo ważna różnica między modelami kwantowymi i klasycznymi, ponieważ kwantowe dane wejściowe / wyjściowe umożliwiają zapytanie o wyroki z superpozycjami stanów klasycznych lub komunikowanie stanów kwantowych (które mogą potencjalnie mieć wykładnicze opisy klasyczne) między weryfikatorem a przysłowia. Rzeczywiście istnieją wyrocznie, które oddzielają BQP od P, a komunikacja kwantowa prowadzi do zmniejszonej złożoności komunikacyjnej dla wielu problemów. A zatem,

Z tego powodu pytanie, czy P = BQP nie jest decydującym czynnikiem, czy modele kwantowe i klasyczne są równe w sytuacjach, w których wykorzystuje się kwerendy komunikacyjne / oracle.