Jakie są konsekwencje ?

Shiva Kintali właśnie ogłosił (zimne!) Co powoduje, że izomorfizm wykres dla ograniczonych wykresach treewidth szerokości IS -hard $\geq 4$ $\oplus L$ . Nieformalnie moje pytanie brzmi: „Jak trudne to jest?”

Wiemy, że nierównomiernie , patrz odpowiedzi na to pytanie . Wiemy również, że jest mało prawdopodobne, aby , zobaczył odpowiedzi na to pytanie . Jak zaskakujące byłoby, gdyby ? Słyszałem, że wiele osób mówi, że nie byłoby szokujące jak . $NL \subseteq \oplus L$ $\oplus L = P$ $L=\oplus L$ $L=NL$ $P=NP$

Jakie są konsekwencje ? $L=\oplus L$

Definicja: jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko parzystą liczbę lub nieparzystą liczbę ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji) oraz który jest dodatkowo ograniczony do pracy w przestrzeni logarytmicznej. $\oplus L$

cc.complexity-theory complexity-classes logspace

— Aaron Sterling
źródło

Odpowiedzi:

Wigderson udowodnił, że . Według standardowych argumentów oznacza . (Weź maszynę w języku . Ma ona równoważną maszynę w . Weź język par instancji-porad . Jeśli ten język jest w , to po zapisaniu odpowiedniej porady otrzymujemy maszynę odpowiadającą ) $NL/poly \subseteq \oplus L/poly$ $L = \oplus L$ $L/poly = NL/poly$ $M$ $NL/poly$ $M'$ $\oplus L/poly$ $\oplus L$ $S = \{(x,a)~|~M'(x,a)~\textrm{accepts}\}$ $L$ $a$ $L/poly$ $M$

Myślę, że byłoby to zaskakujące: niedeterministyczne programy rozgałęziające byłyby równoważne deterministycznym programom rozgałęziającym (do czynników wielomianowych).

— Ryan Williams
źródło

(Wynik Widgerson został przejęty przez Nl / poli = UL / poli ).

Cóż, jeśli to symulacja obwodów stabilizatora jest w , ponieważ Aaronson i Gottesman (Physical Review A 70, 052328) udowodnili, że taka symulacja jest zakończona dla przy zmniejszeniu przestrzeni logów lub, co słabsze, że symulowanie sieci CNOT jest w . Równoważnie Jeżeli symulacja takich układów jest następnie . Osobiście uważałbym to za zaskakujące, ale nie w wyniku upadku z fotela uznałbym zaskakujące. $L=\oplus L$ $L$ $\oplus L$ $L$ $L$ $L = \oplus L$ $P=NP$

— Joe Fitzsimons
źródło

Dziękuję Ci. Czy istnieje intuicyjne wyjaśnienie, co mogą zrobić obwody stabilizujące? Nie znam ich.

— Aaron Sterling

@AaronSterling: Obwody stabilizujące są ograniczonym modelem obliczeń kwantowych; są one generowane przez bramki CNOT (odwracalnie obliczające XOR dwóch bitów wejściowych) i dwie bramki, które nie mają bezpośrednich analogów w obliczeniach klasycznych. Działając na „klasyczne” dane wejściowe (tak zwane obliczeniowe stany bazowe) lub na dane wejściowe, które są tylko nieco bardziej ogólne niż dane „klasyczne”, można je skutecznie symulować pod względem symplektycznych transformacji modulo 2, mimo że mają kwantowo mechaniczny smak ( i tylko nieznacznie boję się możliwości uniwersalności obliczeń kwantowych).

— Niel de Beaudrap 16.11.11

@AaronSterling: Są one podzbiorem wszystkich obwodów kwantowych, które obejmują CNOTS (zasadniczo XOR + fanout), a także szereg bramek kwantowych, które mogą tworzyć równe superpozycje (np. Bramki Hadamarda). Jeśli jesteś zaznajomiony z obliczeniami kwantowymi, wówczas obwody odpowiadają operatorom, które odwzorowują operatory Pauliego na inne operatory Pauliego w koniugacji, działając na podstawie danych klasycznych (lub danych wejściowych, które można uzyskać z danych klasycznych przez inny obwód grupy Clifforda).

— Joe Fitzsimons,

Myślę, że potrzebujemy hierarchii „niespodzianki” z „spadaniem z krzesła” na górze :)

— Suresh Venkat