Квантовые вычисления и коммуникация:реальность и перспективы

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

Автору приходилось слышать всевозможные, иногда противоречащие друг другу спекуляции по поводу квантовых компьютеров: от отрицания самой возможности существования таковых до утверждений, что квантовые компьютеры большой мощности уже тестируются в лабораториях. В этой небольшой статье мы расскажем о нескольких существующих квантовых вычислительных устройствах и кратко коснемся более отдаленных планов развития квантовых компьютеров (О квантовых вычислениях и технологиях квантовых устройств наш журнал уже не раз писал. Обширные материалы на эту тему есть в «КТ» ##224, 373, 385, 414 и др).

Начнем с уточнения термина «квантовый компьютер». Обычно слово «компьютер» связывают с одной из реализаций так называемой архитектуры фон Неймана, предложенной Джоном фон Нейманом (John von Neumann) еще в 1945 году. В этой архитектуре вычисляющая машина состоит из четырех частей: памяти, системы ввода/вывода (I/O), арифметическо-логического блока (ALU) и системы управления. В качестве примеров назовем соответственно: жесткий диск и оперативную память; клавиатуру, дисплей, принтер; процессор; программное обеспечение. Однако в квантовом случае можно говорить о реализации лишь одной из составляющих фон-неймановской архитектуры — системы ввода-вывода. Остальные составляющие не имеют квантовых аналогов в привычном нам понимании. Например, память квантового компьютера, работающего с N квантовыми битами, в теории бесконечна и вероятностна, но при этом позволяет считывать только N обычных бит информации, причем чтение информации разрушает саму вычисляющую систему (заодно отметим, что существующие сегодня квантовые компьютеры могут обрабатывать и хранить информацию только в течение долей секунды). ALU квантового компьютера даже теоретически допускает применение только обратимых операций, а на практике оказывается, что и не любая обратимая операция может быть выполнена за конечное время. Система управления (в традиционном смысле) принципиально не может быть частью квантового вычислителя. В результате от привычного содержания слова «компьютер» в квантовом случае остается лишь условная способность «считывать информацию».

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

Как бы ни развивалась технология квантовых вычислителей, они вряд ли целиком и полностью заменят классические компьютеры. В лучшем случае, как представляется автору, будут созданы квантовые сопроцессоры, ответственные за определенные типы вычислений. Бегло напомним основные принципы, на которых построены квантовые вычисления (подробное и строгое введение в предмет см., например, в [1]).

Единичный квантовый бит (кубит, qubit), основа всех квантовых вычислений, — это квантовая система, которая может находиться в одном из двух классических состояний, |0> или |1> или в так называемом смешанном состоянии, a|0> + b|1> (a и b — комплексные числа называемые амплитудами, такие, что |a|² + |b|² = 1). При попытке узнать состояние кубита окажется, что с вероятностью |a|² измерение даст |0>, а с вероятностью |b|² — |1>. Каждое последующее измерение даст (уже с вероятностью 1) тот же результат (|0> или |1>), что и первое измерение. В общем случае квантовая система с N кубитами имеет 2^N нормированных амплитуд. Эволюция этой системы математически описывается так называемым унитарным оператором. Квантовое вычисление состоит в том, что система кубитов приводится в исходное состояние, кодирующее начальные данные, после чего специальным образом организуется эволюция этой системы. Проведенное в нужный момент измерение дает (вероятностную) информацию о результате вычисления. Интерес к квантовым вычислениям во многом определяется тем, что по такой схеме удается (хотя бы теоретически) решить некоторые задачи, не решаемые на классическом компьютере за приемлемое время.

Для некоторых задач квантовые алгоритмы пока существуют лишь на бумаге, для других они уже реализованы «в железе». Так, компании ID Quantique [2] и MagiQ Technologies [3] недавно выпустили на рынок свои квантовые системы: генератор случайных чисел и дистрибьютор секретного ключа (устройство для обмена секретными ключами, которые используются для шифрования сообщений).

Математическая схема работы генератора случайных чисел проста. Создается кубит в состоянии |0>, затем к нему применяется так называемое преобразование Адамара. После этого при измерении данного кубита значения |0> или |1> появятся с одинаковыми вероятностями. Повторив процесс N раз, мы получим случайное целое число в пределах от 0 до 2^N – 1. Проблема создания случайного числа крайне важна во многих криптографических протоколах. Отсюда и интерес к квантовым технологиям ее решения, где случайность не имитируется детерминированными классическими вычислениями, а связана с физикой работы самого вычислителя.

Надежный дистрибьютор секретного ключа необходим для применения высоконадежных криптосистем, использующих такие ключи. Рассмотрим, например, классический абсолютно стойкий шифр Вернама, который действует так. Для шифрования булевой строки длины N используется секретный ключ — полностью случайная булева строка длины N. Допустим, что Алиса и Боб имеют этот секретный ключ и больше никто в мире его не знает. Чтобы послать Алисе сообщение (булеву строку длины N), Боб побитно складывает текст сообщения с секретным ключом по модулю 2 и пересылает результат Алисе. Алиса, имея точно такой же ключ, сможет восстановить исходное сообщение, побитно сложив полученную от Боба строку с ключом. Шеннон показал, что такой шифр будет абсолютно стойким при условии полной случайности ключа и однократности его использования. Имеются и другие весьма стойкие шифры, использующие секретный ключ (в том числе и для многократного обмена информацией), но их практическое применение осложняется тем, что Алиса и Боб (и только они!) должны заранее получить нужное количество секретных ключей. Для решения этой проблемы и нужен дистрибьютор секретного ключа.

Квантовый дистрибьютор секретного ключа [3], реализованный компаниями ID Quantique и MagiQ Technologies, использует протокол BB84, предложенный Беннетом (Charles Bennett) и Брассаром (Giles Brassard) в 1984 году [4]. Общая схема работы протокола такова. Алиса создает N кубитов в случайных базисных состояниях (|0> или |1>) и случайную булеву строку длины N. Если k-й элемент этой случайной строки равен единице, то к k-му кубиту она применяет преобразование Адамара; если же этот элемент равен 0, с k-м кубитом ничего не делается. Затем Алиса высылает кубиты по квантовому каналу. Получатель Боб сам решает, измерять ли каждый из полученных кубитов сразу или сначала применить к нему обратное (совпадающее, впрочем, с прямым) преобразование Адамара, а потом провести измерение. Последовательность произведенных измерений (но не результатов измерений!) Боб высылает Алисе по обычному каналу связи. Эта информация не секретна. Алиса в ответ высылает Бобу перечень тех позиций, по которым измерения Боба и Алисы совпадают (она-то знает, как надо было правильно измерять),— опять же по обычному, не секретному каналу связи. На основе этой информации Боб и Алиса создают последовательность случайных чисел, известную только им двоим (рш иф) и имеющую в среднем длину N/2.

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

В Лос-Аламосской национальной лаборатории ведутся исследования по беспроводной передаче ключа. В частности, был проведен опыт, в котором единичный фотон выстреливался из фотонной пушки и регистрировался датчиком, находящимся в 10 км от источника. Удалось добиться передачи секретных данных со скоростью 45576 бит/час днем и 113273 бит/час ночью (из-за высокой дневной освещенности создается много помех, мешающих «поймать» нужный фотон) [5]. В дальнейшем ученые надеются научиться перебрасывать фотоны с Земли на спутники и обратно, а также между спутниками, что позволит реализовать квантовое распределение ключей на очень больших расстояниях.

Более сложные квантовые алгоритмы пока далеки от практической реализации. Самый знаменитый из них — квантовая факторизация, то есть разложение целого числа на простые множители. Быстрый алгоритм для решения этой задачи позволил бы взломать RSA — один из самых распространенных криптопротоколов, и тем самым сильно изменить криптографию как науку, а также многие криптографические приложения. Такой алгоритм, реализуемый за разумное время на обычном компьютере, пока не найден. Сенсацией, привлекшей внимание ко всей области квантовых вычислений, стало создание Питером Шором (Peter Shor) в 1994 году быстрого квантового алгоритма факторизации [6]. Для числа из n знаков этот алгоритм требует n³(log n)^k (k — константа) шагов. Самый мощный из известных на сегодня квантовый компьютер, построенный в 2001 в лаборатории IBM под руководством Айзека Чуанга (Isaac Chuang), работает только с семью кубитами и позволяет, используя алгоритм Шора, разложить на множители лишь числа, не больше 15. Квантовая система, состоящая из, скажем, 1000 кубитов, в теории позволила бы раскладывать на множители 500-значные булевы (приблизительно 150-значные десятичные) числа, что имело бы большой практический и теоретический интерес. Однако специалисты до сих пор ведут более [7] и менее [8] научные споры даже о принципиальной возможности создания квантовых вычислительных систем, работающих с таким количеством битов.

Среди технологий, с помощью которых ученые пытаются построить более мощные квантовые вычислители, назовем оптическую технологию, технологию ядерного магнитного резонанса (ЯМР) и технологию на основе переходов Джозефсона (Josephson junctions). Оптическая технология хороша тем, что с нею удобно работать (именно в ней реализованы описанные выше квантовые устройства). Однако одновременная работа уже с парой кубитов при этом довольно сложна из-за слабой связи между фотонами. С помощью технологии ЯМР была создана самая большая известная автору рабочая квантовая система, содержащая семь кубитов. Но используемые способы приготовления начального состояния квантовой системы в технологии ЯМР неэффективны. В технологии же переходов Джозефсона главная проблема — создание единичного стабильного кубита, зато наращивание их количества представляется не столь сложным.

В заключение упомянем о менее известных квантовых алгоритмах [9]. Отметим квантовое преобразование Фурье, работающее быстрее классического. Алгоритм Гровера (Grover), позволяющий вести поиск в неупорядоченной базе данных из N записей за время ЎN, представляется автору статьи не слишком перспективным из-за сложности приготовления начального состояния. Наконец, существует алгоритм Дойча-Джосы (Deutsch-Jozsa) — по-видимому, первый в истории пример квантового алгоритма, превосходящего по скорости классический. Практическое применение ему пока не найдено.

Литература

[1] М. Nielsen, and I. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2000. (См. также А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления. М., МЦНМО-ЧеРо, 1999.)
[2] ID Quantique, www.idquantique.com.
[3] MagiQ Technologies, www.magiqtech.com.
[4] C.H. Bennett, and G. Brassard, Quantum cryptography: Public-key distribution and coin tossing. Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, Dec 1984, pp. 175-179.
[5] www-inst.eecs.berkeley.edu/~cs191/lectures/UC_Berkeley_lecture_1103.pdf.
[6] tph.tuwien.ac.at/~oemer/doc/quprog/node18.html.
[7] S. Aaronson, Multilinear Formulas and Skepticism of Quantum Computing. Proceedings of ACM STOC 2004, www.cs.berkeley.edu/~aaronson/research.html.
[8] L. Levin, Polynomial time and extravagant models. Problems of Information Transmission 39(1), 2003. www.cs.bu.edu/fac/lnd/misc/qc.html.
[9] «Квантовый компьютер и квантовые вычисления», тт. 1, 2, Ижевск, 1999.