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



На правах рукописи УДК 510.5, 519.7

Васильев Александр Валерьевич

Эффективные алгоритмы в модели квантовых ветвящихся программ

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

Автореферат

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

Казань - 2009

.....

003471283

Работа выполнена на факультете вычислительной математики и кибернетики Казанского государственного университета.

Официальные оппоненты: доктор физико-математических наук,

доцент Андрей Анатольевич Вороненко,

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

Ведущая организация: Физико-технологический институт РАН

Защита диссертации состоится 4 июня 2009 года в 14.30 на заседании диссертационного совета Д 212.081.24 при Казанском государственном университете им.В.И.Ульянова-Ленина по адресу: 420008, Казань, ул. Кремлевская, д.18., конференц-зал научной библиотеки им. Н.И.Лобачевского.

С диссертацией можно ознакомиться в научной библиотеке им. Н.И.Лобачевского Казанского государственного университета.

Автореферат разослан ^ ЛойЛ._200^г.

Ученый секретарь специализированного

Совета Д 212.081.24 при КГУ кандидат физико-математических наук, доцент

А.И.Еникеев

Общая характеристика работы

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

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

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

Для модели ветвящихся программ наиболее разработанными являются ограничения на порядок и количество считываний входных переменных. Один раз читающая ветвящаяся программа - это ветвящаяся программа с

тем ограничением, что на каждом вычислительном пути каждая переменная встречается не более одного раза. Дополнительное условие "забывания" требует, чтобы считывание всегда происходило в соответствии с фиксированным порядком переменных. Забывающие один раз читающие ветвящиеся программы (используемые при тестировании сверхбольших интегральных схем) называются упорядоченными бинарными диаграммами решений (Ordered Binary Decision Diagrams, сокращенно OBDD).

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

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

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

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

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

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

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

Цель работы. Разработка методов построения эффективных квантовых ветвящихся программ с ограничениями. Применение этих методов для получения более экономных по памяти алгоритмов вычисления булевых функций по сравнению с классическим случаем.

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

Научная новизна. В диссертации получены следующие новые результаты:

1. Предложено представление квантовых ветвящихся программ в виде квантовых схем из функциональных элементов и адаптирована техни-

ка уменьшения вероятности ошибки для квантовых ветвящихся программ.

2. Разработан квантовый метод отпечатков. Он применен для эффективного вычисления индивидуальных функций, представленных в диссертации.

3. Доказано, что квантовые ветвящиеся программы, вычисляющие функции из известного класса NC1 на одном кубите, являются к раз читающими ветвящимися программами специального вида.

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

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

Публикации. По теме диссертации опубликовано 6 работ, в том числе 1 -в журнале, входящей в Перечень ВАК.

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

Основное содержание работы

В первой главе приводятся основные сведения о детерминированных пвероятностных ветвящихся программах, необходимые для их сравнения с квантовыми аналогами.

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

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

Пусть - d-мерное гильбертово пространство. Разобьем 3íd на прямую сумму двух ортогональных подпространств Uífcceí,t и H?eject, где !Hfccej>t назовем принимающим подпространством, a "Kfeject - отвергающим подпространством. Будем называть базисные состояния |z) £ y^cctpt принимающими, а |г) 6 0ifeject - отвергающими.

Определение 1. Квантовая ветвящаяся программа Q над гильбертовым пространством !Kd есть тройка

Q = (Т, \фо) iMaccept),

где Т есть последовательность из I инструкций: Tj = определяется переменной х^, считываемой на шаге j, и унитарными преобразованиями Uj(Q) и Uj( 1) в пространстве "Kd.

Векторы \ф) € К* называются состояниями (векторами состояний) программы <Э, \фо) 6 есть начальное состояние (2, а Массерь - это проектор на принимающее подпространство "К^^ (т.е. диагональная матрица, определяющая проекционное измерение финального состояния).

Вычисления на входном наборе а = (<71,... ,ап) € {0,1}" происходят следующим образом:

1. (3 начинает вычисления в исходном состоянии \фо);

2. у-ая инструкция <3 считывает переменную х^ и применяет преобразование и^ = [¡¡{а^) к текущему состоянию |ф), переводящее программу в состояние |ф/) = |Ф);

