Эффективные алгоритмы в модели квантовых ветвящихся программ тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Васильев, Александр Валерьевич

• Васильев, Александр Валерьевич
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Васильев, Александр Валерьевич

Основные обозначения и понятия

Введение

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

1.1 Детерминированные ветвящиеся программы.

1.1.1 Определения.

1.1.2 Связь с другими моделями вычислений.

1.2 Вероятностные ветвящиеся программы.

1.2.1 Определения.

1.2.2 Уменьшение вероятности ошибки.

1.2.3 Метод Fingerprinting.

2 Квантовые ветвящиеся программы

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

2.2 Определение квантовых ветвящихся программ.

2.3 Эффективные квантовые ветвящиеся программы.

2.4 Схемное представление

2.5 Уменьшение вероятности ошибки.

2.6 Связь с другими схемными моделями вычислений

3 Квантовый метод отпечатков

3.1 Квантовый метод отпечатков.

3.1.1 Существование "хорошего" множества параметров

3.1.2 Конструктивные методы построения "хорошего" множества параметров.

3.1.3 Варианты использования техники отпечатков

3.2 Вычисление функции KIODm.

3.2.1 Вычисление функции MOD'm.

3.3 Квантовая OBDD для проверки равенства и сводимых к ней функций.

3.3.1 Понятие сводимости.

3.3.2 Проверка равенства.

3.3.3 Проверка симметрии.

3.3.4 Проверка периодичности

3.3.5 Функция Semi-Simon.

3.4 Квантовая OBDD для проверки перестановочности матрицы

3.5 Квантовая OBDD для задачи о скрытой подгруппе . 69 3.5.1 Доказательство верхней оценки сложности

3.6 Вычисление функции голосования на одном кубите

3.7 Проблема равенства в коммуникационной модели SMP

3.8 Упрощенный метод отпечатков.

4 Моделирование функций из NC1 квантовыми fc-OBDD

4.1 Перестановочные ветвящиеся программы.

4.2 Результаты Баррингтона

4.3 Моделирование NC1 квантовыми &-OBDD.

Введение диссертации (часть автореферата) на тему «Эффективные алгоритмы в модели квантовых ветвящихся программ»

Что значит полностью решить вычислительную задачу?

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

Для построения алгоритмов необходимо зафиксировать некоторую модель вычислений, в терминах которой и будет описываться решение задачи. Такие модели, как машины Тьюринга и схемы из функциональных элементов, предоставляют эту возможность, но доказывать нижние оценки сложности решения некоторой задачи при определенных вычислительных ограничениях оказывается довольно трудно. Более того, известно очень небольшое число таких результатов. Гораздо чаще удается сводить решение одной задачи к решению другой, т.е. доказать, что первая задача не сложнее второй. Это привело к тому, что трудность решения огромного числа практически значимых задач держится на центральной гипотезе теории сложности, а именно на неравенстве Р ф NP. С другой стороны, каждая такая сводимость приближает нас к решению вопроса о справедливости указанной гипотезы, поскольку эффективная вычислимость хотя бы одной из NP-полных ("самых сложных" в классе NP) проблем будет означать наличие эффективного алгоритма для всех остальных задач из класса NP.

Модель ветвящихся программ, зарекомендовавшая себя при тестировании сверхбольших интегральных схем, помимо удобства описания алгоритмов предоставляет подходы для доказательства нижних оценок сложности при некоторых "естественных" ограничениях. В то же время меры сложности ветвящихся программ тесно связаны со сложностью машин Тьюринга и схем из функциональных элементов, что позволяет переносить результаты с одной модели на другую [48].

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

