Элементарное введение в квантовые вычисления

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

Р. ПЕРРИ

Второе издание

Перевод с английского
А. Д. Калашникова

Ð. Ïåððè
Ýëåìåíòàðíîå ââåäåíèå â êâàíòîâûå âû÷èñëåíèÿ. Ïåð. ñ
àíãë.: Ó÷åáíîå ïîñîáèå / Ð. Ïåððè – 2-å èçä. – Äîëãîïðóäíûé: Èçäàòåëüñêèé Äîì «Èíòåëëåêò», 2018. – 208 ñ.
ISBN 978-5-91559-249-9

Êíèãà ïðåäñòàâëÿåò ñîáîé ââîäíûé ó÷åáíèê ïî êâàíòîâûì âû÷èñëåíèÿì. Àâòîð ñîáðàë çäåñü ìèíèìàëüíî íåîáõîäèìûé äëÿ
ïîíèìàíèÿ êâàíòîâûõ âû÷èñëåíèé è çàíÿòèé èìè íàáîð ñâåäåíèé èç ëèíåéíîé àëãåáðû, êâàíòîâîé ìåõàíèêè, èíôîðìàòèêè è
òåîðèè èíôîðìàöèè.
Ó÷åáíîå ïîñîáèå áóäåò ïîëåçíî ñòóäåíòàì è ïðåïîäàâàòåëÿì,
ñïåöèàëèçèðóþùèìñÿ â ïðèêëàäíîé ìàòåìàòèêå, òåîðåòè÷åñêîé
ôèçèêå è êðèïòîãðàôèè, êîòîðûì èíòåðåñíû êâàíòîâûå âû÷èñëåíèÿ.
Ïåðâîå èçäàíèå êíèãè íà ðóññêîì ÿçûêå øèðîêî èñïîëüçóåòñÿ
â ðîññèéñêèõ óíèâåðñèòåòàõ.

© 2012 by World Scientific Publishing
Co. Pte. Ltd.
© 2015, ÎÎÎ Èçäàòåëüñêèé Äîì
«Èíòåëëåêò», ïåðåâîä íà ðóññêèé
ÿçûê, îðèãèíàë-ìàêåò, îôîðìëåíèå

NEW JERSEY  LONDON  SINGAPORE  BEIJING  SHANGHAI  HONG KONG  TAIPEI  CHENNAI  
Riley Tipton Perry

University of New South Wales, Australia

Quantum Computing
from the Ground Up

QUANTUM COMPUTING FROM THE GROUND UP
8515ISBN 978-5-91559-249-9
ISBN 978-981-4412-11-7 (àíãë.)

ОГЛАВЛЕНИЕ

Предисловие к изданию на русском языке . . . . . . . . . . . . . . . . . . . .
9

Благодарности. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10

Глава 1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.1. Почему квантовые вычисления? . . . . . . . . . . . . . . . . . . . . . . .
11
1.2. Зачем нужен еще один учебник по квантовым вычислениям? . . .
12
1.2.1. Квантовые вычисления и квантовая информация . . . . . . . .
12

Глава 2. Информатика . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13

2.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.2. История . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.3. Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.3.1. Двоичные числа и формальные языки . . . . . . . . . . . . . . .
17
2.3.1.1. Двоичное представление . . . . . . . . . . . . . . . . . . .
18
2.3.1.2. Формальные языки . . . . . . . . . . . . . . . . . . . . . .
19
2.3.2. Машины Тьюринга в действии . . . . . . . . . . . . . . . . . . . .
19
2.3.3. Универсальная машина Тьюринга . . . . . . . . . . . . . . . . . .
20
2.3.4. Проблема останова . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.3.4.1. Проблема останова — доказательство от противного
21
2.4. Цепи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.4.1. Наиболее распространенные логические элементы . . . . . . .
23
2.4.2. Сочетание логических элементов . . . . . . . . . . . . . . . . . .
25
2.4.3. Существенные свойства. . . . . . . . . . . . . . . . . . . . . . . . .
26
2.4.4. Универсальность . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
2.5. Вычислительные ресурсы и эффективность их использования . . .
27
2.5.1. Количественная мера вычислительных затрат . . . . . . . . . .
28
2.5.2. Стандартные классы сложности . . . . . . . . . . . . . . . . . . .
30
2.5.3. Физический тезис Черча–Тьюринга . . . . . . . . . . . . . . . . .
31
2.5.4. Квантовые машины Тьюринга . . . . . . . . . . . . . . . . . . . .
33
2.6. Энергия и вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
2.6.1. Обратимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
2.6.2. Необратимость. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34

