Введение в квантовые вычисления. Квантовые алгоритмы

Учебное пособие

С. С. Сысоев

ВВЕДЕНИЕ  
В КВАНТОВЫЕ ВЫЧИСЛЕНИЯ.  
КВАНТОВЫЕ АЛГОРИТМЫ

ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

УДК 519.684:004.4
ББК 22.18+32.973.2
С95

Р е ц е н з е н т ы: д-р физ.-мат. наук, проф. О. Н. Граничин (С.-Петерб. гос.
ун-т), канд. физ.-мат. наук А. В. Рыбин (С.-Петерб. нац.
исслед. ун-т информ. технологий, механики и оптики)

Рекомендовано к публикации
учебно-методической комиссией
математико-механического факультета
Санкт-Петербургского государственного университета

С95
Сысоев С. С.
Введение в квантовые вычисления. Квантовые алгоритмы: учеб. пособие. — СПб.: Изд-во С.-Петерб. ун-та,
2019. — 144 с.
ISBN 978-5-288-05933-9

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

УДК 519.684:004.4
ББК 22.18+32.973.2

ISBN 978-5-288-05933-9

c⃝
Санкт-Петербургский
государственный
университет, 2019

c⃝
С. С. Сысоев, 2019

ОГЛАВЛЕНИЕ

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5

Глава 1. Вычисления. От классических к квантовым . .
7

1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.2. Информация и вычисления. . . . . . . . . . . . . . . . . . . . .
9
1.3. Характеристики вычислительной системы . . . . .
15
1.4. Вычислимость и алгоритм. . . . . . . . . . . . . . . . . . . . . .
17
1.5. Сложность вычислений. . . . . . . . . . . . . . . . . . . . . . . . .
21
1.6. Квантовые вычисления . . . . . . . . . . . . . . . . . . . . . . . . .
25
1.7. Многомировая интерпретация
квантовой механики . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
1.8. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34

Глава 2. Математическая модель
квантовых вычислений. . . . . . . . . . . . . . . . . . . . . . .
35

2.1. Кубит .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
—
2.2. Измерение кубита.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
2.3. Система кубитов.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
2.4. Измерение системы кубитов .. . . . . . . . . . . . . . . . . . .
48
2.5. Эволюция квантовой системы . . . . . . . . . . . . . . . . . .
50
2.6. Оператор Адамара.. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
2.7. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59

Глава 3. Квантовый компьютер
и квантовые алгоритмы . . . . . . . . . . . . . . . . . . . . . .
64

3.1. Задача Дойча .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
—
3.2. Квантовый компьютер на фотонах .. . . . . . . . . . . .
70
3.3. Задача Дойча—Джозы.. . . . . . . . . . . . . . . . . . . . . . . . .
80
3.4. Задача Бернштейна—Вазирани .. . . . . . . . . . . . . . . .
83
3.5. Задача Саймона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
3.6. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86

Оглавление

Глава 4. Алгоритм Шора. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89

4.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
—
4.2. Факторизация и RSA . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
4.3. Поиск периода и факторизация . . . . . . . . . . . . . . . .
93
4.4. Квантовое преобразование Фурье . . . . . . . . . . . . . .
97
4.5. Алгоритм Шора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
101
4.6. Пример реализации. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
107
4.7. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
109

Глава 5. Алгоритм Гровера
и границы квантовых вычислений . . . . . . . . . . .
114

5.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
—
5.2. Алгоритм Гровера .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
116
5.3. Оптимальность алгоритма Гровера. . . . . . . . . . . . .
126
5.4. Всегда ли квантовый компьютер
имеет преимущество перед классическим? . . . . .
131
5.5. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
133

Использованная литература. . . . . . . . . . . . . . . . . . . . . . . . . . .
136

Рекомендованная литература . . . . . . . . . . . . . . . . . . . . . . . . .
137

Ответы к упражнениям . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
139

ПРЕДИСЛОВИЕ

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

Предисловие

