Квантовое превосходство

23 октября в журнале Nature была опубликована статья исследователей из отдела квантового искусственного интеллекта компании Google, в которой говорилось о достижении квантового превосходства. Коллектив ученых под руководством Джона Мартиниса заявил о решении с помощью квантового компьютера задачи, непосильной для самого современного классического суперкомпьютера. N + 1 подробно разобрался в случившемся.

Зарождение

Идея квантового компьютера появилась около 40 лет назад в работах советского ученого Юрия Манина, но была вскоре независимо и в существенно более четком виде сформулирована Ричардом Фейнманом.

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

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

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

Эволюция

Квантовые компьютеры не привлекали большого внимания до середины 1990-х годов, когда появились первые квантовые алгоритмы, то есть программы, теоретически выполнимые с их помощью. Перелом произошел после выхода работы Питера Шора, нашедшего способ эффективно факторизовать большие числа, то есть раскладывать их на простые множители.

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

К разработке квантовых компьютеров приступили ученые во многих странах мира. Более того, интерес стали проявлять коммерческие структуры, такие как Google, IBM, Microsoft и даже некоторые финансовые организаций, например банк Morgan Stanley. Причина этого заключается в ожидаемых способностях квантовых компьютеров решать задачи криптографии и многомерной оптимизации, возникающие, в частности, при анализе биржевых курсов.

В начале 2010-х годов наиболее оптимистичные аналитики утверждали, что полезный квантовый компьютер появится в течение нескольких ближайших лет. Более осторожные специалисты отводили на его создание пару десятков лет. Чтобы хоть как-то формализовать прогресс в этой области и обозначить завершение начального этапа развития, физик Джон Прескилл в 2012 году предложил термин «квантовое превосходство».

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

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

Превосходство

23 октября сотрудники Google опубликовали в журнале Nature работу, в которой говорится о достижении квантового превосходства. Такое заявление исследователи сделали по результатам работы с 53-кубитным процессором Sycamore, сумевшим решить очень специфическую задачу за 200 секунд, в то время как оценочное время ее решения на самом мощном современном компьютере Summit должно составить 10 тысяч лет.

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

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

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

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

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

Физической основой кубитов в компьютере Google являются сверхпроводящие контуры. Этот вариант относительно проще в создании, но страдает от достаточно высоких шумов и ошибок, затрудняющих вычисления. Это стало дополнительным аргументом в пользу выбранной задачи, так как алгоритм ее решения устойчив к ошибкам и не требует их корректировки.

Последствия

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

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

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

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

На вопрос о возможной угрозе безопасности шифрования сотрудники Google ответили, что для практически реализуемого взлома криптографического алгоритма, например RSA, ориентировочно понадобится около сотни миллионов физических кубитов.

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

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