Как бы ни развивалась технология квантовых вычислителей, они вряд ли целиком и полностью заменят классические компьютеры. В лучшем случае, как представляется специалистам, будут созданы квантовые сопроцессоры, ответственные за определенные типы вычислений.
Вот основные принципы, на которых построены квантовые вычисления. Единичный квантовый бит (кубит, qubit), основа всех квантовых вычислений, - это квантовая система, которая может находиться в одном из двух классических состояний, |0> или |1> или в так называемом смешанном состоянии, a|0> + b|1> (a и b - комплексные числа называемые амплитудами, такие, что |a|2 + |b|2 = 1). При попытке узнать состояние кубита окажется, что с вероятностью |a|2 измерение даст |0>, а с вероятностью |b|2 - |1>. Каждое последующее измерение даст (уже с вероятностью 1) тот же результат (|0> или |1>), что и первое измерение. В общем случае квантовая система с N кубитами имеет 2N нормированных амплитуд. Квантовое вычисление состоит в том, что система кубитов приводится в исходное состояние, кодирующее начальные данные, после чего специальным образом организуется эволюция этой системы. Проведенное в нужный момент измерение дает (вероятностную) информацию о результате вычисления. Интерес к квантовым вычислениям во многом определяется тем, что по такой схеме удается (хотя бы теоретически) решить некоторые задачи, не решаемые на классическом компьютере за приемлемое время.
Для некоторых задач квантовые алгоритмы пока существуют лишь на бумаге, для других они уже реализованы "в железе". Так, компании ID Quantique и MagiQ Technologies недавно выпустили на рынок свои квантовые системы: генератор случайных чисел и дистрибьютор секретного ключа (устройство для обмена секретными ключами, которые используются для шифрования сообщений).
Математическая схема работы генератора случайных чисел проста. Создается кубит в состоянии |0>, затем к нему применяется так называемое преобразование Адамара. После этого при измерении данного кубита значения |0> или |1> появятся с одинаковыми вероятностями. Повторив процесс N раз, мы получим случайное целое число в пределах от 0 до 2N – 1. Проблема создания случайного числа крайне важна во многих криптографических протоколах. Отсюда и интерес к квантовым технологиям ее решения, где случайность не имитируется детерминированными классическими вычислениями, а связана с физикой работы самого вычислителя.
Надежный дистрибьютор секретного ключа необходим для применения высоконадежных криптосистем, использующих такие ключи. Рассмотрим, например, классический абсолютно стойкий шифр Вернама, который действует так. Для шифрования булевой строки длины N используется секретный ключ - полностью случайная булева строка длины N. Допустим, что Алиса и Боб имеют этот секретный ключ и больше никто в мире его не знает. Чтобы послать Алисе сообщение (булеву строку длины N), Боб побитно складывает текст сообщения с секретным ключом по модулю 2 и пересылает результат Алисе. Алиса, имея точно такой же ключ, сможет восстановить исходное сообщение, побитно сложив полученную от Боба строку с ключом. Шеннон показал, что такой шифр будет абсолютно стойким при условии полной случайности ключа и однократности его использования. Имеются и другие весьма стойкие шифры, использующие секретный ключ (в том числе и для многократного обмена информацией), но их практическое применение осложняется тем, что Алиса и Боб (и только они!) должны заранее получить нужное количество секретных ключей. Для решения этой проблемы и нужен дистрибьютор секретного ключа.
Квантовый дистрибьютор секретного ключа, реализованный компаниями ID Quantique и MagiQ Technologies, использует протокол BB84, предложенный Беннетом (Charles Bennett) и Брассаром (Giles Brassard) в 1984 году. Общая схема работы протокола такова. Алиса создает N кубитов в случайных базисных состояниях (|0> или |1>) и случайную булеву строку длины N. Если k-й элемент этой случайной строки равен единице, то к k-му кубиту она применяет преобразование Адамара; если же этот элемент равен 0, с k-м кубитом ничего не делается. Затем Алиса высылает кубиты по квантовому каналу. Получатель Боб сам решает, измерять ли каждый из полученных кубитов сразу или сначала применить к нему обратное (совпадающее, впрочем, с прямым) преобразование Адамара, а потом провести измерение. Последовательность произведенных измерений (но не результатов измерений!) Боб высылает Алисе по обычному каналу связи. Эта информация не секретна. Алиса в ответ высылает Бобу перечень тех позиций, по которым измерения Боба и Алисы совпадают (она-то знает, как надо было правильно измерять),- опять же по обычному, не секретному каналу связи. На основе этой информации Боб и Алиса создают последовательность случайных чисел, известную только им двоим и имеющую в среднем длину N/2.
Имеющиеся в продаже квантовые дистрибьюторы случайных ключей используют оптическую квантовую технологию и пересылают единичный фотон (являющийся физической реализацией единичного кубита) по оптоволокну на расстояния до 100 км. Передать ключ на большую дистанцию пока не удается, но можно надеяться на заметный прогресс - ведь, например, недавно коммерчески доступные дистрибьюторы работали лишь на расстояниях не более 67 км.
В Лос-Аламосской национальной лаборатории ведутся исследования по беспроводной передаче ключа. В частности, был проведен опыт, в котором единичный фотон выстреливался из фотонной пушки и регистрировался датчиком, находящимся в 10 км от источника. Удалось добиться передачи секретных данных со скоростью 45576 бит/час днем и 113273 бит/час ночью (из-за высокой дневной освещенности создается много помех, мешающих "поймать" нужный фотон). В дальнейшем ученые надеются научиться перебрасывать фотоны с Земли на спутники и обратно, а также между спутниками, что позволит реализовать квантовое распределение ключей на очень больших расстояниях.
Более сложные квантовые алгоритмы пока далеки от практической реализации. Самый знаменитый из них - квантовая факторизация, то есть разложение целого числа на простые множители. Быстрый алгоритм для решения этой задачи позволил бы взломать RSA - один из самых распространенных криптопротоколов, и тем самым сильно изменить криптографию как науку, а также многие криптографические приложения. Такой алгоритм, реализуемый за разумное время на обычном компьютере, пока не найден. Сенсацией, привлекшей внимание ко всей области квантовых вычислений, стало создание Питером Шором (Peter Shor) в 1994 году быстрого квантового алгоритма факторизации. Для числа из n знаков этот алгоритм требует n3(log n)k (k - константа) шагов. Самый мощный из известных на сегодня квантовый компьютер, построенный в 2001 в лаборатории IBM под руководством Айзека Чуанга (Isaac Chuang), работает только с семью кубитами и позволяет, используя алгоритм Шора, разложить на множители лишь числа, не больше 15. Квантовая система, состоящая из, скажем, 1000 кубитов, в теории позволила бы раскладывать на множители 500-значные булевы (приблизительно 150-значные десятичные) числа, что имело бы большой практический и теоретический интерес. Однако специалисты до сих пор ведут более и менее научные споры даже о принципиальной возможности создания квантовых вычислительных систем, работающих с таким количеством битов.
Среди технологий, с помощью которых ученые пытаются построить более мощные квантовые вычислители, назовем оптическую технологию, технологию ядерного магнитного резонанса (ЯМР) и технологию на основе переходов Джозефсона (Josephson junctions). Оптическая технология хороша тем, что с нею удобно работать (именно в ней реализованы описанные выше квантовые устройства). Однако одновременная работа уже с парой кубитов при этом довольно сложна из-за слабой связи между фотонами. С помощью технологии ЯМР была создана одна из самых больших рабочих квантовых систем, содержащая семь кубитов. Но используемые способы приготовления начального состояния квантовой системы в технологии ЯМР неэффективны. В технологии же переходов Джозефсона главная проблема - создание единичного стабильного кубита, зато наращивание их количества представляется не столь сложным.
Список использованых материалов:
Генетические алгоритмы
http://algolist.manual.ru/go.php?url=http://www.chat.ru/~saisa/
Квантовые вычисления
http://offline.computerra.ru
Статьи:
Квантовые кубики
Квантовые вычисления и связь: реальность и перспективы
http://www.neuropro.ru
http://algolist.manual.ru
Ежов А.А, Шумский С.А. Нейрокомпьютинг и его применение в экономике и бизнесе. М.: МИФИ, 1998. - 224с.