Оглавление

2.6.3. Принцип Ландауэра . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.6.4. Демон Максвелла . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.6.5. Обратимые вычисления . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.6.6. Обратимые логические элементы . . . . . . . . . . . . . . . . . .
36
2.6.6.1. Управляемый NOT . . . . . . . . . . . . . . . . . . . . . . .
36
2.6.6.2. Логический элемент Тоффоли . . . . . . . . . . . . . . .
36
2.6.6.3. Логический элемент Фредкина . . . . . . . . . . . . . .
37
2.6.7. Обратимые цепи . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38

Глава 3. Математика квантовых вычислений . . . . . . . . . . .
39

3.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
3.2. Полиномы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.3. Логическая символика . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.4. Краткие сведения из тригонометрии . . . . . . . . . . . . . . . . . . . .
41
3.4.1. Прямоугольные треугольники . . . . . . . . . . . . . . . . . . . . .
41
3.4.2. Перевод из градусов в радианы и обратно . . . . . . . . . . . .
42
3.4.3. Обратные тригонометрические функции . . . . . . . . . . . . . .
42
3.4.4. Углы в других квадрантах . . . . . . . . . . . . . . . . . . . . . . .
42
3.4.5. Наглядные представления и тождества . . . . . . . . . . . . . .
43
3.5. Краткие сведения о логарифмах . . . . . . . . . . . . . . . . . . . . . . .
44
3.6. Комплексные числа. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
3.6.1. Полярные координаты и комплексное сопряжение . . . . . . .
46
3.6.1.1. Полярные координаты. . . . . . . . . . . . . . . . . . . . .
47
3.6.2. Домножение на сопряженное и деление . . . . . . . . . . . . . .
48
3.6.3. Экспоненциальная форма. . . . . . . . . . . . . . . . . . . . . . . .
49
3.7. Матрицы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
3.7.1. Операции над матрицами . . . . . . . . . . . . . . . . . . . . . . .
50
3.7.1.1. Сложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
3.7.1.2. Умножение на скаляр . . . . . . . . . . . . . . . . . . . . .
51
3.7.1.3. Произведение матриц . . . . . . . . . . . . . . . . . . . . .
51
3.7.1.4. Свойства операций над матрицами . . . . . . . . . . . .
51
3.7.1.5. Нулевая матрица . . . . . . . . . . . . . . . . . . . . . . . .
52
3.7.1.6. Единичная матрица . . . . . . . . . . . . . . . . . . . . . .
52
3.7.1.7. Обратная матрица . . . . . . . . . . . . . . . . . . . . . . .
53
3.7.1.8. Транспонирование матриц . . . . . . . . . . . . . . . . . .
53
3.7.1.9. Детерминанты и ранги . . . . . . . . . . . . . . . . . . . .
53
3.8. Векторы и векторные пространства . . . . . . . . . . . . . . . . . . . . .
54
3.8.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
3.8.1.1. Векторы в R × R . . . . . . . . . . . . . . . . . . . . . . . .
55
3.8.1.2. Интересные свойства векторов в R3 . . . . . . . . . . .
56
3.8.1.3. Кое-что о векторах в C. . . . . . . . . . . . . . . . . . . .
57
3.8.2. Столбцы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
3.8.3. Нуль-вектор . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
3.8.4. Свойства векторов в Cn
. . . . . . . . . . . . . . . . . . . . . . . .
58
3.8.4.1. Умножение на скаляр и сложение . . . . . . . . . . . .
58
3.8.4.2. Сложение векторов . . . . . . . . . . . . . . . . . . . . . .
58

