Czy jest jakiś dowód, że komputery kwantowe są bardziej wydajne niż komputery klasyczne?

Algorytm Shora jest często używany jako argument. Może rozwiązać problem faktoryzacji szybciej niż jakikolwiek znany algorytm dla klasycznych komputerów. Jednak nie mamy dowodu, że klasyczne komputery nie mogą również efektywnie uwzględniać liczb całkowitych.

Czy istnieje jakiś faktyczny dowód, że komputery kwantowe mogą rozwiązać niektóre problemy szybciej niż klasyczne komputery?

algorithms efficiency quantum-computing MaiaVictor
źródło

niektóre z nich są formalnie ujęte w otwartych separacjach klas złożoności, takich jak BPP = A BQP (1. klasyczny, 2. zorientowany na QM). istnieje także problem implementacji polegający na tym, że nie wiadomo (w przeciwieństwie do klasycznych maszyn), czy QM jest rzeczywiście wykonalne fizycznie. itd ... może ugotować niektóre z tych odpowiedzi.

vzn

Ściśle powiązane: dlaczego i jak komputer kwantowy jest szybszy niż zwykły komputer?

Gilles 'SO - przestań być zły'

Odpowiedzi:

Tak, algorytm Grovera pokazuje, że można użyć algorytmu kwantowego do znalezienia elementu w nieuporządkowanej bazie danych o rozmiarze z dużym prawdopodobieństwem poprzez zapytanie do bazy danych tylko $N$ razy. Każde klasyczne rozwiązanie, które się powiedzie z dużym prawdopodobieństwem, wymagakwerenddo bazy danych. $O(\sqrt{N})$ $\Omega (N)$

Ran G.
źródło

Warto również wspomnieć o algorytmie Deutsch – Jozsa. Biorąc pod uwagę dostęp do wyroczni funkcji boolowskiej

, o której wiadomo, że jest jednorodna lub stała (przez uniform rozumiemy, że wynosi

dla dokładnie połowy możliwych danych wejściowych). Oczywiście każdy klasyczny algorytm wymagałby co najmniej

zapytań (w warunkach deterministycznych). Komputery kwantowe mogą decydować o tym za pomocą jednego zapytania.

f : {0, 1}^{n} \to {0, 1}

$f: \{0,1\}^n\rightarrow \left\{0,1\right\}$

0

$0$

2^{n - 1} + 1

$2^{n-1}+1$

Ariel,

„przeglądanie bazy danych” - myślę, że możesz nazbyt dosłownie przyjąć wyrażenie „eksploracja danych”. :-)

David Richerby,

