Программирование квантовых компьютеров. Базовые алгоритмы и примеры кода

Никита Федотов Ник Хэрриган Эрик Джонстон

Обложка:


От издательства............................................................................................. 14
Предисловие .................................................................................................. 15
Структура книги ...............................................................................................15
Типографские соглашения................................................................................17
Благодарности..................................................................................................17
Глава 1. Введение.......................................................................................... 19
Необходимая подготовка..................................................................................19
Что такое QPU? ................................................................................................21
Практический подход .......................................................................................22
Учебник QCEngine .......................................................................................22
Отладка ......................................................................................................24
Низкоуровневые команды QPU .........................................................................25
Ограничения моделирования ......................................................................28
Аппаратные ограничения ............................................................................28
QPU и GPU: некоторые общие характеристики..................................................29
ЧАСТЬ I.
ПРОГРАММИРОВАНИЕ ДЛЯ QPU
Глава 2. Один кубит....................................................................................... 32
Краткий обзор физических кубитов ..................................................................34
Круговая запись ...............................................................................................37
Размер круга ...............................................................................................38
Поворот ......................................................................................................39
Первые операции QPU......................................................................................41
Команда QPU: NOT ......................................................................................41
Команда QPU: HAD......................................................................................42
Команда QPU: READ ....................................................................................43
Команда QPU: WRITE ..................................................................................43
Практический пример: идеально случайный бит .........................................45
Пример кода ...............................................................................................46
Пример кода ...............................................................................................48
Команды QPU: PHASE(θ) .............................................................................48
Команды QPU: ROTX(θ) и ROTY(θ)...............................................................49
COPY: недостающая операция ..........................................................................50
Объединение операций QPU.............................................................................50
Команда QPU: ROOT-NOT.............................................................................51
Пример кода ...............................................................................................52
Практический пример: квантовая проверка защиты .........................................53
Пример кода ...............................................................................................54
Итоги................................................................................................................57
Глава 3. Группы кубитов ............................................................................... 58
Круговая запись для многокубитных регистров ................................................58
Пример кода ...............................................................................................60
Изображение многокубитного регистра ............................................................61
Однокубитные операции в многокубитных регистрах .......................................62
Чтение кубита в многокубитном регистре....................................................64
Наглядное представление большего количества кубитов .................................65
Команды QPU: CNOT.........................................................................................67
Практический пример: использование пар Белла для реализации
совместной случайности...................................................................................70
Пример кода ...............................................................................................71
Команды QPU: CPHASE и CZ..............................................................................71
Приемы программирования QPU: фазовый откат..............................................73
Пример кода ...............................................................................................75
Команда QPU: CCNOT (вентиль Тоффоли) ........................................................75
Команды QPU: SWAP и CSWAP ..........................................................................76
Проверка обменом ......................................................................................77
Пример кода ...............................................................................................78
Построение произвольной условной операции .................................................81
Пример кода ...............................................................................................82
Практический пример: дистанционно управляемая случайность.......................84
Пример кода ...............................................................................................84
Итоги................................................................................................................87
Глава 4. Квантовая телепортация ................................................................ 88
Практический пример: первые шаги в телепортации........................................88
Пример кода ...............................................................................................90
Анализ программы............................................................................................94
Шаг 1: создание запутанной пары...............................................................95
Шаг 2: подготовка данных...........................................................................95
Шаг 3.1: связывание данных с запутанной парой........................................96
Шаг 3.2: перевод кубита данных в суперпозицию .......................................97
Шаг 3.3: чтение обоих кубитов Алисы.........................................................97
Шаг 4: получение и преобразование ...........................................................98
Шаг 5: проверка результата........................................................................99
Интерпретация результатов ........................................................................... 101
Как используется телепортация? .................................................................... 102
Известные проблемы при телепортации ......................................................... 102
ЧАСТЬ II.
ПРИМИТИВЫ QPU
Глава 5. Квантовая арифметика и логика ................................................. 106
Странно и необычно....................................................................................... 106
Арифметика с QPU.......................................................................................... 108
Практический пример: построение операторов инкремента и декремента....109
Пример кода ............................................................................................. 110
Сложение двух квантовых целых чисел .......................................................... 112
Пример кода ............................................................................................. 113
Отрицательные числа..................................................................................... 114
Практический пример: более сложные вычисления........................................ 115
Пример кода ............................................................................................. 116
Переход на квантовый уровень ...................................................................... 116
Квантовое условное выполнение............................................................... 116
Пример кода ............................................................................................. 117
Фазовое кодирование результата.............................................................. 118
Пример кода ............................................................................................. 118
Обратимость и служебные кубиты.................................................................. 119
Отмена вычислений........................................................................................ 122
Отображение булевой логики на операции QPU ............................................. 125
Базовая квантовая логика ......................................................................... 126
Пример кода ............................................................................................. 127
Итоги.............................................................................................................. 128
Глава 6. Усиление комплексной амплитуды ............................................. 129
Практический пример: преобразование между фазой и амплитудой............... 129
Пример кода ............................................................................................. 130
Итерация усиления комплексной амплитуды .................................................. 132
Больше итераций?.......................................................................................... 133
Пример кода ............................................................................................. 134
Инвертирование нескольких элементов.......................................................... 136
Пример кода ............................................................................................. 137
Использование усиления комплексной амплитуды.......................................... 142
AA и QFT при оценке суммы ...................................................................... 142
Ускорение традиционных алгоритмов с применением AA .......................... 143
Внутри QPU .................................................................................................... 143
Интуитивное понимание............................................................................ 143
Итоги.............................................................................................................. 146
Глава 7. QFT: квантовое преобразование Фурье ...................................... 147
Скрытые закономерности ............................................................................... 147
Пример кода ............................................................................................. 148
QFT, DFT и FFT ............................................................................................... 149
Частоты в регистре QPU ................................................................................. 150
Пример кода ............................................................................................. 151
Пример кода ............................................................................................. 154
DFT ................................................................................................................ 154
Вещественные и комплексные входные данные для DFT ........................... 156
Подробнее о DFT....................................................................................... 158
Пример кода ............................................................................................. 160
Практическое применение QFT....................................................................... 163
Скорость QFT ............................................................................................ 163
Пример кода ............................................................................................. 167
Пример кода ............................................................................................. 167
Пример кода ............................................................................................. 168
Внутри QPU .................................................................................................... 169
Интуитивное объяснение........................................................................... 170
Последовательность операций .................................................................. 172
Пример кода ............................................................................................. 173
Итоги.............................................................................................................. 176
Глава 8. Квантовая оценка фазы ............................................................... 177
Получение информации об операциях QPU .................................................... 177
Собственные фазы предоставляют полезную информацию ............................ 178
Что делает оценка фазы................................................................................. 180
Как пользоваться оценкой фазы..................................................................... 180
Ввод.......................................................................................................... 182
Пример кода ............................................................................................. 182
Вывод........................................................................................................ 184
Предостережения........................................................................................... 184
Выбор размера выходного регистра .......................................................... 185
Сложность................................................................................................. 186
Условные операции................................................................................... 186
Оценка фазы на практике............................................................................... 186
Внутри QPU .................................................................................................... 187
Пример кода ............................................................................................. 187
Интуитивное объяснение........................................................................... 188
Операция за операцией............................................................................. 190
Итоги.............................................................................................................. 192
ЧАСТЬ III.
ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ QPU
Глава 9. Реальные данные.......................................................................... 194
Нецелые данные............................................................................................. 195
QRAM ............................................................................................................. 196
Пример кода ............................................................................................. 198
Пример кода ............................................................................................. 200
Кодирование векторов ................................................................................... 201
Пример кода ............................................................................................. 203
Ограничения комплексного амплитудного кодирования ............................ 204
Комплексное амплитудное кодирование и круговая запись ....................... 206
Кодирование матриц ...................................................................................... 207
Как матрицы могут представляться операциями QPU?............................... 208
Квантовое моделирование ........................................................................ 209
Глава 10. Квантовый поиск......................................................................... 215
Фазовая логика .............................................................................................. 216
Построение элементарных операций фазовой логики................................ 218
Построение сложных команд фазовой логики ........................................... 219
Пример кода ............................................................................................. 221
Решение логических головоломок .................................................................. 222
О котятах и тиграх .................................................................................... 223
Пример кода ............................................................................................. 226
Общий рецепт для решения задач выполнимости булевых формул ................ 227
Практический пример: задача выполнимости 3-SAT .................................. 229
Пример кода ............................................................................................. 229
Практический пример: невыполнимая задача 3-SAT .................................. 231
Пример кода ............................................................................................. 232
Ускорение традиционных алгоритмов............................................................. 234
Глава 11. Квантовая избыточная выборка................................................ 236
Применение QPU в компьютерной графике .................................................... 236
Традиционная избыточная выборка................................................................ 237
Практический пример: вычисление изображений с фазовым
кодированием................................................................................................. 239
Пиксельный шейдер .................................................................................. 240
Использование операции PHASE для рисования ........................................ 241
Пример кода ............................................................................................. 242
Рисование кривых ..................................................................................... 243
Пример кода ............................................................................................. 244
Выборка в изображениях с фазовым кодированием........................................ 245
Пример кода ............................................................................................. 247
Более интересное изображение...................................................................... 247
Избыточная выборка ...................................................................................... 248
Пример кода ............................................................................................. 250
QSS и традиционная выборка методом Монте-Карло ...................................... 251
Как работает QSS...................................................................................... 252
Пример кода ............................................................................................. 255
Добавление цветов......................................................................................... 257
Итоги.............................................................................................................. 259
Глава 12. Алгоритм Шора............................................................................ 260
Практический пример: алгоритм Шора на QPU............................................... 261
Пример кода ............................................................................................. 262
Что делает алгоритм Шора............................................................................. 263
Для чего вообще нужен QPU?.................................................................... 264
Пример кода ............................................................................................. 264
Квантовое решение................................................................................... 266
Шаг за шагом: разложение числа 15 на простые множители .......................... 268
Пример кода ............................................................................................. 268
Шаг 1: инициализация регистров QPU....................................................... 269
Шаг 2: перевод в квантовую суперпозицию .............................................. 270
Шаг 3: условное умножение на 2 .............................................................. 272
Шаг 4: условное умножение на 4 .............................................................. 274
Шаг 5: квантовое преобразование Фурье .................................................. 276
Шаг 6: чтение квантового результата........................................................ 276
Шаг 7: цифровая логика............................................................................ 278
Пример кода ............................................................................................. 279
Шаг 8: проверка результата...................................................................... 281
Важные подробности...................................................................................... 281
Вычисление остатка .................................................................................. 281
Время и память ......................................................................................... 283
Другие значения переменной coprimes...................................................... 283
Глава 13. Квантовое машинное обучение ................................................. 284
Решение систем линейных уравнений............................................................. 285
Описание и решение систем линейных уравнений..................................... 286
Решение линейных уравнений на QPU....................................................... 288
Квантовый анализ главных компонент............................................................ 298
Традиционный анализ главных компонент ................................................ 299
PCA с QPU ................................................................................................. 301
Квантовый метод опорных векторов............................................................... 305
Традиционный метод опорных векторов.................................................... 306
SVM с QPU................................................................................................. 310
Другие применения машинного обучения....................................................... 315
ЧАСТЬ IV.
ПЕРСПЕКТИВЫ
Глава 14. Обзор литературы....................................................................... 318
От круговой записи к комплексным векторам ................................................. 318
Некоторые нюансы и примечания по терминологии ....................................... 321
Измерительный базис..................................................................................... 322
Разложение и компиляция вентилей............................................................... 324
Телепортация вентилей.................................................................................. 326
Зал славы QPU................................................................................................ 326
Гонка между квантовыми и традиционными компьютерами............................ 327
Алгоритмы на базе оракулов .......................................................................... 328
Алгоритм Дойча—Джозы........................................................................... 329
Задача Бернштейна—Вазирани ................................................................. 329
Задача Саймона ........................................................................................ 330
Языки квантового программирования............................................................. 330
Перспективы квантового моделирования........................................................ 332
Исправление ошибок и устройства NISQ......................................................... 332
Что дальше? ................................................................................................... 333
Книги ........................................................................................................ 333
Конспекты лекций ..................................................................................... 334
Сетевые источники информации ............................................................... 334