Оглавление
5

3.8.5.
Дуальный вектор . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
3.8.6.
Линейная комбинация векторов . . . . . . . . . . . . . . . . . .
59
3.8.7.
Линейная независимость векторов. . . . . . . . . . . . . . . . .
59
3.8.8.
Линейная оболочка . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
3.8.9.
Базис . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
3.8.10. Теория вероятностей . . . . . . . . . . . . . . . . . . . . . . . . . .
60
3.8.11. Амплитуды вероятности . . . . . . . . . . . . . . . . . . . . . . .
61
3.8.12. Скалярное произведение . . . . . . . . . . . . . . . . . . . . . . .
62
3.8.13. Ортогональность . . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
3.8.14. Единичный вектор . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
3.8.15. Базисы в Cn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
3.8.16. Метод Грама–Шмидта . . . . . . . . . . . . . . . . . . . . . . . . .
66
3.8.17. Линейные операторы . . . . . . . . . . . . . . . . . . . . . . . . . .
67
3.8.18. Векторное произведение и проекторы. . . . . . . . . . . . . . .
68
3.8.19. Эрмитово сопряжение . . . . . . . . . . . . . . . . . . . . . . . . .
70
3.8.20. Собственные значения и векторы . . . . . . . . . . . . . . . . .
71
3.8.21. След. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
3.8.22. Нормальные операторы . . . . . . . . . . . . . . . . . . . . . . . .
73
3.8.23. Унитарные операторы . . . . . . . . . . . . . . . . . . . . . . . . .
74
3.8.24. Эрмитовы и положительные операторы . . . . . . . . . . . . .
76
3.8.25. Диагонализируемая матрица. . . . . . . . . . . . . . . . . . . . .
76
3.8.26. Коммутатор и антикоммутатор . . . . . . . . . . . . . . . . . . .
77
3.8.27. Полярное разложение . . . . . . . . . . . . . . . . . . . . . . . . .
78
3.8.28. Спектральное разложение . . . . . . . . . . . . . . . . . . . . . .
78
3.8.29. Тензорные произведения . . . . . . . . . . . . . . . . . . . . . . .
79
3.9. Фурье-преобразования. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
3.9.1. Ряды Фурье . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
3.9.2. Дискретное фурье-преобразование . . . . . . . . . . . . . . . . .
84

Глава 4. Квантовая механика . . . . . . . . . . . . . . . . . . . . . . .
87
4.1. История . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
4.1.1. Классическая физика . . . . . . . . . . . . . . . . . . . . . . . . . .
87
4.1.2. Важные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
4.1.2.1. Атомы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
4.1.2.2. Термодинамика . . . . . . . . . . . . . . . . . . . . . . . . .
90
4.1.3. Статистическая механика . . . . . . . . . . . . . . . . . . . . . . .
91
4.1.4. Великие эксперименты . . . . . . . . . . . . . . . . . . . . . . . . .
92
4.1.5. Фотоэлектрический эффект . . . . . . . . . . . . . . . . . . . . . .
93
4.1.6. Спектры испускания и поглощения . . . . . . . . . . . . . . . . .
94
4.1.7. Прото-квантовая механика . . . . . . . . . . . . . . . . . . . . . .
95
4.1.8. Новая теория квантовой механики . . . . . . . . . . . . . . . . .
99
4.2. Понятия, которые существенны для квантовых вычислений . . . .
102
4.2.1. Линейная алгебра . . . . . . . . . . . . . . . . . . . . . . . . . . . .
102
4.2.2. Суперпозиция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
103
4.2.3. Обозначения Дирака. . . . . . . . . . . . . . . . . . . . . . . . . . .
105
4.2.4. Представление информации . . . . . . . . . . . . . . . . . . . . . .
105
4.2.5. Неопределенность . . . . . . . . . . . . . . . . . . . . . . . . . . . .
106
4.2.6. Перепутывание . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
106

