Содержание к диссертации
Введение
1 Предварительные сведения 15
1.1 Детерминированные ветвящиеся программы 15
1.1.1 Определения 15
1.1.2 Связь с другими моделями вычислений 17
1.2 Вероятностные ветвящиеся программы 19
1.2.1 Определения 19
1.2.2 Уменьшение вероятности ошибки 20
1.2.3 Метод Fingerprinting 21
2 Квантовые ветвящиеся программы 23
2.1 Основы квантовых вычислений 23
2.2 Определение квантовых ветвящихся программ 32
2.3 Эффективные квантовые ветвящиеся программы 35
2.4 Схемное представление 36
2.5 Уменьшение вероятности ошибки 37
2.6 Связь с другими схемными моделями вычислений . 40
3 Квантовый метод отпечатков 42
3.1 Квантовый метод отпечатков 42
3.1.1 Существование "хорошего" множества параметров 44
3.1.2 Конструктивные методы построения "хорошего" множества параметров 46
3.1.3 Варианты использования техники отпечатков . 48
3.2 Вычисление функции MODm 52
3.2.1 Вычисление функции MOD'm 55
3.3 Квантовая OBDD для проверки равенства и сводимых к ней функций 57
3.3.1 Понятие сводимости 57
3.3.2 Проверка равенства 58
3.3.3 Проверка, симметрии 61
3.3.4 Проверка периодичности 62
3.3.5 Функция Semi-Simon 64
3.4 Квантовая OBDD для проверки перестановочности матрицы 65
3.5 Квантовая OBDD для задачи о скрытой подгруппе . 69
3.5.1 Доказательство верхней оценки сложности . 71
3.6 Вычисление функции голосования на одном кубите . 74
3.7 Проблема равенства в коммуникационной модели SMP 76
3.8 Упрощенный метод отпечатков 80
4 Моделирование функций из NC1 квантовыми fc-OBDD 84
4.1 Перестановочные ветвящиеся программы 85
4.2 Результаты Баррингтона 87
4.3 Моделирование NC1 квантовыми &-OBDD 92
Заключение 96
Литература 99
- Связь с другими моделями вычислений
- Связь с другими схемными моделями вычислений
- Конструктивные методы построения "хорошего" множества параметров
- Моделирование 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(\ogn) кубит, где п -длина входного набора) вычисление многих функций оказывается затруднено, а соответствующие задачи в таких моделях с ограничениями могут иметь экспоненциальную сложность [43].
Отметим, что разработка квантовых компьютеров ставит множество задач как для математиков, так и для инженеров. Причем обе категории исследователей движутся навстречу друг другу: одни разрабатывают быстрые и эффективные по памяти квантовые алгоритмы, а вторые продвигаются в создании полномасштабных квантовых вычислителей, способных устойчиво работать достаточно продолжительное время.
Однако на данный момент вычислители сильно ограничены как по времени жизни системы, так и по числу одновременно доступных кубит. Поэтому реалистичным представляется вариант квантового компьютера, состоящего из небольшого (по памяти) квантового устройства, работающего под управлением классического компьютера. Рассматриваемая нами модель вычислений под названием квантовые ветвящиеся программы, предложенная в [13] и [40], адекватно описывает упомянутые "квантово-классические" вычисления.
В данной работе мы рассматриваем квантовые один раз читающие ветвящиеся программы полиномиальной ширины (квантовые OBDD, QOBDD), что также соответствует заявленной минимизации квантовых вычислений по времени. Полиномиальная ширина означает логарифмическое ограничение числа кубит для хранения текущего состояния вычислений. Согласно обобщенной нижней оценке из [14], логарифмическое число кубит является асимптотически минимальным для многих важных функций.
"Алгебраическое" определение квантовых ветвящихся программ, используемое в диссертации, следует работам [13, 14] и, как было показано в [43], является полиномиально эквивалентным "графовому" определению из [40]. Для выбранного подхода возможно наглядное представление алгоритмов в виде квантовых схем с классическим управлением, описанное в работе [20]. Данный подход позволяет наиболее наглядно и достаточно детально описывать квантовые алгоритмы за счет более четкого вычленения их "элементарных шагов".
В рамках построения эффективных квантовых алгоритмов, в основном в модели квантовых ветвящихся программ, нами был предложен вариант техники отпечатков (в англоязычной литературе называемый "fingerprinting"), позволяющий строить надежные и экономные по памяти квантовые алгоритмы. На основе данного метода, ориентированного на квантовые модели вычислений с классическим управлением (квантовые ветвящиеся программы, квантовые автоматы и т.п.), нами разработаны эффективные квантовые алгоритмы для булевых функций, которые "сводятся" к проверке равенства.
Основные результаты диссертации в области построения эффективных квантовых алгоритмов в модели квантовых ветвящихся программ:
В главе 2 предлагается схемное представление квантовых ветвящихся программ, позволяющее наглядно иллюстрировать алгоритмы и вычленять их этапы. Мы исходим из того, что квантовые ветвящиеся программы можно рассматривать как схемы из функциональных элементов, дополненные возможностью классического управления, т.е. каждый унитарный оператор применяется или не применяется в зависимости от значения соответствующего классического бита.
Кроме того, рассматривается приложение техники уменьшения вероятности ошибки (probability amplification) к модели квантовых ветвящихся программ. Показано, что, в отличие от классического
вероятностного случая, многократные повторы вычислений, нивелирующие вероятность ошибки, можно производить параллельно, а не последовательно.
Связь с другими моделями вычислений
"Алгебраическое" определение квантовых ветвящихся программ, используемое в диссертации, следует работам [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), на итоговых конференциях Казанского государственного университета и на семинарах по классическим и квантовым вычислениям Казанского государственного университета.
Связь с другими схемными моделями вычислений
Векторы называются состояниями (векторами состояний) программы Q, \фо) Є 0i.d есть начальное состояние Q, a Maccept -это проектор на принимающее подпространство ЇК . (т.е. диагональная матрица, определяющая проекционное измерение финального состояния).
Вычисления на входном наборе a = ( JI, .... ап) Є {0,1}п происходят следующим образом: 1. Q начинает вычисления в исходном состоянии \фо); 2. j-ая инструкция Q считывает переменную х и применяет преобразование Uj = Ujfaj) к текущему состоянию \ф), переводящее программу Q в состояние \ф ) = Uj{xi) \ф); 3. Конечным состоянием программы является 4- После 1-го (последнего) шага вычислений измеряется состояние Q, и набор а принимается с вероятностью РТассерМ) = {ФаМІссері \ Массеріфа) = Moccept \фа) \\\. Шириной квантовой ветвящейся программы Q называется размерность d пространства 3id: а длиной - число I инструкций в последовательности Т. Будем говорить, что квантовая ветвящаяся программа Q точно вычисляет булеву функцию /, если для любого набора а /_1(1) программа Q заканчивает свою работу в принимающем состоянии, а для любого а Є /-1(0) программа Q заканчивает свою работу в отвергающем состоянии, т.е. вероятность правильного ответа равна 1. Будем говорить, что квантовая ветвящаяся программа Q вычисляет булеву функцию f с неограниченной ошибкой, если для любого входного набора а Є {0,1}п выполняется Pr[Q(a) ф /(о-)] 1/2. Говорят, что квантовая ветвящаяся программа Q вычисляет булеву функцию f с ограниченной ошибкой, если существует є Є (0,1/2) такое, что для любого входного набора а Є {0,1}п вероятность ошибки не превосходит є, т.е. В частности, говорят, что квантовая ветвящаяся программа Q вычисляет булеву функцию f с односторонней ошибкой, если существует є Є (0,1) такое, что для любого а Є /_1(1) вероятность принятия этого набора программой Q равна 1, а для любого о Є /"1(0) вероятность принятия не превышает б. Заметим, что это модель с одним измерением ("measure-once"), аналогичная модели конечных квантовых автоматов в работе [38], в которой состояние системы изменяется унитарным образом за исключением финального измерения состояния. Квантовые один раз читающие ветвящиеся программы. Определение 2.2.2. Квантовая ветвящаяся программа Q называется QOBDD или один раз читающей квантовой ветвящейся программой, если каждая переменная х Є {х\,... ,хп]- появляется в последовательности инструкций Т программы Q не более одного раза. Т.к. для квантовых ветвящихся программ порядок считывания переменных на всех вычислительных путях один и тот же, данное определение согласуется с формулировкой понятия OBDD в терминах графов. Обозначим через QOBDD класс функций, представимых квантовыми OBDD полиномиальной ширины. Квантовые к раз читающие ветвящиеся программы. Определение 2.2.3. Квантовая ветвящаяся программа Q называется k-QOBDD или к раз читающей QOBDD, если ее можно разбить на к последовательных подпрограмм, каждая из которых будет QOBDD. Причем для каждой подпрограммы порядок считывания переменных один и тот же.
По определению квантовых ветвящихся программ унитарные операторы, используемые в инструкциях, могут быть произвольными, в том числе решающими NP-трудные задачи. Поэтому разумным ограничением является полиномиальная по времени конструируемость этих преобразований, т.е. они должны быть представимы в виде произведения не более чем полиномиального числа "элементарных" унитарных операторов из некоторого конечного базиса (например, из "стандартного" базиса {#,S,CNOT,7r/8}, см. [11]). В силу вышесказанного эффективными будем называть те квантовые ветвящиеся программы, ширина и длина которых не превосходит no{i) т.к. при ограничении ширины п0( число кубит, задействованных в вычислениях, составляет q = O(logn), каждое унитарное преобразование такой программы можно представить в виде произведения 0(q2Aq) = п0 (т.е. полиномиального числа) "элементарных" операторов. Поэтому полиномиальное ограничение на ширину и длину программы влечет и полиномиальную сложность используемых унитарных преобразований.
В данной работе мы ограничиваемся рассмотрением эффективных квантовых один раз читающих ветвящихся программ. Предлагаемые нами методы построения эффективных квантовых алгоритмов в модели квантовых ветвящихся программ опираются на их схемное представление. А именно, квантовая ветвящаяся программа рассматривается как квантовая схема, дополненная возможностью считывать классические биты в качестве контролирующих для унитарных операторов. Таким образом, любая квантовая схема есть квантовая ветвящаяся программа, которая существенно не зависит от своих классических входов.
Конструктивные методы построения "хорошего" множества параметров
Заметим, что приведенная квантовая OBDD не зависит от порядка считывания переменных, т.к. используемые в процессе вычислений вращения коммутируют. Соответственно, можно предложить аналогичную программу для произвольного порядка считывания.
Задача распознавания симметрии входного набора была одной из первых индивидуальных функций, для которой удалось получить квадратичную нижнюю оценку временной сложности при вычислении на детерминированной машине Тьюринга [2]. В данной работе мы рассматриваем вычисление данной функции методом отпечатков в модели квантовых ветвящихся программ.
Рассмотрим функцию Palindromen{xi,..., хп), проверяющую, является ли входной набор палиндромом, т.е. при прочтении в обратном порядке дает исходное слово. Определение 3.3.4. Palindromen(xi, ..., хп) = 1 тогда и только тогда, когда {х\Х2 . хп) = („#„_! . . . Х\), или, что эквивалентно, когда
Непосредственно из определения видно, что вычисление функции Palindromen сводится к алгоритму для EQn т.к. Palindromen{xi,..., xn) = QL/2J Оіж2 ... х[п/21, хпхп-г... Z[-n/2-+i), т.е. Palindromen rop EQn. Следовательно, справедлива следующая теорема. Теорема 3.3.2. Для любого є Є (О, 1) существует квантовая OBDD, вычисляющая функцию Palindromen с односторонней ошибкой є и имеющая ширину 0{п). Доказательство. Доказательство данного результата повторяет доказательство теоремы 3.3.1 с единственным отличием в определении операторов Rij\ Для некоторого целого положительного параметра s определим функцию Period(xo,... ,хп-\), проверяющую периодичность входного набора. Определение 3.3.5. Period{x0, . . . ,xn-i) = 1 тогда и только тогда, когда х\ = Xi+S mod п для всех г = О, п — 1. Заметим, что Period (x0,..., а:п г) = 1 тогда и только тогда, когда совпадают последовательности (х0, х\,..., аг„_а,... ГЕП-І) И (xs, ж6-+і,..., XQ, ... #s_i), т.е. проверка периодичности сводится к проверке равенства: Period (x0l..., xn-i) = EQn(x0, жъ ..., xn-i,x3, xs+i,..., жв_і), т.е. Period proj EQn. Однако, из этого непосредственно не вытекает существование эффективной квантовой OBDD для Period . Тем не менее, согласно следующей теореме, приведенную ветвящуюся программу для функции EQn можно перестроить в программу для Period . Теорема 3.3.3. Для любого є Є (0,1) существует квантовая OBDD. вычисляющая функцию Period с односторонней ошибкой е и имеющая ширину 0(п). Доказательство. Для доказательства данного утверждения используется квантовая OBDD для функции EQn с заменой операторов вращения на Другими словами, каждая переменная Xj = 1 будет учитываться дважды: в j-ы разряде со знаком плюс и со знаком минус в разряде (j — s modn). Следовательно, после прочтения всего входного набора будет осуществлен поворот на угол, пропорциональный Заметим, что g(x) проверяет равенство нулю целых чисел, соответствующих последовательностям (XQ, Х\, ..., xn-s,... а;т;_і) и (xs, xs+i, ..., XQ, ... xs-i), поэтому g(x) = 0 тогда и только тогда, когда Period (x) = 1. Таким образом, метод отпечатков дает возможность проверить СІЮОЙ-ство входного набора, кодируемое отображением д(х), с односторонней ошибкой е. Пусть задан целочисленный параметр s (0,п]. Определим функцию Semi-Simonbn следующим образом. Определение 3.3.6. Semi-Simon (xo,..., xn-i) = 1 тогда и ггго гъко тогда, когда Xj = xi$s для всех і — О, п — 1. Здесь ф — это побитовое слоэюение по модулю 2, позтоліу , us трактуются и как натуральные числа, и как двоичные последовсгтгге.ль-ности, представляющие эти числа. По аналогии с функцией Period можно заметить, что вычисление Semi-Simon (xQ,..., жп-і) сводится к проверке равенства последователь-ностей (XQ, Х\, . . . , Xi, . . , Хп— і) и (xs, xsi,..., xsj,... rcs(rc-i))- Следовательно, В общем случае это не гарантирует эффективной вычислимости Semi-Simonsn, однако следующая теорема показывает, как можно модифицировать квантовую OBDD, вычисляющую EQn, для получения эффективного алгоритма для функции Semi-Simonsn. Теорема 3.3.4. Для любого є Є (0,1) и всех s Є (0, гг] сущееггызует квантовая OBDD, вычисляющая функцию Semi-Simon с односторонней ошибкой є и имеющая ширину 0(п).
Моделирование NC1 квантовыми &-OBDD
Известный результат статьи [3] позволяет моделировать схемы из класса NC1 ветвящимися программами константной ширины, используя коммутаторы подстановок из группы S . В работе [5] была проанализирована структура получаемых программ и показано, что они являются fc-OBDD, где к = п(1\ В статье [14] предлагается моделирование конструкции Баррингтона на 1 кубите в квантовых ветвящихся программах, что позволяет представить любую функцию из NC1 1-кубитной квантовой (n)-OBDD.
Баррингтоном была предложена следующая конструкция: произвольной схеме из конъюнкторов и инверторов ставилась в соответствие перестановочная ветвящаяся программа, состоящая из последовательности инструкций, выдающих одну из двух подстановок из А Є S , в зависимости от значения считываемой переменной. Такая программа выдает ответ 0, если композиция выданных подстановок есть тождественная подстановка id Є А5, и единицу в противном случае. В основе индуктивного построения такой программы лежит моделирование конъюнкции при помощи четырех инструкций следующего вида: (xivri,id), (xt2,T2,id), (xi r id), (a r-f1, ). Другими словами, при хн = ХІ2 = 1 выдается последовательность подстановок , а в остальных случаях выдается последовательность, выроЖгСг ахоща-яся в тождественную подстановку. Для моделирования отрицан с___5ї необходимо лишь модифицировать последнюю инструкцию програмі хдьі
Для метода Баррингтона существенным моментом является &=з:споль-зование неразрешимой группы, что позволяет на каждом шаг выбирать такие элементы т\ и тг, что их коммутатор г1Г2Г1_1г2-1 не : ырож-дается в тождественную подстановку. Данный результат обобщается па случай произвольной неасгіЗ елевой группы. В частности, программы над группой двумерных уш-ц- ц-арных преобразований также могут вычислять все функции из NC3- что и было доказано в статье [14]. При описании результатов Баррингтона будем опираться гл ь монографию [47]. Для формулировки теоремы, на которую опирается данная paSi ота, потребуется определение специального типа ветвящихся програмісті. Пусть Sn - это группа подстановок n-й степени с композиц зіей подстановок в качестве групповой операции. Определение 4.1.1. Назовем подстановку т Є S$ 5-циклс лл, если T{{J) ф 3 для і Є {1,..., 4} и j Є {1,..., 5}, т.е. если она cocr- ъоит из единственного цикла длины 5. Будем представлять такие посЗ?с танов-ки строками вида (0.10,20.3(24(), где T(OJ) = аг+і при і 4 и r(czz-5) = а\. Определение 4.1.2. Перестановочную ветвящуюся npoepaMJV- y (ПВП) ширины к и длины (или глубины) I будем задавать послед}сз зателъ-ностъю инструкций вида {xj(i),gi,hj), где Xj ) - одна из пер sjvtewmx {#1,... ,хп], gi, hi Є Sk для всех 1 і І. Такая ПВП содер н2.ига уровнях 1 г 1 + 1 по к вершин vhi,..., Vi . Ha уровне г = 1,..., / реализуется подстановка О І(Х) — gi, если Xj = 0, в противном случае o i(x) = hi, т.е. для всех 1 га к два ребра, помеченные 0 и 1, ведут из вершины Vi m к вершинам Vi+it9.(m-) и Уі+іг}ц(т) соответственно. Последний (1+1)-ый уровень содержит конечные вершины, отображающие результаты вычислений. ПВП на входном наборе х вычисляет композицию подстановок а(х) = о і(х)о 2(х).. .СТІ(Х) Є Sk Говорят, что ПВП вычисляет функцию /п Є Вп посредством подстановки г, если а(х) = id для х Є f l(0) и о {х) — т ф id для х Є / (1). Следующее свойство устанавливает связь перестановочных и стандартных ветвящихся программ. Пусть G - перестановочная ветвящаяся программа ширины к и длины I, вычисляющая некоторую функцию /. Тогда сушрствует стандартная ветвящаяся программа ширины к и длины к I, вычисляющая ту э/се самую функцию. Доказательство. Для каждой из к вершин на первом уровне ПВП построим ветвящуюся программу ширины к и длины I: все вершины на уровне і помечаются переменной Xj , а ребра на следующий уровень соответствуют подстановкам g и / , т.е. ведут из вершины vim к верши нам Vi+i}9i(m) и vi+ijH(rn) соответственно. Вершины на последнем уровне заменяются конечными, а именно: в r-той ветвящейся программе т{г) тая вершина последнего уровня заменяется на 1, остальные на 0. Полу ченная ветвящаяся программа вычисляет 1 тогда и только тогда, когда a(x)(r) = т(г). Таким образом, f(x) — 1 тогда и только тогда, когда все построенные ветвящиеся программы вычисляют 1, т.е. о (х) — т. Для получения конечного результата достаточно соединить ветвящие ся программы следующим образом: единичная конечная вершина г-той программы заменяется на начальную вершину (г + 1)-ой программы и так далее. Итоговая ветвящаяся программа сохраняет ширину k, а длина увеличивается до к В данном подразделе приводится теорема Баррингтона, построения которой имитируют работу функционального элемента AND, используя коммутаторы подстановок. В результате для схемы из функциональных элементов глубины d индуктивно вырабатывается ПВП длины 4d, вычисляющая ту же функцию, что и исходная схема. Это означает, что для любой функции из NC1 существует ПВП полиномиальной длины, ее вычисляющая.
Похожие диссертации на Эффективные алгоритмы в модели квантовых ветвящихся программ
