Сравнительная сложность квантовых и классических моделей вычислений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Гайнутдинова Аида Фаритовна

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

Специальность: 01.01 09 — дискретная математика и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2004

Работа выполнена в Научно-Исследовательском Институте Математики и Механики имени Н.Г.Чеботарева при Казанском государственном университете

Научный руководитель: доктор физико-математических наук,

профессор, зав. кафедрой теоретической кибернетики фак. ВМК КГУ Фарид Мансурович Аблаев.

Официальные оппоненты:

доктор физико-математических наук, профессор, зав. кафедрой математической кибернетики фак. ВМиК МГУ Валерий Борисович Алексеев;

кандидат физико-математических наук,

с.н.с. ВЦ РАН

Михаил Николаевич Вялый.

Ведущая организация:

Физико-Технологический Институт РАН

Защита диссертации состоится & 2004 г.

в на заседании диссертационного совета Д002.017 02

Вычислительного центра им. А.А.Дороницына РАН по адресу: 119991, Москва, ГСП-1, ул.Вавилова, дом 40.

С диссертацией можно ознакомиться в библиотеке ВЦ РАН. Автореферат разослан ^ ^Сср/ъ ¿Ъ- 2004 г.

Ученый секретарь диссертационного совета Д002.017.02 д.ф.-м.н.

Рязанов В.В.

SU4

21ST 3MY

Актуальность темы исследования Современная теория квантовых вычислений берет свое начало с 80-х годов 20-го века В 1980 году Ю.И Манин и в 1982 году Р. Фейнман высказали идею, что, поскольку моделирование квантовых процессов на классических компьютерах является сложной задачей, возможно, использование квантовых эффектов может быть полезным для решения классических задач. В 90-х годах Дойч определил квантовую модель машины Тьюринга. Было доказано, что полиномиальную по времени квантовую машину Тьюринга можно промоделировать на классической машине Тьюринга с полиномиальной памятью Также доказано существование универсальной квантовой машины Тьюринга По аналогии с известными классическими классами сложности были определены и исследованы квантовые классы сложности: класс BQP (аналог класса ВРР), содержащий задачи, решаемые полиномиальными по времени квантовыми алгоритмами с большой вероятностью правильного результата (будем называть такие вычисления вычислениями с ограниченной ошибкой - bounded-error) и класс PrQP (аналог класса РР), содержащий задачи, решаемые полиномиальными по времени квантовыми алгоритмами с небольшой вероятностью правильного результата (будем называть такие вычисления вычислениями с неограниченной ошибкой - unbounded-error).

Интерес к области квантовых вычислений в немалой степени связан с тем, что в 90-х годах были построены эффективные квантовые алгоритмы для некоторых задач, для которых эффективных классических алгоритмов неизвестно. В частности, это полиномиальный квантовый алгоритм Шора для факторизации чисел. Отметим, что задача факторизациии чисел лежит в основе RSA систем шифрования. Другой известный квантовый алгоритм - это алгоритм Гровера поиска в неупорядоченной базе данных.

Важным является вопрос о месте вычислительных моделей, основанных на использовании квантовых принципов, среди других моделей - детерминированных, недетерминированных, вероятностных. Теоретически и практически важными являются исследования моделей вычислений с ограниченными ресурсами. В последние годы были определены квантовые аналоги различных вычислительные моделей: конечных автоматов, схем из функциональных элементов, бинарных программ (контактных схем), получен ряд результатов по сравнительной сложности квантовых и классических (детерминированных, вероятностных) моделей вычислений с различными ограничениями.

рос. и 6, , С -! TOOgPR

-4-__

'"\ЛЬНЛЯ ■ • КА V^ypr

Бинарные (ветвящиеся) программы (BP - Branching Program)- известная модель для вычисления булевых функций. Интерес к этой модели, в частности, обусловлен тем, что логарифм сложности BP соответствует объему памяти машины Тьюринга, а максимальная длина вычислительного пути BP - времени вычисления В 90-х годах были введены и начали активно изучаться вероятностные модели BP. Известно, что вероятностные BP с различными ограничениями могут быть экспоненциально экономнее соответствующих детерминированных BP.

В последние годы были определены различные модели квантовых BP В частности, квантовая BP, описанная с работе Наканиши, Хамагучи, Ка-шивабара, определена как обобщение вероятностной BP. Для этой модели приведен пример функции, которая может быть вычислена квантовой BP константной ширины, но не может быть вычислена вероятностной BP константной ширины Модель квантовой бинарной программы, которая вводится в диссертации, отлична от модели Наканиши, Хамагучи, Кашивабара

Исследования конечных вероятностных автоматов ведутся с 60-х годов 20-го века Известно, что вероятностные автоматы с ограниченной ошибкой распознают только регулярные языки (Теорема Рабина). В 90-х годах была определена модель квантового конечного автомата В литературе исследуются две разновидности одностороннего квантового конечного автомата -много раз измеряющий односторонний QFA (MM-QFA) и один раз измеряющий односторонний QFA (MO-QFA) Различие в этих моделях состоит в том. что MM-QFA производит измерения после каждого шага вычисления, в то время как MO-QFA производит измерение только один раз по окончании вычисления. На сегодняшний день известно, что односторонние квантовые автоматы с ограниченной ошибкой способны распознавать лишь собственное подмножество регулярных языков. Известны примеры языков, для которых квантовые автоматы экономнее как детерминированных, так и вероятностных.

Цель работы. Исследование сравнительной сложности квантовых и классических (детерминированных, вероятностных) моделей вычислений с ограничениями - бинарных программ и конечных автоматов.

Методы исследований. В работе используются методы линейной алгебры, теории метрических пространств, дискретной математики, комбинаторные методы, методы теории вероятностей и теории сложности.

Научная новизна Все основные результаты диссертации являются новыми и касаются сравнительной сложности детерминированных, вероятностных и квантовых бинарных программ и конечных автоматов.

Основными результатами диссертации в области квантовых бинарных программ являются следующие Определяется модель квантовой бинарной программы Данное определение является новым. В отличие от модели из работы Наканиши, Чамагучи, Кашивабара, определенная в диссертации модель всегда является уровневой и забывающей. Преимуществом определенной в диссертации модели является то, что в ней задействовано гораздо меньше кубитов, что может оказаться важным для практической реализации. Для введенной модели квантовых бинарных программ доказываются следующие результаты:

1. Разработан метод "линейного моделирования "квантовой ВР классической вероятностной ВР и метод "квантового моделирования"классической вероятностной ВР. На основе методов "линейного моделирования "и "квантового моделирования "доказаны следующие соотношения классов сложности, определяемых для модели бинарных программ:

• РгОР-ВР = РР-ВР,

• ВЯР-ВР С РР-ВР,

• врр-вр с вяр-вр,

где РгС}Р-ВР, ВЯР-ВР {РР-ВР, ВРР-ВР) - классы функций, вычислимых с неограниченной и ограниченной ошибкой, соответственно, квантовыми (вероятностными) бинарными программами полиномиальной сложности

