Время и память квантовых и недетерминистических вычислений

• Автор: Ожигов, Юрий Игоревич
• Шифр специальности: 01.04.02
• Научная степень: Докторская
• Год защиты: 1999
• Место защиты: Москва
• Количество страниц: 75 с. : ил.

Глава 1. Квантовые компьютеры с последовательным доступом
1.1. Классические и квантовые вычисления
1.1.1. Введение в классические алгоритмы
1.1.2. История квантовых вычислений. Недетерминизм
1.2 Общие принципы квантовых вычислений
1.2.1 Гильбертово пространство состояний и наблюдения
1.2.2 Матрица плотности и проблема декогерентности
1.3 Формализация квантовых алгоритмов
1.3.1 Различные модели квантовых вычислений
1.3.2 Модель квантового компьютера... (неформальное описание)
1.3.3. Модель квантового компьютера
1.3.4 Роль оракула в квантовом компьютере
1.4 Формулировка основных результатов
1.5 Вероятностная мера на оракулах
1.6. Моделирование эволюций на компьютере с оракулом
1.6.1. Классическое моделирование эволюций
1.6.2. Квантовое моделирование коротких эволюций
1.6.3. Нижняя граница времени квантовой имитации
Глава 2. Квантовые алгоритмы, использующие поиск
2.1 Проверка формул логики предикатов
2.1.1 Формулировка результата
2.1.2 Унитарные алгоритмы
2.1.3 Элиминация кванторов
2.2 Нижняя оценка сложности квантового перебора
2.2.1 Формулировка основной теоремы
2.2.3 Нижняя оценка времени квантового поиска
2.2.2 Доказательство
2.3 Квантовая база данных
2.3.1 Квантовые методы хранения и защиты информации
2.3.2 Основные свойства преобразования диффузии
2.3.3 Относительное преобразование диффузии
2.3.4 Реализация относительного преобразования диффузии
2.3.5 Защита информации
2.3.6 Замечание о коррекции ошибок в базе данных
Глава 3. Вычисления на недетерминистических клеточных
3.1 Клеточный автомат как модель вычислений
3.2 Основные определения и результаты
3.3 Метод прямого моделирования
3.4 Оптимизация автоматов
3.5 Метод эвольвент
Некоторые проблемы
Заключение и выводы
Благодарности
Список литературы

Цель работы
Основная цель диссертации - исследовать соотношение между временем и памятью для вычислений на квантовых компьютерах и классических недетерминистических клеточных автоматах , и выяснение возможности общих методов квантово - механического ускорения классических алгоритмов с оракулами.
Полученные результаты
В диссертации установлены следующие новые научные результаты.
По квантовым компьютерам.
1. Предложена простая схема квантового компьютера с разделенными классической и квантовой частями (см. Главу 1).
2. Доказано, что не слишком длинная эволюция классической системы, выбранной произвольно с вероятностью 1 не может быть предсказана на квантовом компьютере даже на один шаг вперед. Таким образом, большинство классических алгоритмов с оракулом нельзя ускорить на квантовом компьютере. Вот точная формулировка этого результата.
Теорема 1.1.
Если Т = 0(2Т+7), є > 0, то для черного ящика / выбранного случайно из равномерного распределения с вероятностью 1 всякое квантовое вычисление Т итераций / требует не меньше Т обращений к /.
3. Для эволюций произвольной длины классических систем, выбранных с вероятностью 1, получена нижняя оценка на время квантовой имитации как квадратный корень из длины эволюции. Точная формулировка результата такова.
Теорема 1.2. Для черного ящика / выбранного произвольно из равномерного распределения с вероятностью 1 всякий квантовый компьютер, вычисляющий результат Т итераций f использует П(л/Т) обращений к /.
4. Получена новая нижняя оценка для квантового перебора:
Теорема 2.2.
Пусть і(п) = о(у/Лг/6(п)), п —у оо; и некоторый квантовый компьютер с оракулом для ф находит за время £(п) решение уравнения ф(х) — 1 для некоторых ф с фиксированной верхней оценкой е для вероятности ошибки (О < е < 1). Пусть р(п) будет вероятностью того, что этот алгоритм дает правильный ответ для оракула ф, выбранного случайно из равномерного распределения на Иь- Тогда р(п) —> 0 (п —)■ оо).
5. Построен квантовый алгоритм с параллельным доступом к оракулу, распознающий истинность формул логики предикатов за время порядка квадратного корня из длины формулы (уточнение и модернизация алгоритма Бурхама и др., полученное независимо).
Теорема 2.1 [36]. Существует квантовый алгоритм, проверяющий формулу логики предикатов вида (2.1) за время 0{ь/Й) с ограниченной вероятностью ошибки с использованием (Сп)к одновременных обращений к оракулу, где константа С зависит от вероятности ошибки.