Оглавление

Глава 5. Квантовые вычисления . . . . . . . . . . . . . . . . . . . . .
108

5.1. Элементы квантовых вычислений . . . . . . . . . . . . . . . . . . . . . .
108
5.1.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
108
5.1.2. История . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
108
5.1.3. Биты и кубиты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
109
5.1.3.1. Одиночные кубиты . . . . . . . . . . . . . . . . . . . . . . .
109
5.1.3.2. Кет-векторы |⟩ . . . . . . . . . . . . . . . . . . . . . . . . . .
112
5.1.3.3. Двумерная визуализация кубитов . . . . . . . . . . . . .
113
5.1.3.4. Трехмерная визуализация кубита — сферы Блоха . .
113
5.1.3.5. Наборы кубитов . . . . . . . . . . . . . . . . . . . . . . . .
114
5.1.3.6. Тензорные произведения . . . . . . . . . . . . . . . . . . .
116
5.1.3.7. Частичное измерение . . . . . . . . . . . . . . . . . . . . .
116
5.1.3.8. Проективные измерения . . . . . . . . . . . . . . . . . . .
118
5.1.4. Перепутанные состояния . . . . . . . . . . . . . . . . . . . . . . . .
119
5.1.5. Квантовые цепи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
120
5.1.5.1.
Логические элементы, действующие на один кубит
120
5.1.5.2. Вентиль Паули I . . . . . . . . . . . . . . . . . . . . . . .
121
5.1.5.3. Вентиль Паули X . . . . . . . . . . . . . . . . . . . . . . .
121
5.1.5.4. Вентиль Паули Y . . . . . . . . . . . . . . . . . . . . . . .
122
5.1.5.5. Вентиль Паули Z . . . . . . . . . . . . . . . . . . . . . . .
122
5.1.5.6. Фазовый вентиль . . . . . . . . . . . . . . . . . . . . . . .
123
5.1.5.7.
π
8 -вентиль (T-вентиль) . . . . . . . . . . . . . . . . . . .
123
5.1.5.8. Вентиль Адамара . . . . . . . . . . . . . . . . . . . . . . .
123
5.1.5.9. Логический элемент как векторное произведение .
125
5.1.5.10. Некоторые свойства вентилей Паули . . . . . . . . . .
126
5.1.5.11. Операторы вращения . . . . . . . . . . . . . . . . . . . .
126
5.1.5.12. Логические элементы, действующие на несколько
кубитов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
127
5.1.5.13. Двухкубитный вентиль NOT . . . . . . . . . . . . . . .
129
5.1.5.14. Вентиль Тоффоли . . . . . . . . . . . . . . . . . . . . . . .
130
5.1.5.15. Вентиль Фредкина . . . . . . . . . . . . . . . . . . . . . .
130
5.2. Важные свойства квантовых цепей . . . . . . . . . . . . . . . . . . . . .
130
5.2.1. Распространенные цепи . . . . . . . . . . . . . . . . . . . . . . . . .
131
5.2.1.1. Управляемый U-вентиль . . . . . . . . . . . . . . . . . . .
131
5.2.1.2. Цепь обмена битов. . . . . . . . . . . . . . . . . . . . . . .
131
5.2.1.3. Цепь копирования . . . . . . . . . . . . . . . . . . . . . . .
132
5.2.1.4. Логический элемент Белла . . . . . . . . . . . . . . . . .
133
5.2.1.5. Сверхплотное кодирование . . . . . . . . . . . . . . . . .
133
5.2.1.6. Телепортация кубита . . . . . . . . . . . . . . . . . . . . .
135
5.3. Особенности построения цепей . . . . . . . . . . . . . . . . . . . . . . . .
136
5.3.1. Построение программируемого квантового компьютера. . . .
137
5.4. Постулаты квантовой механики . . . . . . . . . . . . . . . . . . . . . . .
137
5.4.1. Постулат состояния . . . . . . . . . . . . . . . . . . . . . . . . . . .
138
5.4.2. Постулат унитарности . . . . . . . . . . . . . . . . . . . . . . . . . .
138
5.4.2.1. Простая форма записи . . . . . . . . . . . . . . . . . . . .
138
5.4.2.2. Форма записи, учитывающая время . . . . . . . . . . .
138