2. Доказана нижняя оценка сложности представления произвольной булевой функции в один раз читающих квантовых ВР. Из доказанной нижней оценки следует, что при реализации произвольной булевой функции /п в квантовой бинарной программе мы можем достичь экономии сложности не более чем в О(1о§п) раз по сравнению с минимальной сложностью детерминированной ВР, представляющей /п. На примере известной симметрической функции МОпоказывается, что полученная нижняя оценка точна Сравнительная сложность представления МОИр в вероятностных и квантовых ВР изучается подробно: доказывается нижняя оценка сложности вероятностной стабильной ВР, вычисляющей МОИр с ограниченной ошибкой Строится квантовая ВР, вычисляющая МОИр с большой вероятностью.

Основными результатами диссертации в области квантовых конечных автоматов являются следующие:

1. Доказана оценка сложности вероятностного моделирования квантовых конечных автоматов.

2. Предложен метод "квантового моделирования "вероятностных конечных автоматов, который является развитием разработанного нами метода "квантового моделирования "вероятностных бинарных программ. На основе метода "квантового моделирования"доказана оценка сложности квантового моделирования вероятностных конечных автоматов

3. Доказана нижняя оценка сложности квантового конечного автомата, распознающего произвольный язык с ограниченной ошибкой Пример языка из работы А. Амбайниса, Р Фрейвалда демонстрирует, что доказанная нижняя оценка является почти точной

Практическая и теоретическая ценность. Диссертация носит теоретический характер. Полученные результаты и разработанные методы могут найти применение в теории сложности квантовых алгоритмов и моделей вычислений.

Апробация работы

Основные результаты диссертации докладывались на 25 Международной конференции FCT'2000 (Братислава, Словения), международной конференции "Optimal Discrete Structures and Algorithms"(Росток, Германия, 2000 г.), IV Международной конференции "Дискретные модели в теории управляющих систем"(мехмат, МГУ, 2000 г.), 13 Международной конференции FCT'2001 (Рига, Латвия), XIII, XIV Международных школах-семинарах по теоретической и математической физике (Казань, 2001 г., 2002 г., 2003г), VII Международном семинаре "Дискретная математика и ее приложения "(мехмат, МГУ, 2001 г), XIII Международной конференции "Проблемы теоретической кибернетики" (Казань, 2002 г.), на семинарах мехмата Московского госуниверситета (руководитель - академик РАН, д.ф.-м.н., профессор Лупанов ОБ.) , на семинарах математического института им. В А. Стеклова (руководитель - член кор. РАН, профессор Разборов А.А.), на семинарах физико-технологического института РАН (руководитель - академик РАН, профессор Валиев К.А.), на семинаре Латвийского госуниверситета (руководитель

академик Латвийской АН, д.ф -м н., проф Фрейвалд Р.В ), на июговых научных конференциях Казанского госуниверситета, на семинарах по квантовым вычислениям Казанского госуниверситета (руководитель - д ф -м н , проф Аблаев Ф.М.).

Публикации По теме диссертации опубликовано 12 работ Список работ опубликованных по теме диссертации, приводится в конце автореферата

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы. Объем работы 101 страница

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Основные обозначения, некоторые определения, понятия и сведения приведены в начале диссертации.

Во введении кратко приводятся основные результаты, полученные в области квантовых вычислений Описана структура диссертации и перечислены основные результаты.

В первой главе приведены основные понятия, используемые в диссертации. Дадим необходимые определения

Н* - ¿-мерное гильбертово пространство с нормой ||.|| = ||.||2. Для 2 €

г = {2х—, г<г}, ||г|| — |г,|2. Элемент ф пространства Нл бу-

дем обозначать \ф) (кет-вектор. или вектор-столбец в обозначениях Дирака). Для вектора \ф) = (г\,..., га) е На через (ф\ (бра^всктор) обозначается вектор-строка, такая что (ф\ = (г^,. ., (г* - число, комплексно сопряженное к числу г) При этом выполняется следующее. Если \ф) = 17\ф), то (ф\ = (ф\и\ где - оператор, сопряженный к оператору и.

Пусть QS квантовая система с й устойчивыми состояниями {1,..., й} Чистое квантовое состояние \ф) квантовой системы С^Б - это вектор в

пространстве На в базисе {|1)____, |я!)} (|г), г = 1____ й - базисное состояние

вектор со значением 1 в г-ой позиции и значением 0 во всех остальных) То есть

<г

И =

или коротко \ф) = ...,

Далее |ф) называется конфигурацией. Элемент г, называется амплитудой базисного состояния |г) С^ При измерении квантовой системы С^ |2,|2 дает вероятность обнаружения С^Б в состоянии \г)

Эволюция квантовой системы задается унитарным оператором и описывается следующим образом. Если |ф) ~ конфигурация системы ОБ на текущем шаге, то на следующем шаге конфигурация ОБ будет |ф'). где

\ф') = U\ф) и U - dx d - унитарная матрица

Извлечение информации о QS из конфигурации | ф) называется измерением, задается оператором проекции и определяется следующим образом Пусть 4d = Wi © ■ • • ® W*. Измерение О = {Wi,..., Wk} относительно {Wi,..., W/t} состоит в следующем.

1 Выбирается одно из подпространств {W\,.... Wjt}. Вероятность выбора подпространства W, равна \\Pw,(|^))||2, гДе Pw, ~ оператор проекции на подпространство W,.

2 После выбора подпространства состояние \$wt) = ^VG^)) нормализуется То есть конфигурация |ф') после измерения становится \ф') = Pw,^))/\\Рщ{\"Ф))\\' Вся информация, не принадлежащая теряется

3. Исходом измерения О является значение /х(О) = г (г € {1,... fc}) -информация о том, какое из подпространств W\,..., W^ было выбрано в результате измерения.

Если измерение производится на некотором этапе вычисления, то будем называть такое измерение промежуточным измерением. В этом случае дальнейший процесс вычисления зависит от результата этого промежуточного измерения. Когда измерение производится по окончании вычисления, будем называть его финальным измерением. В этом случае вектор конфигурации проецируется на одно двух подпространств Еасс. Erej Еасс Ф Erej = fid, Еасс -L Егеу Будем называть Еасс (Erej) подпространством принимающих (отвергающих) состояний. Оператор проекции на подпространство Еасс будем задавать при помощи матрицы проекции Масс Для конфигурации |ф) вероятность выбора подпространства принимающих состояний росс = ||Macc|V)||2.

Также в первой главе даются определения детерминированной и вероятностной бинарной программы, вводятся сложностные характеристики, приводятся сложностные соотношения данной модели с другими моделями вычислений - машинами Тьюринга, схемами из функциональных элементов, формулами. Дадим определения.