6. Предложена схема квантовой базы данных, реализующая степень защиты информации, принципиально недостижимую в классических базах данных. Система управления такой базой данных основана на введенном автором относительном преобразовании диффузии (см. Главу 2). Соотношение между вероятностями несанкционированного получения информации и обнаружения такой попытки устанавливает такая Теорема.
Теорема 2.4. Существует функция а(д, Ы), такая что /е > 0 Зд : а(д,Д)> 1—б N = 1,2,... со следующим свойством. Для всякого выбора блоков, обозреваемых 5 и унитарных преобразований, которые б совершает, имеет место неравенство
Рех > раИо классическим недетерминистическим алгоритмам, реализуемым на клеточных автоматах.
7. Для самых быстрых недетерминистических клеточных автоматов установлена линейная связь памяти и времени.
Теорема 3.3. Пусть Л есть наибыстрейший недетерминистический клеточный автомат. Тогда
(3.3) Тд(п) = 0(5д(п)).
8. Построен способ имитации ?'-мерных недетерминистических клеточных автоматов с временем Т и памятью 5 в г + 1-мерном пространстве за время 0(Т'1~г/(г+1)2) или Тг+1
0(Т1/2 +
Теорема 3.1.
Щг, Т, 5) С Щг + 1, у/Г + 5, у/Т + 5).
Теорема 3.2.
Щг.ЗДсЩг.ТьТО,
где Т
Разработанные методы
В диссертации исследованы вычисления в моделях с двумя вариантами недетерминистичности: более сильной - классической и более слабой - квантовой. Предложена удобная для теоретических исследований модель квантового компьютера с разделением классической и квантовой частей. Для квантовых вычислений разработан метод получения нижних оценок, основанный на подсчете расстояний между состояниями квантового компьютера как точками в Гильбертовом пространстве состояний. На основе этого метода получены три первых результата о квантовых вычислениях. Введено понятие унитарных квантовых вычислений, и с использованием этого понятия построен квантовый алгоритм с параллельным доступом к оракулу для проверки истинности формул логики предикатов 1 порядка.
Для классических недетерминистических вычислений предложен метод оптимизации алгоритмов, и на его основе получены два последних результата.

Клеточные автоматы представляют собой удобный способ формализации этой проблемы. Клеточные автоматы являются динамическими системами с локальным взаимодействием в дискретном пространстве и времени, и одновременно их можно рассматривать как общую модель вычислительных устройств. Клеточные автоматы впервые были введены в работах У лама [45] и фон Неймана [30], и с тех пор различные проблемы, связанные с клеточными автоматами исследовались большим числом авторов (см. например, работы [14],[18],[44],[50],[54], [56]).
Пусть г > 1 - натуральное число, Zr - вычислительное пространство, элементы которого называются клетками, со - конечный алфавит для возможных состояний любой клетки г 6 Ъг. Клеточный автомат размерности г в алфавите со - это функция вида: А : ш2г+1 —> со
Клеточный автомат определяет специальный тип эволюции пространства . так что состояния всех клеток i € Ът изменяются синхронно в дискретные моменты времени в зависимости от состояния их ближайших окрестностей.
Нужно отметить, что возможен более общий подход, когда функция А зависит от г или 1. Мы не будем здесь рассматривать такие возможности.
Конфигурацией будем называть набор состояний всех клеток пространства в некоторый момент времени. В силу определения, эволюция клеточного автомата однозначно определяется начальной конфигурацией.
Если рассмотреть многозначную функцию вместо А, мы получим определение недетерминистического клеточного автомата. Вообще говоря, эволюция такого автомата не будет однозначно определяться заданием начальной конфигурации. Поведение недетерминистического автомата можно описать графом перемен состояний (см. работу [50]). Это граф, каждая вершина которого представляет некоторую конфигурацию. Направленные ребра соединяют вершины, показывая изменение конфигурации при одном шаге эволюции автомата. Каждая вершина имеет ровно одно исходящее ребро тогда и только тогда, когда данный автомат - детерминистический. Более того, если автомат недетерминистический, то для некоторой вершины число исходящих ребер будет бесконечно большим.
Отличие одномерных клеточных автоматов от многомерных впервые выяснилось при решении проблемы существования предшественника. Эта проблема заключается в нахождении конфигурации, предшествующей данной конечно определенной конфигурации в эволюции заданного клеточного автомата. Вольфрам показал в работе [50], что эта проблема алгоритмически разрешима для одномерных клеточных автоматов, а Таки в работе [52] показал, что данная проблема неразрешима для некоторых клеточных автоматов размерностей г, где г = 2,3,
Вычислительная эквивалентность клеточных автоматов и машин Тьюринга является простым и хорошо известным фактом (см. работы [17],[54]). Время вычислений Т(п) и память 3(7г) определяются стандартным образом для любого клеточного автомата А.
Здесь возникает следующий вопрос: если задан произвольный предика-т V, какой будет минимальная сложность г-мерного клеточного автомата, вычисляющего этот предикат, в зависимости от г?
Более точно, если некоторый предикат V вычисляется на клеточном ав-