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

Содержание
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 Некоторые проблемы ...
70 Заключение и выводы
72 Благодарности
73 Список литературы
2
Введение
Цель работы
Основная цель диссертации - исследовать соотношение между временем и памятью для вычислений на квантовых компьютерах и классических недетерминистических клеточных автоматах , и выяснение возможности общих методов квантово - механического ускорения классических алгоритмов с оракулами.
Полученные результаты
В диссертации установлены следующие новые научные результаты.
По квантовым компьютерам.
1. Предложена простая схема квантового компьютера с разделенными классической и квантовой частями (см. Главу 1).
2. Доказано, что не слишком длинная эволюция классической системы, выбранной произвольно с вероятностью 1 не может быть предсказана на квантовом компьютере даже на один шаг вперед. Таких! образом, большинство классических алгоритмов с оракулом нельзя ускорить на квантовом компьютере. Вот точная формулировка этого результата.
Теорема 1.1.
Если Т — 0(27+7), є > 0, то для черного ящика f выбранного случайно из ■равномерного распределения с вероятностью 1 всякое квантовое вычисление Т итераций J требует не меньше Т обращений к /.
3. Для эволюций произвольной длины классических систем, выбранных с вероятностью 1, получена нижняя оценка на время квантовой имитации как квадратный корень из длины эволюции. Точная формулировка результата такова.
Теорема 1.2. Для черного ящика / выбранного произвольно из равномерного распределения с вероятностью 1 всякий квантовый компьютер, вычисляющий результат, Т итераций f использует П(\/Т) обращений к /.
4. Получена новая нижня я оценка для квантового перебора:
Теорема 2.2. _______
Пусть t(n) = o(y/N/b(n)), п —>■ оо, и некоторый квантовый компьютер с оракулом для ф находит за время t(n) решение уравнения ф(х) = 1 для некоторых ф с фиксированной верхней оценкой б для вероятности ошибки (О < е < I). Пусть р(п) будет вероятностью т,ого, что этот алгоритм дает правильный ответ для оракула ф, выбранного случайно из равномерно?,о распределения на Sb. Тогюа р(п) —> 0 (п —ь оо).
о. Построен квантовый алгоритм с параллельным доступом к оракулу, распознающий истинность формул логики предикатов за время порядка квадратного корня из длины формулы (уточнение и модернизация алгоритма Бурхама и др., полученное независимо).
Теорема 2.1 [36]. Существует квант.овый алгоритм, проверяющий формулу логики предикатов егіда (2.1) за время 0(y/N) с ограниченной вероятностью ошибки с использованием (Сп)* одновременных обращений к оракулу, где константа С зависит от. вероятности ошибки.
3
G. Предложена схема квантовой базы данных, реализующая степень защиты информации, принципиально недостижимую в классических базах данных. Система управления такой базой данных основана на введенном автором относительном преобразовании диффузии (см. Главу 2). Соотношение между вероятностями несанкционированного получения информации и обнаружения такой попытки устанавливает такая Теорема-
Теорема 2.4. Существует функция a(g,N), такая что Vc > 0 3g : a(gyN) > 1 — е ДГ = 1,2,... со следующим свойством. Для всякого выбора блоков, обозреваемых S и унитарных преобразований, которые S совершает, имеет место неравенство
Pcx > Р<*•
По классическим недетерминистическим алгоритмам, реализуемым на клеточных автоматах.
7. Для самых быстрых недетерминистических клеточных автоматов установлена линейная связь памяти и времени.
Теорема 3.3. Пусть Л есть наибыстрейший не детерминистический клеточный автомат.. Тогда
(3.3) ТА(п) = 0(5д(п)).
8. Построен способ имитации r-мерных недстерминистических клеточных автоматов с временем Т и памятью 5 в г -f 1-мерном пространстве за время 0(Т1~'^Г+1^) или Tr+1 = 0(T]f2 -f S1).
Теорема 3.1.
NC(r, Г, S) Ç NC(r + 1, s/T + S, Vf + S).
Теорема 3.2.
NC(r,T,5)ÇNC(r,T1,T1),
где Ту = TTTïS^î
Разработанные методы
О диссертации исследованы вычисления в моделях с двумя вариантами недетерминистичности: более сильной - классической и более слабой - квантовой. Предложена удобная для теоретических исследований модель квантового компьютера с разделением классической и квантовой частей. Для квантовых вычислений разработан метод получения нижних оценок, основанный на подсчете расстояний между состояниями квантового компьютера как точками в Гильбертовом пространстве состояний. На основе этого метода получены три первых результата о квантовых вычислениях. Введено понятие унитарных квантовых вычислений, и с использованием этого понятия построен квантовый алгоритм с параллельным доступом к оракулу для проверки истинности формул логики предикатов 1 порядка. •
Для классических недетерминистических вычислений предложен метод оптимизации алгоритмов, и на его основе получены два последних результата.
4
Структура диссертации
Глава 1 посвящена вычислениям на квантовых компьютерах с последовательным доступом к оракулу. Здесь определена абстрактная модель квантового компьютера с разделенной классической и квантовой частью, р-ассмотрены вычисления с оракулом и с заданной вероятностью ошибки в такой модели и рассмотрена проблема общего метода квантовомеханического ускорения классических алгоритмов на квантовом компьютере. Для этой проблемы установлено отрицательное решение. Получена сильная форма нижней оценки времени квантового вычисления экстремума целочисленной функции.
В Главе 2 дано понятие унитарного алгоритма, и рассмотрены два приложения »того понятия: уточнение алгоритма Клива, Бурхама и Вигдерс-она о распознавании истинности формул логики предикатов 1 порядка и схема защиты информации в квантовой базе данных.
В Главе 3 рассматриваются вычисления на недетерминистических классических клеточных автоматах. Здесь устанавливается соотношение между временем и памятью для таких вычислений и находится зависимость с ложности от размерности вычислительного пространства.
В Заключении описываются перспективы применения разработанных методов и нерешенные проблемы.
5
Глава 1. Квантовые компьютеры с последовательным доступом к оракулу
1.1. Классические и квантовые вычисления
Представим себе такую ситуацию. Имеется ”черный ящик”, называемый оракулом, с. неизвестным внутренним устройством, обладающий входом и выходом. На вход можно подать произвольную последовательность х из 12 десятичных цифр. На выходе через 1 секунду появляется: 1, если .т совпадает с некоторым неизвестным нам паролем а; о, и 0 в противном случае. Сколько времени уйдет па то, чтобы найти неизвестный пароль с вероятностью р ? Пусть N - число всевозможных значений х, N = 1012. Поскольку об то нам ничего не известно, вероятность его угадать при одном обращении к оракулу будет 1/Л/-, при двух - 2/1У, и т.д. Следовательно, чтобы найти то с вероятностью р, нам понадобится примерно рАг вопросов, что при р = 1/2 займет 1012/2 секунд, или около 15000 лет.
Однако при наличии квантового компьютера в тех же самых условиях неизвестный пароль можно найти за 5 дней! Это следует из полученного Ловом Гровером в 1996 году замечательного результата о том, что квантовый компьютер способен решить задачу перебора за время порядка квадратного корня из классического (этот алгоритм описан в Главе 2 настоящей диссертации). Данный пример обосновывает утверждение некоторых исследователей о том, что практическое создание работоспособного квантового компьютера оказало бы на человеческую цивилизацию воздействие, сравнимое с изобретением атомной бомбы.
Однако у квантового компьютера существуют и принципиальные ограничения по скорости работы, называемые нижними оценками времени работы, некоторые из которых, найденные автором, будут описаны в этой главе. Значение этих результатов о невозможности ”слишком быстрых” квантовых вычислений в том, что это помогает сберечь время исследователей, ряд которых пытался (а некоторые пытаются до сих пор) использовать квантовый компьютер для решения задач, которые ему не по силам: ускорить произвольные классические вычисления, или добиться большего ускорения слишком широкого класса переборных задач. Значение этих оценок также и в том, что они показывают истинную ценность каждого частного результата о квантовом ускорении классических алгоритмов, так как такие частные результаты исчерпывают все, что вообще можно сделать в данной области.
Для нахождения новых квантовых алгоритмов наличие формальной модели квантового компьютера, вообще говоря, не является необходимым, так как алгоритмы всегда описываются содержательно. Нам же для получения нижних оценок (т.е. для доказательства несуществования некоторых алгоритмов) понадобится такая формальная модель. В этой главе описывается предложенная автором модель квантового компьютера с разделенными классической и квантовой частями, одно из достоинств которой состоит в ее независимости от формализма классической теории алгоритмов, при этом все результаты сохраняются и для любой другой схемы квантового компьютера. Поэтому мы начнем в следующей части с неформального введения в классические алгоритмы.
6