Детерминированная бинарная программа (BP - Branching Program) над множеством переменных X = {хь..., хп} - это ориентированный ациклический граф с конечными вершинами, помеченными 0 и 1 Каждая внутренняя вершина помечена булевской переменной х € X, и имеет два исходящих ребра, помеченных 0 и 1, соответственно. BP представляет булеву функцию / : {0.1}" —> {0,1} следующим образом Вычисление значения /(сг) для

входного набора д € {0,1}п стартует из выделенной начальной вершины Для каждой внутренней вершины, помеченной переменной х3, осуществляется переход из этой вершины либо по 0-рсбру, либо по 1-ребру, в соответствии со значением ег;, которое принимает переменная х3 во входном наборе. Значение функции / для входа а это значение достигнутой конечной вершины.

Вероятностная бинарная программа (РВР - Probabilistic Branching Program ) - это бинарная программа, в которой, в дополнении к обычным внутренним вершинам, в которых тестируется булева переменная, присутствуют вероятностные вершины, не помеченные никакой переменной. Каждая такая вероятностная вершина имеет два исходящих ребра, по каждому из которых переход осуществляется с вероятностью 1/2. Очевидным образом для каждого входного набора а £ {0,1}" каждой вершине вероятностной бинарной программы Р можно сопоставить вероятность попадания в эту вершину из начальной вершины. Для входного набора а вероятность Рг^а) принятия РВР Р входа а - это вероятность того, что на входе а вычисление приведет в конечную вершину, помеченную 1

РВР Р вычисляет функцию / с ограниченной ошибкой, если существует е G (0,1/2] такое, что для любого д € /-1(1) Pr^ff) > l/2+e, и для любого <т' € /-1(0) РГасс(а>) ^ 1/2-е При этом говорят, что Р (1/2 + е)-вычисляет функцию /.

ВРВ Р вычисляет функцию / с неограниченной ошибкой, если для любого а е /_1(1) РГасс(о-) > 1/2. и для любого о' 6 /^(О) РгЦр') < 1/2.

Сложность Size{P) бинарной программы Р - это количество ее внутренних вершин. Глубина Depth(P) бинарной программы Р - это длина ее самого длинного пути из начальной вершины в конечную

Определяются классы Р-ВР, ВРР-ВР, РР-ВР - аналоги известных классических классов сложности Р ВРР, РР, соответственно, определенных для модели бинарных программ.

Вводится модель один раз читающих бинарных программ В этой модели на каждом пути из начальной вершины в конечную каждая вершина х Е X тестируется не более одного раза. Для модели один раз читающих бинарных программ известны следующие включения. Р-ВР С ВРР-ВР с РР-ВР.

Далее вводятся дополнительные ограничения бинарной программы - уров-невость и забываемость. Вводимая нами в дальнейшем квантовая бинарная программа будет определяться как обобщение соответствующей вероятност-

ной забывающей модели.

Бинарная программа называется уровневой, если ее вершины могут быть разбиты на уровни 0,1,... таким образом, что для каждого г ребра из вершин уровня i ведут только в вершины уровня (г + 1). Уровневая бинарная программа Р называется забывающей, если на любом уровне Р тестируется только одна переменная.

Ширина Width(P) бинарной программы Р - это максимум от количества вершин на уровне, взятый rio всем уровням программы Р.

Известно, что произвольная бинарная программа может быть преобразована в уровневую и забывающую не более чем с полиномиальным увеличением сложности. Мы доказываем аналогичные свойства для вероятностных бинарных программ. Далее, без ограничения общности, мы рассматриваем уровневые забывающие бинарные программы. При этом такие бинарные программы можно определить следующим образом.

Вероятностная бинарная программа ширины d глубины 1 (d, l)-PBP Р =

(И0)),т,{г|).

Здесь |/z(0)) - (d х 1)-вектор начального распределения вероятностей состояний; Т = {{г;, Í/ДО), í/j(1))}j=1- последовательность стохастических преобразований, где (d х d)-MaTpmj,bi U}(0),U}(1) (j — 1являются стохастическими по столбцам (в U¡(cr), а Е {0,1} на пересечении s-ro столбца и s'-ой строки стоит вероятность перехода из вершины 5 (j — 1)-го уровня вершину s1 j-го уровня при значении входной переменной = а), (г| - решающий вектор - (1 х d) булевский вектор такой, что г, = 1, тогда и только тогда, когда вершина i 1-го уровня помечена единицей.

Процесс вычисления Р на наборе а = {0,1}" можно представить следующим образом

• Процесс вычисления начинается из начального вектора |/i(0)).

• На j-ом шаге (j — 1Р считывает значение входной переменной ¡rtj = аХ] и преобразует текущий вектор распределения вероятностей состояний \¡j) в вектор |д') = U}{ah)

• После ¿-го (последнего) шага вычислений Р производит измерение результата вычисления. Пусть результирующий вектор распределения вероятностей \цд) = [/¡(сг,,) ■ • ■ U\{atl) |д(0)). Р принимает набор а € {0,1}" с вероятностью Pr^Ja) = (г | fj,¿).

Отметим, что, в отличие классического представления стохастических процессов в работе используется представление текущего состояния в ви-

де вектора-столбца, и оператор воздействует на него слева, что сделано по аналогии с принятым представлением квантовых процессов.

В главе 2 вводится определение квантовой бинарной программы Она всегда является уровнсвой и забывающей и является обобщением соответствующей вероятностной модели.

Квантовая бинарная программа ширины <1 и глубины I ((й, 1)-С}ВР) основанная на С38, определяется как

Р={\ф(0)),Т,Масс).

Здесь Т = {(?',, иг(0), {/¿(1))}'=1 - это последовательность (длины I) ¿-мерных квантовых преобразований квантовой системы ОБ с й устойчивыми состояниями, где иг{0), £/,(1) - унитарные {й х ¿)-матрицы, {й х 1)-вектор |^(0)) - начальная конфигурация Р, Масс - матрица проекции на пространство принимающих состояний.

Вычисление Р на входном наборе а = ... ап € {0,1}" осуществляется аналогично вероятностному случаю, за исключением снятия результата вычисления А именно: вероятность Рг^сс{д) принятия программой Р входа а определяется как Рг^а) = ]|Масс|-0г)||2

Аналогично вероятностному случаю вводятся определения вычисления с ограниченной и неограниченной ошибкой. Будем говорить, что квантовая ВР вычисляет функцию / точно, если она 1/2 + г вычисляет / и г — 1/2.

Шириной 1УгсЙ/1(Р) квантовой бинарной программы Р называется размерность (1 пространства Нл конфигураций. Глубиной ОерМР) квантовой бинарной программы Р называется длина I последовательности Т квантовых преобразований. Как и в классическом случае, глубина квантовой ВР оценивает время вычисления. Ширина квантовой ВР оценивает память -а именно, число кубитов, задействованных в процессе вычисления. Напомним, что число кубитов равно логарифму от числа устойчивых состояний квантовой системы.

Для введеной модели квантовой ВР доказываются основные вычислительные свойства. А именно,

• Квантовая ВР способна вычислять произвольную булеву функцию

• ЫС1 С Е(^Р-ВРсопц, где ЛГС1 - класс функций, представимых схемами из функциональных элементов логарифмической глубины, ЕС^Р-ВРгопм ~ класс функций, точно вычислимых квантовыми ВР константной ширины.

• Если функция / вычислима квантовой ВР с комплексными амплитудами, то / вычислима квантовой ВР только с вещественными амплитудами.

Много-раз измеряющая квантовая ВР (ММ-С}ВР) — С}ВР, в которой после каждого шага вычисления допускается промежуточное измерение текущей конфигурации является естественным обобщением С}ВР, определенной выше.

