Czy istnieje kwantowy odpowiednik twierdzenia o hierarchii czasu?

Moim ulubionym twierdzeniem w teorii złożoności jest twierdzenie o hierarchii czasu. Dokonano tego jednak w 1965 r.

Chciałem wtedy wiedzieć, czy jest coś podobnego do obliczeń kwantowych.

Jeśli nie, to jakie osoby / grupy pracują w tym kierunku!

Najnowszym cytatem na temat twierdzeń o hierarchii czasu jest „Ogólna hierarchia czasu dla modeli semantycznych z jedną radą” Dietera van Melkebeeka i Konstantina Pervysheva, które można uzyskać ze strony internetowej Dietera. Tamte techniki dają hierarchię czasu z 1 bitem porady na temat „każdego rozsądnego” semantycznego modelu obliczeń, w tym algorytmów kwantowych.

Ponadto normalnie stosunkowo łatwo jest uzyskać hierarchię dla problemów związanych z obietnicą obliczanych przez modele semantyczne. Problem z obietnicą wymaga tylko algorytmu, aby „zachowywał się ładnie” (np. Miał ograniczony błąd) na niektórych danych wejściowych - tych, które zostały wybrane jako część problemu z obietnicą. W przypadku danych wejściowych, które nie zostały wybrane jako część obietnicy, algorytm może zachowywać się arbitralnie (np. Nie mieć ograniczonego błędu). Hierarchia problemów związanych z obietnicą jest wynikiem folkloru; dowód na ustawienie BPP znajduje się w „Wyniki hierarchii kosmicznej dla randomizowanych i innych modeli semantycznych” autorstwa Dietera van Melkebeka i Jeffa Kinne (ja), które można uzyskać ze strony Dietera lub mojej strony internetowej. Powinno to dotyczyć również algorytmów kwantowych.

Tak więc odpowiedź brzmi: przyzwoite twierdzenia dotyczące hierarchii są znane dla algorytmów kwantowych, które albo otrzymują 1 bit porady, albo mogą ignorować problematyczne dane wejściowe. Niektóre techniki tych wyników opierają się na właściwościach algorytmów losowych. Interesujące byłoby spróbowanie wykorzystania właściwości algorytmów kwantowych w obszarze twierdzeń hierarchicznych.

Nieco powiązany obszar, w którym istnieją wyniki specyficzne dla algorytmów kwantowych, to obszar dolnych granic czasoprzestrzeni. Istnieje ankieta Dietera van Melkebeeka: „Badanie dolnych granic satysfakcji i powiązanych problemów”.

Odpowiedź brzmi nie. Nie mamy nawet twierdzenia o hierarchii czasu dla probabilistycznego wielomianowego czasu błędu ograniczonego (tj. BPTIME). Twierdzenia o deterministycznej i niedeterministycznej hierarchii czasu zawierają argument przekątny, który wydaje się nie działać w przypadku klas semantycznych. Dlatego nie mamy silnych twierdzeń hierarchicznych dla klas semantycznych.

Najlepszy wynik, jaki znam, to twierdzenie o hierarchii dla BPTIME z 1 małą radą: Fortnow, L .; Santhanam, R. (2004). Twierdzenia o hierarchii dla probabilistycznego czasu wielomianowego .

Nie znam żadnych grup pracujących nad twierdzeniem o kwantowej hierarchii czasu. Sądzę, że dzieje się tak, ponieważ wydaje się, że problem hierarchii BPTIME jest łatwiejszy, dlatego badacze zaatakowaliby ten problem.

(Nieco powiązane pytania: Czy istnieje charakterystyka składniowa dla BPP, BQP lub QMA? Na MathOverflow i Semantic vs. Syntactic Complexity Classes na cstheory.)

Niedeterministycznymi kwantowymi klasami związanymi z czasem i przestrzenią są te, w których językami są zestawy ciągów akceptowanych przez kwantowe maszyny Turinga działające w odpowiednich granicach z niezerowym prawdopodobieństwem.

W rozdziale 8 „ udowodnienia potęgi ponownej selekcji ” pokazujemy, że istnieją ścisłe hierarchie dla niedeterministycznych kwantowych klas związanych z czasem i przestrzenią.