Для модели ветвящихся программ наиболее разработанными являются ограничения на порядок и количество считываний входных переменных [48]. Один раз читающая ветвящаяся программа - это ветвящаяся программа с тем ограничением, что на каждом вычислительном пути каждая переменная встречается не более одного раза. Дополнительное условие "забывания" требует, чтобы считывание всегда происходило в соответствии с фиксированным порядком переменных. Забывающие один раз читающие ветвящиеся программы (они как раз используются при тестировании сверхбольших интегральных схем) называются упорядоченными бинарными диаграммами решений (Ordered

Binary Decision Diagrams, сокращенно OBDD). Поскольку такие ветвящиеся программы имеют широкое практическое применение, то важным вопросом является возможность эффективной (полиномиальной) реализации в них практически важных функций, таких как целочисленное умножение. Оказалось, что для классических детерминированных OBDD и один раз читающих ветвящихся программ умножение сложно [29, 41]. В 1997 году было показано, что умножение остается сложным и для вероятностных OBDD [15]. Открытым остается вопрос о сложности реализации в квантовых OBDD.

Предложенная в 80-х годах XX века квантовая парадигма вычислений дала новые подходы к определению алгоритмической сложности некоторых вычислительных задач. Например, была показана возможность эффективного вычисления на квантовых компьютерах функций, для которых не доказано существование эффективных алгоритмов в классических моделях. Наиболее известными являются алгоритм факторизации Шора [44] и алгоритм поиска Гровера [35].

В чем же преимущества квантовых вычислений и какие у них слабости?

Наибольшие надежды возлагаются на -квантовый параллелизм - возможность квантового регистра находиться одновременно во всех своих состояниях. Так, если классический тг-битный регистр находится ровно в одном из своих состояний, то n-битный квантовый регистр сразу во всех 2та базисных состояниях. С одной стороны, это позволяет производить вычисления сразу на множестве наборов, в том числе на всех наборах сразу. Однако прямолинейное применение этого приема ничего не дает, поскольку достоверно извлечь нужный ответ не удастся. Потребуется преобразование состояния таким образом, чтобы нужный ответ получил бы большую амплитуду, а значит проявился при измерении с большой вероятностью. В решении указанной проблемы может помочь другая особенность квантовых вычислителей - наличие интерференции между состояниями, возникающей из-за того, что новые амплитуды базисных состояний оказываются линейными комбинациями старых амплитуд. Это позволяет строить алгоритмы таким образом, чтобы неверные решения исчезали за счет деструктивной интерференции (уменьшающей амплитуду), в то время как желаемые состояния усиливались при конструктивной интерференции (увеличивающей амплитуду).

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

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

Еще одна особенность квантовых вычислений - обратимость используемых преобразований - не представляет проблемы, если нет ограничений на размер квантового регистра. Однако при довольно умеренных ограничениях (порядка 0(1о§тг) кубит, где п - длина, входного набора) вычисление многих функций оказывается затруднено, а соответствующие задачи в таких моделях с ограничениями могут иметь экспоненциальную сложность [43].

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

Однако на данный момент вычислители сильно ограничены как по времени жизни системы, так и по числу одновременно доступных кубит. Поэтому реалистичным представляется вариант квантового компьютера, состоящего из небольшого (по памяти) квантового устройства, работающего под управлением классического компьютера. Рассматриваемая нами модель вычислений под названием квантовые ветвящиеся программы, предложенная в [13] и [40], адекватно описывает упомянутые "квантово-классические" вычисления.

В данной работе мы рассматриваем квантовые один раз читающие ветвящиеся программы полиномиальной ширины (квантовые ОВББ, С^ОВОБ), что также соответствует заявленной минимизации квантовых вычислений по времени. Полиномиальная ширина означает логарифмическое ограничение числа кубит для хранения текущего состояния вычислений. Согласно обобщенной нижней оценке из [14], логарифмическое число кубит является асимптотически минимальным для многих важных функций.