Основной результат главы 2 касается соотношения сложности квантовых и вероятностных бинарных программ, представляющих произвольную булеву функцию Обозначим ЕС^Р-ВР, В(^Р-ВР, Рг(ЗВ-ВР - классы функций, вычислимых точно с ограниченной ошибкой, с неограниченной ошибкой квантовыми ВР (один раз или много раз измеряющими) полиномиальной сложности.

Теорема 1. Рг(2Р-ВР = РР-ВР.

Для доказательства Теоремы 1 разработаны методы "линейного"и "квантового моделирования". Основной Теоремой метода "линейного моделирования "является:

Теорема 2. (Классическое моделирование) Пусть функция / вычислима с неограниченной (с ограниченной) ошибкой квантовой бинарной программой (с?. 1)-С}ВР Р. Тогда существует забывающая (4с£2 + 3,1)-РВР Р', вычисляющая функцию / с неограниченной ошибкой.

Для доказательства Теоремы 2 отмечается, что квантовую ВР и вероятностную ВР можно рассматривать как некие линейные бинарные программы с определенными ограничениями, в которых на каждом вычислительном шаге текущий вектор распределения состояний преобразовывается в вектор распределений состояний на следующем шаге путем умножения его на матрицу преобразований. При этом разница между квантовой и вероятное гной ВР состоит в виде преобразований (стохастические для одного случая и унитарные для другого), в природе пространства, где производятся преобразования (вещественное в одном случае и комплексное в другом), в различии определения вероятности принятия (вероятность является линейной в одном случае и квадратичной в другом) В качестве преодоления этих различий доказываются несколько Лемм, что и доказывает Теорему 2.

Теорема 3. (Квантовое моделирование) Пусть функция / вычислима вероятностной забывающей бинарной программой (й, 1)-РВР Р. Тогда она вычислима много раз измеряемой квантовой бинарной программой (с1,1)-ММ^ВР (р такой, что

Рг^Ло) = РгЦд) для любого а 6 {0,1}".

Для доказательства Теоремы 3 используется известный прием моделирования классической вероятности 1/2 при помощи квантовой частицы.

Из Теорем 2 и 3 следуют включения: В(^)Р-ВР С РР-ВР, РгС)Р-ВР С РР-ВР, ВРР-ВР С ВС^Р-ВР, РР-ВР С РгС^Р-ВР, которые, в частности, и доказывают Теорему 1.

В главе 3 определяются один раз читающие квантовые бинарные программы (1С2ВР) — такие ВР, в которых каждая переменная х € X присутствует в последовательности Т квантовых преобразований не более одного раза. Для таких бинарных программ в первом параграфе главы 3 доказывается нижняя оценка ширины квантовой бинарной программы, представляющей произвольную булеву функцию /.

Теорема 4. Пусть е € (0,1/2). Пусть / - булева функция, (1/2 + е)-вычислимая один раз читающей квантовой ВР <2- Тогда верно

* 2108(1 + 2/0)-

где - минимальная ширина один раз читающей детерминиро-

ванной ВР, вычисляющей функцию /, 9 —

Доказательство Теоремы 4 использует метрические свойства пространства состояний квантовой бинарной программы, вычисляющей функцию /. Тот факт, что <5 вычисляет / с ограниченной ошибкой, создает на этом пространстве определенную топологию

Во втором параграфе рассматривается известная симметрическая булева функцию МОБр. на наборе а = <71... ап б {0,1}п МОПр(сг) = 1 тогда и только тогда, когда число единиц в наборе а кратно р, где р просюе число, р < п/2. Легко проверяется, что

ВР^(МООр) > р. (1)

Теорема 5. Любая стабильная один раз читающая вероятностная бинарная программа, вычисляющая функцию МОБр с вероятностью 1/2 + е для фиксированного е £ (0,1/2], имеет ширину не менее р.

Под стабильной бинарной программой понимается такая ВР, в которой преобразования, применяемые на каждом уровне при считывании значения входной переменной х, = 0 (х, = 1) одни и те же (не зависят номера уровня, на котором они применяются).

Теорема 6. Существует стабильная {0(\о%р),п)-1С}ВР, с односторонней ошибкой е > 0, вычисляющая функцию МОИр.

В доказательстве используется свойство простоты числа р, комплексность пространства состояний квантовой бинарной программы и возможность квантового параллелизма. Теоремы 5, 6 и (1) показывают, что оценка Теоремы 4 точна, и что квантовые ВР могут быть экспоненциально экономнее классических ВР

Глава 4 диссертации посвящена исследованию сравнительной сложности квантовых и классических конечных автоматов. Квантовый односторонний конечный автомат (С^ЕА) определяется как обобщение соответствующей вероятностной модели.

Квантовый конечный автомат определяется на основе квантовой системы С^Б. Под квантовым конечным автоматом 2 понимается пятерка

д = {Е, 5, {М(а) : <7 € £}, в0, П

Здесь Е - это конечный входной алфавит с символом $ в качестве маркера конца входного слова, 5 - конечное множество состояний (положим б. = |5|). функция переходов задается матрицами переходов М(а),а е Е, во £ 5 -начальное состояние, РС§ - финальное множество состояний,

Квантовый конечный автомат работает следующим образом На каждом шаге вычисления автомат <2 может находиться в любой суперпозиции состояний из 5 Вычисление начинается в суперпозиции |во) (через |,§) обозначается базисное состояние - вектор, в котором в-ая компонента равна 1, остальные равны нулю) Если на текущем шаге состояние автомата О, описывалось суперпозицией = (г0, ..., •г<г-1)г, то после считывания очередного символа а е Е входного слова новой суперпозицией автомата будет IV»') = (¿о— , г^)7", где вектор |ф') = М(а)\ф). Матрица переходов М(<т) это (с£ х ¿)-комплекснозначная унитарная матрица, в которой на пересечении б'-ой строки и 5-ого столбца находится 6(в, а, я') - амплитуда состояния

в суперпозиции состояний, в которое перейдет автомат О, из состояния 5 4

