vs?

Centralnym problemem teorii złożoności jest zapewne vs . $P$ $NP$

Ponieważ natura jest kwantowa, bardziej naturalne wydaje się rozważenie klas (tj. Problemów decyzyjnych rozwiązanych przez komputer kwantowy w czasie wielomianowym, z prawdopodobieństwem błędu co najwyżej 1/3 dla wszystkich instancji) i (ekwiwalent kwantowy z ) zamiast. $BQP$ $QMA$ $NP$

Moje pytania:

1) Czy rozwiązanie problemu vs dałoby rozwiązanie vs ? $P$ $NP$ $BQP$ $QMA$

2) Czy trzy bariery relatywizacji, dowodów naturalnych i algebriacji dotyczą również problemu vs. ? $BQP$ $QMA$

cc.complexity-theory complexity-classes quantum-computing

— Anthony Leverrier
źródło

1) Żadna implikacja nie jest znana w żadnym kierunku. Wiemy, że P = NP oznacza P = PH. Ale nie wiemy, czy BQP i QMA są w PH, więc może P może równać się NP, ale BQP i QMA nadal nie zawalą się. (Z drugiej strony zauważmy, że QMA⊆PP⊆P ^#P , więc na pewno P = P ^#P oznaczałoby BQP = QMA.) Wykazanie, że BQP = QMA implikuje P = NP, wydaje się jeszcze bardziej beznadziejne w obecnym stanie wiedzy .

2) Oczywiście, wszystkie trzy bariery obowiązują z pełną siłą w stosunku do BQP vs. QMA (a nawet do „łatwiejszego” problemu udowodnienia P ≠ PSPACE). Po pierwsze, w odniesieniu do wyroczni PSPACE (lub nawet niskiego stopnia rozszerzenia wyroczni PSPACE) mamy

P = NP = BQP = QMA = PSPACE,

z pewnością potrzebne będą techniki nierelatywizujące i niealgebryzujące, aby oddzielić którąkolwiek z tych klas. Po drugie, aby uzyskać naturalną barierę dowodową dla umieszczania rzeczy poza BQP, wszystko czego potrzebujesz to rodzina funkcji pseudolosowych, którą można obliczać w BQP, co jest formalnie słabszym wymaganiem niż rodzina funkcji pseudolosowych obliczalna w P.

Dodatek: Pozwól, że powiem coś o „metakwestii”, o którą nie pytałeś, ale sugerowałeś, dlaczego ludzie nadal koncentrują się na P vs. NP, chociaż uważamy, że Natura jest kwantowa. Osobiście zawsze widziałem P vs. NP jako „sztandarowy” dla całej gamy pytań barierowych w teorii złożoności (P vs. PSPACE, P vs. BQP, NP vs. coNP, NP vs. BQP, istnienie funkcji jednokierunkowych itp.), brakna które wiemy, jak odpowiedzieć i z których wszystkie są powiązane w tym sensie, że jakikolwiek przełom z jednym prowadziłby do przełomów z innymi (nawet jeśli nie mamy formalnych implikacji między pytaniami, co w wielu przypadkach robić). P vs. NP nie jest z natury bardziej fundamentalny niż jakikolwiek inny - ale jeśli musimy wybrać jedno pytanie, które będzie służyć za dziecko złożoności plakatu, to jest to dobry wybór.

— Scott Aaronson
źródło

Cześć Scott, wielkie dzięki za tę wspaniałą odpowiedź! A twój aneks dotyczy dokładnie tego, co miałem na myśli.

— Anthony Leverrier

Przypuszczam, że znaczenie P vs. NP, jako „sztandarowego” problemu teorii złożoności, wskazuje coś na temat historii teorii obliczeń. Po logikach wydaje się, że to kombinatorycy zajmowali się tym tematem z największym zainteresowaniem. Być może gdyby zamiast tego teoretycy operatorów opracowali teorię złożoności, sztandarowym problemem „twardości” nie byłaby logiczna satysfakcja, 3-zabarwienie lub problem podróżnego sprzedawcy, ale problem ustalenia, czy suma k-lokalnych pozytywnych operatorów półfinałów jest pozytywnie określony. (Co oczywiście oznacza k-QSAT.)

— Niel de Beaudrap,

Tak, myślę, że dopóki potrzebne są nowe techniki dla każdego takiego problemu (P vs NP, BQP vs QMA itp.), Nie za bardzo boli koncentrowanie się na jednym konkretnym problemie.

— Anthony Leverrier,

Dodatkowy komentarz - jeśli weźmiesz pod uwagę obliczenia kwantowe jako definicję wykonalnego obliczenia, prawdopodobnie spojrzałbyś na BQP vs NP jako główne pytanie, a nie na BQP vs QMA. Powodem jest to, że NP wciąż przechwytuje ogromną część pytań, które chcemy rozwiązać (lub chcemy pozostać twardymi wobec krypto), niezależnie od tego, czy spróbujemy je rozwiązać za pomocą komputera klasycznego czy kwantowego.

— Boaz Barak

@ Boaz - Czy uważasz, że problemy NP są z natury bardziej istotne niż problemy QMA, czy wydaje się, że tak jest obecnie, ponieważ jesteśmy bardziej przyzwyczajeni do myślenia w kategoriach problemów klasycznych niż kwantowych?

— Anthony Leverrier