Как квантовая физика ведет к расшифровке общих алгоритмов

Ассоциация рост квантовых вычислений и ее последствия современные стандарты шифрования хорошо известны. Но почему именно квантовые компьютеры должны особенно хорошо взламывать шифрование? Ответ — изящное математическое жонглирование, называемое Алгоритм Шора. Остается открытым вопрос: что делает этот алгоритм, благодаря которому квантовые компьютеры намного лучше взламывают шифрование? В здесь, YouTuber минутная физика объясняет это в своем традиционном мультяшном стиле на доске.

«У квантовых вычислений есть потенциал, чтобы сделать доступ к зашифрованным данным супер-простым — например, иметь световой меч, который можно использовать, чтобы пробить любой замок или барьер, независимо от того, насколько они прочны», — говорит Minist Physics. «Алгоритм Шора и есть этот световой меч».

Согласно видео, алгоритм Шора работает на понимании того, что для любой пары чисел умножение одного из них само на себя в конечном итоге приведет к коэффициенту другого числа плюс-минус 1. Таким образом, вы угадываете первое число и факторизуете его. out, прибавляя и вычитая 1, пока не дойдете до второго числа. Это разблокирует шифрование (в частности, RSA здесь, но оно работает на некоторые другие типы), потому что тогда у нас были бы оба множителя.

Одна из причин, по которой этот, казалось бы, простой процесс зависит от разработки мощных квантовых компьютеров, заключается в том, что поиск правильной степени, на которую нужно умножить первое число, чтобы найти множитель второго числа (N) ± 1, требует огромного количества попыток. Ключ шифрования — это довольно длинное число, поэтому мощность может быть от 1 до миллионов. Но квантовые компьютеры здесь так хорошо работают не из-за грубой силы.

Сверхспособности суперпозиций

Вкратце, благодаря квантовому суперпозиционированию квантовый компьютер может вычислить множество ответов для одного входа. Однако в видео говорится, что вы получаете только один ответ за раз с добавленными вероятностями. Чтобы решить эту проблему, вычисление настроено так, что неправильные ответы мешают друг другу, поэтому, скорее всего, будет выведен только правильный ответ (или, по крайней мере, хорошее предположение). Этот расчет, который фокусируется на поиске правильной мощности p, — алгоритм Шора.

Все это чрезвычайно математически, включая помощь от Алгоритм Евклида, а также квантовое преобразование Фурье, которое превращает серию суперпозиций суперпозиций в синусоидальные волны, которые либо конструктивно (дополняют друг друга), либо деструктивно интерферируют, т. е. компенсируют друг друга. В ролике сказано, что, по сути, можно подстроить так, чтобы только 1/p сохраняется, а все остальные ответы деструктивно вмешиваются из-за разногласий. Как только вы там, это прогулка в парке, чтобы найти p, что значительно упрощает поиск двух факторов шифрования. Посмотрите все видео, чтобы узнать подробности и, возможно, почувствовать себя немного умнее.

Кстати, Петр Шор все еще процветает, а если вам интересно поглубже покопаться в том, как он сломал интернет, вот еще видео, где сам человек объясняет, как он понял его одноименный шедевр.