ление» в отношении к реализующему его физическому процессу. Выделяются некоторые важные характиристики физических процессов и их эволюция, известная как смена поколений ЭВМ. Обосновывается прогноз перехода к пятому поколению вычислительных машин, которое будет работать на основе
квантовых систем. Далее, в главе 2, рассматривается математическая модель квантовых вычислений — квантовые данные и
квантовые операции (гейты). Глава 3 посвящена разбору простейших примеров квантовых алгоритмов в хронологическом
порядке их публикаций в работах Дойча и Джозы, Бернштейна
и Вазирани, Саймона. Этот материал готовит читателя к материалу глав 4 и 5, в которых описаны алгоритм факторизации
составных чисел Питера Шора и обобщенный алгоритм решения задач из класса NP Лова Гровера. Кроме того, в главе 5
обсуждаются границы применимости квантовых алгоритмов и
разбирается задача, для решения которой квантовые компьютеры не дают существенного ускорения.
Все квантовые алгоритмы иллюстрируются примерами их
реализации на симуляторе квантового компьютера, а для задачи Дойча приводится реальный прототип квантового компьютера на фотонах, который любознательные читатели могут
собрать самостоятельно.

Глава 1

Вычисления.
От классических
к квантовым

1.1.
Введение

Математики и программисты привыкли воспринимать вычисления как абстрактный процесс, не имеющий физической основы. Тем не менее любое устройство, выполняющее вычисления, основано на каком-либо физическом процессе. Принятие данного факта приводит к отказу от платоновского мира
идей, зато при этом открываются великолепные перспективы
для экспериментов с различными физическими системами.
Поколения ЭВМ являются наглядной иллюстрацией истории таких экспериментов. До ЭВМ вычисления выполнялись
механическими системами. Потом появились устройства, основанные на электромагнитных реле, радиолампах, транзисторах. . . Каждый последующий тип устройства был эффективнее предыдущего, поэтому естественно было бы ожидать появления новых, еще более эффективных ЭВМ.
Вместе с устройствами эволюционировали и алгоритмы. В
1936 году Алан Тьюринг предложил математическую модель вычислений, названную впоследствии машиной Тьюринга. Модель
Тьюринга [Turing, 1938] формализовала понятие алгоритма (способа

7

Глава 1. Вычисления. От классических к квантовым

вычисления некоторой функции на физическом устройстве), что позволило ввести понятие вычислимости и в дальнейшем — понятие сложности вычислений. Тогда же, в 1936 году, Тьюринг показал, что существуют невычислимые (undecidable) функции —
такие функции, которые можно формально определить, но для
вычисления которых невозможно предложить алгоритм.
Понятие сложности вычислений (количества ресурсов, необходимых для выполнения алгоритма) позволило выделить классы задач, названных неразрешимыми (intractable). В отличие от невычислимых функций, для них существуют алгоритмы, работающие за конечное время. Однако ресурсы, необходимые для выполнения этих алгоритмов, растут слишком быстро (например,
экспоненциально) с увеличением размера входных данных.
С появлением неразрешимых задач возникла потребность
в физических устройствах, вычислительные возможности которых
зависели бы экспоненциально от размеров (ресурсов) устройства.
В 1981 году нобелевский лауреат по физике Ричард Фейнман предложил построить вычислительное устройство на основе квантовой
системы. Оптимизм Фейнмана [Feynman, 1982] был основан на
том, что простейшая квантовая система намного сложнее простейшей классической системы. Кроме того, линейным ростом
квантовой системы вызывается экспоненциальный рост сложности ее описания. Например, для классического описания состояния 10-кубитной системы потребуется 1024 комплексных
числа, а для 30 кубит — более миллиарда комплексных чисел.
Уже в 1985 году Дэвид Дойч [Deutsch, 1985] разработал
математическую модель универсального квантового компьютера и показал некоторые ее преимущества перед классической моделью. А в 1994-м Питер Шор взорвал научную общественность, опубликовав полиномиальный квантовый алгоритм разложения составного числа на множители. Результат
Шора [Shor, 1994] поставил под угрозу широко используемый
алгоритм ассиметричного шифрования RSA1.

1 RSA — ассиметричный алгоритм шифрования, названный по первым
буквам фамилий его авторов — Rivest, Shamir, Adleman.

1.2. Информация и вычисления
9

Таким образом, квантовые вычисления имеют все шансы превзойти современные классические компьютеры сразу по
двум напрявлениям: 1) как более совершенный, быстрый и информационно емкий физический процесс, 2) как более перспективная в теоретическом смысле модель. Репертуар квантового
компьютера шире, чем у классической машины Тьюринга (которая не может, например, генерировать случайные числа), а
для многих сложных для классических вычислений задач уже
существуют эффективные квантовые алгоритмы.
Цель этого курса — познакомить читателя с моделью квантовых вычислений, структурой и примерами квантовых алгоритмов. Квантовые вычисления — сравнительно новая область
науки, и поэтому она может быть интересной для молодых исследователей, желающих работать на самом острие современной научной мысли.
Развитие аппаратной базы квантового компьютера в скором времени может породить спрос на алгоритмистов, способных понимать существующие квантовые алгоритмы и разрабатывать новые. Создание фундамента подобных знаний у читателей является главной задачей этого учебного пособия.

