О квантовом превосходстве

nabbla1 — 08.11.2019 Невообразимых 6 лет назад я перевёл научно-популярную статью из блога Скотта Ааронсона про алгоритм Шора по разложению чисел на простые множители на квантовом компьютере: https://nabbla1.livejournal.com/21789.html
Как сейчас поясняет мой брат, исходный заголовок "Shor, I'll do it" созвучен "Sure, I'll do it", но увы, в переводе этот момент был упущен.

В целом, автор подчёркивал, что хоть в квантовых компьютерах с ростом числа кубит экспоненциально растёт количество состояний, пребывающих одновременно в суперпозиции, это вовсе не означает, что мы "автоматом" можем решить любую задачу "прямым перебором", т.к не можем приказать всем "неправильным" состояниям самоуничтожиться. В большинстве случаев, при попытке ИЗМЕРИТЬ состояния кубитов, мы получим практически случайное значение, из которого восстановить, что он там "насчитал" невозможно. С редкими исключениями в виде алгоритма Шора и пары других.

Сейчас вдруг зашёл на его блог и почитал недавние записи, про "Квантовое превосходство" от google. Что удивительно, сейчас он весьма и весьма оптимистичен и возмущён, почему эта новость не наделала должного шуму во всём мире, хотя, прочитав его же описание, что же там происходит, я особого оптимизма не почувствовал...

Хочу вкратце рассказать, что там у них творится. Довольно сильно ИМХО.


Имеется 54 кубита, реализованные в виде сверхпроводящих витков с током, причём один не работает. Они расположены в виде "решетки", и каждый можно соединять с четырьмя соседями для выполнения некоторой логической операции.

Им присваивают некие начальные значения, после чего случайным образом запускают логические операции, одну за другой, в количестве 20 штук.

Затем измеряют получившиеся значения, нули и единицы. Понятно, что в процессе измерения происходит "схлопывание" суперпозиции, и мы получаем какую-то случайную выборку.

Согласно Ааронсону, результат каждого измерения на 99,8% состоит из случайного шума, не имеющего отношения к суперпозициям, и лишь оставшиеся 0,2% следуют распределению, которое определяется начальными состояниями кубитов и теми 20 логическими операциями, которые над ними провели. Из-за случайного характера и того и другого, распределение весьма и весьма близко к равномерному, ДА НЕ СОВСЕМ.

Как утверждают в гугле, чтобы самому мощному на сегодняшний день классическому суперкомпьютеру (IBM-скому Summit) посчитать все эти распределения, потребуется 10 000 лет. Впрочем, сами IBM выпустили статью, в которой описывают, как их можно посчитать всего за 2,5 дня.

Сам термин "квантовое превосходство" (точнее было бы quantum COMPUTING supremacy) должен означать, что мы научились проводить такие вычисления, которые у обычного, классического компьютера заняли бы совершенно безумное время.

Весь вопрос - что назвать вычислениями. Да, "антураж" вполне соответствующий - кубиты, логические операции. Прибор, который в нужном порядке выполняет логические операции над кубитами - как будто бы да, компьютер, что-то вычисляет.

Вот только всё, что он выдавал, для всех практических целей является просто случайными числами, с немножечко плавающими взад-вперёд распределениями. И со времён Фейнмана, который (в числе прочих) и ввёл в обиход понятие квантового компьютера, полезных алгоритмов для квантового компьютера нашлось не так уж много.

Видимо, алгоритм Шора как раз наиболее популярен. Полезным для "нормальных людей" его не назовёшь, хотя криптологи всех стран ликуют - вот-вот можно будет поднять глобальный шухер "вся приватность скоро превратится в тыкву, потому что квантовый компьютер расщёлкает все самые популярные системы шифрования за считанные секунды, айда переходить на новые!". И народ, испугавшись полного обвала всей экономики и пр., перейдёт на новые алгоритмы шифрования, не завязанные на простые числа, так что квантовый компьютер больше не страшен. В итоге окажется, что реальная возможность сломать шифрование была у того же Гугла, и не сейчас, а через 20 лет, но он и так знал логины и пароли практически каждого жителя Земли, и по-прежнему знает, так что ему этот компьютер как зайцу баян. Повторение "ошибки 2000 года" - все счастливы. Даже имя уже придумано, Y2Q (Years to Quantum, по аналогии с Y2K, Year 2000).

Существующий драндулет о 53 кубитах ничего сколько-нибудь полезного взломать не может, в лучшем случае 53-битный ключ, если состояния совсем не "развалятся" от O(N³) операций, которые нужны алгоритму Шора (да, это тебе не 20 логических операций!). Но 53-битный ключ и персоналка взломает легко и непринуждённо. Сейчас самый минимум 512 бит, а лучше 1024 или 2048 бит.

