УДК 53:621.373.8:681.3
ВАЛИЕВ К.А.
изменяются согласно плану выполнения алгоритма. Доказано, что любой

квантовый алгоритм может быть разложен на последовательность
КВАНТОВАЯ ИНФОРМАТИКА:
преобразований состояний отдельных кубитов и пар кубитов (одно- и
КОМПЬЮТЕРЫ, СВЯЗЬ И КРИПТОГРАФИЯ
двухкубитовые преобразования, или "вентили"). Чтобы построить

квантовый компьютер, необходимо уметь осуществлять:
Физико-технологический институт РАН,
1) любые суперпозиции состояний |0> и |1> любого кубита,
117218, Москва, Нахимовский пр., 36/1
2)
контролируемый
одним ("контролирующим")
кубитом

преобразование НЕ другого ("контролируемого") кубита.
На рубеже Х1Х-ХХ вв. возникла великая физическая теория,
Контролируемое преобразование можно осуществить только при
описывающая свойства частиц и их движение в микромире - квантовая
наличии физического взаимодействия между контролирующим и
физика (механика).
контролируемым кубитами. Чтобы выполнить необходимые операции на
На квантовом уровне мир описывается уравнением Шредингера:
кубитах, на них воздействуют импульсами внешнего резонансного поля.

Квантовая эволюция состояния кубита |Y(t)> совершается согласно
ih
H^
=

уравнению Шредингера, где Hi (t) = -me0cos(wt + j) - энергия
t

.
взаимодействия дипольного момента m кубита и внешнего резонансного
Оператор Н линейный:
поля (например, лазера). При этом необходимо иметь возможность
^
воздействовать избирательно на любой избранный кубит.
H (a 1 + b 2 ) = a ^H 1 + b ^H 2 ,
Мысль о возможности построения квантового компьютера впервые
высказал Р.П. Фейнман. Квантовую часть компьютера составляют п
следствием чего является квантовый принцип суперпозиции состояний.
кубитов. К каждому из них может быть приложено селективное
Если квантовая система может существовать в состояниях |Y1> и b|Y2>, то
воздействие импульсами резонансного внешнего переменного поля.
она может столь же "законно" существовать и в состояниях их
Включение генераторов полей и адресация их излучения на данный кубит
суперпозиции: a|Y1> + b|Y2> = |Y>, a, b - комплексные амплитуды, |a|2 +
осуществляется под управлением классического компьютера. Эволюция
|b|2 = 1. Эволюция состояний квантовых систем происходит согласно
состояния кубитов изображается вдоль горизонтальных линий (ось
квантовому уравнению Шредингера.
времени) в виде последовательности однокубитовых и двухкубитовых
Квантовая система с двумя различимыми состояниями |Y0>, |Y1>
вентилей. До того как "запустить" вычислительный процесс на квантовом
способная нести 1 бит информации, получила название кубит (qubit). Если
компьютере, все n кубитов должны быть приведены в состояние |0>. Эта
состояния |Y0>, |Y1> связаны с двумя уровнями энергии E0 < Е1, то можно
процедура носит название "инициализация". Ввод данных и исполнение
говорить о двухуровневой системе. Простейшим случаем двухуровневой
алгоритма совершаются применением однокубитовых и двухкубитовых
квантовой системы является спин ядра атома или электрона / = 1/2 в
вентилей. По завершении алгоритма результат вычисления будет записан в
постоянном внешнем поле B0: два уровня энергии и состояния
конечном квантовом состоянии кубитов. Чтобы "считать" результат,
соответствуют проекциям спина на направление B0.
необходимо провести квантовое измерение состояния кубитов (одного или
Два оптических уровня энергии и состояния электрона в ионе также
нескольких). Квантовые алгоритмы решения сложных задач могут
могут быть выбраны в качестве двух состояний кубита.
состоять из большого числа (~109) операций (вентилей), выполняемых на
В других случаях состояния |Y0>, |Y1> могут различаться
компьютерах, содержащих -103 кубитов.
поляризацией (фотона) или фазой (сверхпроводника). Квантовая система
Сейчас
разработано
немного
алгоритмов
для
квантовых
может быть макроскопической (сверхпроводники, сверхтекучие жидкости,
компьютеров, но в том, что сделано, получены ошеломляющие результаты.
бозе-газ), отдельной атомной частицей, или колебательной модой. Все эти
В 1994 г. Шор создал алгоритм факторизации - то есть определения
системы могут быть использованы в качестве кубита.
простых множителей больших п разрядных чисел. На классическом
Некоторое число п кубитов образуют квантовый регистр
компьютере для этого требуется экспоненциально большое число
компьютера. В ходе выполнения квантового алгоритма состояния кубитов
операций. Недоступность этой задачи современным компьютерам