при считывании входного символа а После считывания всех символов входного слова а (после считывания конечного маркера $) работа автомата Q останавливается и производится измерение результирующей суперпозиции = Ы> ■ ■ гй~{)Т- В результате получаем $г е 5 с вероятностью ¡¿¡I2. Если 51 € входное слово принимается. Если зх € слово отвергается. При этом вероятность принятия автоматом 2 слова а Рг^сс(а) = |2г|2.

Вероятность того, что слово отвергается, равна Рг® (&) = 1 - Pr£c(ä).

Сложность S(Q) автомата ß - это число d его состояний.

Известно, что QFA способны распознавать только собственное подмножество регулярных языков В 1997 г A. Kondacs, J. Watrous привели пример регулярного языка, непредставимого с ограниченной ошибкой квантовым конечным автоматом. В 1998 г. A. Ambainis, R. Freivalds определили язык Lp, для которого квантовый конечный автомат, распознающий с ограниченной ошибкой, является экономнее как детерминированного, так и вероятностного, распознающего с ограниченной ошибкой. Lp - эю язык в однобуквенном алфавите, состоящий из всех слов длины, кратной р {р - простое число)

Третий параграф главы 4 посвящен сравнительной сложности представления языков в вероятностных и квантовых конечных автоматах. Мы доказываем сложность вероятностного моделирования квантового конечного автомата, распознающего произвольный язык L.

Теорема 7. Пусть язык L распознается с ограниченной (с неограниченной) ошибкой квантовым конечным автоматом Q. Тогда существует вероятностный конечный автомат V, распознающий L с неограниченной ошибкой такой, что

S{V) < 2S2(Q) + 3.

Доказательство следует из результатов С. Moore and J. Crutchfield о связи квантовых и линейных конечных автоматов и результата П Туракайнена о моделировании линейных автоматов вероятностными

Мы определяем модель много раз измеряемого квантового конечного автомата. Данное определение отлично от определения много раз измеряемого квантового автомата, данного A. Kondacs, J. Watrous и является efo обобщением.

Теорема 8. (Квантовое моделирование) Пусть вероятностный конечный автомат V определяет словарную функцию Рг^сс(д). Тогда существует много раз измеряемый квантовый конечный автомат Q, который определяет словарную функцию Рг^^д) = Рт^сс{д) такой, что S{Q) = S{V).

Для доказательства Теоремы 8 предложен метод "квантового моделирования", который является адаптацией метода "квантового моделирования "вероятностных бинарных программ

В четвертом параграфе главы 4 доказывается нижняя оценка сложности квантового конечного автомата, распознающего произвольный язык L с ограниченной ошибкой.