1.2.
Информация и вычисления

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

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

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

Глава 1. Вычисления. От классических к квантовым

по-разному. Рассмотрим в качестве примера действия пастуха,
не умеющего считать, описанные в популярной книге Дэвида
Дойча «Начало бесконечности».
Каждое утро пастух выпускает своих овец из хлева на выпас, а по вечерам загоняет их обратно в хлев. В силу непреодолимых обстоятельств, не являющихся важными для читателя,
пастух не умеет считать. Он не знает, сколько у него овец, и,
по всей видимости, не считает эту информацию важной. Важно
для него только то, чтобы число овец в стаде оставалось неизменным в течение дня. Недостаток овец вечером необходимо
отслеживать, и если не все они вернутся, то пастух должен отправляться на поиски заблудившихся животных. Для решения
этой задачи он использует вычислительное устройство — веревку, помогающую ему отслеживать неизменность числа овец
утром и вечером. Утром при выходе каждой овцы из хлева
пастух наматывает один виток веревки на столб, стоящий неподалеку. Вечером, загоняя овцу обратно, он разматывает один
виток со столба. Если все витки к концу процесса размотаны,
то пастух вправе полагать, что все овцы на месте.
Подобный вычислительный процесс, включающий в себя
веревку, столб и пастуха, хорошо демонстрирует данное выше
определение.
Во-первых, процесс, безусловно, основан на физических системах. Все его составляющие присутствуют в наблюдаемой
вселенной, а одна из них — пастух — даже преобразовывает в ходе вычислений энергию. Пастух, являясь одновременно
частью вычислителя и его пользователем, различает только
шесть состояний процесса:
1) утро, веревка полностью размотана (начальное состояние);
2) утро, веревка наматывается на столб (сохранение числа
овец);
3) вечер, веревка разматывается со столба (считывание
числа овец);
4) вечер, все овцы зашли, веревка размотана неполностью
(конечное состояние: недостаток овец);

1.2. Информация и вычисления
11

5) вечер, веревка полностью размотана, но овцы зашли не
все (конечное состояние: избыток овец);
6) вечер, все овцы зашли, веревка размотана полностью
(конечное состояние: все овцы на месте).

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

Информация — это описание в некоторой кодировке состояния физической системы (не обязательно выполняющей вычисления).

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

Количество вычислений — это число смен состояний вычислительного процесса.

Для определения количества информации воспользуемся
формулой Шеннона, предложенной американским криптоаналитиком Клодом Шенноном в 1948 году. Она определяет информационную емкость системы, имеющей n состояний, для
каждого из которых определена его вероятность Pi:

I = −

n
i=1
Pi logb(Pi).

Глава 1. Вычисления. От классических к квантовым

Те, кто помнит школьную физику, заметят несомненное
сходство информации в этой формуле с энтропией системы.
Если мы возьмем логарифм по основанию 2 (b = 2), то
информационная емкость по формуле будет рассчитываться в
битах. Бит — минимальная частичка информации, еще одно
понятие, подаренное миру Клодом Шенноном.
Для системы, имеющей n равновероятных состояний, количество информации в битах по формуле Шеннона выглядит
проще:

I = −

n
i=1

1
n log2
1
n = log2 n.

Например, для простейшего тумблера (рис. 1.1), имеющего два равновероятных состояния, мы получаем по формуле
(I = log2 = 1) информационную емкость 1 бит. Получается,
что такой тумблер может хранить (содержать) 1 бит информации.

Рис. 1.1. Переключатель
с двумя состояниями

Если мы добавим тумблеру третье состояние, то его информационная емкость увеличится и станет равной log3 ≈ 1,6 бит.
Оказывается, информация не только материальна, она еще
и в некотором смысле эквивалентна энергии! Рассмотрим мысленный эксперимент, предложенный венгерским физиком Лео
Сцилардом в 1929 году.
В этом эксперименте рассматривается камера, ограниченная с двух сторон подвижными невесомыми поршнями и разделенная перегородкой. Перегородку можно убирать (рис. 1.2).