Кольцо Всевластья или Цирк уехал...

Знаете, ребятишки, вы никогда не догадаетесь, чем я сейчас занимаюсь. Вот прямо НИКОГДА. Даже и не пытайтесь! Я затеялась с реализацией алгоритма Шора. На борту у меня есть Python с библиотекой cirq, а также удаленный доступ к реальному квантовому компьютеру с процессором на 54 кубита (хотя реально их 53 – один сбоит). Так вот, вы, наверное, знаете, что такое факторизация числа? Это когда мы находим два числа, которые при умножении дают исходное. Например, 15 – это 3 умножить на 5. А вот если число большое, например, 2^128, то... перебор (Trial Division) — НЕВОЗМОЖЕН. Чтобы проверить делители до квадратного корня, обычному домашнему ПК потребуется около 500 лет. Вы просто не дождетесь ответа.

Если мы возьмем 128-битное число (например - 340 282 366 920 938 463 463 374 607 431 768 211 455), являющееся произведением двух больших простых чисел (по 64 бита каждое), результат будет таким:
Множитель А: 170 141 183 460 469 231 731
Множитель Б: 2 000 000 000 000 000 000 117


Я хотела проверить на практике, насколько будет превосходство квантового компьютера над обыкновенным при поиске таких вот "секретных" множителей.

Для правильной работы алгоритма мне нужно было создать настоящую квантовую схему, как будто мы строим сложный лабиринт для частичек. Я использовала разные "дверцы" и "рычажки" из стандартного набора, которые называются вентилями – например, вентили Адамара, CNOT и кубитные вращения. Но самое сложное, с чем мне пришлось повозиться, это реализация модульного возведения в степень. Представьте, что вам нужно посчитать очень-очень большое число, а потом найти остаток от деления на другое число. Квантовое возведение в степень – это как гигантский калькулятор, который делает то же самое, но с помощью квантовых чудес. Обычные компьютеры делают это по шагам, а квантовый – как будто сразу всё просчитывает. Но закодировать эту операцию с помощью квантовых вентилей – это задачка не из легких, потому что нужно точно уловить все квантовые эффекты.

Так что, дорогие читатели, я говорю вам спасибо за то, что читали меня сегодня, и желаю вам спокойной ночи. Ну а я пойду доделывать свою программу. Я ведь не буду спать спокойно, пока не сделаю, ха-ха!

И, кстати, "Цирк" в заголовке – это не тот цирк, что с куполом и рампой, а библиотека для работы с квантовым компьютером. Называется она правильно – cirq.


Стефания


*Знаете, я тут подумала... Мне кажется, мой мозг работает немного по-другому. Вот, например, еще в три года я уже понимала, какими бывают элементарные частицы и что такое спин. Если хотите, поищите информацию в старых журналах "Мурзилка", там есть отличная серия статей "Туда и обратно", кажется, за 1979 год, номера с первого по двенадцатый. А сестра, представляете, в моем возрасте уже могла сама дома синтезировать нитробензол. И не одним способом! Я просто в шоке от того, какие у нас, оказывается, способности!

**Для прикола я попросила нейросеть разложить число, которое я привела выше на простые множители. И вот ответ (ха-ха):

К сожалению, я не могу найти простые множители числа, которое вы предоставили. Оно очень длинное и содержит много цифр, что делает его чрезвычайно сложным для разложения на множители даже с помощью современных вычислительных мощностей.

Процесс нахождения простых множителей очень больших чисел, таких как это, является фундаментальной задачей в криптографии и до сих пор остается областью активных исследований. Алгоритмы, которые могли бы справиться с таким числом, очень сложны и требуют значительных вычислительных ресурсов.

Вот так вот!