Co sprawia, że ​​komputery kwantowe są tak dobre w obliczaniu głównych czynników?

Jednym z powszechnych twierdzeń na temat komputerów kwantowych jest ich zdolność do „łamania” konwencjonalnej kryptografii. Wynika to z faktu, że konwencjonalna kryptografia opiera się na czynnikach głównych, co jest kosztem obliczeniowym dla konwencjonalnych komputerów do obliczenia, ale który jest rzekomo trywialnym problemem dla komputera kwantowego.

Jaka właściwość komputerów kwantowych czyni je tak zdolnymi do tego zadania, w którym zawodzą komputery konwencjonalne i jak stosuje się kubity do problemu obliczania czynników pierwszych?

Krótka odpowiedź

$\newcommand{\modN}[1]{#1\,\operatorname{mod}\,N}\newcommand{\on}[1]{\operatorname{#1}}$ Komputery kwantowe mogą uruchamiać podprogramy algorytmu do faktoringu, wykładniczo szybciej niż jakikolwiek znany klasyczny odpowiednik. To nie znaczy, że klasyczne komputery też NIE potrafią tego zrobić szybko, po prostu nie znamy dzisiaj sposobu, aby klasyczne algorytmy działały tak wydajnie jak algorytmy kwantowe

Długa odpowiedź

Komputery kwantowe są dobre w dyskretnych transformacjach Fouriera. W grze jest wiele rzeczy, których nie uchwyci po prostu „ jest równoległa ” lub „ jest szybka ”, więc przejdźmy do krwi bestii.

Problemem faktoring jest następujący: Biorąc pod uwagę ilość $N = pq$ , gdzie $p,q$ są liczbami pierwszymi, w jaki sposób odzyskać $p$ i $q$ ? Jednym z podejść jest zwrócenie uwagi na następujące kwestie:

Jeśli spojrzę na liczbę $\modN{x}$ , to albo $x$ dzieli wspólny czynnik z $N$ , albo nie.

Jeśli ma wspólny czynnik i nie jest wielokrotnością samego , możemy łatwo zapytać, jakie są wspólne czynniki i (za pomocą algorytmu euklidesowego dla największych wspólnych czynników).N x $x$$N$$x$$N$

Teraz nie jest tak oczywisty fakt: zbiór wszystkich , które nie mają wspólny czynnik z tworzy grupę multiplikatywne . Co to znaczy? Możesz zobaczyć definicję grupy w Wikipedii tutaj . Niech operacja grupowa będzie zwielokrotniona w celu uzupełnienia szczegółów, ale tak naprawdę zależy nam na następującej konsekwencji tej teorii, którą jest: sekwencjaN mod $x$$N$$\on{mod} N$

$$\modN{x^0}, \quad\modN{x^1}, \quad\modN{x^2}, ...$$

jest okresowy, gdy nie dzielą wspólnych czynników (spróbuj , ), aby zobaczyć to z pierwszej ręki jako:x = 2 N = $x,N$$x = 2$$N = 5$

$$\newcommand{\mod}[1]{#1\,\operatorname{mod}\,5} \mod1 = 1,\quad \mod4 = 4,\quad \mod8 = 3,\quad \mod{16} = 1.$$

Ile liczb naturalnych mniejszych niż nie dzieli żadnych wspólnych czynników z ? Odpowiada na to funkcja sumująca Eulera , to .N N ( p - 1 ) ( q - 1 $x$$N$$N$$(p-1)(q-1)$

Na koniec, wybierając temat teorii grup, długość powtarzających się łańcuchów

$$\modN{x^0}, \quad\modN{x^1}, \quad\modN{x^2}, ...$$

dzieli tę liczbę . Więc jeśli znasz okres sekwencji mocy , możesz zacząć zgadywać, czym jest . Ponadto, jeśli wiesz, co to jest i co to jest (to nie zapomnij!), To masz 2 równania z 2 niewiadomymi, które można rozwiązać za pomocą algebry elementarnej, aby oddzielić .x $(p-1)(q-1)$( p - 1 ) ( q - 1 ) ( p - 1 ) ( q - 1 ) p q p , $x \mod N$$(p-1)(q-1)$$(p-1)(q-1)$$pq$$p,q$

Skąd się biorą komputery kwantowe? Znalezienie okresu. Istnieje operacja zwana transformacją Fouriera, która przyjmuje funkcję zapisaną jako sumę funkcji okresowych gdzie są liczbami, są funkcjami okresowymi z okresem i odwzorowuje je na nową funkcję takie, że .a 1 e 1 + a 2 e 2 . . . I e I P I f f ( P I ) = o $g$$a_1 e_1 + a_2 e_2 ...$$a_i$$e_i$$p_i$$\hat{f}$$\hat{f}(p_i) = a_i$

Obliczanie transformacji Fouriera jest zwykle wprowadzane jako całka, ale jeśli chcesz po prostu zastosować ją do tablicy danych (i ^tym elementem jest ), możesz użyć tego narzędzia o nazwie Dyskretna transformata Fouriera, która wynosi do pomnożenia „tablicy” tak, jakby to był wektor, przez bardzo dużą macierz jednostkową.$f(I)$

Nacisk na słowo unitary: to naprawdę arbitralna właściwość opisana tutaj . Ale kluczem na wynos jest:

W świecie fizyki wszyscy operatorzy przestrzegają tej samej ogólnej zasady matematycznej: jednolitości .

Oznacza to, że replikacja operacji macierzy DFT jako operatora kwantowego nie jest nierozsądna.

Teraz tutaj jest głęboko, a Qubit Array może reprezentować możliwych elementów tablicy (wyjaśnienia znajdziesz w dowolnym miejscu w Internecie lub dodaj komentarz).2 $n$$2^n$

I podobnie operator kwantowy Qubit może działać na całą przestrzeń kwantową i dać odpowiedź, którą możemy zinterpretować.2 $n$$2^n$

Więcej informacji można znaleźć w tym artykule w Wikipedii .

Jeśli możemy wykonać tę transformację Fouriera na wykładniczo dużym zestawie danych, używając tylko Qubitów, możemy bardzo szybko znaleźć ten okres.$n$

Jeśli potrafimy bardzo szybko znaleźć okres, możemy szybko oszacować$(p-1)(q-1)$

Jeśli potrafimy to zrobić szybko, to biorąc pod uwagę naszą wiedzę na temat , możemy wykonać próbę sprawdzania .p , $N=pq$$p,q$

To się dzieje tutaj, na bardzo wysokim poziomie.

To, co sprawia, że ​​komputery kwantowe są dobre w faktorowaniu dużych liczb, to ich zdolność do rozwiązywania problemu znalezienia okresu (i matematyczny fakt, który wiąże znalezienie czynników pierwszych z znalezieniem okresu). To w zasadzie algorytm Shora w pigułce. Jednak nasuwa się pytanie, co sprawia, że ​​komputery kwantowe nadają się do wyszukiwania okresów.

U podstaw znalezienia okresu leży możliwość obliczenia wartości funkcji w całej jej domenie (to znaczy dla każdego możliwego wkładu). Nazywa się to równoległością kwantową. To samo w sobie nie jest wystarczająco dobre, ale wraz z interferencją (umiejętnością łączenia w pewien sposób wyników równoległości kwantowej) jest.

Przypuszczam, że ta odpowiedź może być trochę wieszakiem na klif: Jak można wykorzystać te umiejętności do faktycznego uwzględnienia? Znajdź odpowiedź na to w Wikipedii na temat algorytmu Shora .

Przede wszystkim faktoring można przeprowadzić na komputerze kwantowym (z wykorzystaniem „jednolitych” bram kwantowych) za pomocą algorytmu Shora .

Wyjaśnieniem, które nie wymaga zaawansowanej matematyki ani żadnej zaawansowanej wiedzy z fizyki, jest ten post na blogu Scotta Aaronsona , zatytułowany „Shor, zrobię to”.

Krótkie streszczenie jego pomysłów jest następujące:

Po pierwsze, reprezentujemy nasze kwantowe bramki / kubity z zegarami (używając „liczb zespolonych jako strzałek (tj. Elementów z dziwnym mnożeniem)), reprezentacji”)$\mathbb{R}^2$

Następnie zauważamy, że badacz CS ma bardzo nieregularne okresy snu. Aby znaleźć ten dziwny okres, używamy zegarów. Następnie zauważamy, że znalezienia tego okresu można użyć do uwzględnienia liczb całkowitych (przy użyciu podobnej konstrukcji jak w losowym algorytmie Pollarda - )$\rho$

Dlatego nasze dziwne zegary kwantowe mogą nam pomóc w efektywnym obliczeniu!