Jak fizyka kwantowa prowadzi do odszyfrowywania popularnych algorytmów

Połączenia powstanie komputerów kwantowych i jego implikacje dla obecnych standardów szyfrowania są dobrze znane. Ale dlaczego dokładnie komputery kwantowe miałyby być szczególnie biegłe w łamaniu szyfrowania? Odpowiedzią jest fajny kawałek matematycznej żonglerki tzw algorytm faktoryzacji shora. Pytanie, które wciąż pozostaje, brzmi: co takiego robi ten algorytm, że komputery kwantowe są o wiele lepsze w łamaniu szyfrowania? W ten film, YouTuber minutafizyka wyjaśnia to w swoim tradycyjnym stylu rysunkowym z tablicą.

„Obliczenia kwantowe mogą sprawić, że dostęp do zaszyfrowanych danych będzie super, bardzo łatwy – na przykład posiadanie miecza świetlnego, którego można użyć do przebicia się przez dowolną blokadę lub barierę, bez względu na to, jak mocną” — mówi minutephysics. „Algorytm Shora to ten miecz świetlny”.

Zgodnie z filmem, algorytm Shora opiera się na założeniu, że dla dowolnej pary liczb ostatecznie pomnożenie jednej z nich przez samą siebie da współczynnik drugiej liczby plus lub minus 1. W ten sposób zgadujesz pierwszą liczbę i rozkładasz ją na czynniki out, dodając i odejmując 1, aż dojdziesz do drugiej liczby. To odblokowałoby szyfrowanie (w szczególności RSA tutaj, ale działa dalej kilka innych typów), ponieważ mielibyśmy wtedy oba czynniki.

Jednym z powodów, dla których ten pozornie prosty proces opiera się na rozwoju potężnych komputerów kwantowych, jest to, że znalezienie odpowiedniej potęgi do pomnożenia pierwszej liczby w celu znalezienia współczynnika drugiej liczby (N) ± 1 wymaga ogromnej liczby prób. Klucz szyfrowania jest dość długą liczbą, dlatego moc może wynosić od 1 do milionów. Ale brutalna siła nie jest powodem, dla którego komputery kwantowe działają tutaj tak dobrze.

Supermoce superpozycji

Krótko mówiąc, dzięki superpozycji kwantowej komputer kwantowy może obliczyć wiele odpowiedzi dla jednego wejścia. Jednak film mówi, że otrzymujesz tylko jedną odpowiedź na raz, z dołączonymi prawdopodobieństwami. Aby rozwiązać ten problem, obliczenia są skonfigurowane w taki sposób, że błędne odpowiedzi kolidują ze sobą, tak że prawdopodobnie zostanie wyświetlona tylko poprawna odpowiedź (lub przynajmniej dobre przypuszczenie). To obliczenie, które koncentruje się na znalezieniu odpowiedniej mocy p, jest algorytmem Shora.

To wszystko jest niezwykle matematyczne, z udziałem asysty Algorytm Euklidesa, a także kwantową transformatę Fouriera, która zamienia serię superpozycji superpozycji w fale sinusoidalne, które albo konstruktywnie (dodają się do siebie), albo destrukcyjnie interferują — tj. wzajemnie się znoszą. Film mówi, że zasadniczo można go ustawić tak, aby tylko 1/p zostaje uratowany, a wszystkie inne odpowiedzi zostały destrukcyjnie wyeliminowane z rywalizacji. Gdy już tam będziesz, to spacer po parku, aby znaleźć p, co znacznie ułatwia znalezienie dwóch czynników szyfrowania. Obejrzyj cały film, aby uzyskać więcej szczegółów i być może poczuć się trochę mądrzej.

Nawiasem mówiąc, Peter Shor jest wciąż kwitnący, a jeśli chcesz dowiedzieć się więcej o tym, jak włamał się do Internetu, oto kolejny film, w którym sam mężczyzna wyjaśnia, jak się domyślił jego tytułowe arcydzieło.