Czy istnieją opisowe reprezentacje złożoności kwantowych klas złożoności?

Tytuł mniej więcej mówi wszystko, ale myślę, że mógłbym dodać trochę tła i kilka konkretnych przykładów, którymi jestem zainteresowany.

Teoretycy złożoności opisowej, tacy jak Immerman i Fagin, scharakteryzowali wiele najbardziej znanych klas złożoności za pomocą logiki. Na przykład NP można scharakteryzować za pomocą zapytań egzystencjalnych drugiego rzędu; P można scharakteryzować za pomocą zapytań pierwszego rzędu z dodanym operatorem najmniej ustalonego punktu.

Moje pytanie brzmi: czy były jakieś próby, szczególnie udane, wymyślenia takich reprezentacji dla klas złożoności kwantowej, takich jak BQP lub NQP? Jeśli nie, dlaczego nie?

Dziękuję Ci.

Aktualizacja (moderator) : odpowiedź na to pytanie jest całkowicie udzielona na mathoverflow .

cc.complexity-theory quantum-computing descriptive-complexity

— Philip White
źródło

patrz pytanie Kaveha

— Alessandro Cosentino

zamknąć jak duplikat?

— Suresh Venkat,

Dla tych, którzy zastanawiają się, dlaczego to pytanie zostało zamknięte jako nie na temat (jak ja): Zignoruj bliski powód, ponieważ jest on bez znaczenia (o ile dotyczy tego pytania). Zamknięcie pytania wymaga jednego z kilku powodów. „Dokładny duplikat” byłby odpowiednim powodem, ale system nie pozwala nam zamknąć pytania jako dokładnego duplikatu pytania w MathOverflow. Dlatego myślę, że Suresh losowo wybrał jedną z dostępnych przyczyn.

— Tsuyoshi Ito,

ps: Myślę, że rozsądne może być rozważenie tych przypadków w sposób podobny do krzyżowania postów i nie zamykanie ich. Ktoś (np. OP) publikuje odpowiedź CW na podstawie (lub tylko link do) odpowiedzi na MO.

— Kaveh

Ponownie otworzyłem pytanie.

— Ryan Williams,

Odpowiedzi:

Myślę, że odpowiedź jest Robins do mojego pytania o MO odpowiada również ten.

Opisowe złożoność charakterystyka klasa złożoności daje język, którego zapytań (tj wzorów) są dokładnie takie funkcje obliczalne w . Składnia języka jest zwykle bardzo prosta, tzn. Biorąc pod uwagę ciąg łatwo jest sprawdzić, czy jest poprawnie sformułowanym zapytaniem języka, przynajmniej oczekuje się, że będzie rozstrzygalne (ale zwykle sprawdzenie składni można wykonać w mała klasa złożoności). Wiązałoby się to skuteczne enumerablity problemów w klasie i dałoby składniowej charakteryzację dla . (Jeśli złożoność sprawdzania składni jest niska, może to również sugerować istnienie pełnego problemu dla klasy.) $C$ $C$ $q$ $q$ $C$ $C$

W powyższych komentarzach Robin powiązał artykuł Korda Eickmeyera i Martina Grohe'a „ Randomizacja i derandomizacja w teorii złożoności opisowej ”, który daje charakterystykę pod względem „złożoności opisowej” . Sami autorzy zauważają we wstępie, że różni się to od tego, co zwykle oznacza opisowa charakterystyka złożoności: $BPP$

Udowadniamy, że , probabilistyczna wersja logiki stałoprzecinkowej z liczeniem, przechwytuje klasę złożoności , nawet w strukturach nieuporządkowanych. W przypadku struktur uporządkowanych wynik ten jest bezpośrednią konsekwencją twierdzenia Immermana-Vardiego [7, 8], a dla struktur arbitralnych wynika z obserwacji, że możemy zdefiniować losowy porządek z dużym prawdopodobieństwem w BPIFP + C. Mimo to wynik jest zaskakujący na pierwszy rzut oka ze względu na podobieństwo do otwartego pytania, czy istnieje logika przechwytująca , oraz ponieważ uważa się, że . polega na tym, że logika $BPIFP+C$ $BPP$ $P$ $P = BPP$ $BPIFP+C$ nie ma skutecznego składni, a zatem nie jest „logika” według Gurevich [9] Definicje leżącej na pytanie z logiką, który przechwytuje . $P$ Niemniej jednak uważamy, że daje całkowicie odpowiedni opis klasy złożoności , ponieważ definicja jest również z natury nieskuteczna (w przeciwieństwie do definicji pod względem rozstrzygalnego zestawu wielomianowo taktowanych maszyn Turinga). $BPIFP+C$ $BPP$ $BPP$ $P$

Nie jestem ekspertem od teorii modeli skończonych / złożoności opisowej (i osobiście chciałbym usłyszeć więcej od ekspertów), ale mam wrażenie, że jest tu trochę oszustwa, mówiąc, że jest to opisowa charakterystyka złożoności. Powodem mojego odczucia jest to, że jeśli pozwolimy sobie na nieefektywną składnię, możemy zastosować dowolne ograniczenia semantyczne, aby ograniczyć klasę dobrze sformułowanych zapytań i możemy nadać charakterystykę „złożoności opisowej” dowolnej klasie złożoności. Weźmy na przykład (który przechwytuje ), a następnie weź dokładnie te zapytania, które są obliczalne w ; lub rozważ język, który ma jeden symbol funkcji dla każdej maszyny w . Oba z nich przechwytują $SO(TC)$ $PSpace$ $BQP$ $BQP$ $BQP$ ale nie mają skutecznej składni.

— Kaveh
źródło

$\mathsf{P}$ $\sigma$ $\sigma$ $\sigma$ $M$ $\varphi$ $M$ $\varphi$ $\sigma$ $R_1,R_2,\ldots$

$\sigma$ $\sigma$ $\rho$ $\sigma$ $\rho$ . To jest moja wersja definicji 1 w artykule Eickmeyera-Grohe, do którego nawiązuje Robin Kothari. W szczególności słownictwo nie jest skończone (no cóż, każde słownictwo jest, ale musimy wziąć pod uwagę nieskończenie wiele różnych słowników), zestaw zdań tej logiki jest nierozstrzygalny, a pojęcie satysfakcji różni się od tego przedstawionego przez Gurewicza .

— Aaron Sterling
źródło