Квантовые вычисления для настоящих айтишников
Квантовые вычисления часто упоминаются в новостях: Китай телепортировал кубит с Земли на спутник; алгоритм Шора поставил под угрозу ныне используемые методы шифрования; квантовое распределение ключей снова сделает шифрование надежным средством защиты; алгоритм Гровера увеличит скорость поиска данных.
Но что все это означает на самом деле? Как все это работает? Можно ли освоить эту тему без знания математики?
Нет, если вы хотите по-настоящему понять суть происходящего. Основные идеи берут начало в квантовой механике и часто противоречат здравому смыслу. Попытки описать их обычными словами обречены на провал, потому что эти явления не имеют отражения в обыденной жизни. Хуже того, словесные описания часто создают впечатление, что мы что-то поняли, хотя на самом деле все не так плохо — нам не придется сильно углубляться в математику, достаточно того, что пытались вбить в наши головы в старших классах школы.
Квантовые вычисления — это удивительный сплав квантовой физики и информатики, объединяющий самые яркие идеи из физики двадцатого века и позволяющий по-новому взглянуть на компьютерные технологии.
Благодарности.............................................................................................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
Изучаем Python, том 1, 5-е издание3 280 ₽
Java. Полное руководство, 10-е издание4 430 ₽
Анализ ценных бумаг. 3-е издание5 690 ₽