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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как это связано с тем, с чем можно встретиться в реальной жизни?

Моделирование свойств химических веществ — в некотором смысле задача моделирования квантовых систем. Поэтому многие ученые надеются на то, что квантовые компьютеры упростят расчет свойств отдельных молекул (например, их спектров), а также поиск новых лекарств и материалов. Задачи оптимизации тоже часто связаны с перебором вариантов, например задача о коммивояжере. Постепенно появляются квантовые нейросети — с их помощью эксперты уже рассчитывали состояние молекулы водорода. 

С квантовым компьютером связаны и некоторые опасения — ему по плечу оказываются многие задачи по расшифровке данных. К примеру, алгоритм шифрования RSA основан на том, что классический компьютер не может за разумное время разложить на простые множители число длиной несколько тысяч бит. Поэтому ключ дешифровки можно передавать в открытом виде. Если хакер хранит где-то набор открытых ключей и данных, зашифрованных с их помощью, то в будущем квантовый компьютер поможет ему расшифровать эти данные. Интересно, что из тех же соображений квантовый компьютер можно использовать для атаки на системы блокчейна, подобные биткоину.

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

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

Сейчас квантовые компьютеры находятся лишь на первых стадиях своего развития — даже многократный прирост производительности из-за использования квантовых алгоритмов не позволяет им надежно превзойти обычные компьютеры. Тем не менее, уже есть серьезные заявки на квантовое превосходство от неуниверсальных квантовых вычислителей. Это устройства, которые способны решать строго определенную задачу. В конце 2015 года Google показала, что устройство для квантового отжига D-Wave в 100 миллионов раз быстрее решает задачу оптимизации, чем обычный компьютер. Однако речь шла о специально разработанной искусственной задаче, подходящей для конкретной цели. А недавно группа китайских физиков разработала бозонный семплер, который благодаря своей квантовой природе обошел ENIAC (первый компьютер человечества) в 220 раз.

Но универсальные квантовые компьютеры, которые можно сравнивать с классическими компьютерами, все еще используют слишком малое количество кубитов — до 17 штук. Такие системы все еще можно полностью моделировать даже обычным настольным компьютером.

Сколько надо кубитов, чтобы обойти современные суперкомпьютеры?

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

Без борьбы с ошибками увеличение количества кубитов практически не увеличивает производительности системы. Так, по оценкам физиков, новая 16-кубитная система IBM лишь на 40 процентов производительнее 5-кубитного компьютера-предшественника. Сверхпроводящие кубиты этого типа совершают около одной ошибки на 100 операций. По словам специалистов IBM, коммерческий 17-кубитный квантовый компьютер за счет сниженного уровня ошибок обладает в два раза большей производительностью.

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

Тем не менее, физики полагают, что эту границу скоро удастся пересечь. Так, лаборатория компании Google под руководством Джона Мартиниса планирует запустить 20-кубитный универсальный компьютер в течение ближайшего месяца. А в наиболее амбициозные планы Google входит запуск 50-кубитного универсального квантового компьютера уже к концу 2017 года.

Автор: Владимир Королёв