Алгебраическое" определение квантовых ветвящихся программ, используемое в диссертации, следует работам [13, 14] и, как было показано в [43], является полиномиально эквивалентным "графовому" определению из [40]. Для выбранного подхода возможно наглядное представление алгоритмов в виде квантовых схем с классическим управлением, описанное в работе [20]. Данный подход позволяет наиболее наглядно и достаточно детально описывать квантовые алгоритмы за счет более четкого вычленения их "элементарных шагов".

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

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

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

Кроме того, рассматривается приложение техники уменьшения вероятности ошибки (probability amplification) к модели квантовых ветвящихся программ. Показано, что, в отличие от классического вероятностного случая, многократные повторы вычислений, нивелирующие вероятность ошибки, можно производить параллельно, а не последовательно.

• Глава 3 описывает предложенный нами метод отпечатков (fingerprinting), ориентированный на. модель квантовых ветвящихся программ. Техника отпечатков представляет входной набор в виде его образа (,fingerprint), сохраняющего некоторое свойство входного набора, и позволяет достоверно проверять это свойство при измерении квантового состояния. Приводится доказательство существования набора необходимых параметров и варианты применения данной техники. Указанный метод в совокупности со схемным представлением квантовых ветвящихся программ используется для построения экономных по памяти квантовых ветвящихся программ и протокола для проверки равенства в некоторой трехсторонней коммуникационной модели (SMP).

• В главе 4 исследуется структура квантовых ветвящихся программ, моделирующих функции из класса NC1 по методу Баррингтона. Приводятся необходимые сведения о результатах Баррингтона, и исследуется структура получаемых ветвящихся программ. Далее, описывается моделирование перестановочных ветвящихся программ квантовыми, что позволяет сделать выводы об их структуре. Данный результат уточняет метод построения эффективных квантовых ветвящихся программ из работы [14] и позволяет сводить исследование классических и квантовых ветвящихся программ константной ширины к исследованию программ, имеющих, соответственно, ширину 5 и 2 и обладающих описанной структурой.

Результаты диссертации были представлены в работах [1], [5], [6], [18], [20], [46], а также на IX международном семинаре "Дискретная математика и ее приложения" (Москва, 2007 г.), на WACC'07 (Workshop on Algebra, Combinatorics and Complexity, Москва, 2007), XV международной конференции "Проблемы теоретической кибернетики" (Казань, 2008), на семинаре при CSR'08 (Москва, 2008), на семинаре ФТИ-АН (Москва, 2008), на семинаре кафедры математической кибернетики МГУ (Москва, 2008), на семинаре кафедры дискретной математики МГУ (Москва, 2009), на семинарах в университете Турку (Финляндия, 2007), на итоговых конференциях Казанского государственного университета и на семинарах по классическим и квантовым вычислениям Казанского государственного университета.

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Васильев, Александр Валерьевич

Заключение

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

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

На основе схемной интерпретации квантовых ветвящихся программ предложен метод отпечатков, позволяющий строить эффективные по памяти квантовые алгоритмы. Техники такого класса (называемые fingerprinting) позволяют вместо исходных объектов (слов в конечном алфавите) рассматривать их компактные образы (отпечатки, fingerprints), сохраняющие искомое свойство входных данных. В результате проверка этого свойства становится вероятностной, и возможна односторонняя ошибка, поэтому отпечатки должны позволять достоверно извлекать информацию о входном наборе. Предложенный нами вариант техники отпечатков позволяет эффективно вычислять такие булевы функции, как проверка равенства двоичных наборов, проверка перестановочности булевой матрицы, булевы варианты функций Periodicity, Semi-Simon, Hidden Subgroup, т.е. функции, которые "сводятся" к проверке равенства. Согласно известной нижней оценке на ширину квантовых OBDD, предлагаемые алгоритмы оказываются оптимальными. Причем в сравнении с известными классическими вероятностными OBDD предлагаемые алгоритмы дают полиномиальное преимущество, а детерминированные аналоги превосходят экспоненциально.

