На правах рукописи

УДК 510.5, 519.7

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

Эффективные алгоритмы в модели

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

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

Автореферат

диссертации на соискание ученой степени

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

Казань – 2009

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

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

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

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

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

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

Автореферат разослан 200 г.

Ученый секретарь диссертационного Совета Д 212.081.24 при КГУ кандидат физико-математических наук, А.И.Еникеев доцент

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

Вычислительные задачи рассматриваАктуальность темы исследования.

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

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

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

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

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

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

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

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

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

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

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

Разработка методов построения эффективных квантовых Цель работы.

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

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

матики, математической кибернетики, теории вероятностей и теории чисел.

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

Научная новизна.

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

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

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

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

Результаты диссертации представлены на российских Апробация работы.

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

По теме диссертации опубликовано 6 работ, в том числе 1 – Публикации.

в журнале, входящем в Перечень ВАК.

Структура и объем работы.

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

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

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

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

Пусть Hd – d-мерное гильбертово пространство. Разобьем Hd на прямую сумму двух ортогональных подпространств Haccept и Hreject, где Haccept наd d d зовем принимающим подпространством, а Hreject – отвергающим подпроd странством. Будем называть базисные состояния |i Haccept принимаюd щими, а |i Hreject – отвергающими.

Определение 1. Квантовая ветвящаяся программа Q над гильбертовым пространством Hd есть тройка где T есть последовательность из l инструкций: Tj = xij, Uj (0), Uj (1) определяется переменной xij, считываемой на шаге j, и унитарными преобразованиями Uj (0) и Uj (1) в пространстве Hd.

Векторы | Hd называются состояниями (векторами состояний) программы Q, |0 Hd есть начальное состояние Q, а Maccept – это проектор на принимающее подпространство Haccept (т.е. диагональная матd рица, определяющая проекционное измерение финального состояния).

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

1. Q начинает вычисления в исходном состоянии |0 ;

2. j-ая инструкция Q считывает переменную xij и применяет преобразование Uj = Uj (ij ) к текущему состоянию |, переводящее программу Q в состояние | = Uj (xij ) | ;

3. Конечным состоянием программы является 4. После l-го (последнего) шага вычислений измеряется состояние |(), и набор принимается с вероятностью Шириной квантовой ветвящейся программы Q называется размерность d пространства Hd, а длиной – число l инструкций в последовательности Будем говорить, что квантовая ветвящаяся программа Q точно вычисляет булеву функцию f, если для любого набора f 1 (1) программа Q заканчивает свою работу в принимающем состоянии, а для любого f 1 (0) программа Q заканчивает свою работу в отвергающем состоянии, т.е. вероятность получения правильного ответа равна 1.

Говорят, что квантовая ветвящаяся программа Q вычисляет булеву функцию f с неограниченной ошибкой, если для любого входного набора {0, 1}n выполняется P r[Q() = f ()] < 1/2.

Будем говорить, что квантовая ветвящаяся программа Q вычисляет булеву функцию f с односторонней ошибкой, если существует (0, 1) такое, что для любого f 1 (1) вероятность принятия этого набора программой Q равна 1, а для любого f 1 (0) вероятность принятия не превышает.

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

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

Здесь xj1,..., xjl – последовательность переменных (необязательно различных), обозначающих классические управляющие сигналы, а |i образуют регистр квантовых бит (кубит). Согласно принятой в литературе по квантовым схемам нотации, классическая информация обозначается на схеме двойными проводами, а квантовая – одиночными.

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

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

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

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

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

Техника отпечатков.

и допустимая погрешность (0, 1). Затем фиксируется t = 2 log((2/ ) ln 2m) и строится отображение g : {0, 1}n Z, описывающее некоторое свойство входного набора.

Далее, для произвольного двоичного набора = 1... n порождается его отпечаток |h, соединяющий в себе t однокубитных отпечатков hi :

Другими словами, последний из log t + 1 кубита в квантовом регистре подвергается t различным преобразованиям параллельно. Такой квантовый параллелизм достигается за счет использования контролируемых операторов Ci (Ri ), которые применяют вращение Ri к последнему кубиту, если первые log t кубит находились в состоянии |i, а в противном случае применяется тождественное преобразование I.

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

Определение 3. Множество параметров K = {k1,..., kt } называется “хорошим” для целого b = 0 mod m, если для некоторого (0, 1)