Взломать пин-код и идеально собрать рюкзак

Зачем нужны квантовые компьютеры и когда их ждать 16 Июль 2015, 14:03

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

Так выглядит типичный кубит — квантовый аналог бита. Фото: Erik Lucero, с сайта physics.ucsb.edu

Задача рюкзака и идеальный маршрут

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

Описанная выше задача — оптимизировать перемещение по нескольким местам — в математике известна как задача коммивояжера, и ее невозможно решить за разумное время. Если мест назначения немного, скажем пять, вычислить кратчайшую траекторию несложно. Число вариантов для 15 точек составит уже 43 589 145 600. Если на оценку каждого тратить одну секунду, для перебора всех возможностей придется просидеть за столом 138 лет. Для 66 точек время решения превысит несколько миллиардов лет — при условии, что вы используете компьютер и он тратит на оценку одного варианта доли секунды.

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

Подбор пин-кода — элементарная задача для квантового компьютера. Фото: Consumerist Dot Com/flickr

С еще одной NP-полной задачей вы сталкиваетесь, пытаясь выбрать, что ценного привезти из командировки, учитывая, что вес багажа ограничен. Если каждый раз вы не можете определиться, не расстраивайтесь: понять, как уложить в чемодан покупки на максимальную сумму и при этом не выйти за лимит по весу, невозможно за время человеческой жизни. Задача о рюкзаке — так эта проблема именуется в математике — определяет огромное количество решений в жизни: от выбора стратегии оптимального капиталовложения до схемы, как разместить товары на складе ограниченного объема.
Собрать рюкзак, упаковав в него нужные вещи с учетом ограничений, невозможно за время человеческой жизни. Фото: Jillian Kern/flickr
Помочь в решении NP-полных задач не может ни одно классическое вычислительное устройство в мире. Классическое — то есть основанное на привычных алгоритмах и решающее в единицу времени только одну задачу (многозадачность современных операционных систем искусственная, а базовые процессы по-прежнему происходят по очереди). Все, на что они способны, — слегка уменьшить время решения. Но существуют машины, которые справляются с NP-полными задачами за считанные секунды. Это квантовые компьютеры, и впервые их существование предрек выдающийся физик Ричард Фейнман.

Все и сразу


Еще в 1981 году, отвечая на вопрос, можно ли смоделировать физику на компьютере, он ответил, что можно, но не всю: квантовые процессы — то есть процессы, которые происходят с элементарными частицами, — принципиально не могут быть воспроизведены на обычном компьютере. Эти процессы включают слишком много составляющих, и чтобы проследить их все, нужно огромное количество времени. Предположим, что для описания одной элементарной частицы достаточно двух переменных (в реальности их больше). Для того чтобы описать n частиц, нужно 2n переменных. Для описания 100 частиц требуется 2

​100
​​ переменных, и это число с 30 нулями.

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

Квантовый компьютер, как и классический, оперирует информацией, выраженной в битах. Но в отличие от стандартных машин, которые работают только с двумя состояниями бита — 0 и 1 — квантовые вычислительные устройства легко совмещают их в любых пропорциях. Если представить два состояния классического бита стрелочками, направленными вверх и вниз, то состояния квантового бита (кубита) можно изобразить (очень грубо) как поверхность сферы, и выходящая из ее центра «стрелочка» кубита может поворачиваться в любых направлениях в зависимости от того, какая «доля» 0 и 1 есть в том или ином состоянии кубита. Такое смешанное состояние называется суперпозицией.
Художественное представление кубита. Изображение: Saltay Boltay/shutterstock
Благодаря тому что кубит может одновременно существовать во многих состояниях, оперирующий кубитами квантовый компьютер легко справляется с задачами, требующими перебора. Вместо того чтобы по одному рассматривать все состояния системы (например, варианты упаковки рюкзака), он анализирует множество состояний одновременно, позволяя сократить время решения на порядки. Если говорить о реальных задачах, например о разложении числа на множители (например, для взлома пин-кода), то для числа с 400 значимыми цифрами мощный суперкомпьютер найдет решение за 10 миллиардов лет, а несложный квантовый — за три года. 

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

Реальность