Кроме того, рассматривается конструкция эффективных квантовых ветвящихся программ для всех функций из класса NC1. Основываясь на методе Баррингтона и работе Аблаева, Мура и Поллетта, можно для любой функции из класса NC1 предложить эффективную квантовую ветвящуюся программу. В работе доказано, что эти программы имеют четкую структуру, а именно, являются к раз читающими OBDD ширины 2, причем общий порядок считывания индуктивным образом задается методом Баррингтона. Данный результат позволяет сводить рассмотрение ветвящихся программ константной ширины, имеющих произвольную структуру, к исследованию программ с описанной структурой.

Естественным продолжением наших исследований может стать изучение следующих проблем:

• Определение критерия применимости метода отпечатков.

В каких случаях можно эффективно применить предложенный метод и построить соответствующие отпечатки? Например, известно, что функцию NОп, проверяющую, есть ли во входном наборе две единицы на соседних позициях, можно вычислить, подсчитав число таких пар и проверив, равно ли оно нулю. Однако применение метода отпечатков упирается в сложность вычисления этого свойства входного набора, т.к. требуется запоминать очередную единицу, чтобы проверить наличие пары, а операция стирания запрещена. Эти соображения подтверждаются тем фактом, что реализация функции АЮп в квантовых ОВОБ экспоненциально сложна, что было доказано в [43]. Соответственно, в этом случае метод отпечатков не поможет получить эффективную квантовую ОВОБ.

• Существуют ли проблемы, эффективно разрешимые в модели квантовых ОВБО, но экспоненциально сложные при использовании метода отпечатков?

• Дает ли квантовый метод отпечатков преимущество над классическим вероятностным для некоторой вычислительной задачи? Можно ли получить суперполиномиальное улучшение сложности?

Список литературы диссертационного исследования кандидат физико-математических наук Васильев, Александр Валерьевич, 2009 год

1. Бардзинь, Я.М. Сложность распознавания симметрии на машинах Тьюринга / Я.М. Бардзинь // Проблемы кибернетики. М.: Наука, 1965. - Вып. 15. - С. 245-248.

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

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

4. Васильев, A.B. О функциях, вычислимых булевыми схемами логарифмической глубины и ветвящимися программами специального вида / A.B. Васильев // Дискретный анализ и исследование операций. Серия 1. - 2007. - Т. 14, вып. 3. - С. 31-39.

5. Васильев, А.В. Соотношение классов NC1 и poly-OBDD5 / А.В. Васильев // Материалы IX международного семинара "Дискретная математика и приложения". М.: Изд-во механико-математического факультета МГУ, 2007. - С. 68-71.

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

7. Ежов, А.А. Некоторые проблемы квантовой нейротехнологии / А.А. Ежов // V всероссийская научно-техническая конференция "Нейроинформатика-2003": Лекции по нейроинформатике. Часть 2. М.: МИФИ, 2003. - С. 29-79.

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

9. Манин, Ю.И. Вычислимое и невычислимое / Ю.И. Манин. М.: Сов. радио, 1980. - 128 с.

10. Нильсен, М. Квантовые вычисления и квантовая информация / М. Нильсен, И. Чанг; Пер. с англ. под ред. М.Н. Вялого и П.М. Островского с предисловием К.А. Валиева. М.: Мир, 200G. -824 с.

11. Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. М: Наука, 1986. - 384 с.

12. Ablayev, F. On computational power of quantum branching programs / F. Ablayev, A. Gainutdinova, M. Karpinski // Lecture Notes in Computer Science. Springer-Verlag, 2001. - V. 2138. - P. 59-70.

13. On the computational power of probabilistic and quantum branching programs of constant width / F. Ablayev, A. Gainutdinova, M.

14. Karpinski, C. Moore, C. Pollette // Information and Computation. Elsevier, 2005.

15. Ablayev, F. On the power of randomized ordered branching programs / F. Ablayev, M. Karpinski // Electronic Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc/). TR98-004, 1998.