@DavidRicherby cholera autokorekta? (;

Ran G.

@ ariel Myślę, że zasługuje na dodatkową odpowiedź! dlaczego tego nie dodasz? (można również wspomnieć, że daje to pomysły na algorytm Simona, który z kolei odnosi się do algorytmu Shora)

Ran G.

„Każde klasyczne rozwiązanie, które z dużym prawdopodobieństwem odniesie sukces, wymaga kwerend Ω (N) do bazy danych” - czy dotyczy to również modelu innego niż czarna skrzynka? Czy to jest udowodnione?

user976850,

To zależy od tego, co uważasz za rzeczywisty dowód i co rozumiesz przez „szybszy”. Z teoretycznej perspektywy złożoności odpowiedź brzmi „nie” - nie mamy takiego dowodu. BQP (klasa problemów, które można skutecznie rozwiązać za pomocą komputera kwantowego) jest zawarta w PSPACE. Możliwość udowodnienia separacji między BQP i PSPACE oznaczałaby również separację między P i PSPACE, która nie jest znana.

Zauważ, że algorytm Grovera przyspiesza jedynie pierwiastek kwadratowy, więc nie ma sprzeczności.

Norbert Schuch
źródło

Witamy! Niestety twoja odpowiedź wydaje się zaprzeczać samej sobie. Mówicie, że „z perspektywy teorii złożoności odpowiedź brzmi„ nie ”, ale następnie podajecie jeden teoretyczny argument złożoności, że odpowiedź brzmi„ nie wiemy ”, a drugi, że odpowiedź brzmi„ tak ”. Jak więc odpowiedź brzmi „nie”?

David Richerby,

\neq

$\ne$

Pytanie dotyczy tego, czy istnieje „faktyczny dowód, że komputery kwantowe mogą rozwiązać niektóre problemy szybciej niż klasyczne komputery”. Algorytm Grovera jest znacznie szybszy niż jakikolwiek klasyczny algorytm, więc odpowiedź jest jednoznacznie „tak”.

David Richerby,

@DavidRicherby Algorytm Grovera opiera się na wyroczni (czarnej skrzynce), która nie jest niczym, z czym można się spotkać w prawdziwych problemach. Kiedy zastanowisz się nad strukturą problemu w wyroczni (np. Weryfikując rozwiązanie problemu NP-zupełnego), (afaik) nie jest jasne, czy przyspieszenie trwa.

Norbert Schuch,

Ta odpowiedź jest nieco myląca z czytaniem. Myślę, że pomogłoby to zredagować odpowiedź, aby wyjaśnić te kwestie i dokładnie przemyśleć, jakie twierdzenia starasz się przedstawić i jakie uzasadnienie możesz zaoferować na poparcie tych twierdzeń. Są dwa punkty, które moim zdaniem pomogłyby wyjaśnić: (a) różnicę między przyspieszeniem w czasie wielomianowym a większym przyspieszeniem, (b) różnicę między algorytmem z wyrocznią a zwykłym algorytmem. Następnie użyj tych, aby wyjaśnić, dlaczego algorytm Grovera przyspieszył, ale to nie jest sprzeczne z twoimi innymi stwierdzeniami.

-1

pytasz o „dowód”, który może być ograniczony do poziomu matematycznego, ale podstawowe pytanie jest o wiele głębsze. teoretycy potwierdzą, że w zasadzie wciąż pozostaje otwarte pytanie o względną wydajność algorytmów kwantowych w porównaniu z klasycznymi i prawdopodobnie nie ma prostej / ogólnej odpowiedzi, ale przy pewnym eksperckim konsensusie, że algorytm Shorsa wydaje się „niezwykle szybki w porównaniu z oczekiwaną najlepszą klasyczną prędkością . ” szybki faktoring w klasycznym komputerze złamie powszechnie przyjęte założenia bezpieczeństwa kryptograficznego, takie jak system RSA .

część z nich jest formalnie ujęta w pytaniu o otwartej klasie złożoności BPP =? Pytanie BQP . są to analogiczne klasy klasyczne i kwantowe, a rozdział jest nieznany i jest aktywnym obszarem badań.
ściśle powiązane pytanie brzmi, czy fizycznie można zbudować komputery QM, które są zgodne z teoretycznymi specyfikacjami, a kilku / mniejszość naukowców (inaczej „sceptycy”) argumentuje, że mogą istnieć prawa dotyczące hałasu lub skalowania, które uniemożliwiają skalowanie QM zgodnie z teorią. w pewnym sensie ostatecznym „dowodem” szybkości komputera QM musi być fizyczna implementacja. (jest to podobne do sposobu, w jaki teza Churcha-Turinga jest teoretyczna, ale wydaje się, że ostatecznie wiąże się z twierdzeniem o fizycznych implementacjach.) niektórzy badacze mówią o analogach Church-Turinga w obliczeniach QM. patrz np. teza Churcha Turinga w świecie kwantowym autorstwa Montanaro.
istotne / wpływające na to pytanie / debatę są w toku znacznych / „gorących” (naukowych) prób analizy porównawczej obecnego na świecie „największego” komputera kwantowego przez DWave. jest to duży temat z wieloma pokrewnymi materiałami, ale dla stosunkowo niedawnego przeglądu wypróbuj badanie porównawcze sporów D-Wave pokazujące powolny komputer kwantowy / rejestr

vzn
źródło