используется для кодирования (шифрования) секретной информации (в
электромагнитного поля. Возможно создание кубитов на состояниях
RSA криптосистемах). Шор показал, что квантовый компьютер способен
сверхпроводников,
разделенных
переходами
Джозефсона
и
решить эту задачу за n3 операций. Коэффициент ускорения задачи при
различающихся числом зарядов или фазой сверхпроводников. Модели
больших п может быть очень большим. Такое же ускорение имеет место
квантовых компьютеров могут быть построены на линейных оптических
при решении на квантовом компьютере задач квантовой физики. В то же
элементах
(делители
пучка,
поляризаторы,
фазовращатели,
время установлено, что многие алгоритмы, выполняемые неплохо на
интерферометры).
классических компьютерах, не ускоряются на квантовом.
В
ансамблевом
ядерном
магнитнорезонансном
квантовом
Ускорение процесса решения задач на квантовом компьютере лежит
компьютере кубитами выступают спины - ядер водорода (протоны) и
в квантовой природе кубитов. Квантовость кубитов приводит к нескольким
углерода 13С в молекулах жидкости. Так, в молекуле трихлорэтилена
феноменам.
спины ядер двух атомов 13С и одного протона образуют три кубита. Два
1. Гильбертово пространство состояний квантовой системы из n
атома 13С химически неэквивалентны и поэтому имеют различные частоты
кубитов имеет огромную размерность, равную 2n. Физически это означает,
ядерного магнитного резонанса wA и wB в заданном внешнем постоянном
что система имеет 2n базовых состояний, а состояние компьютера
магнитном поле B0, протон будет иметь третью резонансную частоту wC.
описывается суперпозицией из этих 2n базовых состояний. При
Подавая импульсы внешнего переменного магнитного поля на частотах
воздействии на какой-либо кубит одновременно изменяются все 2n
(ид, tog, о)с, мы селективно управляем квантовой эволюцией любого из
базовых состояний. Этот феномен носит название квантового
этих спинов (выполняем одноку битовые вентили). Между спинами ядер,
параллелизма.
разделенных одной химической связью 1H-13С и 13С-13С, имеется
2. Вычислительный процесс носит характер интерференции, так как
магнитное контактное взаимодействие, что позволяет построить
амплитуды базисных состояний являются комплексными числами.
двухкубитовые вентили.
Квантовый
компьютер
можно
рассматривать
как
сложное
Макроскопически большое число (~1020) молекул в пробирке
интерференционное устройство, в котором интерференция состояний
импульсного ЯМР спектрометра, запрограммированного на выполнение
создает вычислительную мощь компьютера.
квантового алгоритма на трехкубитовом компьютере /А, /B, /C представляет
С возникновения идеи создания квантовых компьютеров
собой ансамбль работающих параллельно квантовых компьютеров.
математики нашли новую важную задачу: разработать квантовые
"Ансамблевость" компьютера в данной ситуации позволяет решить
алгоритмы решения вычислительных задач математики и определить, где
трудные проблемы инициализации компьютера (т.е. приведения всех
есть ускорение и каково оно. В алгоритме Шора, по-видимому, впервые
кубитов в состояние (0) перед вычислением) и измерения состояния
обнаружен феномен, когда класс сложности задачи коренным образом
кубитов по завершении процесса вычислений. Состояния |0> и |1>
изменяется в зависимости от того, на каких физических принципах
некоторого кубита в конечном состоянии определяется путем наблюдения
строится вычислительный процесс.
знака (фазы) линии резонансного поглощения: в случае |0> наблюдается,
По-видимому, место квантовых компьютеров можно определить
например, линия поглощения, а при |1> - излучения.
следующим образом: они не вытесняют, а дополняют существующий
К настоящему времени на спиновых двух- и трехкубитовых
компьютерный мир. Их надо будет применять в тех случаях, когда они
квантовых компьютерах выполнен модельный квантовый алгоритм Дойча-
дают большое ускорение решения задачи.
Иозса по определению типа дискретной функции от дискретного
К настоящему времени предложены различные пути реализации
аргумента, алгоритма Гровера поиска в базе данных, алгоритм с квантовой
квантовых компьютеров. Наиболее впечатляющие результаты получены в
коррекцией ошибок.
экспериментах по квантовым вычислениям методом импульсного ядерного
Анализ показывает, что масштабирование квантового компьютера
магнитного резонанса в молекулярных жидкостях. Предлагается также
на спинах в молекулах на число кубитов порядка 103 вряд ли возможно:
использовать в качестве элементной базы квантовых компьютеров ионы в
трудно представить, что такое количество спинов ядер будут иметь
ловушках в вакууме, ядерные спины атомов 31Р в монокристаллическом
различимые частоты резонанса.
кремнии, спины одиночных электронов в квантовых точках в двумерном
Интересна идея создания квантового компьютера на ловушках в
газе в полупроводниковых гетероструктурах, атомы в резонаторах
вакууме. "Подвешенные" в вакууме ионы (атомы) напрямую осуществляют

