Problemy w BQP, ale przypuszczano, że są poza P

Aby uzyskać listę takich problemów, możesz spojrzeć na listę poprawy prędkości wielobiegunowej w zoo algorytmu kwantowego (QAZ). Poniższa lista oparta jest na tym ( dokładne definicje i odniesienia znajdują się w QAZ . To kolejny sposób na powiedzenie, że nawet nie udaję, że rozumiem wiele problemów z tej listy!)

Problemy algebraiczne i teoretyczne

Jeśli się nie mylę, wszystkie problemy wymienione przed problemem ukrytej podgrupy Abelian są tego szczególnym przypadkiem.

Faktoryzacja
Dyskretny logarytm
Równanie Pella . Faktoring sprowadza się do równania Pell.
Główny ideał Idealny problem. Równanie Pella ogranicza się do tego problemu, który jest co najmniej tak trudny jak faktoring.
Problem grupy jednostek
Problem z grupą klas
Szacunek sumy Gaußa
Elementy macierzowe reprezentacji grupowych
Zamówienie grupowe i członkostwo
Problem ukrytej podgrupy Abelian
Niektóre (ale nie wszystkie) problemy z ukrytymi podgrupami niebędącymi abelami
Niektóre (ale nie wszystkie) problemy wyrażone jako specjalne przypadki ukrytego przesunięcia
Niektóre (ale nie wszystkie) problemy z ukrytymi strukturami nieliniowymi
Poznawanie niektórych wykresów (spawane drzewa)
Grupowy izomorfizm dla Abelian i niektórych grup nie-Abelowych
Znajdź niektóre właściwości skończonych pierścieni i ideałów

Zbliżenie i symulacja

Symulacja kwantowa. Oczywiście -Complete $BQP$
Obliczanie niektórych niezmienników węzłów, w tym wielomianu HOMFLY, którego szczególnym przypadkiem jest wielomian Jonesa. Niektóre z nich są -Complete $BQP$
Obliczanie niektórych niezmienników trójdzielnych. Niektóre z nich są . $BQP$
Szacowanie termodynamicznej funkcji podziału niektórych klasycznych układów
Obliczanie Zeta Funkcje na skończonych polach
Ciąg przepisywanie problemem jest -Complete $\mathit{PromiseBQP}$
aproksymowanie elementów macierzy mocy wykładniczo dużych macierzy rzadkich.

Algorytm, którego tak naprawdę nie rozumiem.

Są to przede wszystkim algorytmy gdzie QAZ zastrzega superpolynomial wzrost, ale nie rozumiem, dlaczego oryginalny problem ma być z . To powiedziawszy, założę się dużo pieniędzy na to, że QAZ ma rację, a ja się mylę. $P$

Dopasowanie wzorca dla wystarczająco dużych ( ) wzorców $>\log(n)$
Niektóre problemy z układem liniowym, w ale z algorytmem kwantowym , jeśli układ liniowy podano jako wyrocznię. $P$ $\mathrm{polylog}$
opór elektryczny wykresu, ma algorytm kwantowy , jeśli obwód elektryczny jest podany jako wyrocznia $\mathrm{polylog}$
Problem z licznikami masy. Coś związanego z funkcjami kodu i partycji, ale nie rozumiem o co chodzi.

$P$ problemy 1. okazały się być w a następnie w $BQP$ $P$

Oto niektóre problemy, w których skuteczny algorytm kwantowy został opublikowany przed klasycznym. Innymi słowy, kiedyś przypuszczano, że są w ale nie w , ale ta hipoteza jest teraz nieważna. $BQP$ $P$

Spełniając więcej niż (ale mniej niż ) ograniczenia problemu Max E3LIN2. Jak zauważył Juan Berego Vega w komentarzach: istnieje teraz klasyczny algorytm dla , który był motywowany przez wynik kwantowy. ( Blog post na ten wynik , papier 1 , paper2 ) $(\tfrac12-\tfrac{\text{constant}}{D})N$ $\left(\tfrac12-\tfrac{1}{22D^{3/4}}\right)N$ $(\tfrac12-\tfrac{\text{constant}}{\sqrt{D}})N$
Systemy rekomendacji ( więcej szczegółowych wyjaśnień na blogu Scotta Aaronsona ). System rekomendacji - à la Netflix / Amazon / itp. może być postrzegana jako wypełnienie rzadki macierz niskiej rangi bardzo niekompletnych danych. Znany klasyczny algorytm, w którym wielomian , ad . Jeśli matryca jest podana jako wyrocznia, Iordanis Kerenidis i Anupam Prakash znaleźli algorytm kwantowy w 2016 r. ( Artykuł $m×n$ $k$ $m$ $n$ $k$ $\mathrm{poly}(k)\mathrm{polylog}(mn)$ ). W 2018 r., Próbując udowodnić, że skalowanie jest niemożliwe przy użyciu klasycznej maszyny, Ewin Tang znalazł klasyczny algorytm osiągający tę samą wydajność w tych samych warunkach (papier dostępny tutaj i tutaj ).

Frédéric Grosshans
źródło

To świetna odpowiedź! Jeden komentarz: Właśnie zauważyłem, że wpis QAZ dotyczący przyspieszenia Max E3LIN2 nie jest aktualny z powodu niedawnego postępu w klasycznych algorytmach [1 ], [2 ], [3 ]; Obawiam się, że nie wiemy, czy w chwili pisania istnieje przyspieszenie wielobiegunowe dla tego problemu.

Juan Bermejo Vega

@JuanBermejoVega: Zredagowałem odpowiedź, aby wziąć pod uwagę twój komentarz

Frédéric Grosshans

W ostatnim punkcie pocisku, constrant stała .

$\:$

\mapsto

$\mapsto$

$\:$

$\;\;\;\;$

Jedna aktualizacja: teraz Zoo również jest pod tym względem aktualne, por. „Jednak efektywny klasyczny algorytm osiągający jeszcze lepszy współczynnik aproksymacji (w rzeczywistości stosunek aproksymacji nasycający granicę wyznaczoną przez twardość aproksymacji) został później odkryty [260]. Obecnie moc kwantowych algorytmów optymalizacji przybliżonej w stosunku do klasycznej algorytmy pozostają niejasne i są aktywnym obszarem badań. ”

Juan Bermejo Vega

FYI (1) Myślę, że wszystkie twierdzenia o „kompletności BQP” są w rzeczywistości technicznie PromiseBQP-kompletnością. Wierzę, że jest otwarte, czy BQP ( nie PromiseBQP) ma jakieś kompletne problemy, ponieważ BQP jest klasą semantyczną, i pamiętam, że widziałem wyrocznie idące w obie strony w tej kwestii. (2) Myślę, że rzecz algebry liniowej polega na tym, że układy liniowe nxn „b / c” uważamy, że zajmuje czas, nawet jeśli system jest ci dany jako wyrocznia, i jest to wykładniczo więcej niż wymagany czas polilogu do przybliżenia zasięgu na komputerze kwantowym.

n^{ω}

$n^\omega$

Joshua Grochow

Problemy w BQP, ale przypuszczano, że są poza P

Odpowiedzi:

Problemy algebraiczne i teoretyczne

Zbliżenie i symulacja

Algorytm, którego tak naprawdę nie rozumiem.

PPP problemy 1. okazały się być w a następnie wBQPBQPBQPPPP

$P$ problemy 1. okazały się być w a następnie w $BQP$ $P$