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

27

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

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ę?

glS
źródło
Powiedziałbym, że odpowiedź brzmi „nie”, jeśli ograniczysz problemy jako problem decyzyjny , ponieważ istnieją problemy z próbkowaniem (np. BosonSampling i IQP), dla których wykazano wykładniczą przewagę kwantową (a raczej udowodniono przy silnych założeniach). Mogą istnieć inne, których nie znam.
glS
Zwróć uwagę, że istnieje już wiele klasycznych algorytmów kosztów podwykonawczych dla faktoringu. (Istnieje znaczna różnica między kosztami wielomianowymi a wykładniczymi.)
Squeamish Ossifrage
Jak mówi Heather, obecnie nie jest to znane, ponieważ granice klasycznych (i kwantowych) komputerów nie są znane. Kryteria określone w pytaniu ostatecznie wymagają od osoby odpowiadającej nawet wyjścia poza udowodnienie związku poza P i NP. Sugeruję przeredagowanie pytania, aby poprosić o inne prawdopodobne przykłady (a także faktoring).
Toby Hawkins
2
Te praktyczne konsekwencje SpeedUp kwantowej, np za czy algorytm Shor może rzeczywiście przewyższają klasyczne GNFS, nie są też koniecznie implikowane przez asymptotyczne stosunków krzywych wzrostu kosztów. Zobacz tę odpowiedź, aby dowiedzieć się więcej o ustawieniu asymptotycznym vs. konkretnym i dlaczego pytania wokół P = NP są trochę czerwonym śledztwem dla kryptografii i praktycznych porównań wydajności.
Squeamish Ossifrage
1
O(n1235436546)O(n3)
Dyskretna jaszczurka

Odpowiedzi:

9

f:F2nF2ns{0,1}nf(x)=f(y)x+y=ss=0fsf(x)=f(x+s)x2=0f

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?

ffp

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(nTf(n)+G(n))Tf(n)fnG(n)n×nF2

f2n/42n/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.

Squeamish Ossifrage
źródło
1
BQPBPP
@glS Dodałem zdanie, które moim zdaniem powinno przejść do sedna różnicy. To pomaga?
Squeamish Ossifrage,
12

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×NAbq

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

Emily Tyhurst
źródło
5

BPPOBQPO

tparker
źródło
2
2

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.

piramidy
źródło