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

Что такое квантовый компьютер?

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

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

В чем отличие квантовых вычислений от классических?

Как в основе классических вычислителей лежат операции с битами, так в случае с квантовыми компьютерами объектом операций становятся квантовые биты, или кубиты. При измерении бита мы всегда получим один и тот же результат — «ноль» или «единицу». Измерение одинаково приготовленных кубитов будет с некоторой вероятностью давать и «ноль», и «единицу» — до измерения кубит будет одновременно и «нулем» и «единицей». Как говорят физики — он будет в суперпозиции двух состояний.

Оказывается, такая необычная единица данных позволяет упростить решение многих вычислительных задач, в особенности — связанных с перебором. Зато такие задачи, как сложение двух натуральных чисел (например, 2+2), для квантового компьютера оказываются совсем не тривиальными.

Что представляют собой квантовые биты?

Физически кубиты бывают разных типов. Самые распространенные (их используют научные группы Google и IBM) — сверхпроводящие. Это кольца из сверхпроводника с небольшой изолирующей перемычкой, в которых ток течет одновременно и по, и против часовой стрелки. Иначе их называют джозефсоновскими контактами. Кроме того, существуют кубиты на базе отдельных атомов, захваченных лазерными лучами. Роль нуля и единицы в них играют состояния электронной оболочки атомов. На их основе уже были построены универсальные квантовые компьютеры. Разрабатываются кубиты и на основе наноразмерных кристаллов полупроводников — квантовых точек.

Какие задачи квантовый компьютер решает лучше классического?

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

Другой пример — алгоритм Шора для разложения натурального числа на простые множители. Классические алгоритмы могут сделать это только полным перебором, причем с ростом количества знаков в раскладываемом натуральном числе количество операций растет экспоненциально (условно, каждый знак увеличивает время расчета в 10 раз). Квантовому алгоритму требуется лишь полиномиальное время (полином от числа знаков в числе).

Есть еще несколько примеров, связанных с перебором, которые быстро решаются с помощью квантовых алгоритмов. Основной прирост производительности в таких задачах связан именно с существованием кубитов в суперпозиции состояний. Интересно, что в ряде случаев в алгоритм можно вводить суперпозицию порядка вычислений. То есть, например, одновременно проводить над числом умножение, а потом возведение в степень, и возведение в степень, а потом умножение. Такие операции позволяют выяснить за одно действие, есть ли разница между порядком выполнения двух операций (A, затем B, и B, затем A).

Кроме того, следуя природе квантового компьютера, с его помощью можно моделировать квантовые системы. Чтобы проанализировать поведение системы из 50 кубитов (здесь — частиц, которые могут быть в двух состояниях одновременно), потребуется по меньшей мере 250 бит оперативной памяти — не учитывая логические вентили в системе.

Читать далее.