3. Конечным состоянием программы является

4■ После 1-го (последнего) шага вычислений измеряется состояние ¡ф (а)), и набор а принилшется с вероятностью

Шириной квантовой ветвящейся программы <5 называется размерность ё пространства 'К'1, а длиной - число I инструкций в последовательности

Будем говорить, что квантовая ветвящаяся программа <5 точно вычисляет булеву функцию /, если для любого набора а е /-1(1) программа <2 заканчивает свою работу в принимающем состоянии, а для любого а ё /_1(0) программа <3 заканчивает свою работу в отвергающем состоянии, т.е. вероятность получения правильного ответа равна 1.

Говорят, что квантовая ветвящаяся программа <5 вычисляет булеву функцию / с неограниченной ошибкой, если для любого входного набора а б

Ргассерг{<г) = ||Массер{ |фа) \\1.

Т.

{0,1}п выполняется Рг\<2(а) ф /(сг)} < 1/2.

Будем говорить, что квантовая ветвящаяся программа <5 вычисляет булеву функцию / с односторонней ошибкой, если существует е 6 (0,1) такое, что для любого сг £ /-1(1) вероятность принятия этого набора программой С} равна 1, а для любого а € /"'(О) вероятность принятия не превышает е.

В диссертации для описанной выше модели предлагается схемное представление, позволяющее наглядно иллюстрировать алгоритмы и вычленять их этапы.

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

\\Фг) Н I Фя)

ил 1)

0)

1)

ад

Н5Ъ

01(0)

-А

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

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

механики для реализации квантовой ветвящейся программы ширины d (системы с d состояниями) потребуется как минимум log d кубит.

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

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

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

Техника отпечатков. Для решаемой задачи выбираются целое число т > 2 и допустимая погрешность е 6 (0,1). Затем фиксируется t = 2flos((2A)ln2m)l и строится отображение g : {0,1}п —> Z, описывающее некоторое свойство входного набора.

Далее, для произвольного двоичного набора а = сгх... сгп порождается его отпечаток \ha), соединяющий в себе t однокубитных отпечатков

\hi) = COS^|0)+sm^|l>

к) =

¿=1

Другими словами, последний из logi+ 1 кубита в квантовом регистре подвергается t различным преобразованиям параллельно. Такой квантовый па-

раллелизм достигается за счет использования контролируемых операторов Q(Я,), которые применяют вращение Я, к последнему кубиту, если первые logi кубит находились в состоянии |г), а в противном случае применяется тождественное преобразование /.

Предлагаемая техника нацелена на достоверное распознавание равенства нулю значения д(а). Для этого параметры fc; е {1,..., m -1} для всех г =l,t выбираются специальным образом, исходя из следующего определения.

Определение 3. Множество параметров К — {ku...,kt} называется "хорошим" для целого Ьф 0 mod тп, если для некоторого е € (0,1)

1 Лг^ 2тгЩ2

)<е'

Левая часть неравенства при b — д(а) соответствует квадрату амплитуды базисного состояния |0)x logt |0) после применения оператора Я'?1ое! 01 к отпечатку \ha). Неформально, такое множество гарантирует, что вероятность ошибки будет ограничена величиной е.

Приводится доказательство существования набора необходимых параметров, которое позволяет ограничить вероятность ошибки на всех наборах, где д(и) ф 0 mod т:

Лемма 1. Существует множество К, где 1^1 = i = 2i1°g((2/e)in2m)1< которое является "хорошим" для всех целых Ьф 0 mod т.

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

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

Функция MODm, равная 1 тогда и только тогда, когда число единиц во входном наборе кратно т, где т> 2- целое число.

Предложенная нами квантовая OBDD имеет ширину порядка log тп, тогда как в детерминированном случае для вычисления данной функции требуется ширина как минимум т.

Функция MOD'm отличается от MODm только тем, что входной набор интерпретируется как двоичное число. Поэтому для нее справедливы те же оценки сложности.

Функция проверка равенства:

