Содержание к диссертации
Введение
1 Предварительные сведения. 17
1.1 Основы квантовых вычислений 17
1.2 Классические бинарные программы 22
1.2.1 Один раз читающие бинарные программы 26
1.2.2 Забывающие бинарные программы 27
2 Квантовые бинарные программы. Квантовое и классическое моделирование . 33
2.1 Определения и основные вычислительные свойства 33
2.2 Сложность моделирования 39
2.2.1 Классическое моделирование квантовых бинарных программ 39
2.2.2 Квантовое моделирование классических бинарных программ 47
3 Один раз читающие квантовые бинарные программы. Нижняя оценка сложности . 54
3.1 Нижняя оценка сложности вычисления булевой функции в квантовых бинарных программах 55
3.1.1 Доказательство нижней оценки сложности 56
3.2 Сложность реализации функции MODp в классических и квантовых бинарных программах 63
3.2.1 Сложность реализации функции MODp в детерминированных и вероятностных OBDD 64
3.2.2 Реализации функции MODp в квантовых OBDD. 68
4 Классические и квантовые конечные автоматы 73
4.1 Конечные автоматы 73
4.1.1 Детерминированный конечный автомат 73
4.1.2 Вероятностный конечный автомат 74
4.2 Квантовый конечный автомат 77
4.3 Сравнительная сложность квантовых и вероятностных конечных автоматов 80
4.3.1 Классическое моделирование квантовых автоматов. 80
4.3.2 Квантовое моделирование вероятностного автомата. 83
4.4 Нижняя оценка сложности распознавания языков квантовым конечным автоматом . 87
4.4.1 Доказательство нижней оценки сложности
Литература 94
- Классические бинарные программы
- Классическое моделирование квантовых бинарных программ
- Сложность реализации функции MODp в детерминированных и вероятностных OBDD
- Нижняя оценка сложности распознавания языков квантовым конечным автоматом
Введение к работе
Какие проблемы являются вычислимыми и как эффективно они могут быть вычислены? В основе теории вычислимости лежит Тезис Черча-Тыоринга: все разумные модели вычислений могут быть смоделированы машиной Тьюринга. Для вычислимых проблем встает вопрос о сложности вычисления, а именно, какие физические ресурсы требуются для того, чтобы решить проблему - такие, как память, время, энергия, и т.д. Основными сложностными характеристиками, изучаемыми в теории сложности, являются время вычисления и память, затрачиваемая в процессе вычисления.
ФуЕідаментальньїй вопрос теории сложности - как ведет себя функция сложности, если ее рассматривать как функцию от размера входа - л, и, в частности, является ли она полиномиальной или экспонен-циональной от п. При этом принято считать, что некоторая проблема решается просто, если сложность является полиномиальной от размера входа; и является трудно разрешимой, если функция сложности является экспоненциальной от размера входа.
Не менее актульный вопрос - что значит решить проблему? Решить точно или допустить некоторую вероятность ошибочного результата? Теория вероятностных алгоритмов отменяет требование к результату всегда быть точным и разрешает некоторую вероятность ошибки. Это позволяет получить заметное.уменьшение сложности решения ряда известных проблем. В связи с этим была выдвинута современная версия тезиса Черча: Все разумные модели вычислений могут быть эффек-
Введение
тивно (с полиномиальной сложностью) смоделированы вероятностной машиной Тьюринга.
В 80-х годах было предложено рассматривать вычислительные модели, которые делают возможным использование кваитово-механических эффектов. Впервые эти идеи были высказаны Benioff [33], Feynman [40], и Маниным [16]. Фейнман в 1982 высказал идею, что квантовая физическая система из R частиц не может быть смоделирована на обычном компьютере без эксионенционального замедления в эффективности моделирования. Фейнман также заметил, что этого замедления можно избежать, если использовать вычислительные устройства, работающие, опираясь на законы квантовой физики.
Впоследствии эти идеи были формализованы Deutsh [38], который впервые определил квантовую вычислительную модель, основанную на использовании квантовой суперпозиции - квантовый аналог вероятностной машины Тьюринга. Deusth предположил, что эта модель может быть эффективнее, чем классическая, для некоторых задач. Ои также показал существование универсальной квантовой машины Тьюринга (а также модели квантовых сетей - квантовый аналог классических схем). Однако его модель универсальной квантовой машины Тьюринга имела один недостаток - моделирование других квантовых машин Тьюринга (QMT) могло иметь экспоненциальную сложность. Эта проблема была решена Bernstein и Vazirani (1993) [34]. Они показали существование универсальной QMT, способной моделировать другие QMT в полиномиальное время.
Могут ли квантовые вычисления быть эффективнее классических? Прежде всего, отметим, что квантовые вычислители не могут решать проблемы, не разрешимые на классической машине Тьюринга. Это следует из того, что все вычислимое в квантовой модели может быть смоделировано на классической машине просто вычислением амплитуд суперпозиции и записи их на рабочую ленту. Это моделирование может
Введение
быть эксноненционально по времени, но в конце концов мы сможем решить все, что мы можем решить квантово. Таким образом, различие между классическими и квантовыми вычислениями лежит только в вопросе их сложности. Тривиальное моделирование квантовых вычислений классическим экспоненциально по времени и памяти. Bernstein и Vazirani [34] показали, что моделирование может быть полиномиально но памяти, хотя все еще эксноненционально но времени.
Теорема 0.1 (34І BQP С PSPACE.'
Это включение виоследствне было уточнено: BQP С РР [30]. Соотношение между классами BQP и NP неизвестно.
В 1992 Deutsch, Josza [39] показали, что существует проблема (в настоящий момент неизвестно, лежит ли она в классе Р), которая может быть решена точно, в полиномиальное время на квантовом компьютере.
В 1994 Simon [54] получил важный результат - он предложил квантовый алгоритм решения задачи (состоящей в нахождении периода булевской функции), не имеющей классических эффективных решений даже при использовании вероятностных методов.
Позже Shor [53] предложил квантовый полиномиальный алгоритм разложения числа на простые множители (и вычисления дискретного логарифма) - проблемы, имеющей существенную важность для криптографии. На сегодня это наиболее известный и эффектный из пока еще небольшого числа существующих квантовых алгоритмов. На данный момент не известно классического полиномиального алгоритма решения данной задачи, не известно также, лежит ли данная проблема в классе ВРР и является ли она iVP-иолной. После этого результата, а также нескольких других, таких, как алгоритм Гровера [41] поиска в неупорядоченной базе данных и алгоритма Китаєва [44] нахождения стабилизатора Абелевой группы, возрос интерес математического сообщества к теории квантовых вычислений.
Введение *А
За счет чего квантовые вычисления могут быть мощнее классических?
Прежде всего это так называемый квантовый параллелизм. Размер квантового вычислительного пространства состояний экспоненциален по сравнению с физическим размером системы. Квантовая система может находиться одновременно в суперпозиции экспоненциального числа устойчивых базисных состояний, и параллельно выполнять операции над экпоненциальным количеством аргументов.
Следующее - параллельные вычисления могут создавать интерференцию, за счет чего вычислительные пути, накладываюсь друг на друга, могут как гасить, так и усиливать друг друга.
И наконец, это возможность устраивать скрещенные состояния, которые позволяют удаленным частям системы быть сильно связанными друг с другом.
Данная работа посвящена сравнительному анализу квантовых, детерминированных, вероятностных моделей вычислений, а именно, бинарных программ и конечных автоматов. Диссертация состоит из 4 глав и устроена следующим образом. В главе 1 представлены необходимые определения, понятия и сведения, лежащие в основе теории квантовых вычислений. Главы 2,3 посвящены бинарным программам, глава 4 - конечным автоматам. Основные результаты диссертации представлены в главах 2-4.
В главах 2-4 рассматривается известная модель для вычисления булевых функций - бинарные програмы (ВР). В главе 2 приведены необходимые определения и предварительные сведения, касающиеся соотношений между детерминированными и вероятностными ВР с ограничениями. Основные результаты диссертации, касающиеся бинарных программ, приведены в главах 2,3.
Введение
Вычисления на ВР можно трактовать как вычисления на одиночном процессоре, который на каждом такте работы может считывать не более одного бита входного слова. Введение в модель ВР случайных вершин, в которых, в зависимости от датчика случайных чисел, выбирается тот или иной путь дальнейшего вычисления, приводит к модели вероятностных бинарных программ. Впервые модель вероятностной бинарной программы была определена в работе [26]. Известно, что вероятностные бинарные программы с определенными ограничениями могут быть экспоненциально экономнее соответствующих детерминированных ВР.
В главе 1 рассматриваются дополнительные ограничения бинарных программ, такие, как уровневость и забываемость. Известно, что бинарные программы общего вида могут быть преобразованы в уровневыс забывающие не более чем с полиномиальным увеличением сложности. В работе мы определяем модель'квантовой бинарной программы как обобщение соответствующей вероятностной уровневой забывающей модели. Известная модель перестановочных детерминированных бинарных программ является частным случаем квантовых бинарных программ, где преобразования, применяемые на каждом шаге вычисления - это перестановки. Известно, что класс функций, вычислимых перестановочными бинарными программами ограниченной ширины совпадает с классом NC1 функций, вычислимых схемами из функциональных элементов логарифмической глубины [8].
Наканиши, Хамагучи и Кашивабара в работе [50] определили несколько иную модель квантовой бинарной программы. В отличиеот модели, определяемой в работе, язык описания этой бинарной программы графовый. Квантовая бинарная программа [50] не обязательно уровневая и забывающая. Иначе определяются понятия ширины и конфигурации квантовой бинарной программы. Под конфигурацией в модели |50] понимается суперпозиция множества всех вершин бинарной программы. В нашей модели конфигурация - это суперпозиция множества вершин
Введение
на уровне. С этой точки зрения приемущсством квантовой бинарной программы, описанной в работе, является то, что в данной модели задействовано гораздо меньше кубитов, чем в модели [50], что может оказаться важным для практической реализации. Напомним, что число кубитов равно логарифму от числа устойчивых состояний квантовой системы.
Основными результатами диссертации.в области бинарных программ являются следующие.
Доказываются соотношения классов сложности РР-ВР, PrQP-
-BF, BQP-BP, определенных для модели бинарных программ. При
этом используется техника моделирования:
Моделирование классического вероятностного процесса вычисления квантовым использует известный прием моделирования вероятности 1/2 при помощи квантовой частицы. Имея вероятностную бинарную программу, вычисляющую функцию / на наборе о с вероятностью правильного результата а^, мы строим квантовую бинарную программу, использующую измерения на каждом шаге вычисления, которая вычисляет функцию / на наборе а с той же вероятностью а& (метод "квантового моделирования "вероятностной бинарной программы - Теорема 2.3).
Для моделирования квантового процесса вычисления классическим вероятностным (Теорема 2.2) используется разработанный нами метод "линейного моделирования", который частично является обобщением метода моделирования линейных конечных автоматов вероятностными.
Мы доказываем нижнюю оценку сложности один раз читающей
квантовой бинарной программы, вычисляющей произвольную бу
леву функцию / с ограниченной ошибкой (Теорема 3.1). Полу-
Введение
ченная нижняя оценка формулируется в терминах сложности минимальной один раз читающей детерминированной бинарной программы, вычисляющей ту же функцию /.
На примере известной симметрической функции MODp мы доказываем, что один раз читающая квантовая ВР может быть экспоненциально экономнее один раз читающей как детерминированной, так и вероятностной В Р. Для данной функции доказываются нижние оценки сложности детерминированной ВР и вероятностной ВР, дающей правильный результат с большой вероятностью. Строится квантовая ВР, вычисляющая MODp с ограниченной ошибкой.
Классические бинарные программы
За счет чего квантовые вычисления могут быть мощнее классических? Прежде всего это так называемый квантовый параллелизм. Размер квантового вычислительного пространства состояний экспоненциален по сравнению с физическим размером системы. Квантовая система может находиться одновременно в суперпозиции экспоненциального числа устойчивых базисных состояний, и параллельно выполнять операции над экпоненциальным количеством аргументов.
Следующее - параллельные вычисления могут создавать интерференцию, за счет чего вычислительные пути, накладываюсь друг на друга, могут как гасить, так и усиливать друг друга.
И наконец, это возможность устраивать скрещенные состояния, которые позволяют удаленным частям системы быть сильно связанными друг с другом.
Данная работа посвящена сравнительному анализу квантовых, детерминированных, вероятностных моделей вычислений, а именно, бинарных программ и конечных автоматов. Диссертация состоит из 4 глав и устроена следующим образом. В главе 1 представлены необходимые определения, понятия и сведения, лежащие в основе теории квантовых вычислений. Главы 2,3 посвящены бинарным программам, глава 4 - конечным автоматам. Основные результаты диссертации представлены в главах 2-4.
В главах 2-4 рассматривается известная модель для вычисления булевых функций - бинарные програмы (ВР). В главе 2 приведены необходимые определения и предварительные сведения, касающиеся соотношений между детерминированными и вероятностными ВР с ограничениями. Основные результаты диссертации, касающиеся бинарных программ, приведены в главах 2,3.
Вычисления на ВР можно трактовать как вычисления на одиночном процессоре, который на каждом такте работы может считывать не более одного бита входного слова. Введение в модель ВР случайных вершин, в которых, в зависимости от датчика случайных чисел, выбирается тот или иной путь дальнейшего вычисления, приводит к модели вероятностных бинарных программ. Впервые модель вероятностной бинарной программы была определена в работе [26]. Известно, что вероятностные бинарные программы с определенными ограничениями могут быть экспоненциально экономнее соответствующих детерминированных ВР.
В главе 1 рассматриваются дополнительные ограничения бинарных программ, такие, как уровневость и забываемость. Известно, что бинарные программы общего вида могут быть преобразованы в уровневыс забывающие не более чем с полиномиальным увеличением сложности. В работе мы определяем модель квантовой бинарной программы как обобщение соответствующей вероятностной уровневой забывающей модели. Известная модель перестановочных детерминированных бинарных программ является частным случаем квантовых бинарных программ, где преобразования, применяемые на каждом шаге вычисления - это перестановки. Известно, что класс функций, вычислимых перестановочными бинарными программами ограниченной ширины совпадает с классом NC1 функций, вычислимых схемами из функциональных элементов логарифмической глубины [8].
Наканиши, Хамагучи и Кашивабара в работе [50] определили несколько иную модель квантовой бинарной программы. В отличиеот модели, определяемой в работе, язык описания этой бинарной программы графовый. Квантовая бинарная программа [50] не обязательно уровневая и забывающая. Иначе определяются понятия ширины и конфигурации квантовой бинарной программы. Под конфигурацией в модели 50] понимается суперпозиция множества всех вершин бинарной программы. В нашей модели конфигурация - это суперпозиция множества вершин на уровне. С этой точки зрения приемущсством квантовой бинарной программы, описанной в работе, является то, что в данной модели задействовано гораздо меньше кубитов, чем в модели [50], что может оказаться важным для практической реализации. Напомним, что число кубитов равно логарифму от числа устойчивых состояний квантовой системы.
Основными результатами диссертации.в области бинарных программ являются следующие. Доказываются соотношения классов сложности РР-ВР, PrQP -BF, BQP-BP, определенных для модели бинарных программ. При этом используется техника моделирования: — Моделирование классического вероятностного процесса вычисления квантовым использует известный прием моделирования вероятности 1/2 при помощи квантовой частицы. Имея вероятностную бинарную программу, вычисляющую функцию / на наборе о с вероятностью правильного результата а , мы строим квантовую бинарную программу, использующую измерения на каждом шаге вычисления, которая вычисляет функцию / на наборе а с той же вероятностью а& (метод "квантового моделирования "вероятностной бинарной программы - Теорема 2.3). — Для моделирования квантового процесса вычисления классическим вероятностным (Теорема 2.2) используется разработанный нами метод "линейного моделирования", который частично является обобщением метода моделирования линейных конечных автоматов вероятностными. Мы доказываем нижнюю оценку сложности один раз читающей квантовой бинарной программы, вычисляющей произвольную бу леву функцию / с ограниченной ошибкой (Теорема 3.1). Полученная нижняя оценка формулируется в терминах сложности минимальной один раз читающей детерминированной бинарной программы, вычисляющей ту же функцию /. На примере известной симметрической функции MODp мы доказываем, что один раз читающая квантовая ВР может быть экспоненциально экономнее один раз читающей как детерминированной, так и вероятностной В Р. Для данной функции доказываются нижние оценки сложности детерминированной ВР и вероятностной ВР, дающей правильный результат с большой вероятностью. Строится квантовая ВР, вычисляющая MODp с ограниченной ошибкой.
Классическое моделирование квантовых бинарных программ
Сложность реализации вычисления функций. Мы будем исследовать две сложиостиые характеристики квантовых бинарных программ - ширину и глубину QBP.
Шириной Width(P) квантовой бинарной программы Р называется размерность d пространства 7id конфигураций. Глубиной Depth(P) квантовой бинарной программы Р называется длина I последовательности Т квантовых преобразований. Глубина квантовой ВР оценивает время вычисления. Ширина квантовой ВР оценивает память - а именно, число кубитов, задействованных в процессе вычисления. Наиомтш, что число кубитов равно логарифму от числа устойчивых состояний квантовой системы. Для произвольной функции / обозначим: QBPWl/2(f) {QBPWl/2+e(f), QBPWexact(f)) - минимальную ширину бинарной программы, с неограниченной ошибкой (с ограниченной ошибкой, точно) вычисляющей функцию /. QBPD1/2{f) {QBPDl/2+{f), QBPDexact{f)) - минимальную глубину бинарной программы, с неограниченной ошибкой (с ограниченной ошибкой, точно) вычисляющей функцию /. Далее мы исследуем основные вычислительные свойства квантовых бинарных программ. Следующая Лемма показывает, что определенная нами модель квантовой бинарной программы способна вычислять произвольную булеву функцию. Бинарные программы. Квантовое и классическое моделирование 3G Лемма 2.1 Для произвольной булевой функции f существует (2п,п)-QBP, которая точно вычисляет J. Доказательство: Рассмотрим (2", n)-QBP Р, определенную следующим образом. Все возможные конфигурации Р содержат ровно одну единицу, остальные элементы равны пулю. Начальная конфигурация (0)} = (1,0,..., 0)Т, Р считывает переменные в порядке xi, Х2,..., хп. Последовательность квантовых преобразований определена следующим образом. На г -ом шаге, і = 1,..., тг, Р считывает пременную Xj = &І и преобразовывает текущую конфигурацию \ф) следующим образом. Если СІ = 0, \ф) не изменяется; если crt- — 1, то происходит циклический сдвиг } на 2""1 разрядов вправо. Преобразования, определенные таким образом - это перестановки - взаимнооднозначные преобразования, являющиеся частным случаем унитарных преобразований. Для входной последовательности a = o"i,... , тп обозначим через 1а номер позиции единицы в финальной конфигурации \фо). Ясно, что h h тогда и только тогда, когда а — а . Множество принимающих состоянии F определим следующим образом: если /(a) = 1, то Іа є F, если f(a) = 0, то la F. Подространство принимающих состояний Еасс образовано ортонормированными векторами г) : г" є F. О Квантовые бинарные программы ограниченной ширины Известная модель перестановочных бинарных программ является частным случаем модели QBP. Напомним, что перестановочная ВР - это уровневая забывающая детерминированная ВР, в которой преобразования, применяемые на каждом уровне - это перестановки. Перестановочная матрица - это унитарная матрица. Обозначим EQP-BPcon$t класс функций, иредставимых точно (с нулевой ошибкой) квантовыми ВР константной ширины полиномиальной Бинарные программы. Квантовое и классическое моделирование сложности. NC1 - класс функций, представимых схемами из функциональных элементов логарифмической глубины. Утверждение 2.1 NC1 С EQP-BP t. Доказательство: Доказательство непосредственно следует из результата Баррингтоиа 8], показавшего, что перестановочные бинарные программы ограниченной ширины (а именно, ширины 5) полиномиальной сложности в точности совпадают с классом NC1. Перестановочная детерминированная ВР ширины 5 полиномиальной сложности, которая вычисляет функцию / - частный случай (const, poly)-QBP} точно вычисляющей /. Более сильный результат представлен в работе [29J, где показано, что квантовые ВР ширины 2 полиномиальной сложности способны вычислять любую функцию из NC1. Будем называть QBP Р веществен позначной QBP, если ее конфигурации и матрицы преобразований содержат только вещественные значения. В противном случае QBP Р будем называть комилекснозначной QBP. Следующая Лемма показывает, что мы можем перейти только к вещественным амплитудам и при этом сложность увеличится вдвое. Утверждение 2.2 Если функция f вычислима комплекснозпачиой (d, I)-QBP Р, то она вычислима веществепиозпачной (2d, l)-QBP Р , и при этом выполняется:
Сложность реализации функции MODp в детерминированных и вероятностных OBDD
Следующая Лемма показывает, что для любой РВР, вычисляющей функцию / с точкой сечения А. можно построить РВР, вычисляющую ту же функцию / с точкой сечения А А.
Лемма 2.5 Пусть (с/, 1)-РВР Р вычисляет функцию f с точкой сечения А Є [0,1). Тогда для любого Xі Є (А. 1) существует (d + 1,1)-РВР Р\ которая вычисляет j с точкой сечиния X . Доказательство: Пусть ( L 1)-РВР Р (/х(0) , Г, (г), где Т {{ij, /Д0), C/j(l))}j-=1. Определим вероятностную бинарную программу Р следующим образом. (d+i,D-PBP р - ([//(о)).г, (г ). здесь ио)) = (/?,(І-/?)/І(О))Т, где/ї мы определим позднее. Решающий вектор (г = (1,г). Последовательность преобразований V — {( j-f/j (0),t/j(l))}J=1. Матрицы /j( r) (j — 1,.. -, I, и Є {(), 1}) переходных вероятностей - это стохастические по столбцам матрицы Пусть вероятность принятия входного слова а программой Р Рг (сг) — А. Тогда бинарная программа Р принимает т с вероятностью Pr , (r t//(o-I()Ui( 7it)\fi ({))) = 5 + (1- 3)Х. ІЬ л того, чтобы выполнялось РГасс Х- достаточно юить 0 1-(1- А }/(1 — А). При этом ширина построенной РВР Width(P ) = d+[.D Таким образом, имея квантовую ґл і парную программу Р, в соответствии с четырьмя этапами, описанными выше, строим вероятностную бинарную программу. При этом вероятность принятия входного слова a изменяется только на этапах 3, 4 (Леммы 2,4, 2.5). Учитывая изменения ширины бинарной программы на этапах 1-4, имеем, ширина построенной вероятностной бинарной программы Width(P ) = AWidth{P)2 + 3.Замечание 2.2 Из Теоремы 2.2 классического моделирования квантовых бинарных программ следует, что если мы имеем квантовую ВР Р, вычисляющую функцию / с е-изолированной точкой сечения 1/2, мы можем построить вероятностную ВР Q, вычисляющую ту же функцию / с точкой сечения 1/2. При этом глубина ВР не изменится, ширина Width(Q) = 4Width2(P) -f 3. То есть сложность возрастет полиномиально. Однако в качестве платы за это мы имеем следующее: мы теряем -изолированность точки сечения (что следует из Леммы 2.4). То есть в построенной ВР вероятность ошибки может быть сколь угодно близкой к 1/2, тогда как в исходной ВР вероятность ошибки была мала. Таким образом, используя Теорему 2.2, мы имеем следующие соотношения классов сложности: Для доказательства включения РР С PrQP введем понятие много раз измеряющей квантовой бинарной программы MM-QBP (measured-many QBP). Отличие этой модели от рассматриваемой нами всюду до этого одии-раз измеряющей квантовой бинарной программы (МО-QBP) состоит в следующем. Для входного набора а {0,1}" один раз измеряющая {d, l)-MO-QBP Р начинает вычисление из начальной конфигурации ) (0)). На шаге і (і = 1,...,/) Р считывает значение переменной Xjt — ajt и преобразует текущую конфигурацию \ф) в конфигурацию \ф ) = Ufaії)\ф). После последнего 1-го шага Р производит финальное измерение результирующей конфигурации. То есть измерение производится один раз по окончании вычисления. В MM-QBP после каждого вычислительного шага і (і = 1,...,/) производится измерение текущей конфигурации, и выбор дальнейшего преобразования зависит от исхода измерения. Много раз измеряемая квантовая бинарная программа ширины d и длины / {{d,l)-M M-QBP) определяется как где IV (O)) = 1) - начальная конфигурация, Я - последовательность (длины /) d-мсрных квантовых преобразований квантовой системы QS с d устойчивыми состояниями, определенная следующим образом где //(0) и //(1), і = 1,...,1, j = 1,...,d- унитарные d х (/-матрицы, F С {1,..., d} - множество принимающих состояний. Определим вычисление Р на входном наборе а = о\.. .ап Є {0,1}" следующим образом: На каждом шаге работы состояние программы Р описывается вектором р = (pi,... ,ра) распределения вероятностей конфигураций, где pi - вероятность нахождения Р в конфигурации г). Вектор начального распределения конфигураций р(0) = (1,0..., 0) (так как начальная конфигурация программы 0(О)) — 1)). Бинарные программы. Квантовое и классическое моделирование Каждый шаг работы программы Р состоит из унитарного преобразования текущей конфигурации (зависящее от считываемого символа и базисного состояния, являющегося исходом измерения на предыдущем шаге) и измерения. Пусть (г) - конфигурации Р на текущем шаге. Тогда следующий (?-Ь1И 3 = 1)---)0 шаг работы программы Р состоит в следующем: 1. Р считывает очередной символ а входного слова а Є п, определяемый последовательностью R преобразований программы Р. 2. Преобразует текущую конфигурацию \і) в конфигурацию 1) = 3. Измеряет конфигурацию \фг) = {z{,... ,zd). Результат измерения — вероятностный. Как исход измерения состояние к Є {1,..., d} выпадает с вероятностью q\ \zlk\2. 4. Сразу после измерения \фг) преобразуется в конфигурацию ]г ), где і - состояние, выпавшее в результате измерения.
Нижняя оценка сложности распознавания языков квантовым конечным автоматом
Доказательство: Предположим, что существует стабильная забывающая вероятностная бинарная программа Р ширины q р, вычисляющая MODp с вероятностью 1/2 + е для фиксированого є Є (0,1/2]. Без ограничения общности предполагаем, что каждый уровень Р содержит ровно q вершин. В противном случае мы можем достроить бинарную программу так, чтобы это условие выполнялось.
Каждому уровню j программы Р соответствует вектор распределения вероятностей {ij = (/ ,..., fj,3q), где fij - это вероятность нахождения в і-ой вершине jr -ro уровня. Мы можем описать процесс вычисления функции / программой Р для входа х = о\у..., ап следующим образом: Вычисление начинается с начального вектора распределения вероятностей ft0. На J -OM шаге, 1 j п, Р считывает входной символ С{. и преобразует вектор распределения вероятностей р? х в /JJ = р? хА где А - q X q стохастическая матрица, А = А{0) если а 0, и А = /1(1) если (7ij = 1. После последнего п-го шага вычисления Р принимает вход а с вершин, помеченных 1. Если /(а) = 1, тогда Расс( ?) 1/2 4-е, иначе Расс{&) 1/2 — Є. Нижняя оценка сложности бинарных программ 66 Без ограничения общности полагаем, что Р считывает переменные в естественном порядке #1, УХП В противном случае мы можем просто переупорядочить входной иабор. Через Е" обозначим всевозможные п входных наборов сгп,...,сгі, в которых сначала идут все нули, а затем все единицы. Для і Є {1,...,п} &І = &ial, гДе &ї Q_u -9 п—і о} = j_- Д- Будем подавать на вход Р только входные наборы из En. Пусть /І1 - вектор распределения вероятностей после считывания of. To есть, // = /іЛ(0) -- Л(0) = /A4"-l(0). Часть а} содержит только единицы, следовательно вычисление после считывания о может быть описано цепью Маркова. В этом случае р? - это начальное распределение вероятностей, Л{1) - матрица переходных вероятностей. Состояния Марковской цени разделяются на эргодическис и невозвратные (см., например, [13). Эргодическое множество состояний - это множество, которое процесс никогда не сможет покинуть, если в него однажды попадет. Невозвратное множество это множество, в которое процесс не может вернуться, если его покидает. Эргодическое состояние - это элемент эргодического множества. Невозвратное состояние - это элемент невозвратного множества.
Любая цепь Маркова обязательно содержит хотя бы одно эргодическое множество. Наличие невозвратных множеств необязательно. Если цепь Маркова содержит более чем одно эргодическое множество, то между этими множествами нет абсолютно Еіикакого взаимодействия. Следовательно, мы имеем две или более изолированные цени Маркова, обьединенные вместе, которые мы можем изучать по отдельности. Если цепь Маркова состоит из единственного эргодического множества, она называется эргодической цепью. Каждая эргодическая цепь либо регулярна, либо циклична.
Если эргодическая цепь регулярна, то достаточно высокая степень матрицы переходных вероятностей содержит только положительные
Нижняя оценка сложности бинарных программ 67 элементы. Это значит, что из какого бы состояния процесс пи начался, но прошествии достаточно большого числа шагов он может оказаться в любом состоянии. Кроме того, существует предельный вектор вероятностей, не зависящий от выбора вектора начального распределения вероятностей (см., например, Теорему 4.1.6. [13]).
Если цепь Маркова цикличиа, то она имеет период t и все ее состояния разбиваются на і циклических множеств ( 1). При выбранном начальном состоянии процесс движется по циклическим множествам в определенном порядке, возвращаясь в множество, содержащее начальное состояние, через каждые t шагов. По прошествии достаточного времени процесс может находиться в любом состоянии циклического множества, соответствующего данному моменту. Следовательно, для каждого из циклических множеств -ая степень матрицы переходных вероятностей описывает регулярную цепь Маркова. К тому же, если эргодическая цепь цикличиа с периодом t, она имеет не менее t состояний.
Мы предположили, что число состояний q р. То есть, для каждой циклической цепи число t р. Через D обозначим наименьшее общее кратное всех таких t. Т.к. р простое и t pt t относительно просто с р. Следовательно, D относительно просто с р} и любая положительная степень Dm также относительно просто с р.
Пусть or - распределение вероятностей после считывания части д\ слова о . Без ограничения общности мы можем считать, что у нас одно принимающее состояние. Пусть „, - вероятность нахождения в принимающем состоянии после считывания а\. Так как после каждых D шагов процесс может быть в любом состоянии множества, содержащего принимающее состояние, -ая степень матрицы А(1) описывает регулярную Марковскую цепь для этого множества.
Похожие диссертации на Сравнительная сложность квантовых и классических моделей вычислений