Теорема 9. Пусть е 6 (0,1/2]. Пусть язык Ь С Е* (1/2+е)-распознается (¿РА 2. Тогда справедливо

2к^(1 + 2/6)'

где ОЯ(Ь) - сложность минимального конечного детерминированного автомата, распознающего язык Ь, в = 2^26/^1 + л/2(1 - 2е).

Доказанная оценка показывает максимальную эффективность, которая может быть достигнута при использовании квантового автомата по сравнению с детерминированным. Пример языка Ьр (А. АтЬашз, И,. РгетИэ) демонстрирует, что доказанная нижняя оценка сложности квантового конечного автомата является почти точной.

Автор выражает признательность своему научному руководителю Абла-еву Ф М.

Работа выполнена при поддержке фонда РФФИ грант 03-01-00769 и фонда АНТ РТ грант 05-5.2-170/2003 Ф(05).

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Аблаев Ф М. Сложность представления языков в квантовых автоматах / Ф.М Аблаев, А.Ф. Гайнутдинова // Сборник трудов IV Международной конференции "Дискретные модели в теории управляющих систем"(МГУ, Москва, июнь, 2000г) - М.: Издательский отдел факультета ВМиК МГУ. - С. 6-7.

2 Аблаев Ф. М. Вычислительная мощность квантовых бинарных программ / Ф М. Аблаев А.Ф. Гайнутдинова. М. Карпинский // Тезисы докладов XIII международной летней школы-семинара по теоретической и математической физике (Казань, 22 июня - 3 июля 2001 г.). -Казань: ООО "Издательство Регент", 2001. - С. 17.

3. Аблаев Ф.М. Вычислительные свойства квантовых бинарных программ / Ф.М Аблаев, А.Ф. Гайнутдинова, М. Карпинский // Материалы VII Международного семинара "Дискретная математика и ее приложения" (Москва. 29 января - 2 февраля 2001 г.) - М.: Изд-во центра прикладных

исследований при механико-математическом факультете МГУ, 2001. -С. 43-45

4. Аблаев Ф.М. Уточнение оценки сложности представления языков в квантовых автоматах / Ф.М. Аблаев, Н.З. Габбасов, А.Ф. Гайнутди-нова // Проблемы теоретической кибернетики. Тезисы докладов XIII Международной конференции (Казань, 27-31 мая 2002 г.) - М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002. - С 4.

5 Аблаев Ф М. Сложность классического моделирования квантовых машин / Ф М. Аблаев, А Ф. Гайнутдипова // Труды V Международной конференции "Дискретные модели в теории управляющих систем"(Рат-мино, 26-29 мая 2003г)- М Издательский отдел факультета ВМиК МГУ имени М.В Ломоносова. - С 4

6. Гайнутдинова А Ф. О сравнительной сложности квантовых и классических бинарных программ / А Ф. Гайнутдинова // Дискретная математика. - Москва' изд-во РАН, 2002 - Т14, вып. 3. - С 109-121.

7. Гайнутдинова А. Ф Сложность распознавания функции MODp в квантовых и классических бинарных программах / А.Ф. Гайнутдинова // Проблемы теоретической кибернетики, Тезисы докладов XIII Международной конференции (Казань. 27-31 мая 2002 г.) - М.: Изд-во центра прикладных исследований при механико-математическом факультете МГУ, 2002. - С. 42.

8. Ablayev F. Оп the Lower Bounds for One-Way Quantum Automata / F Ablayev, A. Gainutdinova // Proc. of the 25th International Symposium. Mathematical Foundations of Computer Science (MFCS'2000, Bratislavaj - Springer-Verlag, 2000. - V. 1893. - P. 132-140

9. Ablayev F. On the Lower Bounds for One-Way Quantum Automata / F Ablayev, A. Gainutdinova // Optimal Discrete Structures and Algorithms (Rostok, Germany, September 11-13, 2000), Schedule and abstracts. - University Rostok, 2000. - P. 13.

10 Ablayev F On Computational Power of Quantum Branching Programs / F Ablayev, A. Gainutdinova, M. Karpinski // Proc. of the 13th international

symposium, Fundamentals of computation theory (FCT 2001, Riga, Latvia)

- Lecture Notes in Computer Science, 2001 - V 2138 - P. 59-70.

11. Ablayev F On Computational Power of Quantum Branching Programs / F Ablayev, A. Gamutdinova, M. Karpinski // Preprint. - Mathematical Sciences Research Institute, MSRI, 2002- - N 2002-028. - 20 p.

12. Ablayev F Classical Simulation Complexity of Quantum Machines / F Ablayev, A. Gainutdinova // Fundamentals of Computation Theory 14th International Symposium FCT 2003, Malmo, Sweden, August 12-15, 2003.

- Lecture Notes in Computer Science, 2003. - V 2751. - P. 296-302

Отпечатано с готового оригинал-макета в типографии Издательского центра Казанского государственного университета Тираж 100 экз. Заказ 3/11 420008, Казань, ул. Университетская, 17 Тел. 38-05-96

РНБ Русский фонд

2006-4 9824

i s мр да

Основные обозначения, используемые в работе

Введение

1 Предварительные сведения.

1.1 Основы квантовых вычислений.

1.2 Классические бинарные программы.

1.2.1 Один раз читающие бинарные программы.

1.2.2 Забывающие бинарные программы.

2 Квантовые бинарные программы. Квантовое и классическое моделирование.

2.1 Определения и основные вычислительные свойства.

2.2 Сложность моделирования.

2.2.1 Классическое моделирование квантовых бинарных программ.

2.2.2 Квантовое моделирование классических бинарных программ.

3 Один раз читающие квантовые бинарные программы. . Нижняя оценка сложности. 54 3.1 Нижняя оценка сложности вычисления булевой функции в квантовых бинарных программах.

3.1.1 Доказательство нижней оценки сложности.

3.2 Сложность реализации функции MODp в классических и квантовых бинарных программах.

3.2.1 Сложность реализации функции MODp в детерминированных и вероятностных OBDD.

3.2.2 Реализации функции MODp в квантовых OBDD.

4 Классические и квантовые конечные автоматы

4.1 Конечные автоматы.

4.1.1 Детерминированный конечный автомат.

4.1.2 Вероятностный конечный автомат.

4.2 Квантовый конечный автомат.

4.3 Сравнительная сложность квантовых и вероятностных ко

• ■ нечных автоматов .■.•.:.;•.:;.

4.3.1 Классическое моделирование квантовых автоматов.

4.3.2 Квантовое моделирование вероятностного автомата.

4.4 Нижняя оценка сложности распознавания языков квантовым конечным автоматом.

4.4.1 Доказательство нижней оценки сложности.

Какие проблемы являются вычислимыми и как эффективно они могут быть вычислены? В основе теории вычислимости лежит Тезис Черча-Тьюринга: все разумные модели вычислений могут быть смоделированы машиной Тьюринга. Для вычислимых проблем встает вопрос о сложности вычисления, а именно, какие физические ресурсы требуются для того, чтобы решить проблему - такие, как память, время, энергия, и т.д. Основными сложностными характеристиками, изучаемыми в теории сложности, являются время вычисления и память, затрачиваемая в процессе вычисления.

Фундаментальный вопрос теории сложности - как ведет себя функция сложности, если ее рассматривать как функцию от размера входа - п, и, в частности, является ли она полиномиальной или экснонен-циональной от п. При этом принято считать, что некоторая проблема решается просто, если сложность является полиномиальной от размера входа; и является трудно разрешимой, если функция сложности является экспоненциальной от размера входа.

Не менее актульный вопрос - что значит решить проблему? Решить точно или допустить некоторую вероятность ошибочного результата? Теория вероятностных алгоритмов отменяет требование к результату всегда быть точным и разрешает некоторую вероятность ошибки. Это позволяет получить заметное.уменьшение сложности решения ряда известных проблем. В связи с этим была выдвинута современная версия тезиса Черча: Все разумные модели вычислений могут быть эффективно (с полиномиальной сложностью) смоделированы вероятностной машиной Тьюринга.

В 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 рассматривается известная модель для вычисления булевых функций - бинарные ирограмы (BP). В главе 2 приведены необходимые определения и предварительные сведения, касающиеся соотношений между детерминированными и вероятностными BP с ограничениями. Основные результаты диссертации, касающиеся бинарных программ, приведены в главах 2,3.

Вычисления на BP можно трактовать как вычисления на одиночном процессоре, который на каждом такте работы может считывать не более одного бита входного слова. Введение в модель BP случайных вершин, в которых, в зависимости от датчика случайных чисёл, выбирается тот или иной путь дальнейшего вычисления, приводит к модели вероятностных бинарных программ. Впервые модель вероятностной бинарной программы была определена в работе [26]. Известно, что вероятностные бинарные программы с определенными ограничениями могут быть экспоненциально экономнее соответствующих детерминированных BP.

В главе 1 рассматриваются дополнительные ограничения бинарных программ, такие, как уровневость и забываемость. Известно, что бинарные программы общего вида могут быть преобразованы в уровневые забывающие не более чем с полиномиальным увеличением сложности. В работе мы определяем модель'квантовой бинарной программы как обобщение соответствующей вероятностной уровневой забывающей модели. Известная модель перестановочных детерминированных бинарных программ является частным случаем квантовых бинарных программ, где преобразования, применяемые на каждом шаге вычисления - это перестановки. Известно, что класс функций, вычислимых перестановочными бинарными программами ограниченной ширины совпадает с классом NC1 функций, вычислимых схемами из функциональных элементов логарифмической глубины [8].

Наканиши, Хамагучи и Кашивабара в работе [50] определили несколько иную модель квантовой бинарной программы. В отличие от модели, определяемой в работе, язык описания этой бинарной программы графовый. Квантовая бинарная программа [50] не обязательно уровневая и забывающая. Иначе определяются понятия ширины и конфигурации квантовой бинарной программы. Под конфигурацией в модели [50] понимается суперпозиция множества всех вершин бинарной программы. В нашей модели конфигурация - это суиернозиция множества вершин на уровне. С этой точки зрения приемущеетвом квантовой бинарной программы, описанной в работе, является то, что в данной модели задействовано гораздо меньше кубитов, чем в модели [50], что может оказаться важным для практической реализации. Напомним, что число кубитов равно логарифму от числа устойчивых состояний квантовой системы. Основными результатами диссертации.в области бинарных программ являются следующие.

• Доказываются соотношения классов сложности РР-ВР, PrQP-ВР, BQP-BP, определенных для модели бинарных программ. При этом используется техника моделирования:

Моделирование классического вероятностного процесса вычисления квантовым использует известный прием моделирования вероятности 1/2 при помощи квантовой частицы. Имея вероятностную бинарную программу, вычисляющую функцию / на наборе а с вероятностью правильного результата а-сг, мы строим квантовую бинарную программу, использующую измерения на каждом шаге вычисления, которая вычисляет функцию / на наборе а с той же вероятностью (метод "квантового моделирования "вероятностной бинарной программы - Теорема 2.3).

Для моделирования квантового процесса вычисления классическим вероятностным (Теорема 2.2) используется разработанный нами метод "линейного моделирования", который частично является обобщением метода моделирования линейных конечных автоматов вероятностными.

• Мы доказываем нижнюю оценку сложности один раз читающей квантовой бинарной программы, вычисляющей произвольную булеву функцию / с ограниченной ошибкой (Теорема 3.1). Полу

• • ченная нижняя оценка формулируется в терминах сложности минимальной один раз читающей детерминированной бинарной программы, вычисляющей ту же функцию /.

• На примере известной симметрической функции MODp мы доказываем, что один раз читающая квантовая BP может быть экспоненциально экономнее один раз читающей как детерминированной, так и вероятностной BP. Для данной функции доказываются нижние оценки сложности детерминированной BP и вероятностной BP, дающей правильный результат с большой вероятностью. Строится квантовая BP, вычисляющая MODp с ограниченной ошибкой.

Глава 4 посвящена исследованию конечных автоматов. Модель вероятностного конечного автомата, определяемая как обобщение детерминированного конечного автомата стала являться обьектом пристального исследования с 60-х годов. Известно, что конечные вероятностные автоматы с ограниченной ошибкой распознают только регулярные языки (Теорема редукции Рабина [19]). Известны примеры языков, для которых вероятностный автомат является более экономным, чем детерминированный, и примеры языков, для которых вероятностный автомат не дает приемущества перед детерминированным. Важным является результат П. Туракайнена [56] о тождественности класса стохастических языков и языков, представимых в конечных линейных автоматах. В диссертации рассматривается модель одностороннего квантового конечного автомата. Впервые эта модель была определена в [45, 48]. Известно, что квантовые конечные автоматы с ограниченной ошибкой распознают собственное подмножество регулярных языков. Кроме того, известен пример регулярного языка, не распознаваемого квантовым конечным автоматом с ограниченной ошибкой [45]. В работе мы рассматриваем две модели квантового конечного автомата - один раз измеряемый квантовый конечный автомат, в котором измерение ("снятие результата вычисления") производится один раз по окончании процесса вычисления и много раз измеряемый квантовый конечный автомат, в котором измерение производится после каждого шага вычисления. Основными результатами главы 4 являются:

• Доказывается Теорема 4.1 о сложности классического моделирования квантовых конечных автоматов.

• Мы оцениваем сложность моделирования вероятностного конечного автомата, распознающего произвольный язык L, квантовым конечным автоматом, допускающим измерение текущей конфигурации после каждого шага вычисления (Теорема 4.2). Для этого предлагается метод "квантового моделирования "вероятностного конечного автомата, который является развитием разработанного нами метода "квантового моделирования "вероятностной бинарной программы.

• Мы доказываем нижнюю оценку сложности квантового конечного автомата, распознающего произвольный язык с ограниченной ошибкой (Теорема 4.3). При этом доказанная оценка формулируется в терминах сложности минимального детерминированного автомата, распознающего тот же самый язык. Полученная нижняя оценка является почти точной: пример языка, приведенного в работе [31], демонстрирует экспоненциальное ириемущество квантовых конечных автоматов перед детерминированными и вероятностными автоматами, распознающими языки с ограниченной ошибкой.

Основные результаты, относящиеся к предмету диссертации, изложены в работах [2, 3, 4, 5, 11, 12, 21, 22, 23, 24, 6, 25] и были доложены на 25 Международной конференции FCT'2000 (Братислава, Словения), международной конференции "Optimal Discrete Structures and Algorithms"(Росток, Германия, 2000 г.), IV Международной конференции "Дискретные модели в теории управляющих систем "(мехмат,

МГУ, 2000 г., 2003 г.), 13 Международной конференции FCT'2001 (Рига,. Латвия), XII, XIII, XLV Международных школах-семинарах по теоретической и математической физике (Казань, 2001 г., 2002 г., 2003 г.), VII Международном семинаре "Дискретная математика и ее приложения" (мехмат, МГУ, 2001 г.), XIII Международной конференции "Проблемы теоретической кибернетики "(Казань, 2002 г.), 14 Международной конференции FCT'2003 (Malmo, Sweden), на семинарах мехмата Московского госуниверситета (руководитель - академик РАН, д.ф.-м.н., профессор Лупанов О.В.), на семинарах математического института им. В.А. Стеклова (руководитель - член кор. РАН. профессор Разборов А.А.), на семинарах физико-технического института РАН (руководитель - академик РАН, Валиев К.А.), на семинаре Латвийского госуниверситета (руководитель - академик Латвийской АН, д.ф.-м.н., проф. Фрейвалд Р.В.), на итоговых научных конференциях Казанского государственного университета, на семинарах ио квантовым вычислениям Казанского госуниверситета (руководитель - д.ф.-м.н., нроф. Аблаев Ф.М.).