16. 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.

17. 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.

18. Ablayev, F.M. On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions / F.M. Ablayev, A.F. Khasianov, A.V. Vasiliev // Electronic Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc/). TR08-085, 2008.

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

20. Ablayev, F.M. On the Computation of Boolean Functions by Quantum Branching Programs via Fingerprinting / F.M. Ablayev, A.V. Vasiliev // Electronic Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc/), TR08-059, 2008.

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

22. Construction of a thin set with small Fourier coefficients / M. Ajtai, H. Iwaniec, J. Komlos, J. Pintz, E. Szemercdi // Bulletin of the London Mathematical Society. 1990. - V. 22. - P. 583-590.

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

24. Ambainis, A., Nahimovs N. Improved constructions of quantum automata / A. Ambainis, N. Nahimovs / / http://xxx.lanl.gov/archive/quant-ph. arXiv:0805.1686vl, 2008.

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

26. 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.

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

28. Quantum fingerprinting / H. Buhrman, R. Cleve, J. Watrous J., R. de Wolf // Physical Review Letters. 2001. - 87(16) :167902.

29. Bryant, R. On the complexity of VLSI implementations and graph representations of Boolean functions with applications to integer multiplication / R. Bryant // IEEE Trans. Comput. 40 (2). - 1991. - P. 205-213.

30. 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.

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

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

33. Freivalds, R. Fast probabilistic algorithms / R. Freivalds // FCT'79, LNCS 74 (Berlin, New York). Springer-Verlag, 1979. - P. 57-69.

34. Fürst, M. Parity, circuits, and the polynomial-time hierarchy / M. Fürst, J.B. Saxe, M. Sipser // Math. Systems Theory. 1984. -17:13-27.

35. 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.

36. Katz, N.M. An Estimate for Character Sums / N.M. Katz // Journal of the American Mathematical Society. 1989. - P. 197-200.

37. Khasianov, A. Complexity Bounds On Some Fundamental Computational Problems For Quantum Branching Programs / A. Khasianov. Ph.D. thesis, University of Bonn. - http://nbn-resolving.de/urn:nbn:de:hbz:5N-05696.

38. Moore, C. Quantum automata and quantum grammars / C. Moore, J. Crutchfield // Theoretical Computer Science. 2000. - 237. - P. 275-306.

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

40. Ponzio, S. Restricted branching programs and hardware verification / S. Ponzio. Ph.D. thesis, MIT, 1995. - http://www.eccc.uni-trier.de/eccc/

41. Razborov, A. Constructing small sets that are uniformin arithmetic progressions / A. Razborov, E. Szemeredi, A. Wigderson // Combinatorics, Probability and Computing. 1993. - V.2. - P. 513-518.

42. Sauerhoff, M. Quantum branching programs and space-bounded nonuniform quantum complexity / M. Sauerhoff, D. Sieling // http://xxx.lanl.gov/archive/quant-ph. ph/0403164. - 2004.

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

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

45. Vasiliev, A.V. Functions computable by Boolean circuits of logarithmic depth and branching programs of a special type / A.V. Vasiliev // Journal of Applied and Industrial Mathematics. 2008. - Vol. 2. - No. 4. - P. 585-590.

46. Wegener, I. The Complexity of Boolean Functions / I. Wegener. -Stuttgart: John Wiley & Sons Ltd, and B. G. Teubner, 1987. 458 P

47. Wegener, I. Branching programs and binary decision diagrams / I. Wegener. SI AM Monographs on Discrete Mathematics and Applications, SIAM Press, 2000. - 409 p.

48. Wegener, I. Complexity Theory / I. Wegener. SIAM Monographs on Discrete Mathematics and Applications, Springer, 2005. - 308 p.

49. Yao, A. Some complexity questions related to distributive computing / A. Yao // Proceedings of 11th STOC. 1979. - P. 209-213.

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