Оглавление
7

5.4.3. Постулат измерений . . . . . . . . . . . . . . . . . . . . . . . . . . .
139
5.4.3.1. Простая форма записи . . . . . . . . . . . . . . . . . . . .
139
5.4.3.2. Проекторы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
139
5.4.4. Постулат тензорного произведения . . . . . . . . . . . . . . . . .
141

Глава 6. Теория информации. . . . . . . . . . . . . . . . . . . . . . . .
143

6.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
143
6.2. История . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
144
6.3. Коммуникационная модель Шеннона . . . . . . . . . . . . . . . . . . . .
144
6.3.1. Пропускная способность канала связи . . . . . . . . . . . . . . .
145
6.4. Классические источники информации . . . . . . . . . . . . . . . . . . .
145
6.4.1. Независимые источники информации . . . . . . . . . . . . . . .
146
6.5. Классические избыточность и сжатие . . . . . . . . . . . . . . . . . . .
147
6.5.1. Теорема Шеннона об источнике шифрования . . . . . . . . . .
148
6.5.2. Квантовые источники информации . . . . . . . . . . . . . . . . .
149
6.5.3. Чистые и смешанные состояния . . . . . . . . . . . . . . . . . . .
149
6.5.4. Теорема Шумахера о квантовом источнике шифрования . . .
150
6.5.4.1. Матрица плотности . . . . . . . . . . . . . . . . . . . . . .
151
6.5.4.2. С точки зрения ансамбля . . . . . . . . . . . . . . . . . .
151
6.5.4.3. С точки зрения подсистем . . . . . . . . . . . . . . . . . .
153
6.5.4.4. Фундаментальная точка зрения . . . . . . . . . . . . . .
154
6.5.4.5. Энтропия фон Неймана. . . . . . . . . . . . . . . . . . . .
154
6.6. Шумы и исправление ошибок . . . . . . . . . . . . . . . . . . . . . . . . .
156
6.6.0.1. Зашумленные каналы . . . . . . . . . . . . . . . . . . . . .
156
6.6.0.2.Классическая коррекция ошибок . . . . . . . . . . . . .
156
6.6.0.3.Коды с повторениями . . . . . . . . . . . . . . . . . . . . .
157
6.6.1. Квантовые шумы . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
157
6.6.2. Квантовая коррекция ошибок . . . . . . . . . . . . . . . . . . . . .
157
6.6.2.1. Квантовые коды с повторениями . . . . . . . . . . . . .
158
6.6.2.2. Исправление ошибок . . . . . . . . . . . . . . . . . . . . .
159
6.7. Белловские состояния . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
162
6.7.1. Измерения в одном направлении . . . . . . . . . . . . . . . . . .
163
6.7.2. Измерения в разных направлениях . . . . . . . . . . . . . . . . .
164
6.7.3. Неравенство Белла . . . . . . . . . . . . . . . . . . . . . . . . . . . .
165
6.7.3.1. КМ-предсказание . . . . . . . . . . . . . . . . . . . . . . . .
165
6.7.3.2. ЭПР-предсказание . . . . . . . . . . . . . . . . . . . . . . .
166
6.8. Криптология . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
169
6.8.1. Классическая криптография . . . . . . . . . . . . . . . . . . . . . .
169
6.8.2. Квантовая криптография . . . . . . . . . . . . . . . . . . . . . . . .
170
6.8.2.1. Квантовые деньги . . . . . . . . . . . . . . . . . . . . . . .
171
6.8.2.2. Квантовый перехват пакетов . . . . . . . . . . . . . . . .
172
6.8.2.3. Квантовое распространение ключей . . . . . . . . . . .
172
6.8.2.4. Комментарии к предыдущему примеру . . . . . . . . .
173
6.9. Альтернативные модели вычислений . . . . . . . . . . . . . . . . . . . .
173