1. Аблаев Ф.М. Влияние степени изолированности точки сечения на число состояний вероятностного автомата / Ф.М. Аблаев // Математические заметки. - М.:Изд-во "Наука", Главная редакция физико-математической литературы, 1988. - Т. 4, N 3. - С. 289-297.

2. Александров П.С. Введение а теорию множеств и общую топологию / П.С. Александров. М.: Главная редакция физико-математической литературы издательства "Наука", 1977. - 3G8 с.

3. Баррингтон Д. Ветвящиеся программы ограниченной ширины, имеющие полиномиальную сложность, распознают в точности языки из NC1 / Д. Баррингтон // Кибернетический сборник. М.: Мир, 1991. - вып. 28. - С. 94-113.

4. Бухараев Р.Г. Основы теории вероятностных автоматов / Р.Г. Бу-хараев. М.: Наука. Главная редакция физико-математической литературы, 1985. - 288 с.

5. Валиев В. А. Квантовые компьютеры: надежды и реальность / В.А. Валиев, А.А. Кокин. Ижевск: НИС "Регулярная и хаотическая динамика", 2001. - 352 с.

6. Гайнутдинова А. Ф. О сравнительной сложности квантовых и классических бинарных программ / А.Ф. Гайнутдинова // Дискретная математика. Москва: изд-во РАН, 2002. - Т. 14, вып. 3. - С. 109121.

7. Кемени Д. Конечные цепи Маркова / Д. Кемени, Д. Снелл. М.: Главная редакция физико-математической литературы изд-ва "Наука", 1970.- 271 с.

8. Китаев А. Классические и квантовые вычисления / А. Китаев, А. Шень, М. Вялый. М.: МЦНМО, ЧеРО, 1999. - 192 с.

9. Кострикин А.И. Линейная алгебра и геометрия / А.И. Кострикин, Ю.А. Манин. М.:Изд-во Моск. ун-та, 1980. - 320 е., 10 ил.1G. Манин Ю. И. Вычислимое и невычислимое / Ю.И. Манин. М.: Сов. радио, 1980. - 128 с.

10. Покровская И. А. Некоторые оценки числа состояний вероятностных автоматов, представляющих регулярные события / И.А. Покровская // Проблемы кибернетики. М.: Изд-во физ.-мат литературы, 1979. - вып. 36. - С. 181-194.

