Problemy bez znanej przewagi kwantowej

Zastanawiałem się, jaka jest lista obecnych naturalnych problemów obliczeniowych, dla których nie ma znanej przewagi złożoności przy użyciu komputera kwantowego.

Na początek, myślę, że obliczenie odległości edycji jest tym, dla którego najszybszy znany algorytm kwantowy wydaje się być najszybszym znanym klasycznym. Mówiąc bardziej wstępnie, sugerowałbym również sortowanie jako kolejny problem, dla którego nie jest znane przyspieszenie kwantowe (w porównaniu do najszybszego znanego algorytmu pamięci RAM słowa jednostkowego).

Chociaż nie chcę ustanawiać twardego ograniczenia, jestem szczególnie zainteresowany problemami w NP i / lub problemami bez znanego skutecznego klasycznego rozwiązania.

Zgodnie z sugestią Juana Bermejo Vegi, oto dalsze wyjaśnienia. Interesują mnie problemy w NP, dla których obecnie nie ma żadnej znanej dużej przewagi złożoności czasu jeśli używasz komputera kwantowego. $O$

Nie skupiam się na przypadkach, w których możemy udowodnić, że nie może być przewagi, ani nie koncentruję się na przyspieszeniach wykładniczych (tzn. Wielomian byłby również w porządku). Jak dotąd wydaje się, że jedynymi dwoma przykładami są te w moim pytaniu, co wydaje się bardzo zaskakujące, jeśli to naprawdę prawda.

ds.algorithms quantum-computing big-list

— Lembik
źródło

Przewaga złożoności, ponieważ nie przyspiesza ogólnego czasu działania lub że klasa językowa jest zamknięta w ramach operacji?

— Ryan

@ Ryan Nie miałem na myśli przyspieszenia ogólnego czasu pracy. Dziękuję za pytanie.

— Lembik

Wszystko już czas wielomianowy. :-)

— kasterma

@kasterma Nie sądzę, żeby to było poprawne. Istnieje wiele problemów z czasem wielorakim, dla których obecnie występuje przyspieszenie kwantowe.

— Lembik

Proponuję uściślić to pytanie, określając, czy (a) chodzi o „brak możliwej do udowodnienia przewagi kwantowej” kontra „brak znanej przewagi kwantowej”; czy (b) pytanie dotyczy przyspieszeń wykładniczych lub wielomianowych (w odniesieniu do problemów nie w P ani BPP); oraz czy (c) dozwolone są inne rodzaje przyspieszeń (np. przyspieszenia logarytmiczne w stosunku do problemów w obrębie P lub BPP).

— Juan Bermejo Vega

Odpowiedzi:

Nie dotyczy to NP, ale sortowania na podstawie porównania. dolna granica jest informacja teoretycznie. $\Omega(n \log n)$

— Tyson Williams
źródło

Związana z tym teoria informacji nie pokazuje, że algorytmy kwantowe nie mogą jej przebić.

$\:$ (Rozważ algorytm Grovera ).

$\;\;\;\;$

@RickyDemer Nie jestem pewien, co myślisz. Teoretyczne argumenty informacyjne są niezależne od modelu obliczeń. W przypadku wyszukiwania nieustrukturyzowanego wejściem jest tablica

zawierająca

elementów i element docelowy

, a wynikiem jest indeks

taki, że

(który, jak zakładam, istnieje dla uproszczenia). Ponieważ jeden bit jest dowiedzieliśmy z każdego zapytania, teoria informacji mówi, że każdy algorytm musi

zapytań. Algorytm Grovera przy

A

$A$

n

$n$

x

$x$

i

$i$

A [i] = x

$A[i] = x$

\log n

$\log n$

zapytania, są dalekie od ścisłego trzymania się tej granicy, niech będą mniejsze niż to.

Θ (\sqrt{n})

$\Theta(\sqrt{n})$

— Tyson Williams

O ile rozumiem, argumenty oparte na entropii / liczeniu nie mają natychmiastowego zastosowania dla algorytmów kwantowych, ponieważ dotyczą rozkładów prawdopodobieństwa, a nie superpozycji stanów kwantowych. Na przykład

wyszukiwanie dolnej granicy było na przykład dokumentem FOCS autorstwa Ambainisa, a sortowanie dolnej granicy również wymaga trochę pracy arxiv.org/abs/quant-ph/0102078 . Wygląda więc na to, że twoje roszczenie jest prawidłowe, ale nie tak bezpośrednie, jak sugerujesz.

Ω (\log n)

$\Omega(\log n)$

— Sasho Nikolov

@SashoNikolov Problem wyszukiwania nieustrukturyzowanego, tak jak to zdefiniowałem dla Ricky'ego, nie zapewniał opcji niepowodzenia. Argument, który podałem, dotyczy tego problemu. Dolna granica podana przez Ambainis w FOCS (której nie udało mi się znaleźć) dotyczy prawdopodobnie bardziej ogólnego problemu, który wymaga tylko jednego sukcesu z małym prawdopodobieństwem. To samo dotyczy problemu sortowania i papieru arXiv, do którego linkujesz.

— Tyson Williams

n

$n$

n

$n$

Ostatnio ten artykuł w SODA 2018 pokazuje algorytm stałej aproksymacji współczynnika edycji odległości w komputerach kwantowych z czasem subkwadratowym. Zauważ, że nie jest jeszcze znany algorytm aproksymacji współczynnika stałego dla odległości edycji w klasycznych komputerach z czasem subkwadratowym. Ponadto uważa się, że takiego algorytmu nie ma w klasycznych komputerach.

— Mohemnist
źródło

Nie sądzę, aby ostatnie zdanie było poprawne. Klasyczne rozwiązanie o tej samej złożoności nie ma konsekwencji złożoności.

— Lembik

@Lembik Miałeś rację. Papier jakoś de-quantumized poprzednią papier i znalazł algorytm aproksymacji czynnik stały do edycji odległości w subquadratic czasu złożoności. Zobacz ten post na blogu, aby uzyskać więcej informacji.

— Mohemnist