Оглавление

Глава 7. Квантовые алгоритмы . . . . . . . . . . . . . . . . . . . . . .
174

7.0.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
174
7.1. Алгоритм Дойча. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
175
7.1.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . .
175
7.1.2. Классическое решение . . . . . . . . . . . . . . . . . . . . . . . . .
176
7.1.3. Квантовое решение. . . . . . . . . . . . . . . . . . . . . . . . . . . .
176
7.1.4. Физические реализации . . . . . . . . . . . . . . . . . . . . . . . .
178
7.2. Алгоритм Дойча–Йожи . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
179
7.2.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . .
179
7.2.2. Квантовое решение. . . . . . . . . . . . . . . . . . . . . . . . . . . .
179
7.3. Алгоритм Шора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
181
7.3.1. Квантовое фурье-преобразование . . . . . . . . . . . . . . . . . .
181
7.3.2. Быстрая факторизация . . . . . . . . . . . . . . . . . . . . . . . . .
184
7.3.3. Нахождение порядка . . . . . . . . . . . . . . . . . . . . . . . . . .
185
7.3.3.1. Цепные дроби . . . . . . . . . . . . . . . . . . . . . . . . . .
185
7.3.3.2. Алгоритм и логическая цепь быстрой факторизации
186
7.4. Алгоритм Гровера. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
190
7.4.1. Задача коммивояжера . . . . . . . . . . . . . . . . . . . . . . . . . .
190
7.4.2. Квантовый поиск . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
190

Глава 8. Последние достижения в области
квантово-механических устройств . . . . . . . . . . . . . . . . . . . . .
194

8.1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
194
8.2. Физическая реализация . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
195
8.2.1. Технологии реализации . . . . . . . . . . . . . . . . . . . . . . . . .
196
8.3. Квантовые компьютерные языки . . . . . . . . . . . . . . . . . . . . . . .
197
8.4. Устройства шифрования . . . . . . . . . . . . . . . . . . . . . . . . . . . .
199
8.5. Последние достижения . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
199
8.5.1. Аппаратная архитектура . . . . . . . . . . . . . . . . . . . . . . . .
199
8.5.2. Криптография . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
200
8.5.3. Алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
200

Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
201

ПРЕДИСЛОВИЕ К ИЗДАНИЮ
НА РУССКОМ ЯЗЫКЕ

Квантовые вычисления предоставляют возможность громадного увеличения вычислительных мощностей по сравнению с классическими компьютерами. Множество вычислительно трудных задач,
таких как факторизация больших чисел, являются неразрешимыми для
обычных компьютеров, зато легко решаются с помощью квантовых.
Если квантовые компьютеры станут доступными, они покончат со многими стандартными подходами в шифровании вроде RSA-кодирования,
сделав их бесполезными. Хотя надо отметить, что вместе с квантовыми компьютерами появляются и новые алгоритмы «классического»
шифрования, которые невозможно взломать и с помощью квантовых
вычислений.
Большинство книг и печатных работ по квантовым вычислениям
подразумевают свободное владение читателем многими дисциплинами,
прежде всего линейной алгеброй и квантовой механикой. Это делает
большую часть современной литературы в этой области недоступной
многим студентам и программистам. В предлагаемом учебнике физические и математические основы квантовых вычислений излагаются
доступным языком. Стиль изложения выбран автором сжатым, но в то
же самое время достаточно полным, чтобы читатель мог продолжить
свое освоение квантовых вычислений, вооружившись фундаментальными понятиями и представлениями. Автором рассмотрены все математические и квантово-механические понятия, необходимые для квантовых
вычислений.
Книга рассчитана на инженеров, программистов и продвинутых студентов, имеющих интерес к квантовым вычислениям.

