Квантовые вычисления

Квантовые вычисления

2-е издание, исправленное

В. Биллиг Ю.
Биллиг В.А.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Квантовые вычисления/ Ю. В. Биллиг, В.А. Биллиг - М.: Национальный Открытый Университет
“ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2019-2016
(c) В. Биллиг Ю., Биллиг В.А., 2019-2016

3

Блеск и нищета квантовых компьютеров

Закон Мура, сформулированный одним из основателей фирмы Intel Гордоном Муром,
гласил, что число транзисторов интегральной схемы удваивается каждые два года. Это
возможно при условии уменьшения размеров транзисторов. В 2017 году этот размер
имел порядок 10 нанометров, что соответствует слою толщиной не более 50 атомов.
Уже при этих масштабах становятся существенными квантовые эффекты, такие как
квантовые туннельные эффекты, когда частица преодолевает барьер, который,
согласно законам классической механики, она преодолеть не может из-за нехватки
энергии.

Очевидно, что, следуя траектории закона Мура, принятая парадигма построения
архитектуры компьютера должна натолкнуться на непроходимую стену, поскольку
размер транзистора не может быть меньше межатомного расстояния в кристалле. Более
того при приближении к барьеру, квантовые эффекты становятся определяющими.

В нашей повседневной жизни мы имеем дело с объектами, состоящими из многих
атомов (число атомов в одной песчинке составляет примерно 
. В больших

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

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

Какие же возможности открываются при использования квантовых компьютеров? В
сравнении с обычными компьютерами мы получаем:

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

А что же мы теряем при этом?

1. Исчезает прямой доступ к памяти. Акт чтения из квантовой памяти дает результат

лишь с некоторой вероятностью, неизбежно разрушая при этом прочитанную
запись.

2. Квантовые процессоры должны быть полностью изолированы от окружающей

среды при условии сохранении контроля и управления вычислениями.

3. Отсутствует понимание и навыки создания эффективных квантовых алгоритмов,

использующих всю мощь квантовых компьютеров.

4

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

Необходим существенный прогресс и в разработке квантовых алгоритмов. К счастью,
для выполнения этой работы нет необходимости иметь настоящий работающий
квантовый компьютер. Здесь достаточно пера, бумаги и понимания теории квантовых
вычислений.

Давайте же попытаемся понять разницу между классическими и квантовыми
компьютерами. В классическом компьютере данные хранятся в памяти в виде
последовательности 0 и 1. Минимальной единицей памяти является бит, и он может
хранить либо ноль, либо единицу Для целей нашего обсуждения 0 и 1 следует
рассматривать как символы.

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

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

Тогда значение кубита может быть записано как:

Значение кубита в этом случае можно интерпретировать как суперпозицию с весами а
и b двух классических битов 0 и 1, где 
. Заметьте, что мы рассматриваем

здесь 
 не как вектор длины 0, а как вектор единичной длины, расположенный на

оси, помеченной символом “0”.

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

5

может служить в качестве единицы памяти классического компьютера. Заряженное
состояние конденсатора может рассматриваться как 1, а разряженное- 0.

Фотон может рассматриваться как физическая реализация кубита. Фотон - это квант
электромагнитной волны. Представьте фотон, летящий в трехмерном пространстве
вдоль оси Z. В процессе полета возникает колебание (осцилляция) электрического и
магнитного полей во взаимно перпендикулярных направлениях в плоскости ХУ

Специфический способ проявления осцилляции называется поляризацией фотона.
Существуют два возможных типа поляризация - круговая и линейная. При круговой
поляризации при перемещении фотона направление электрического поля вращается в
плоскости ХУ В этом курсе мы будем рассматривать только простейший случай
линейной поляризации, когда электрическое поле осциллирует в фиксированном
направлении перпендикулярно оси Z. Линейно поляризованные фотоны могут быть
получены пропусканием светового потока через поляризационный фильтр.

Поляризованный свет используется в кинотеатрах 3D. Для создания 3D эффекта
правый и левый глаз должны видеть слегка отличные картинки. Для этого фильм
проецируется двумя камерами, разнесенными на некоторое расстояние. Изображение
обеих камер одновременно проецируется на экран, но свет от двух проекторов
поляризован различными способами. Очки для просмотра фильма имеют
поляризационные фильтры, каждый из которых способен пропускать свет только от
одного проектора. В результате два глаза получают различающиеся изображения, что и
создает 3D эффект.

Вообразите, фотон с линейной поляризацией под углом а в плоскости ХУ Такой фотон
может быть использован в качестве физической реализации кубита со значением

Небольшое техническое замечание относительно положительного и отрицательного
состояний фотона 
 и - 
. Оба состояния соответствуют фотону с теми же осями

6

поляризации, однако осцилляция электрического поля для отрицательного состояния - 

 находится в противофазе относительно состояния 
. Для одного фотона

невозможно различить, в каком состоянии он находится, но для пары фотонов можно
обнаружить разницу в фазах и рассматривать их состояния как два различных значений
кубита.

Давайте перейдем теперь к рассмотрению множества кубитов - мультикубитам. 2-
кубит - это вектор с четырьмя компонентами в форме:

где 
. Базисные вектора в пространстве 2-кубитов: 

, называемые также чистыми состояниями, соответствуют 4-м возможным состояниям
пары классических битов. В общем случае значение 2-кубита представляет
комбинацию значений 4-х классических битов. У каждого бита в этой комбинации есть
свой весовой коэффициент. Эту комбинацию принято называть суперпозицией.

Например, 2-кубит 
 представляет суперпозицию 4-х

классических значений, но 2-бит значение “10” в этой комбинации наиболее весомо.

Как вы уже могли догадаться, 3-кубит - это вектор с 8-мю компонентами:

Обратите внимание на соответствие в нашей нотация между индексом коэффициента а
и меткой, которой мы помечаем базисные вектора. Возьмем, например, терм
(слагаемое) 
 . Значение 110 в этом терме совпадает с двоичной записью

значения индекса 
.

Нетрудно также заметить, что число термов удваивается при увеличении на единицу
числа кубитов. Для 1-кубита термов - 2, для 2-кубита - 4, для 3-кубита- 8. В общем
случае для N кубитов термов 2^N. Для 8-кубита тeрмов будет 256:

В качестве упражнения давайте определим индекс коэффициента “а” для терма с
меткой 
. Каждая цифра в позиционной системе счисления является

коэффициентом основания системы счисления в степени k,

где k - определяется позицией цифры. Для двоичной системы счисления основание

7

равно 2, так что цифры 0 и 1- это коэффициенты при соответствующих степенях
основания 2. Для 8-битного выражения самая левая цифра соответствует степени 
,

самая правая - 
. Бинарное выражение “11010011” следует рассматривать как:

Аналогично, десятичный индекс 117 в двоичном 8-битном представлении имеет вид:

Для более компактной закиси мы иногда будем записывать 8-кубит в десятичной
форме:

При этом мы понимаем, что все десятичные целые, появляющиеся в записи базисных
векторов необходимо перевести в 8-битную двоичную форму записи.

При увеличении числа битов такие выражения становятся чрезмерно длинными.
Эффективный математический способ записи таких сумм использует 
 нотацию. При

использовании этой нотации 8-кубит компактно записывается в виде:

Здесь k - индекс суммирования пробегает все значения от 0 до 255, так что сумма
включает все 255 термов. При k=0 в сумму включается терм 
 при 
 в сумму

включается терм 
 и так далее. Для каждого базисного вектора 
 целое 

следует переводить в двоичную форму записи.

Как мы увидим в следующей главе, состояние объединенной поляризации n
взаимодействующих кубитов описывается как n-кубит. Объем памяти требуемой для
записи такого состояния в классическом компьютере растет экспоненциально в
зависимости от n. Если отводить 1 байт для записи значения каждого а-коэффициента,
то нам потребуется 2 байта для хранения 1-кубита, один килобайт для хранения 10-
кубит, один мегабайт для 20-кубитов, один гигабайт для 30-кубит, один терабайт для
40-кубит, один петабайт для 50-кубит. Даже если нам удастся использовать всю
материю нашей вселенной для построения гигантского чипа памяти, основываясь на
современных способах построения компьютерной памяти, то нам не удастся построить
память для хранения 100-кубит. В то же время совокупность из 100
взаимодействующих фотонов - это то, что нас повсеместно окружает. Осознание того,
что природа широко использует квантовые принципы работы, стало отправной точкой
возникновения самой идеи квантовых вычислений.

Идея использования квантовых систем в вычислительных устройствах была
независимо высказана в 1980 году Юрием Маниным и Паулем Бениофом (Yuri Manin,
Раи1 Вепго). Эта идея также рассматривалась Рихардом Фейнманом (Richard
Feynmann) в 1982 году Основания этой теории систематически разрабатывались

8

Дэвидом Дейтчем (David Deutsch), но настоящий взрывной интерес к этой области
появился с открытием алгоритма Шора в 1994 году Квантовый алгоритм, который
разработал Питер Шор (Реег Shor), может взломать широко используемый в
криптографии алгоритм шифрования с открытым ключом. Такой алгоритм сегодня
повсеместно используется при передаче секретных данных в интернете. Конечно, для
реализации алгоритма требуется построить достаточно большой квантовый компьютер,
что пока технологически недостижимо.

Цель этого курса объяснить алгоритм Шора и все детали, требуемые для его
понимания.

9

Квантовая механика, частично лишенная мифического ореола

В этой лекции мы обсудим аксиоматику квантовой механики. Со времен Ньютона
понятие физического объекта описывалось с помощью числовых характеристик, таких
как позиция объекта, его скорость и ускорение. Физические теории давали точное
предсказание будущей траектории движения объекта, если известны начальные
условия и все силы, действующие на объект. Квантовая механика утверждает, что
будущее не является полностью определенным. Она постулирует, что мы можем
предсказать будущие события лишь с некоторой вероятностью, и что
неопределенность следует из законов природы.

Состояние квантовой системы - это вектор длины 1 в пространстве состояний. Для
наших целей квантовых вычислений мы будем рассматривать это пространство как 
-

мерное пространство n-кубита для некоторого значения n. Пространство n-кубита
является 
-мерным пространством, поскольку каждый n-кубит имеет 
 компонент,

также как в 3-х мерном пространстве каждый вектор имеет 3 компоненты. В общем
случае, в квантовой механике пространство может иметь любую размерность и быть
даже бесконечномерным пространством. Более того, в общепринятой формализации
квантовой механики компоненты векторов являются комплексными числами, но мы
для простоты рассмотрения ограничиваемся ситуацией, когда компоненты
представлены вещественными числами.

В классической механике траектория движения объекта описывается вторым законом
Ньютона, математически представленным в виде дифференциального уравнения.
Второй закон Ньютона гласит, что произведение массы на ускорение равно силе,
действующей на объект, а ускорение является второй производной от позиции объекта.
Таким образом мы получаем уравнение для второй производной, представляющее
дифференциальное уравнение.

В квантовой механике эволюция квантовой системы также описывается некоторым
дифференциальным уравнением, называемым уравнением Шредингера. Уравнение
Шредингера само по себе для нашего изложения не так важно, поэтому мы не будем
выписывать его непосредственно. Для нас более важен тот факт, что эволюция
замкнутой квантовой системы задается ортогональными линейными трансформациями.
В следующей лекции мы детально объясним, что представляют собой эти
трансформации.

Вероятностная природа квантовой механики проявляется в процессе измерений.
Измерение является единственным способом извлечения данных, определяющих
квантовое состояние.

Рассмотрим n-кубит

с нормализацией (длина вектора равна 1)

10