Квантовые вычисления - Стин Э.
Квантовые вычисления
Автор: Стин Э.Издательство: НИЦ: Регулярная и хаотическая динамика
Год издания: 2000
Страницы: 112
Читать: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
Скачать:
Э. Стин
КВАНТОВЫЕ ВЫЧИСЛЕНИЯ
Ижевск: НИЦ "Регулярная и хаотическая динамика", 2000, 112 стр.
Новая область науки о квантовых вычислениях лежит на стыке квантовой
теории информации, компьютерных наук и квантовой физики. В небольшом
обзоре известного английского специалиста обсуждаются основные понятия
квантовых вычислений и квантовой теории информации. Затрагиваются вопросы
квантовой криптографии и телепортации.
Книга написана доступно и просто, ориентирована на широкий круг
читателей, желающих познакомиться с этой новой и перспективной областью
научных исследований.
Содержание
Предисловие 5
Глава 1. Введение 8
Глава 2. Классическая теория информации 23
2.1. Меры (количества) информации 23
2.2. Сжатие информации 26
2.3. Двоичный симметричный канал 30
2.4. Коды, исправляющие ошибки 32
Глава 3. Классическая теория вычислений 37
3.1. Универсальный компьютер. Машина Тьюринга 38
3.2. Сложность вычисления 40
3.3. Невычислимые функции 42
Глава 4. Квантовая физика против физики классической 44
4.1. Парадокс Эйнштейна-Подольского-Розена (EPR). Неравенство Белла 46
Глава 5. Квантовая информация 50
5.1. Кубиты 50
5.2. Квантовые гейты 50
5.3. Неклонируемость квантового состояния 53
5.4. Плотное кодирование 54
5.5. Квантовая телепортация 57
5.6. Сжатие квантовой информации 58
5.7. Квантовая криптография 60
Глава 6. Универсальный квантовый компьютер 64
6.1. Универсальный гейт 65
6.2. Закон Чёрча- Тьюринга 66
Глава 7. Квантовые алгоритмы 68
7.1. Имитация физических систем 68
7.2. Алгоритм поиска периода функции. Алгоритм Шора по разложению 69
на множители
7.3. Алгоритм поиска Гровера 75 Глава 8. Экспериментальные процессоры,
оперирующие квантовой 78
информацией
8.1. Ионная ловушка 79
8.2. Ядерный магнитный резонанс 82
8.3. Высококачественные оптические резонаторы 85
Глава 9. Исправление квантовых ошибок 86
Глава 10. Обсуждение 9-7
Литература 102
Предисловие
Предмет квантовых вычислений объединяет в себе идеи классической
информации, информатики и квантовой физики. В данном обзоре затрагиваются
не только квантовые вычисления, но в общих чертах рассматривается вся
теория квантовой информации. Информация может рассматриваться как какая-
либо структура, движущаяся от причины к следствию. Таким образом,
информация имеет фундаментальное значение в физике. Однако математический
подход к информации и, в частности, ее обработка возникли совсем недавно
- в середине двадцатого века. Таким образом, только сейчас была осознана
вся значимость информатики, как основного понятия физики и, в
особенности, квантовой механики. Поставив информацию на твердую основу,
теория квантовой информации и вычислений привела к более глубокому
пониманию окружающего мира. Выли найдены: защищенный способ переноса
классической информации с помощью квантовых состояний (квантовая
криптография), надежный метод переноса квантовых состояний, посредством
квантового зацепления (телепортация), возможность сохранения квантовой
когерентности при необратимых шумовых процессах (исследование квантовых
ошибок) и метод эффективных квантовых вычислений посредством
контролируемой квантовой эволюции. Идея, объединяющая данные открытия,
заключается в использовании квантового зацепления в качестве
вычислительного средства.
Становится ясно, что теория информации и квантовая механика хорошо
дополняют друг друга. Для объяснения их взаимосвязи обзор начинается со
вступления в классическую теорию информации и в информатику. Там же
рассматривается теорема Шеннона, коды, исправляющие ошибки, машина
Тьюринга и сложность вычислений. После этого даются основные принципы
квантовой механики и описание эксперимента EPR (Einstein-Podolski-Rosen).
Корреляции EPR-Bell и квантовое зацепление проводят линию раздела между
квантовой и классической теорией информации и, возможно, между квантовой
и классической физикой.
6
Предисловие
В дальнейшем в общих чертах обозначаются основные идеи по работе с
квантовой информацией: сжатие кубитов и информации, квантовые логические
гейты, свойство неклонируемости неизвестного квантового состояния (no
cloning property) и телепортация. Вкратце рассматривается квантовая
криптография. Дается описание универсального квантового компьютера,
опирающееся на принцип Чёрча-Тьюринга и сетевую модель вычислений.
Рассматриваются алгоритмы для данного компьютера, в частности, алгоритмы
поиска периода функции и поиска записи в неупорядоченной базе данных. Эти
алгоритмы показывают, что квантовый компьютер, обладающий достаточно
точной структурой, не только существенно отличается от любого другого
компьютера, оперирующего классической информацией, но способен
обрабатывать малый класс функций с более высокой производительностью. Это
значит, что для некоторых важных вычислительных задач требуется только
квантовый компьютер.
Для создания универсального квантового компьютера требуются технологии
даже не завтрашнего дня. Однако принципы физики квантовой информации
