Что не может вычислить традиционный компьютер?
— У нас, — сказала Алиса, с трудом переводя дух, — когда долго бежишь со всех ног, непременно попадешь в другое место.
— Какая медлительная страна! — сказала Королева. — Ну, а здесь, знаешь ли, приходится бежать со всех ног, чтобы только остаться на том же месте! Если же хочешь попасть в другое место, тогда нужно бежать по меньшей мере вдвое быстрее!
Л. Кэрролл. Алиса в Зазеркалье
С самого начала совершенствование компьютера связано в основном с изменением принципов физической реализации элементов компьютерной системы — от электромагнитных реле, транзисторов до интегральных схем. Технологический прогресс очевиден, но он привел только к увеличению скорости вычислений в несколько сотен раз. Однако для довольно обширного класса задач недостаточно линейного увеличения быстродействия компьютерной системы, поскольку время их решения экспоненциально зависит от числа битов во входных данных. В этом смысле такие задачи одинаково трудны как для первого компьютера (разностной машины Чарльза Бэббиджа), так и для современного цифрового компьютера. Примером может служить факторизация — разложение числа на простые множители. В настоящее время не существует быстрых алгоритмов ее решения, а факторизация больших чисел практически невыполнима даже на современных компьютерах, объединенных в сеть. Так, чтобы разложить на простые множители число, состоящее из 155 цифр, потребовалось 3,7 месяца при распределенной обработке информации в компьютерной сети. Для факторизации числа, состоящего из 2000 цифр, потребуется время, превышающее время существования Вселенной, даже при условии, что каждая элементарная частица будет представлять собой классический компьютер, решающий эту задачу. Становится понятно, что простым «умножением» мощности компьютерных систем подобные проблемы не разрешить. Идея, позволяющая преодолеть экспоненциальный барьер сложности, была высказана в 1982 г. физиком Ричардом Фейнманом [1], изучающим моделирование квантово-механических объектов.
Квантовые объекты
Лавка была битком набита всякими диковинками, но вот что странно: стоило Алисе подойти к какой-нибудь полке и посмотреть на нее повнимательней, как она тотчас же пустела, хотя соседние полки прямо ломились от всякого товара.
— Какие здесь вещи текучие! — жалобно проговорила Алиса.
Л. Кэрролл. Алиса в Зазеркалье
Квантовые объекты — это частицы очень малой массы, находящиеся в очень малых участках пространства. Их поведение изучает квантовая механика, законы которой и предложил использовать Фейнман для построения квантового компьютера.
С точки зрения здравого смысла квантовые объекты обладают непостижимыми свойствами. Например, любое измерение, производимое над квантовым объектом, оказывает на него воздействие. Чем точнее измерение, тем сильнее воздействие, и лишь при измерениях очень малой точности воздействие на объект может быть слабым. Вдобавок к этому существуют величины, которые не могут быть измерены одновременно. В частности, если электрон в результате измерения получил определенные координаты, то при этом он не обладает никакой скоростью, и наоборот, обладая скоростью, электрон не может иметь определенного местонахождения.
Состояние квантовой системы невозможно полностью определить с помощью измерений. «Неуловимость» квантовых частиц объясняется тем, что они находятся в состоянии когерентной суперпозиции, т. е. одновременно в нескольких разных состояниях. Измерение вынуждает частицу принять одно из этих состояний.
Неполнота информации о квантовой системе накладывает запрет на клонирование квантовых объектов: поскольку нельзя получить полную информацию о системе, ее невозможно реконструировать. Можно предположить, что это создает непреодолимые препятствия в работе с квантовыми объектами. Однако Чарльз Беннет [2] показал, что именно невозможность клонирования позволяет осуществлять передачу квантовых объектов на расстояние — телепортацию (см. врезку «Квантовая телепортация»).
Квантовые биты
— Не может быть! — воскликнула Алиса. —
Я этому поверить не могу!
— Не можешь? — повторила Королева с жалостью. —
Попробуй еще раз: вздохни поглубже и закрой глаза.
Алиса рассмеялась.
— Это не поможет! — сказала она. — Нельзя поверить в невозможное!
— Просто у тебя мало опыта, — заметила Королева. — В твоем возрасте я уделяла этому полчаса каждый день! В иные дни я успевала поверить в десяток невозможностей до завтрака!
Л. Кэрролл. Алиса в Зазеркалье
По образному выражению Ю. И. Манина [3], работающего в области квантовых вычислений, в современной математике «имеется преобладающая тенденция, предписывающая выражать на квантовом языке все, что движется». Эта участь не миновала и вычислительные процессы.
При классическом подходе бит в каждый момент времени может находиться в одном из двух состояний — 0 или 1. В зависимости от элементной базы компьютерной системы им могут соответствовать различные значения каких-либо физических параметров (например, заряжен конденсатор или разряжен и т. п.). Квантовый бит, или кубит (qubit), отличается от традиционного бита тем, что может находиться одновременно в двух состояниях, т. е. хранит 0 и 1 одновременно (в этом случае говорят, что кубит находится в состоянии квантовой суперпозиции). Как известно, идеи типа «два в одном» могут быть очень продуктивными.
Рассмотрим набор, состоящий из трех кубитов, который будем называть квантовым регистром. Любой классический регистр, состоящий из трех битов, может содержать в каждый момент времени только одно из восьми возможных значений: 000, 001, 010, ..., 111, в то время как квантовый регистр может одновременно хранить все восемь чисел. Если мы будем добавлять кубиты в регистр, то его объем будет увеличиваться экспоненциально — 3 кубита могут хранить 8 различных чисел, 4 — 16, L кубитов смогут хранить 2L чисел одновременно. Поскольку квантовый регистр содержит все числа одновременно, над ними можно одновременно произвести операцию. Это означает, что квантовый компьютер может только за один вычислительный шаг осуществить операцию над 2L различными числами, классическому же компьютеру для выполнения этой операции потребовалось бы повторять ее 2L раз или запускать 2L процессоров, работающих параллельно. Иначе говоря, квантовый компьютер дает колоссальный выигрыш в использовании таких компьютерных ресурсов, как память и время.
Настал момент объяснить, каким образом можно извлечь информацию из кубита. Классические биты легко измерить, а вот кубиты весьма чувствительны — процедура измерения может их разрушить. Измерение кубита носит вероятностный характер: до проведения измерения мы можем сказать, что его результат будет равен 0 с некоторой вероятностью или 1 — с некоторой вероятностью . Если измерение произведено и получен результат 1, то кубит переходит в соответствующее состояние (коллапсирует), если получен 0, то кубит коллапсирует в 0. При повторном проведении измерения значение кубита можно предсказать абсолютно достоверно. Значит, если при первом измерении кубит принял значение 0, то при втором измерении будет также получено значение 0. Вероятностная природа кубитов, которая одновременно является и детерминированной, является мощным орудием для разработки новых принципов решения задач.
Квантовая логика
— Я не знаю, о чем ты думаешь, — сказал Труляля, —
но это не так! Ни в коем разе!
— И задом наперед, совсем наоборот, — подхватил Траляля. — Если бы это было так, это бы еще ничего, а если бы ничего, оно бы так и было, но так как это не так, так оно и не этак!
Такова логика вещей!
Л. Кэрролл. Алиса в Зазеркалье
Основные принципы создания универсального квантового компьютера определил Дэвид Дейч [4] в работе, опубликованной в 1985 г. Начинать же построение реального квантового компьютера необходимо с разработки квантовых логических элементов (вентилей, гейтов). Квантовый логический вентиль, как и классический, — устройство, позволяющее осуществить одну из элементарных логических операций. Безусловно, квантовый логический вентиль должен отличаться от классического, поскольку он будет взаимодействовать с кубитами, находящимися в состоянии квантовой суперпозиции.
Рассмотрим принципы работы квантового логического вентиля NOT (операции отрицания), не сильно углубляясь в «физику процесса». Роль кубита может играть квантовая система с (как минимум) двумя хорошо различимыми дискретными состояниями. В качестве такой системы может выступать атом (в различных экспериментах использовались атомы рубидия и бериллия), как известно, характеризующийся определенным дискретным набором состояний электронов. Можно выбрать два из таких состояний и сопоставить одно из них (основное) — значению 0, а другое (возбужденное) — 1. Для осуществления операции NOT необходимо иметь возможность переводить кубиты, находящиеся в состоянии 0, в состояние 1, и наоборот. Для этого может использоваться световой импульс определенной частоты и интенсивности: если электрон находился в состоянии 0, он поглощает некоторую порцию энергии из светового потока и переходит в состояние 1; если электрон находился в состоянии 1, световой импульс заставляет его перейти в состояние 0.
Описанная таким образом операция отрицания понятна и с чисто классических позиций. Однако могут быть введены и не имеющие аналогов в классике квантовые операции. Что, например, произойдет, если упомянутый выше световой импульс будет обладать лишь вдвое меньшей частотой, чем необходимо для перевода электрона из одного состояния в другое? В результате электрон окажется в состоянии квантовой суперпозиции основного и возбужденного состояний. Если повторить такой световой импульс, результат будет эквивалентен обычной операции NOT, поэтому описанную операцию называют «корень квадратный из NOT». Используя такого рода операции, можно получить в квантовом компьютере состояние квантовой суперпозиции, обеспечивающее, как мы видели, параллельную обработку нескольких чисел.
Квантовые алгоритмы
—...Я как раз изобретал новый способ перелезания через калитку. Хочешь послушать?
— Пожалуйста, — сказала Алиса вежливо.
— Понимаешь, я рассуждал так: единственная трудность в ногах — как поднять их наверх. Голова и так наверху! Значит, так: сначала кладем голову на калитку — голова, значит, уже наверху.
Потом становимся на голову — тогда и ноги тоже наверху, правда?
И перемахиваем на ту сторону!
Л. Кэрролл. Алиса в Зазеркалье
Однако вернемся к факторизации больших чисел. Решение этой задачи интересно еще и тем, что защита многих секретных данных в настоящее время строится на том, что классический компьютер не может за приемлемое время разложить большое число на простые множители. Питер Шор [5] разработал первый квантовый алгоритм, предназначенный для факторизации, чем дал огромный толчок развитию квантовых вычислений.
|
| Схема алгоритма Шора |
Чтобы проиллюстрировать отличия квантовых алгоритмов от классических, остановимся на алгоритме Шора более подробно. Предположим, что N — число, которое нужно разложить на простые множители. Выберем целое число с, меньшее N, и вычислим значение функции:
f(x) = cx mod N,
т. е. найдем остаток от деления cx на N. Математики показали, что данная функция будет периодической, и ее период r позволяет получить простые множители для числа N. Поскольку f(0) = 1 и r — период функции f, то f(r) = 1. Наименьшее ненулевое натуральное число r, отвечающее условию cr = 1 mod N, называют порядком числа с по модулю N. Так как
(cr/2 - 1) (cr/2 + 1) = cr - 1 = 0 mod N,
то наибольший общий делитель — НОД(cr/2 - 1, N) даст искомый результат (сам же НОД может быть найден с помощью алгоритма Евклида за полиномиальное время, т. е. «достаточно быстро»).
Алгоритм Шора предполагает использование двух квантовых регистров, каждый из которых состоит из q кубитов (q должно быть достаточным для размещения в регистре числа N). Вначале первый регистр переводится в состояние суперпозиции, в котором он хранит одновременно все числа от 0 до N. Содержимое первого регистра используется в качестве аргумента при вычислении функции f(x), результат которого помещается во второй регистр. После этого над первым регистром совершается квантовое преобразование Фурье. Шор показал, что в итоге система, состоящая из этих двух квантовых регистров, с большой вероятностью переходит в состояние, позволяющее определить порядок r числа c. Для однозначного определения r алгоритм может быть повторен несколько раз. Шор показал также, что все необходимые для осуществления его алгоритма преобразования могут быть выполнены на квантовом компьютере за полиномиальное время.
Впоследствии появились квантовые алгоритмы для моделирования поведения квантово-механических систем, потенциальная сфера приложения которых — квантовая химия. Лов Гровер [6] предложил квантовый алгоритм для поиска информации в базе данных. Исследуется применение «квантовых стратегий» для решения задач теории игр. Пока невозможно точно очертить круг задач, решение которых может быть существенно ускорено при применении квантовых алгоритмов. Причина, возможно, кроется в том, что, как отмечает Джон Прескилл [7], «все еще недостает глубокого понимания, как работают квантовые алгоритмы». Это понимание может проложить путь к созданию новых эффективных методов решения.
Квантовая криптография
Но я обдумывал свой план,
Как щеки мазать мелом,
А у лица носить экран,
Чтоб не казаться белым.
Л. Кэрролл. Алиса в Зазеркалье
Итак, если удастся построить квантовый компьютер, способный выполнять разложение больших чисел на множители с помощью алгоритма Шора, защита информации в подавляющем большинстве сегодняшних систем окажется ненадежной. Но, оказывается, квантовый мир может дать и средство для обеспечения секретности при обмене информацией.
Как известно, традиционные защитные системы основаны на том, что передаваемое сообщение с помощью некоторого алгоритма комбинируется с дополнительной секретной информацией (ключом), в результате чего получается криптограмма. Если для каждого сообщения использовать отдельный ключ, то обеспечивается абсолютная секретность. Но как скрытно передать сам ключ? Этот вопрос составляет суть проблемы распространения ключа.
Для любой системы передачи информации характерны следующие действующие лица: объекты А и Б, обменивающиеся информацией (будем называть их Алиса и Боб — Алиса передает информацию Бобу), и некто Е, пытающийся перехватить эту информацию (в дальнейшем — Ева). Предложенный в 1984 г. Чарльзом Беннетом и Джилом Брассардом [8] метод квантового распространения ключа (quantum key distribution) позволяет передать ключ от Алисы к Бобу так, что попытка его перехвата неизбежно будет обнаружена.
? Алиса и Боб должны быть соединены квантовым каналом связи (волоконно-оптический канал, в котором информация переносится с помощью фотонов) и обычным общедоступным каналом (например, телефонные линии или Internet-соединение).
? Алиса посылает фотон в одном из четырех поляризованных состояний (вертикальном, горизонтальном, под углами +45?, -45?), которое выбирает случайно, и записывает результат. Боб располагает двумя анализаторами: один анализатор позволяет определять вертикально и горизонтально поляризованные фотоны, другой — фотоны, поляризованные под углами +45? и -45?. Для регистрации каждого фотона Боб случайно выбирает анализатор, записывает выбор и результат, который был получен. Вероятность того, что он выберет неверный анализатор, составляет 50%.
? После получения достаточного количества фотонов Боб по общедоступному каналу сообщает Алисе, какие анализаторы он использовал, но не сообщает, какие результаты он получил. Алиса сравнивает эту последовательность со своей записью и сообщает Бобу, для каких фотонов он правильно выбрал анализатор, но не сообщает, какова была поляризация этих фотонов. Из последовательности выбрасываются те биты, для которых не были применены соответствующие анализаторы. Для оставшихся битов Алиса и Боб должны иметь одинаковые результаты при условии, что Ева не производила перехват.
? Алиса и Боб выбирают случайное подмножество ключа и сравнивают его по общедоступному каналу. Предположим, что Ева разрезала кабель и выполняет измерения с помощью оборудования, аналогичного оборудованию Боба. После этого она посылает Бобу фотон в соответствии с результатами своих измерений (используя оборудование, аналогичное оборудованию Алисы). Тогда в 50% случаев Ева выберет неверный анализатор и будет посылать Бобу фотоны в случайно выбранных состояниях, что в 25% случаев даст ошибку. Таким образом, на этом этапе перехват информации может быть обнаружен.
? Однако ошибки могут возникать даже в том случае, если Ева не производила перехват. Они могут быть устранены посредством стандартных методов коррекции ошибок. Вычисленный коэффициент ошибки (обычно около 1%) может быть полностью отнесен на счет Евы. Процедура, называемая усилением секретности (privacy amplification), позволяет удалить из ключа информацию, которая могла быть перехвачена Евой, однако это вновь приводит к сокращению длины используемого ключа. Поэтому очень важно сделать коэффициент ошибок как можно более малым.
После осуществления указанной процедуры Алиса и Боб получают в распоряжение случайно сгенерированный ключ требуемой длины, благодаря которому они могут зашифровать сообщение и переслать его по общедоступному каналу. Если для каждого нового сообщения они будут повторять эту процедуру, то информация будет безусловно защищена от несанкционированного доступа. Нужно заметить, что этот «протокол» не может быть непосредственно использован для обмена информацией, поскольку часть информации, выбранная случайным образом, должна быть выброшена.
Техническая реализация
И молвил Морж: «Пришла пора
Подумать о делах:
О башмаках и сургуче,
Капусте, королях,
И почему, как суп в котле,
Кипит вода в морях».
Л. Кэрролл. Алиса в Зазеркалье
Для реализации квантовых расчетов необходимо решить несколько важных практических задач. Прежде всего нужно изолировать квантовую систему от окружающей среды на время, достаточное для выполнения расчета. Даже небольшое взаимодействие с внешней средой может привести к повреждению кубитов (проблема декогерентности). В настоящее время это является одним из основных препятствий в построении квантовых компьютеров. Исключительно чувствительны к подобным процессам сцепленные состояния кубитов, так как одно-единственное воздействие на любой из них сможет разрушить все состояние. Несмотря на то что квантовая система должна быть изолирована от окружающей среды, необходимо иметь возможность взаимодействовать с системой, чтобы переводить ее в нужное квантовое состояние. Кроме того, необходимо разработать механизмы для реализации квантовых логических операций, а также методы, позволяющие определять состояние квантовой системы по завершении вычислений. Все эти проблемы решаются в рамках проводящихся во всем мире экспериментов.
Одним из направлений исследований является применение для организации квантовых регистров ионных ловушек, управляемых лазерной вспышкой. Каждый ион представляет собой кубит. Основное и возбужденное состояния иона соответствуют значениям 0 и 1. Другая возможность — использовать кремниевый кристалл с точечно внедренными атомами, спины которых представляют собой кубиты квантового компьютера. В таком кристалле не будет электрического тока: взаимодействуя друг с другом, атомы будут передавать сообщение от одного к другому в соответствии с законами квантовой логики.
Наиболее перспективным считается использование ядерного магнитного резонанса (ЯМР) в жидкости, содержащей большое количество однотипных молекул. Кубиты кодируются с помощью спинa ядра каждого атома молекулы. Благодаря естественной изоляции от окружающей среды, ядерные спины являются особенно хорошими кубитами. В настоящее время имеются экспериментальные реализации квантовых алгоритмов с помощью ЯМР. В частности, осуществлена самая простая версия квантового алгоритма Дейча — Джозеса [9], который определяет, является ли некоторая неизвестная функция сбалансированной.
Для реализации «полновесных» программ потребуется около 1000 кубитов, что сейчас кажется недостижимой мечтой.
Некоторые ученые высмеивают мечту о появлении квантовых компьютеров, которая может осуществиться только в том случае, если произойдет революция в физике. Они считают, что декогерентность не сможет быть уменьшена до приемлемо малой величины, а следовательно, можно будет выполнить только несколько вычислительных шагов. Оптимисты же убеждены, что квантовый компьютер появится в ближайшие 10 лет. Вне зависимости от того, будет ли построен квантовый компьютер или нет, квантовые вычисления уже прочно заняли свое место в информатике. Развитие этой отрасли знаний потребует усилий специалистов, обладающих опытом в разных дисциплинах, включая математику, информатику, теоретическую и экспериментальную физику, химию и инженерию. Тем это и интересно!
ОБ АВТОРАХ
Виноградова Лилия Степановна — ассистент кафедры информационных технологий УкрГХТУ, Виноградов Константин Георгиевич — старший преподаватель той же кафедры, e-mail: viconstg@mail.ru
Литература
1. Feynman R. P. Simulating physics with computers // Int. J. of Theor. Phys. 1982. Vol. 21. P. 467 — 488.
2. Bennett C. H. et al. Teleporting an unknown quantum state via dual classic and Einstein — Podolsky — Rosen channels // Phys. Rev. Lett. 1993. 70 , P. 1893 —1899; Bennett C. H. Quantum information and computation // Phys. Today. 1995. 48, N 10. P. 24 — 30.
3. Манин Ю.И. Классическое вычисление, квантовое вычисление и алгоритм факторизации Шора // Квантовый компьютер & вычисления, 1999.
4. Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer // Proc. Roy. Soc. Lond. 1985. A 400. P. 97 — 117.
5. Shor P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer // SIAM J. Comput. 1997. 26, N 5. P. 1484 — 1509.
6. Grover L. K. A Fast Quantum Mechanical Algorithm for Database Search // Proc. of 28th Ann. ACM Symp. on the Theory of Computing. 1996. P. 212 —219.
7. Preskill J. Quantum computing: pro and con // Proc. Roy. Soc. Lond. 1998. A 454. P. 469 — 486 .
8. Bennett C. H., Brassard G. Proc. of IEEE Int. Conf. on Computers, Systems, and Signal Processing, Bangalore, India, 175. 1984.
9. Chuang I. L., Vandersypen L. M. K., Xinlan ZhouLeung D. W., Lloyd S. Experimental realization of a quantum algorithm // Nature. 1998. Vol. 393. P. 143 — 146.
Квантовая телепортация
...Алиса не удержалась, ткнула пальцем в Труляля и крикнула:
— Первый!
— Ни в коем разе! — тут же отозвался Труляля и так быстро захлопнул рот, что зубы щелкнули.
— Второй! — крикнула Алиса и ткнула пальцем в Траляля.
— Задом наперед, совсем наоборот! — крикнул он.
Другого Алиса и не ждала.
Л. Кэрролл. Алиса в Зазеркалье
Телепортация основана на эффекте сцепления (entanglement), который заключается в том, что два квантовых объекта, будучи сцеплены, ведут себя, как Труляля и Траляля из сказки Льюиса Кэрролла. Если произвести измерение одного из них, то другой «подстроится» к первому и примет противоположное значение. Любопытно, что этот эффект был открыт Альбертом Эйнштейном в 1935 г. «на бумаге», а экспериментально подтвержден физиками лишь в 90-х годах.
Схема телепортации такова. Предположим, что у Алисы есть частица в определенном квантовом состоянии (частица 1) и она хочет, чтобы у живущего от нее вдали Боба была такая же частица. Алиса не может произвести такие измерения, которые позволили бы Бобу реконструировать квантовую систему. Для того чтобы осуществить задуманное, Алисе и Бобу необходимо обзавестись парой сцепленных частиц (частицы 2 и 3). Алиса производит сцепление исходной частицы 1 и находящейся в ее распоряжении частицы 2. При этом частица 2 вначале переходит в состояние, «противоположное» состоянию частицы 1, а затем обе частицы оказываются в одном из четырех возможных сцепленных состояний (состояний Белла). Алиса определяет, какое состояние было реализовано, путем измерения, результаты которого она посылает Бобу. При сцеплении частица 3, находящаяся у Боба, сначала переходит в исходное состояние частицы 1 (ведь она сцеплена с частицей 2!), а затем — в то состояние, в котором частица 1 оказалась после сцепления. Боб, получив от Алисы результаты ее измерения и выяснив, в каком состоянии Белла находится его частица, может путем обратного преобразования перевести частицу 3 в состояние, в котором находилась частица 1 до телепортации. Важно, что во время телепортации Алиса разрушает состояние первой частицы, а Боб это состояние получает, при этом ни Алиса, ни Боб не получают никакой информации о состоянии частицы 1.
|
| Схема телепортации. (Bouwmeester D., Pan J.-W., Mattle K., Eibl M., Weinfurter H., Zeilinger A. Experimental quantum teleporting // Nature. 1997. Vol. 390) |