11. Рабин М. Вероятностные автоматы / М. Рабии // Кибернетический сборник. М.: Изд-во Мир, 1964. - вып.9. - С. 123-141.

12. Фрейвалд Р.В. Об увеличении числа состояний при детерминиза-ции конечных вероятностных автоматов / Р.В. Фрейвалд // Автоматика и вычислительная техника, 1982. N 3. - С. 39-42.

13. Ablayev F. On the Lower Bounds for One-Way Quantum Automata / F. Ablayev, A. Gainutdinova // Proc. of the 25th International Symposium, Mathematical Foundations of Computer Science (MFCS'2000, Bratislava) Springer-Verlag, 2000. - V. 1893.- P. 132-140.

14. Ablayev F. On the Lower Bounds for One-Way Quantum Automata / F. Ablayev, A. Gainutdinova // Optimal Discrete Structures and Algorithms, (Rostok, Germany, September 11-13, 2000), Schedule and abstracts. University Rostok, 2000. - P. 13.

15. Ablayev F. On Computational Power of Quantum Branching Programs / F. Ablayev, A. Gainutdinova, M. Karpinski // Preprint. -Mathematical Sciences Research Institute, MSRI, 2002. N 2002-028.- 20 p.

16. Ablayev F. Classical Simulation Complexity of Quantum Machines / F. Ablayev, A. Gainutdinova // Proc. 14th International Symposium FCT 2003, Mahno, Sweden, August 12-15, 2003. Lecture Notes in Computer Science, 2003. - V. 2751. - P. 296-302.

17. Ablayev F. On the power of randomized branching programs / F. Ablayev, M. Karpinski // Proc. 28th ICALP (1996). LNCS, Springer, 1996.-V. 1099.-P. 348-356.

18. Ablayev F. A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs / F. Ablayev, M. Karpinski // Information and Computation. Elsevier, 2003. - V. 186, N 1. - P. 78-89.

19. Ablayev F. On BPP versus NP U coNP for ordered read-once branching programs / F. Ablayev, M. Karpinski, R. Mubarakzjanov // Theoretical Computer Science. Elsevier, 2001. - V. 264. - P. 127137.

20. Ablayev F. Quantum and Stochastic Branching Programs of Bounded Width / F. Ablayev, C. Moore, C. Pollett // Proc. of the ICALP'2002, Lecture Notes in Computer Science. Springer-Verlag, 2002. - P. 343354.

21. Adleman L. Quantum computability / L. Adleman, J. Demarrais, M. Huang // SIAM Л. on Computing, 1997. V. 26, N 5. - P. 1524-1540.

22. Ainbainis A. 1-way quantum finite automata: strengths, weaknesses and generalization //A. Ambainis, R. Freivalds // Proc. of the 39th IEEE Conference on Foundation of Computer Science. Computer Society Press, 1998. - P. 332-342.

23. Bennett C.H. Logical reversibility of computations / C.H. Bennett // IBM Jounal of Res. Develop, 1973. V. 17. - P. 525-532.

24. Benioff P.A. Quantum mechanical hamiltonian models of turing machines / P.A. BeniofF // Journal of Statistical Physics, 1982. V. 29, N 3. - P. 515-546.

25. Bernstein E., Vazirani U. Quantum complexity theory / E. Bernstein, U. Vazirani.// SIAM J. Comput, 1997. V. 26, N 5. - P. 1411-1473.

26. Cobham A. The recognition problem for the set of perfect squares / A. Cobham // Proc. of the 7th Symposium on Switching an Automata Theory (SWAT), 1996. P. 78-87.

27. Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer / D. Deutsch // Proceedings of the Royal Society. London, 1985. - A400. - P. 97-117.

28. Deutsch D. Rapid solution of problems by quantum computation / D. Deutsch, R. Lozsa // Proc. of the Royal Society. London, 1992. -A439. - P. 553-558.

29. Feynman R. Simulating physics with computers / R. Feynman // International Journal of Theoretical Physics, 1982. V. 21, N 6,7. -P. 4G7-488.

30. Grover L. A fast quantum mechanical algorithm for database search / L. Grover // Proc. of 28th STOC, 1996. P.Philadelphia PA USA, 2996. - P. 212-219.

31. Gruska J. Quantum computing / J. Gruska. McGraw-Hill Publishing Company, 1999. - 419 p.

32. Green F. On the Complexity of Quantum ACC / F. Green, S. Homer, C. Pollet // Proc. of the 15th IEEE Conf. on Computational Complexity. Computer Society Press, 2000. - P. 250-262.

33. Kitaev Л. Yu., Quantum measurements and the Abelian Stabilizer Problem / A. Yu. Kitaev // http://xxx.lanl.gov/archive/quant-ph, 1995. quant-ph/9511026.

34. Kondacs A. On the power of quantum finite state automata / A. Kondacs, J. Watrous // Proc. of the 38th Annual Symposium on Foundations of Computer Science, 1997. P. 66-75.

35. Lecerf Y. Machines de Turing reversibles. Recursive insolubilite en n 6 N de l'equation и = 0n ou в est un isomorphisme de codes / Y. Lecerf // Comptes rendus de l'Academie francaise des sciences, 1963. V. 257. - P. 2597-2600.

36. Moore C. Some Notes on Parallel Quantum Computing / C. Moore, M. Nilson // http://xxx.lanl.gov/archive/quant-ph. quant ph/9804034.

37. Moore C. Quantum automata and quantum grammars / C. Moore, J. Crutchfield // http://xxx.lanl.gov/archive/quant-ph. quant-ph/9707031.

38. Motwani R. Randomized Algorithms / R. Motwani, P. Raghavan. -Cambridge University Press, 1995. 492 p.

39. Nayak A. Optimal lower bounds for quantum automata and random access codes / A. Nayak // Proc. of the 40th IEEE Conference on Foundation of Computer Science, 1999. P. 369-376.

40. Pudlak P. Space complexity of computations / P. Pudlak, S. Zak // Technical report, Univ. Prague, 1983.

41. Shor P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer / P. Shor // SI AM J. on Computing, 1997. V. 26, N 5. - P. 1484-1509.

42. Simon D. On the power of quantum computation / D. Simon // SIAM Journal of Computing, 1997. V. 26, N 5. - P. 1474-1483.

43. Travaglione B.C. ROM-based computation: quantum versus classical / B.C. Travaglione, M.A. Nielsen, H.M. Wiseman, A. Ambainis // http://xxx.lanl.gov/archive/quant-ph. quant-ph/0109016.

44. Turakainen P. Generalized automata and stochastic languages / P. Turakainen // Proc. Amer. Math. Soc.,1969. V. 21. - P. 303-309.

45. Wegener I. Branching Programs and Binary Decision Diagrams / I.Wegener. Siam Monographs on Discrete Mathematics and Applications, 2000. - 408 p.

46. Yao A. Quantum circuit complexity / A. Yao // Proc. 34th IEEE Symposium on Foundation of Computer Science, 1993. P. 352-361.