Ещё есть алгоритм Гровера и его вариации, которые позволяют в задачах перебора перебрать не все N разных вариантов, а только лишь корень из N. Звучит многообещающе, но если число разных вариантов росло экспоненциально - оно так и продолжит расти экспоненциально, причём найдены строгие "нижние границы" - лучше корня из N для произвольной задачи перебора достигнуть нельзя. Соревноваться с классическим компьютером в таких задачах очень тяжело.

По мне, остаётся только один, зато очень широкий класс задач - моделирование квантовых систем. Всякое сворачивание белков, наноматериалы, высокотемпературные сверхпроводники и всё в этом духе. На классических компьютерах это очень тяжело смоделировать, а использовать одну квантовую систему для моделирования другой - почему бы и нет! По большому счёту это получается аналоговый компьютер, ведь из подобных задач сам термин "аналоговый" и пришёл. Чем действительно запускать снаряд, давайте соберём схему, которую будут описывать уравнения, совпадающие с уравнениями движения снаряда!

В классическом варианте цифровые компьютеры взяли верх над аналоговыми благодаря возможности коррекции ошибок непосредственно на каждом этапе, в каждом логическом элементе. Был выход 0 вольт, прилетела помеха в 0,5 вольта - для аналоговой цепи это была бы катастрофа, для цифровой вообще пофиг - ясно же что это не единица - поехали дальше! Данные перестали "портиться": если переписывать музыку с кассеты на кассету, с каждым разом качество будет портиться. А если с жесткого диска на флэшку, а потом послать e-mail'ом, то если всё хорошо работает, ни одного бита не пропадёт. (и можно ещё хэш-функцию посчитать и по ней контролировать, что всё в порядке).

Но "цифровые квантовые компьютеры" в этом плане НИ РАЗУ НЕ ЦИФРОВЫЕ - в том, что сейчас делают google и IBM (и другие) нет никакого способа корректировать испорченные внешними воздействиями квантовые состояния. В целом, разработки в данном направлении ведутся, но, как говорится, "лекарство страшнее болезни" - схема коррекции ошибок сама вносит ошибки, и единственное, что утешает - процесс когда-нибудь "сойдётся" - сделав "многоэтажную систему", как будто бы можно снизить ошибки до какого-то приемлемого уровня. Но разумеется, для этого ну никак не хватит 53 кубитов, и связность между ними должна быть получше, а не как здесь "с четырьмя соседями".

Аналоговыми квантовыми компьютерами (квантовыми симуляторами) народ занимается во всём мире, и, пожалуй, более успешно, чем гугл с IBM, но маркетинг у них всяко похуже :)

Ещё из интересного: раз Гугл заявил, что на проверку тех результатов, что получил его "компьютер", классический супекомпьютер должен затратить 10 000 лет, значит, по сути, они НЕ ЗНАЮТ, ВЕРНЫ ЛИ ЭТИ РЕЗУЛЬТАТЫ. Они проверяли результаты с меньшим числом логических операций и с меньшим числом кубитов и решили что "вроде бы работает" (хотя здесь тоже неплохо бы крутому статистику поработать, посмотреть, как именно они подтвердили наличие этих 0,2% более хитрого распределения). Это не такая задача, где можно "окольным путём" убедиться в истинности. Например, разложи их компьютер число на простые множители - мы можем элементарно умножить их назад, и если получили исходное число, значит всё хорошо! Но здесь задачка, которая на самом деле никому не нужна, и ответа на которую никто не знает.

В общем, меня эта новость как-то не впечатлила. Они сделали нечто, которое даёт случайные отсчёты, но точное распределение для этих отсчётов очень сложно промоделировать, но это абсолютно не новость (У меня когда-то крутилась программа Folding@Home для моделирования сворачивания белков, пока конденсаторы на материнке все не вспухли от непрерывной нагрузки 100%). Они сделали вид, что это не просто абстрактная квантовая система, а "универсальный квантовый компьютер", способный выполнить любую последовательность логических операций над кубитами, но в такой универсальности смысла очень мало. Лишь считанные логические схемы способны породить осмысленный результат, и они почему-то на нём промоделированы быть не могут - не хватает ни кубитов, ни связности, ни времени выполнения (без разрушения квантовой суперпозиции). Они не знают, верны ли результаты работы, т.к аналитических выражений нет, нужно только моделировать, а это сложно (хотя может IBM им поможет - запряжет суперкомпьютер на 2,5 дня). Оценки сложности моделирования даны очень "в лоб" - никто не пытался эту задачу упростить для классических компьютеров, потому как она никому не была интересна, разве что как самый простой способ продемонстрировать пресловутое "квантовое превосходство". Точнее, за ближайший месяц её уже упростили с 10 000 лет до 2,5 дней, и никто не утверждает, что это предел.

Оставить комментарий

Популярные посты:

• Ранее
• Архив