Квантовые вычисления для настоящих айтишников

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

Введение......................................................................................................11
От издательства.............................................................................................17
Глава 1. Спин.....................................................................................................18
«Квантовые» часы..........................................................................................24
Измерения в одном направлении....................................................................24
Измерения в разных направлениях.................................................................25
Измерения......................................................................................................27
Случайность...................................................................................................28
Фотоны и поляризация...................................................................................30
Заключение....................................................................................................34
Глава 2. Линейная алгебра................................................................................36
Комплексные и действительные числа...........................................................37
Векторы..........................................................................................................38
Диаграммы векторов......................................................................................39
Длина вектора................................................................................................40
Скалярное произведение................................................................................40
Сложение векторов........................................................................................41
Ортогональные векторы.................................................................................43
Умножение бра на кет....................................................................................43
Произведение бра-кет и длина.......................................................................44
Произведение бра-кет и ортогональность.......................................................45
Ортонормированный базис.............................................................................46
Векторы как линейные комбинации базисных векторов..................................48
Упорядоченные базисы..................................................................................50
Длины векторов.............................................................................................51
Матрицы.........................................................................................................51
Вычисления с матрицами................................................................................54
Ортогональные и унитарные матрицы............................................................56
Инструменты линейной алгебры.....................................................................57
Глава 3. Спин и кубиты......................................................................................59
Вероятность...................................................................................................59
Математика квантового спина........................................................................60
Эквивалентные векторы состояний.................................................................64
Базис, соответствующий заданному направлению спина................................66
Поворот установки на 60°..............................................................................68
Математическая модель поляризации фотона................................................69
Базис, соответствующий заданному направлению поляризации.....................71
Эксперименты с поляризованными фильтрами...............................................71
Кубиты...........................................................................................................74
Алиса, Боб и Ева.............................................................................................75
Амплитуды вероятности и интерференция.....................................................78
Алиса, Боб, Ева и протокол BB84....................................................................79
Глава 4. Запутанность........................................................................................83
Кубиты Алисы и Боба не запутаны..................................................................84
Незапутанные кубиты.....................................................................................86
Запутанные кубиты........................................................................................87
Общение со сверхсветовой скоростью ...........................................................90
Стандартный базис для тензорных произведений...........................................92
Как запутать кубиты?.....................................................................................93
Запутывание кубитов с помощью вентиля CNOT.............................................95
Запутанные квантовые часы...........................................................................96
Глава 5. Неравенство Белла...............................................................................99
Запутанные кубиты в разных базисах...........................................................101
Эйнштейн и локальный реализм...................................................................104
Эйнштейн и скрытые переменные................................................................106
Классическое объяснение запутанности.......................................................107
Неравенство Белла.......................................................................................109
Ответ модели квантовой механики...............................................................109
Ответ классической модели..........................................................................111
Измерение....................................................................................................115
Протокол Экерта для квантового распределения ключей.............................117
Глава 6. Классическая логика, вентили и цепи.................................................120
Логика..........................................................................................................121
Отрицание............................................................................................121
И...........................................................................................................122
ИЛИ......................................................................................................122
Булева алгебра.............................................................................................123
Логическая эквивалентность........................................................................125
Функциональная полнота.............................................................................126
И-НЕ.............................................................................................................128
Вентили........................................................................................................131
Вентиль НЕ...........................................................................................131
Вентиль И.............................................................................................131
Вентиль ИЛИ.........................................................................................132
Вентиль И-НЕ........................................................................................132
Цепи.............................................................................................................132
И-НЕ — универсальный вентиль...................................................................134
Вентили и вычисления.................................................................................135
Память.........................................................................................................137
Обратимые вычисления................................................................................138
Управляемое НЕ....................................................................................139
Вентиль Тоффоли.................................................................................141
Вентиль Фредкина.................................................................................144
Бильярдный компьютер................................................................................146
Глава 7. Квантовые вентили и цепи.................................................................152
Кубиты.........................................................................................................153
Управляемое НЕ ..........................................................................................154
Квантовые вентили......................................................................................156
Квантовые вентили, воздействующие на один кубит....................................156
Вентили I и Z........................................................................................157
Вентили X и Y........................................................................................158
Вентиль Адамара...................................................................................158
Существуют ли универсальные квантовые вентили?.....................................159
Теорема о запрете клонирования.................................................................160
Квантовые и классические вычисления........................................................163
Цепь Белла...................................................................................................164
Сверхплотное кодирование..........................................................................166
Квантовая телепортация..............................................................................170
Коррекция ошибок.......................................................................................174
Повторение...........................................................................................176
Коррекция с квантовым кульбитом........................................................177
Глава 8. Квантовые алгоритмы.........................................................................181
Классы сложности P и NP.............................................................................182
Квантовые алгоритмы быстрее классических?..............................................185
Запрос сложности.........................................................................................185
Алгоритм Дойча............................................................................................186
Кронекеровское произведение матриц Адамара...........................................191
Алгоритм Дойча—Джозы..............................................................................194
Шаг 1. Передача кубитов через вентили Адамара.................................197
Шаг 2. Передача кубитов через вентиль F.............................................198
Шаг 3. Передача верхних кубитов через вентили Адамара....................199
Шаг 4. Измерение верхних кубитов.......................................................200
Алгоритм Саймона........................................................................................200
Поразрядное сложение последовательностей по модулю 2...................201
Формулировка задачи Саймона.............................................................201
Скалярное произведение и матрица Адамара........................................203
Матрицы Адамара и задача Саймона.....................................................204
Квантовая цепь для задачи Саймона.....................................................206
Классическая часть алгоритма Саймона................................................209
Классы сложности........................................................................................212
Квантовые алгоритмы..................................................................................215
Глава 9. Влияние квантовых вычислений.........................................................217
Алгоритм Шора и криптоанализ...................................................................218
Алгоритм шифрования RSA...................................................................218
Алгоритм Шора.....................................................................................220
Алгоритм Гровера и поиск данных................................................................223
Алгоритм Гровера.................................................................................224
Применения алгоритма Гровера............................................................228
Химия и моделирование...............................................................................229
Оборудование..............................................................................................231
Квантовый отжиг..................................................................................233
Квантовое превосходство и параллельные Вселенные..................................235
Вычисления..................................................................................................237