EQn(xi,...,xn,yu...,yn) = 1 тогда и только тогда, когда х{ = у,-для всех г = 1,п, т.е. проверяется равенство чисел хну, заданных соответствующими двоичными последовательностями.

При наихудшем порядке считывания детерминированная OBDD для данной функции потребует ширины как минимум 2п, в то время как предложенная нами квантовая OBDD при любом порядке считывания имеет ширину 0(п).

Функция проверка симметрии задается следующим образом:

Palindromen(xi,...,х„) = 1 Х\Х2 ■ • - — XnXn-i . . . Х|"пу2"]+1*

Т.к. данная функция по существу является проверкой равенства, для нее справедливы оценки сложности функции EQn.

Функция проверка периодичности, определяемая для целого положительного параметра s следующим образом:

Period°(xо,... ,xn-i) = 1 тогда и только тогда, когда хi = ij+smodn для всех г = 0, п — 1.

Метод отпечатков позволяет построить квантовую OBDD для данной функции, имеющую ширину О(п).

• Функция Semi-Simon, определяемая для целого положительного параметра 5 следующим образом:

Semi-Simonsn(xo,..., хп-\) = 1 тогда и только тогда, когда х,- = для всех г = 0, п — 1 (здесь ф - это побитовое сложение по модулю 2).

Для данной функции также удалось построить квантовую OBDD ширины О(п).

• Функция PERMn проверяет, является ли булевская пхп матрица перестановочной, т.е. содержащей ровно одну единицу в каждой строчке и каждом столбце.

Известно, что асимптотическая нижняя оценка ширины любой детер-

минированной OBDD, вычисляющей данную функцию, есть 2пп~1/2 независимо от порядка считывания переменных. Сложность данной функции в классическом вероятностном случае равна О(n4 log п). Наш алгоритм дает квантовую ветвящуюся программу ширины 0(тгlogп). Учитывая, что известная нижняя оценка в квантовом случае асимптотически равна п — log ri, предложенный алгоритм почти оптимален.

• Булевский вариант задачи о скрытой подгруппе:

Функция HSPg,k(xi, ■ ■ ■ 1 = 1 тогда и только тогда, когда /, закодированная входным набором, "скрывает" подгруппу К в группе G.

При помощи метода отпечатков можно вычислить данную функцию квантовой OBDD ширины 0(п).

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

В заключение рассматривается применение предложенного подхода для вычисления функции голосования MAJORITYn на одном кубите, а также для решения проблемы равенства в трехсторонней коммуникационной модели (simultaneous message passing model, SMP) без общего ключа.

В четвертой главе исследуется структура однокубитных квантовых ветвящихся программ, моделирующих функции из известного класса КС1.

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

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

В работе приводятся необходимые сведения о результатах Баррингтона, и исследуется структура получаемых ветвящихся программ. Далее, описывается моделирование перестановочных ветвящихся программ квантовыми, что позволяет сделать выводы об их структуре. А именно, показано, что они являются к = п0^ раз читающими квантовыми ветвящимися программами, причем порядок считывания рекурсивно задается конструкцией Баррингтона. Данный результат уточняет метод построения эффективных квантовых ветвящихся программ для функций из класса КС1 и позволяет сводить исследование классических и квантовых ветвящихся программ константной ширины к исследованию программ, имеющих соответственно ширину 5 и 2 и обладающих описанной структурой.

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

Публикации по теме диссертации Работа [1] опубликована в журнале, входящем в Перечень ВАК.

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

2. Аблаев, Ф.М. О вычислениях в квантовых ветвящихся программах методом "характерных признаков" / Ф.М. Аблаев, А.В. Васильев // Ма-

_тер и алы XV Международной конференции Проблемы теоретической

кибернетики (Казань, Россия, 2-7 июня, 2008). - Казань: Изд-во "Отечество", 2008. - С. 1.

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

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

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

6. 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. 58.5-590.

Лицензия на полиграфическую деятельность №0128 от 08.06.98г. выдана Министерством информации и печати Республики Татарстан Подписано в печать 29.04.2009 г. Форм. бум. 60x84 1/16. Печ. л. 1. Тираж 100. Заказ 95.

Минитипография института проблем информатики АН РТ 420012, Казань, ул. Чехова, 36.

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

Введение

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]. Соответственно, в этом случае метод отпечатков не поможет получить эффективную квантовую ОВОБ.

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

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

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.