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

Wikipedia wymieniła cztery problemy, które są w ale że są poza : Rozkład na czynniki całkowite; Dyskretny logarytm; Symulacja układów kwantowych; Obliczanie wielomianu Jonesa w pewnych korzeniach jedności.$BQP$$P$

Czy są jakieś inne takie problemy?

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 ).