идею максимально изолированных от окружающего мира квантовых
состоящего из большого числа (-109) вентилей.
частиц. Связь ионов с окружающим миром сохранена только для
Выход из этой, казавшейся тупиковой, ситуации был найден в
удержания ионов в ловушке (электроды с напряжениями) и управления
применении методов квантовой коррекции ошибок . Методы коррекции
квантовой эволюцией (сфокусированные лазерные пучки).
ошибок хорошо известны из теории обычных (классических) компьютеров.
Большой интерес вызывают предложения по созданию элементов
Смысл их в том, что логические |0> и |1> кодируются большим числом
квантовых компьютеров на твердом теле, так как в этом случае можно
битов; анализ кодовых комбинаций позволяет найти и удалить ошибку.
использовать накопленный опыт микроэлектронной технологии, а сами
Эти методы удалось разработать в квантовом варианте, где ошибки могут
квантовые компьютеры могли бы иметь сходство с "чипами" микросхем.
быть фазовыми и амплитудными. Выяснилось, что если вероятность
Предложено использовать в качестве кубитов спины / = 1/2 ядер атомов
ошибки при выполнении одной элементарной операции ниже некоторого
фосфора 31Р в монокристаллическом кремнии. Частотой магнитного
порогового уровня, вычислительный процесс можно длить сколь угодно
резонанса на ядрах 31Р в кремнии можно управлять, подавая на
долго. Это означает, что операции квантовой коррекции ошибок удаляют
наноэлектрод над атомом электрическое напряжение V: оно поляризует
из компьютера больше ошибок, чем вносят. Этот вывод очень важен: по
электронную оболочку атома и изменяет константу А так называемого
существу, он имеет силу теоремы существования полномасштабного
сверхтонкого взаимодействия электронного S и ядерного / спинов атома:
квантового компьютера.
Hi = A(V) · S. Таким образом достигается селективный доступ внешнего
Из обширной области разработки квантовых методов связи и
резонансного магнитного поля к спину ядра данного атома. Структура с
криптографии мы коснемся последствий создания квантовых компьютеров
единичным атомом, встроенным в заданную точку под электродом,
и систем связи для двух современных наиболее популярных криптосистем:
отдаленно напоминает структуру полевого транзистора. Затвор последнего
для системы с открытым ключом (RSA система, Rivest, Sharnir, Adieman,
управляет движением электронов проводимости от истока к стоку. В
1977) и системы с ключом одноразового пользования (Vernam, 1935).
случае кубита напряжения на затворе управляют движением электрона
Сразу отметим, что в основе системы RSA лежит предположение о
внутри атома, поляризуют атом и изменяют резонансную частоту кубита,
том, что решение математической задачи о разложении больших чисел на
связанного со спином его ядра.
простые множители на классических компьютерах невозможно; оно
Интересны предложения о создании элементов квантовых
требует экспоненциально большого числа операций и астрономического
компьютеров на- сверхпроводниках. Одним из достоинств этих
времени.
предложений
является
возможность
использования
структур
с
Квантовый алгоритм Шора дает возможность вычислить простые
наноразмерами (структуры с Джозефсоновскими контактами), технология
множители больших чисел за практически приемлемое время и взломать
которых в значительной мере разработана.
шифры RSA криптосистем. Таким образом, для RSA криптосистем
В самом начале развития идей о квантовом компьютере физики
квантовый компьютер - плохая новость.
обнаружили и грозного противника этой машины. Имя этого противника -
Для криптосистем с ключом одноразового пользования квантовые
декогерентизация.
методы связи оказываются хорошей новостью: они позволяют обнаружить
Кубиты компьютера нельзя полностью изолировать от внешнего
наличие подслушивания при передаче ключа. Эта возможность основана
мира: кубиты работают в условиях шумового воздействия внешней среды.
на квантовом принципе неопределенности Гейзенберга, который гласит,
Флуктуации напряжений на электродах, шумовые токи, неточности
что измерение изменяет состояние измеряемой квантовой системы. Пусть
выполнения самих импульсных воздействий на кубиты в ходе
ключ передается по световолокну с помощью фотонов, и информация
вычислительного процесса - все это вносит неконтролируемые ошибки в
закодирована в поляризации фотонов. Тогда подслушивание заключается в
фазы и амплитуды состояний кубитов в ходе вычислительного процесса.
перехвате и измерении поляризации пересылаемых фотонов; после
По истечении времени, равном времени декогерентизации квантовых
измерения они пересылаются адресату. При наличии подслушивания
состояний системы кубитов, контролируемый вычислительный процесс
адресат обнаружит, что 25% фотонов приходят к нему с "неправильной"
прекратится, эволюция квантового компьютера приобретет случайный
поляризацией. Если этих ошибок нет, то передача ключа не
(диффузионный) характер. Время декогерентизации, как правило, будет
подслушивается, и им можно пользоваться. Таким образом, квантовые
меньше времени, необходимого для выполнения сложного алгоритма,
методы обеспечивают гарантированную секретность ключа одноразового

пользования.
Квантовые каналы связи дают и другие возможности:
1. С помощью одного кубита можно передавать 2 бита информации
("плотное квантовое кодирование").
2. Возможна передача неизвестного квантового состояния
("квантовая телепортация") по классическому каналу, если абоненты связи
предварительно поделили коррелированную пару квантовых частиц.
Потенциальные возможности применения этих феноменов еще не
выяснены.
Квантовые компьютеры, если их удастся построить, будут техникой
XXI в. Для их изготовления потребуется развитие технологий на
нанометровом и атомном уровне размеров. Построение квантовых
компьютеров было бы еще одним подтверждением принципа
неисчерпаемости природы: природа имеет средства для осуществления
любой корректно сформулированной задачи.