Введение в квантовые вычисления

Description

Эта книга, написанная кратко и доступно, обеспечивает всестороннее введение в квантовые вычисления — захватывающую и быстро развивающуюся область, которая находится на пересечении компьютерных, инженерно-технических, математических и физических наук.\nКнига предназначена для студентов старших курсов и начинающих аспирантов перечисленных дисциплин, она насыщена техническими деталями и иллюстрирована пояснительными диаграммами и упражнениями. Пер с англ. Т.С. Никитиной. Предисловие к русскому изданию......Page 4 Предисловие......Page 5 Благодарности......Page 6 1.1. Общие сведения......Page 7 1.2. Компьютеры и строгий тезис Чёрча-Тьюринга......Page 8 1.3. Схемная модель вычислений......Page 13 1.4. Схемная модель в формулировке линейной алгебры......Page 16 1.5. Обратимые вычисления......Page 21 1.6. Знакомство с квантовой физикой......Page 23 1.7. Квантовая физика и квантовые вычисления......Page 26 2.1. Дираковская система обозначений и гильбертово пространство......Page 28 2.2. Двойственные векторы......Page 30 2.3. Операторы......Page 35 2.4. Спектральная теорема......Page 39 2.5. Функции операторов......Page 41 2.6. Тензорные произведения......Page 43 2.7. Теорема Шмидта о разложении......Page 45 2.8. Некоторые замечания о дираковской системе обозначений......Page 48 3.1. Состояние квантовой системы......Page 50 3.2. Временная эволюция изолированной системы......Page 56 3.3. Составные системы......Page 59 3.4. Измерение......Page 62 3.5. Смешанные состояния и обобщенные квантовые операции......Page 68 4.1. Модель квантовой схемы......Page 79 4.2. Квантовые элементы......Page 80 4.3. Универсальные множества квантовых элементов......Page 87 4.4. Эффективность аппроксимации унитарных преобразований......Page 91 4.5. Реализация измерений с помощью квантовых схем......Page 93 ГЛАВА 5. Сверхплотное кодирование и квантовая телепортация......Page 99 5.1. Сверхплотное кодирование......Page 100 5.2. Квантовая телепортация......Page 101 5.3. Применение квантовой телепортации......Page 104 6.1. Сравнение вероятностного и квантового алгоритмов......Page 110 6.2. Возврат фазы......Page 116 6.3. Алгоритм Дойча......Page 120 6.4. Алгоритм Дойча-Джозы......Page 126 6.5. Алгоритм Саймона......Page 131 ГЛАВА 7. Алгоритмы с сверхполиномиальным ускорением......Page 140 7.1. Оценка квантовой фазы и квантовое преобразование Фурье......Page 141 7.2. Оценка собственного значения......Page 159 7.3. Вычисление поряда......Page 166 7.4. Вычисление дискретного логарифма......Page 180 7.5. Скрытая подгруппа......Page 186 7.6. Сопутствующие алгоритмы и методы......Page 192 8.1. Квантовый алгоритм поиска Гровера......Page 194 8.2. Усиление амплитуды......Page 208 8.3. Квантовая оценка амплитуды и квантовое перечисление......Page 216 8.4. Поиск с неизвестной вероятностью успеха......Page 223 8.5. Сопутствующие алгоритмы и методы......Page 226 ГЛАВА 9. Квантовая теория вычислительной сложности и нижние оценки......Page 228 9.1. Вычислительная сложность......Page 229 9.2. Модель черного ящика......Page 236 9.3. Нижние оценки для задачи поиска на модели черного ящика: гибридный метод......Page 239 9.4. Нижние оценки общей модели черного ящика......Page 243 9.5. Метод полиномов......Page 246 9.6. Блоковая чувствительность......Page 250 9.7. Метод от противного......Page 251 ГЛАВА 10. Исправление квантовых ошибок......Page 259 10.1. Классический метод исправления ошибок......Page 260 10.2. Классический трехбитовый код......Page 264 10.3. Отказоустойчивость......Page 268 10.4. Исправление квантовых ошибок......Page 269 10.5. Трех- и девятикубитовые квантовые коды......Page 283 10.6. Отказоустойчивые квантовые вычисления......Page 296 ПРИЛОЖЕНИЕ А......Page 352 А.1. Инструменты анализа вероятностных алгоритмов......Page 305 А.2. Решение задачи дискретного логарифмирования, когда поря-док а есть составное число......Page 308 А.З. Какой должна быть случайная выборка?......Page 310 А.4. Определение г при заданном для произвольного к......Page 312 А.5. Лемма по методу от противного......Page 313 А.6. Черные ящики для групповых вычислений......Page 316 А.7. Выполнение разложения Шмидта......Page 319 А.8. Общие измерения......Page 321 А.9. Оптимальное различение двух состояний......Page 324 Литература......Page 327