А. Д. Калашников

БЛАГОДАРНОСТИ

Настоящее учебное пособие начало свой путь как книга в
открытом доступе, поэтому в ее создании поучаствовало множество читателей. Мне бы хотелось поблагодарить каждого, кто внес даже самый
малый вклад. Особую благодарность заслуживают следующие люди.
Вараниу Пульсават, моя дорогая жена. Вараниу является неиссякаемым источником поддержки, дружбы и вдохновения.
Брайан Ледерер, непосредственно ответственен за отдельные куски
текста. В частности, им написаны раздел, посвященный состояниям
Белла, некоторые части главы о квантовой механике, а также и других
глав. Без его участия настоящая работа никогда бы не состоялась.
Мохамед Баракат и Массуд Гиас Бейги, опубликовавшие собственную версию книги на арабском!
Андреас Гуннарссон. Внимание Андреаса к мелочам не перестает
удивлять.
Моя особая благодарность Ксерксу Ранбю. Ксеркс сделал несколько
ценных замечаний и обнаружил множество опечаток.
Все члены Yahoo-группы QC4Dummies (http://groups.yahoo.com/
neo/groups/QC4dummies/), а также администраторы Дэвид Моррис и
Дэвид Рикман.
Шон Кэй и Майкл Нильсон за упоминание моего учебника в своих
блогах.
Авторы Slashdot (http://slashdot.org) и QubitNews за размещение на своих сайтах обзоров настоящего учебного пособия.
Джеймс Хари, Саймон Джонсон, Джеймс Холлис, Ник Оостерхоф,
Рад Радиш, Карол Барткевич, Робин Котари, Варун Вайдя, Кеннеди Роулстон, а также пользователи сайта Slashdot AC, Birdie 1013 и
s/nemesis.

Г Л А В А
1

ВВЕДЕНИЕ

1.1.
ПОЧЕМУ КВАНТОВЫЕ ВЫЧИСЛЕНИЯ?

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

Гл. 1. Введение

1.2.
ЗАЧЕМ НУЖЕН ЕЩЕ ОДИН УЧЕБНИК
ПО КВАНТОВЫМ ВЫЧИСЛЕНИЯМ?

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

1.2.1.
Квантовые вычисления и квантовая информация

На сегодняшний день наиболее полным изложением квантовых вычислений признана книга Quantum Computation and Quantum Information Майкла А. Нильсена и Исаака Л. Чанга. На русском языке она
издана издательством «Мир» в 2006 г. под названием «Квантовые вычисления и квантовая информация» (ISBN 5-03-003524-9). Мы будем
ссылаться на этот фундаментальный труд по его английской аббревиатуре QCQI.
Возможно, QCQI слишком тяжела для восприятия, особенно теми,
кто не обладает серьезной математической подготовкой. В связи с этим
наше учебное пособие отчасти представляет собой собрание разобранных примеров с различных веб-сайтов, из конспектов лекций, печатных
работ и книг, которые будут полезны для понимания тех или иных
концепций QCQI.

Г Л А В А
2

ИНФОРМАТИКА

2.1.
ВВЕДЕНИЕ

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

2.2.
ИСТОРИЯ

За отправную точку развития информатики принято считать изобретение Евклидом (около 300 г. до н. э.) алгоритма нахождения наибольшего общего делителя двух целых чисел. Существуют

Гл. 2. Информатика

и более древние источники, например вавилонские клинописные таблички (примерно 2000–1700 гг. до н. э.), на которых излагаются некие
алгоритмы [22]. Вплоть до XIX века невозможно отделить информатику
от других математических и инженерных дисциплин. По этой причине
мы будем рассматривать информатику как отдельную науку, начиная
с XIX века.
Предтечей ранних вычислительных машин стал, как это ни странно,
ткацкий станок Жаккара с перфокартами, изобретенный Жозефом Мари Жаккаром (1752–1834) в 1801 г. Этот станок позволял получать
ткани со сложным узором, хранящимся на особых перфокартах, определяющих последовательность операций ткацкого станка. К середине
XIX века Чарльз Бэббидж (рис. 2.1) спроектировал и частично построил несколько программируемых вычислительных машин (на рис. 2.4
показана одна из его машин, построенная в 1822 г.). Эти машины уже
обладали многими чертами современных компьютеров. Одна из машин Бэббиджа, названная аналитической машиной, обладала сменными программами, записанными на перфокартах по образу и подобию
перфокарт, использовавшихся на ткацких станках Жаккара. Подруга
Бэббиджа Ада Августа Кинг, графиня Лавлейс (рис. 2.1), дочь лорда Байрона, считается первым программистом, поскольку именно она
писала программы для аналитической машины. К сожалению, работы
Бэббиджа были почти полностью забыты вплоть до 1930-х годов. Точкой отсчета современной информатики можно считать 1936 г., когда
логик Алан Тьюринг (рис. 2.2) опубликовал свою работу, в которой
впервые употребил термин универсальный компьютер.

Рис. 2.1. Чарльз Бэббидж (1791–1871) и Ада Августа Кинг (1815–1852)

Первый электронный компьютер был разработан только в 1940-х
годах под руководством Джона фон Неймана (рис. 2.3). Именно его конструкция вычислительной машины послужила основой для большинства современных компьютеров. Архитектура фон Неймана состоит

2.2. История
15

из арифметического логического устройства (АЛУ), устройства управления, памяти, устройства ввода-вывода (ВВ) и шин, которые осуществляют вычислительный процесс. Эта архитектура впервые предложена в
1945 г. на чертежах EDVAC [10].

Рис. 2.2. Алан Тьюринг (1912–1954) и Алонзо Чёрч (1903–1995)

В течение следующих шестидесяти с лишним лет вычислительная
мощность компьютеров росла, открывая все новые и новые области их
применения. Сначала это происходило за счет внедрения в 1947 г. в конструкцию вычислительных машин транзисторов, затем в 1959 г. — интегральных схем. Параллельно шло развитие пользовательских интер
Рис. 2.3. Джон фон Нейман (1903–1957)

фейсов. В 1965 г. Гордон Мур, наблюдая за
выпуском каждый год новых интегральных
схем, сформулировал свой закон. В исходном
варианте закон Мура утверждал, что количество транзисторов на одном кристалле интегральной схемы, а с ним и вычислительная
мощность компьютеров удваивается каждые
12 месяцев. Постепенно время удвоения стало равно 18 месяцам, а позднее — примерно
24 месяцам, однако экспоненциальный характер роста удается сохранить и поныне. Впрочем, в последнее время все труднее поддерживать закон Мура, поскольку компоненты
интегральных схем, становясь все мельче и мельче, достигают своего
естественного предела. Вскоре они должны будут состоять всего лишь
из нескольких атомов [4], что делает неизбежными квантовые эффекты
и конец закона Мура.
Выход подсказывают преимущества квантовых эффектов, которые
мы можем использовать для вычислений в классическом смысле. Полностью овладев этими эффектами, мы можем достичь даже большего.

Гл. 2. Информатика

Рис. 2.4. Разностная машина Бэббиджа

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

2.3.
МАШИНЫ ТЬЮРИНГА

В 1928 г. Давид Гильберт (рис. 2.5) задался вопросом, существует ли универсальный алгоритмический процесс, устанавливающий истинность любого математического утверждения. Его ответ
был — да. В 1930 г. он пошел еще дальше, утверждая, что в математике
нет неразрешимых задач. Однако в 1931 г. это утверждение было опровергнуто Куртом Геделем (рис. 2.5) в теореме о неполноте, которую
можно сформулировать примерно так:

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