Czy istnieją problemy, w których wiadomo, że komputery kwantowe zapewniają wykładniczą przewagę?

Powszechnie uważa się i twierdzono, że komputery kwantowe mogą przewyższyć klasyczne urządzenia w przynajmniej niektórych zadaniach.

Jednym z najczęściej cytowanych przykładów problemu, w którym komputery kwantowe przewyższałyby klasyczne urządzenia, jest , ale z drugiej strony nie wiadomo również, czy faktoring można również skutecznie rozwiązać za pomocą klasycznego komputera (tj. Czy faktoring ∈ P ).$\text{Factoring}$$\text{Factoring}$$\text{Factoring}\in \text{P}$

W przypadku innych często cytowanych problemów, w których wiadomo, że komputery kwantowe zapewniają przewagę, takich jak wyszukiwanie w bazie danych, przyspieszenie jest tylko wielomianowe.

Czy znane są przypadki problemów, w których można wykazać (udowodnić lub udowodnić przy założeniu dużej złożoności obliczeniowej), że komputery kwantowe zapewniłyby wykładniczą przewagę?

$f\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$$s \in \{0,1\}^n$$f(x) = f(y)$$x + y = s$$s = 0$$f$$s$$f(x) = f(x + s)$$x$$2 = 0$$f$

Jaki jest koszt jakiegokolwiek przepisanego prawdopodobieństwa sukcesu, na klasycznym lub kwantowym komputerze, odróżnienia jednolitej losowej funkcji 1 do 1 od jednolitej losowej funkcji 2 do 1 spełniającej tę właściwość, jeśli każda opcja (1 do -1 lub 2 do 1) ma równe prawdopodobieństwo?

$f$$f$$p$

To jest scenariusz algorytmu Simona . Ma zastosowanie w ezoterycznych nonsensowny kryptoanalizy , ^* i to było wcześnie narzędziem w badaniu klas złożoności BQP i BPP i wczesną inspiracją dla algorytmu shor za.

$O(n + |f|)$$O(n \cdot T_f(n) + G(n))$$T_f(n)$$f$$n$$G(n)$$n \times n$$\mathbb F_2$

$f$$2^{n/4}$$2^{-n/2}$

$f$

Algorytm Deutsch-Jozsa służy jako ilustracja do podobnego nieco innym problemem sztucznej zbadania zajęcia różnej złożoności, P i EQP, dowiedzieć się, których szczegółowe rozwiązania pozostawiamy jako ćwiczenie dla czytelnika.

_{^* Szymon jest bezsensowny w kwestii kryptoanalizy, ponieważ tylko niepojętnie zdezorientowany idiota wprowadziłby swój tajny klucz do obwodu kwantowego przeciwnika, aby użyć go na kwantowej superpozycji danych wejściowych, ale z jakiegoś powodu robi plusk za każdym razem, gdy ktoś publikuje nowy artykuł na temat korzystania z algorytmu Simona łamać klucze idiotów za pomocą wymyślonego sprzętu, tak działają wszystkie te ataki. Wyjątek: jest możliwe, że może to złamać kryptografię białych skrzynek , ale historia bezpieczeństwa dla kryptografii białych skrzynek nawet przeciwko klasycznym przeciwnikom nie jest obiecująca.}

Nie jestem pewien, czy jest to dokładnie to, czego szukasz; i nie wiem, czy zakwalifikowałbym to jako „wykładnicze” (nie jestem też informatykiem, więc moja zdolność do analizy algorytmów w zasadzie nie istnieje ...), ale ostatni wynik Bravyi i in. przedstawili klasę „problemów z ukrytą funkcją liniową 2D”, które w sposób oczywisty zużywają mniej zasobów na kwantowym urządzeniu równoległym.

$N\times N$$A$$b$$q$

$\log{N}$$>7/8$

Dowód w istocie sprowadza się do tego, że konkretny stan wykresu jest trudny do symulacji przez klasyczny obwód, ten wynik podrzędny został udowodniony nieco wcześniej . Następnie reszta artykułu pokazuje, że większa klasa problemów zawiera ten trudny problem.

$\neq$

$\textbf{BPP}^O \neq \textbf{BQP}^O$ $\neq$

Chociaż nie mogę dostarczyć formalnego dowodu, uważa się, że symulacja (ewolucji czasowej) układu kwantowego jest takim przypadkiem: Nie ma lepszego sposobu na zrobienie tego na klasycznym komputerze niż w czasie wykładniczym, ale komputer kwantowy może trywialnie zrób to w czasie wielomianowym.

Idea takiego symulatora kwantowego (patrz także artykuł w Wikipedii ) polega na tym, jak po raz pierwszy zaproponowano komputery kwantowe.