Время и память квантовых и недетерминистических вычислений Ожигов, Юрий Игоревич

Краткое описание

Ожигов, Юрий Игоревич.Время и память квантовых и недетерминистических вычислений : диссертация ... доктора физико-математических наук : 01.04.02. - Москва, 1999. - 75 с. : ил.

Оглавление диссертациидоктор физико-математических наук Ожигов, Юрий Игоревич
03 Введение
Об Глава 1. Квантовые компьютеры с последовательным доступом
06 1.1. Классические и квантовые вычисления
07 1.1.1. Введение в классические алгоритмы
08 1.1.2. История квантовых вычислений. Недетерминизм 10 1.2 Общие принципы квантовых вычислений
10 1.2.1 Гильбертово пространство состояний и наблюдения
11 1.2.2 Матрица плотности и проблема декогерентности 13 1.3 Формализация квантовых алгоритмов
13 1.3.1 Различные модели квантовых вычислений
13 1.3.2 Модель квантового компьютера. (неформальное описание)
16 1.3.3. Модель квантового компьютера.
18 1.3.4 Роль оракула в квантовом компьютере
20 1.4 Формулировка основных результатов
23 1.5 Вероятностная мера на оракулах
24 1.6. Моделирование эволюций на компьютере с оракулом 24 1.6.1. Классическое моделирование эволюций
26 1.6.2. Квантовое моделирование коротких эволюций
28 1.6.3. Нижняя граница времени квантовой имитации.
30 Глава 2. Квантовые алгоритмы, использующие поиск
30 2.1 Проверка формул логики предикатов
30 2.1.1 Формулировка результата
31 2.1.2 Унитарные алгоритмы
34 2.1.3 Элиминация кванторов
35 2.2 Нижняя оценка сложности квантового перебора 35 2.2.1 Формулировка основной теоремы.
37 2.2.2 Доказательство
40 2.2.3 Нижняя оценка времени квантового поиска
40 2.3 Квантовая база данных
40 2.3.1 Квантовые методы хранения и защиты информации
42 2.3.2 Основные свойства преобразования диффузии
42 2.3.3 Относительное преобразование диффузии
43 2.3.4 Реализация относительного преобразования диффузии.
46 2.3.5 Защита информации
47 2.3.6 Замечание о коррекции ошибок в базе данных
49 Глава 3. Вычисления на недетерминистических клеточных
49 3.1 Клеточный автомат как модель вычислений.
51 3.2 Основные определения и результаты
55 3.3 Метод прямого моделирования
62 3.4 Оптимизация автоматов.
65 3.5 Метод эвольвент
70 Некоторые проблемы