Правда, пока кантовые компьютеры так лихо решают NP-полные задачи только в теории. На практике самым сложным вычислением, которое осилила система из кубитов, стало разложение 15 на множители 5 и 3. Это было сделано в 2001 году при помощи ЯМР (ядерно-магнитного резонанса) в лабораториях компании IBM. Эксперимент был реализован так: в жидкости плавало множество (а именно 1018, или миллиард миллиардов) специально созданных молекул, у каждой из которых было семь спинов. Молекулы, а точнее их спины, вели себя как кубиты. Чтобы заставить молекулы взаимодействовать, ученые использовали радиоимпульс, а затем измеряли спины проконтактировавших кубитов. За прошедшие 14 лет исследователи научились делать более простые и более дешевые убиты, повторили эксперимент на сверхпроводников кубитах (кстати, недавно в России также создали сверхпроводящий кубит), но прорыва в вычислительной мощности квантовых компьютеров не произошло.

И тем не менее физики оптимистичны. «Были принципиальные трудности, которые видели многие физики и которые казались непреодолимыми. Сейчас они преодолены, и дальше вопрос только в технических ухищрениях. То есть это не является принципиально невозможным», — объясняет Алексей Устинов, профессор Технологического института Карлсруэ (Германия), который руководит одной из исследовательских групп Российского квантового центра. «Чердак» пообщался с ученым на третьей международной конференции по квантовым технологиям,  которая проходит в Москве с 13 по 17 июля.
Ученые из Технологического института Джорджии работают над оптическими ловушками — устройствами, при помощи которых создаются кубиты. Фото: Rob Felt, Georgia Tech Research Institute

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

Еще один способ сделать квантовые компьютеры более надежными — «размазать» состояние одного кубита по нескольким. Такие «сложные» убиты, в которых одно состояние кодируется несколькими физическими носителями, называются логическими кубиками, и именно они считаются наиболее перспективными.

По мере того как инженеры будут создавать все более сложные квантовые компьютеры, они неизбежно столкнутся с проблемой черного ящика. Пока ученые имеют дело с не очень сложными квантовыми системами, они могут смоделировать — и понять — их работу, моделируя ее на классических компьютерах. Для систем из большого количества кубитов создать такую модель принципиально невозможно — ровно потому, что квантовые системы приспособлены решать задачи, недоступные стандартным компьютерам. «Для проверки нам придется рассчитывать одно и то же несколькими способами и сверять квантовый компьютер с квантовым компьютером, — говорит Устинов. — Но такой сложности мы пока еще не достигли и можем проверить все, что делают квантовые компьютеры, на обычных». Самый «продвинутый» квантовый компьютер сегодня состоит из девяти кубиков.

Ученый полагает, что первые работающие квантовые вычислительные устройства, которые решают конкретные задачи, появятся лет через десять. С универсальным квантовым компьютером все сложнее: в самом ближайшем будущем такая машина вряд ли появится. Кстати, уже сегодня за каких-то 11 миллионов долларов можно приобрести квантовый компьютер канадской фирмы D-Wave, содержащий тысячу кубитов. На всякий случай: его уже купил Google, хотя интернет-гигант создает собственный квантовый компьютер. Правда, многие ученые с осторожностью отзываются об устройстве: по словам Устинова, есть сомнения, что оно все время работает в квантовом режиме. Кроме того, D-Wave — так называемый адиабатический квантовый компьютер, то есть взаимодействие кубитов в нем во многом пущено на самотек. Такой подход считается менее перспективным.
Квантовый компьютер D-Wave с виду больше всего напоминает рентгеновский сканер в аэропорту. Фото: NASA (агентство тоже приобрело себе канадский квантовый компьютер)

Экспериментальные квантовые компьютеры, на которых исследователи отрабатывают технологии, занимают небольшую комнату — из-за того что большинство существующих квантовых систем нужно охлаждать до сверхнизких температур: так они лучше работают. Холодильники, дающие температуры, близкие к абсолютному нулю (а это минус 273,15 градуса по Цельсию), дешевеют и работают без участия человека, но они все равно большие, так что квантовых смартфонов или ноутбуков ждать не приходится. Впрочем, они не очень нужны: обычные процессоры, установленные в мобильных устройствах, отлично справляются. Кроме того, пока у нас нет повседневных задач, требующих квантовых вычислений. Но, как это уже не раз бывало, они вполне могут появиться после того, как будет созданы поддерживающие их технологии.
                                                                                                                                                                                       Ирина Якутенко