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

Чтобы закончить доказательство в этом случае, осталось проверить, что . Это почти очевидно. Мы должны проверить протокол некоторой НМТ, работающей за полиномиальное время. Это займет нас примерно на то же время (совершенно незачем смотреть на одну ячейку экспоненциально долго).

Опр. 2.2 опр. 2.1. Пусть есть из определения 2.2. Построим для определения 2.1. Она работает в два этапа.

Вначале недетерминированно пишет (который в силу определения 2.2 существует для любого слова , для которого ). Говорят еще, что "отгадывает" ("guesses") . Более точно это означает, что находит правый конец входного слова, сдвигается еще на одну ячейку вправо, записывает в нее , еще раз сдвигается вправо и переходит в такое недетерминированное состояние, в котором она пишет один из символов на ленту, сдвигается вправо и выбирает между сохранением этого состояния и переходом в (уже детерминированное) состояние начала следующего этапа.

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

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

Определение 2.3. Имеются два персонажа: король A rthur (Артур), умственные способности которого полиномиально ограничены, и волшебник M erlin (Мерлин), который интеллектуально всемогущ и знает правильные ответы на все вопросы. Король A интересуется некоторым свойством (например, "есть ли у графа гамильтонов цикл"), а волшебник M хочет, чтобы король признал наличие этого свойства (ну, скажем, граф стремится к званию гамильтонова и дал M взятку). A не доверяет своему волшебнику, зная его корыстолюбие, и хочет иметь возможность самостоятельно проверить предложенный M ответ.

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

В этих терминах определение класса NP можно сформулировать так: свойство принадлежит классу NP, если у Артура есть полиномиальный способ проверять убедительность доводов Мерлина, причем:

у M есть способ убедить A в этом;

как бы M ни изощрялся, A не поверит, что .

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

Тема 2.2 Сводимость и NP-полнота

Сложность вычисления предикатов можно сравнивать, пользуясь следующим определением.

Определение 2.4. Сводимость по Карпу. Предикат сводится к предикату (обозначение ), если существует такая функция , что .

Сводимость по Карпу также называют полиномиальной сводимостью, а часто -- просто сводимостью.

Лемма 2.1. Пусть . Тогда

.

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

Пункт 2 следует из пункта 1.

Пункт 3 также прост. Его можно объяснять по-разному. Например, так: Мерлин сообщает Артуру (длина которого ограничена некоторым полиномом от длины , поскольку ) и слово , которое убеждает Артура в том, что . Артур также может проверить, что ему действительно сообщено . Используя определение 2.2, можно написать цепочку эквивалентностей



Полином в последнем выражении -- это композиция полиномов и .

Определение 2.5. Предикат называется NP- полным, если любой предикат из к нему сводится.

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

NP-полные предикаты существуют, приведем примеры.

Выполнимость. Задается предикатом

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

Теорема 2.2 (Кук, Левин). 1) ; 2) -- NP- полна.

Если , то .

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

2) Пусть предикат из NP, который нужно свести к , имеет вид

.

Рассмотрим таблицу вычисления (см. доказательство теоремы 1.2) для МТ, вычисляющей (входом является пара ). Будем использовать те же переменные, что и в доказательстве теоремы 1.2 (коды состояний клеток таблицы вычисления). Чтобы таблица вычисления соответствовала правильно проведенному успешному (с ответом "да") вычислению, должны выполняться локальные правила согласования для каждой четверки клеток видаи результат должен быть "да". Каждое такое правило задается формулой от переменных, отвечающих либо рассматриваемой четверке, либо нулевой ячейке самой нижней строки таблицы. Определим формулу как конъюнкцию всех этих формул, в которые подставлены значения переменных, кодирующих вход , дополненный символами до длины . Значения, соответствующие и , -- константы, поэтому переменные, от которых зависит эта формула, отвечают и кодам внутренних ячеек таблицы. Так что можно считать, что формула зависит от и еще от каких-то переменных, которые мы обозначим .

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

Другие примеры NP-полных задач получаются с помощью следующей леммы.

Лемма 2.2. Если и , то -- NP-полная. И вообще, если -- NP-полная, и , то -- NP-полная.

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

3-КНФ. Задается предикатом

есть 3-КНФ, которая истинна истинна при некоторых значениях переменных. 3-КНФ -- это конъюнкция дизъюнкций, каждая из которых содержит три литерала.

также NP-полна. Это устанавливается сведением к ней .

Теорема 2.3. .

Доказательство. Сопоставим любой схеме в стандартном базисе такую 3-КНФ, выполнимость которой равносильна тому, что вычисляемая схемой функция не равна тождественно 0. В эту КНФ будут входить все переменные схемы ( и -- используем те же обозначения, что и в определении схемы). Для этого построим вначале конъюнкцию условий, означающих, что каждая из вспомогательных переменных имеет значение, соответствующее правой части присваивания . Есть три типа таких условий (они соответстуют трем базисным функциям), и каждый можно записать в виде 3-КНФ:

Подставляя эти 3-КНФ в , получим 3-КНФ . Искомая 3-КНФ имеет вид . Действительно, истинность равносильна утверждению: все присваивания выполнены правильно и в результате получилась 1 ( ). Значит, если при каких-то значениях переменных схема выдает 1, то выполнима, и наоборот.

Еще один простой пример сведения.

Задача ЦЛП (целочисленного линейного программирования). Дана система линейных неравенств с целыми коэффициентами. Есть ли у нее целочисленное решение? (Другими словами, совместна ли система?)

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

Сведем теперь 3-КНФ к ЦЛП. Построим по 3-КНФ систему линейных неравенств. Целочисленных переменных возьмем столько же, сколько есть булевых переменных. Булевой переменной сопоставим выражение . Отрицанию переменной сопоставим выражение . Каждой дизъюнкции ( -- литералы) сопоставим неравенство , в котором , , -- выражения, сопоставленные литералам дизъюнкции.

Искомая система содержит для всех неравенства , а также все неравенства, сопоставленные дизъюнкциям из КНФ. Очевидно, что выполнимость 3-КНФ равносильна совместности такой системы.

Замечание 2.4. Если не требовать целочисленности решений, то проверить совместность системы линейных неравенств можно за полиномиальное время.

Обширный список NP-полных задач содержится в книге Гэри и Джонсона [3]. Как правило, их NP-полнота доказывается с помощью сведений. Приведем несколько примеров NP-полных задач.

3-раскраска. Дан граф. Спрашивается, можно ли раскрасить его вершины в три цвета так, чтобы концы каждого ребра были покрашены в разные цвета. (Аналогичная задача 2-раскраска решается за полиномиальное время.)

Клика. Даны граф и число . Спрашивается, есть ли -элементное множество вершин графа, любые две вершины которого соединены ребром.

Задачи

Докажите, что задача проверки выполнимости 2-КНФ (конъюнкции дизъюнкций, каждая из которых содержит два литерала) принадлежит P.

Докажите, что задача об эйлеровом пути в неориентированном графе (существует ли путь, проходящий по всем ребрам ровно по одному разу) принадлежит P.

Предположим, что класс NP совпадает с P. Докажите, что в этом случае за полиномиальное время можно не только проверить выполнимость формулы, но и найти значения переменных, при которых она истинна (аналогично для гамильтонова цикла и т.п.)

Докажите, что задача о паросочетаниях (есть мальчиков и девочек, известно, какие пары согласны друг с другом танцевать; надо определить, можно ли устроить танец, в котором все мальчиков и девочек соединены в пары) принадлежит NP и, более того, принадлежит P.

Постройте полиномиальное сведение задачи 3-КНФ к задаче Клика;

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

Постройте полиномиальное сведение задачи 3-КНФ к задаче 3-раскраска;

тот же вопрос, но дополнительно требуется, чтобы количество выполняющих наборов переменных для любой 3-КНФ равнялось бы шестикратному количеству 3-раскрасок соответствующего ей графа.

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

Докажите, что предикат " -- двоичная запись составного числа" принадлежит NP.

Докажите, что предикат " -- двоичная запись простого числа" принадлежит NP.



Лекция №3

Тема 3.1 Вероятностные алгоритмы и класс BPP. Проверка простоты числа

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

Обычно считают, что вероятности выпадения одинаковы для обеих сторон монеты, а результат подбрасывания отождествляется с числом 0 или 1.

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

Определение 3.1. Предикат принадлежит классу BPP, если существуют такие ВМТ и полином , что машина заведомо остановится за время, не превосходящее , причем

с вероятностью большей дает ответ "да";

с вероятностью большей дает ответ "нет".

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

Замечание 3.1. Представить физическую реализацию НМТ очень трудно (вспомним, что нам придется поместить в нее всезнайку Мерлина). А вероятностные машины вполне могут мыслиться как реальные устройства. Поэтому предикаты из класса BPP вполне можно считать реально вычислимыми.

Класс BPP можно определить и с помощью предикатов от двух переменных, как это было сделано для класса NP.

Определение 3.2. Предикат принадлежит классу BPP, если существуют такие полином и предикат , что

доля слов длины , для которых выполнено , больше ;

доля слов длины , для которых выполнено , меньше .

Теорема 3.1. Определения 3.1 и 3.2 эквивалентны.

Доказательство Опр. 3.1 Полагаем (количество подбрасываний монеты не превосходит общего числа действий). Определим предикат "машина на входе дает ответ "да" при указанной в последовательности результатов подбрасываний монеты". Этот предикат по очевидным причинам удовлетворяет определению 3.2.

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

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

Рисунок 3.1.

Классический пример задачи из BPP представляет проверка простоты числа: дано число , требуется определить, простое ли оно. Для этой задачи существует вероятностный алгоритм, работающий за полиномиальное время; он будет сейчас описан.

Необходимые сведения из теории чисел.

Подробное изложение элементарной теории чисел содержится в книге [2]. Мы лишь напомним две теоремы, которые будут важны при анализе работы алгоритма проверки простоты числа.

Малая теорема Ферма. Если -- простое и , то .

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

Другими словами, существует взаимно однозначное соответствие между остатками от деления на и парами остатков от деления на и на . {И это соответствие уважает операции сложения и умножения.)

Из малой теоремы Ферма следует, что позволяет утверждать, что -- составное (говорят, что является свидетелем непростоты числа ). Это свидетельство косвенное -- явного разложения на множители мы не получаем -- и сильное: часто достаточно проверки при !

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

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

Арифметические операции над числами можно выполнять за полиномиальное время от длины их записи (число записывается знаками). Например, схема умножения чисел , столбиком имеет размер , растущий квадратично от длины входа. Хотя квадрат от длины входа уже достаточно мал, чтобы быть полиномиальным, заметим, что для умножения -значных чисел есть и более экономные схемы размера , см.[1, р.7.5] или [7, т. 2, р.4.3.3].

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

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

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

если выбрать подходящее значение . Детали этого (полиномиального) алгоритма оставляются читателю для самостоятельного обдумывания.

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

Тема 3.2 Алгоритм проверки простоты

Вход: число .

Шаг 1. Проверяем четность . Если , то ответ " -- простое", если -- четное и больше 2, то ответ " -- составное", в противном случае переходим к шагу 2.

Шаг 2. Проверяем, извлекается ли из нацело корень -й степени при . Если извлекается, то ответ " -- составное", иначе переходим к шагу 3.

Шаг 3. Записываем в виде , где , а -- нечетное.

Шаг 4. Выбираем случайное среди чисел от до .

Шаг 5. Вычисляем по модулю .

Проверка 1. Если , то ответ " -- составное".

Проверка 2. Если найдено такое , для которого , а , то ответ " -- составное".

В противном случае ответ " -- простое".

Анализ алгоритма.

Теорема 3.2. Если -- простое, то описанный выше алгоритм всегда (с вероятностью 1) выдает ответ " -- простое".

Если -- составное, то ответ " -- составное" будет получен с вероятностью .

Замечание 3.2. Чтобы получить полиномиальный вероятностный алгоритм проверки простоты числа в смысле определения 3.1, нужно дважды применить приведенный алгоритм. Тогда вероятность ошибки станет меньше .

Доказательство (теоремы 3.2). Из сказанного выше следует, что в доказательстве нуждается только второе утверждение.

Пусть , где (если такого представления нет, то на шаге 2 будет обнаружена непростота). Если , то проверка 1 для такого заведомо обнаружит, что -- составное. Так что достаточно доказать, что не меньше половины тех , которые взаимно просты с , обнаруживают непростоту числа.

Обозначим группу через , группу -- через . Из китайской теоремы об остатках следует, что группа изоморфна (изоморфизм задается естественным образом -- вычислением остатков по модулю и по модулю ).

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

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

Дальнейшее рассуждение разбивается на анализ нескольких случаев.

Пусть или .

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

Пусть .

Поскольку -- нечетное, , т.е. найдется такое , , что , а или .

Будем доказывать, что с вероятностью не меньше в этом месте проверка 2 алгоритма обнаружит, что -- составное. В данном случае , так что нужно понять, с какой вероятностью не равно . Рассмотрим два случая.

Одно из множеств , равно . Пусть, например, . В этом случае можно утверждать, что (остатку при делении на соответствует пара остатков при делении на ).

Можно рассуждать так же, как и в случае 1. С вероятностью не меньше получим пару остатков , .

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

Замечание 3.3. Шаг 2 в алгоритме избыточен, дополнительными соображениями устанавливается, что и для чисел вида проверки 1, 2 дают правильный ответ со значительной вероятностью. BPP и схемная сложность.

Теорема 3.3. .

Доказательство. Идея доказательства состоит в том, чтобы усилить оценки вероятностей с до . Число должно быть настолько мало, чтобы можно было выбрать такое случайное слово , при котором рассматриваемый предикат из BPP совпадает с .

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

Действительно, вспомним наглядное толкование BPP, данное после теоремы 3.1. Если доля слов , на которых происходит ошибка, для каждого не превосходит , то доля тех слов , на которых происходит ошибка хотя бы для одного , не превосходит . Значит, найдутся и такие , на которых нет ошибок ни при каком .

Это типичное неконструктивное доказательство существования. Мы доказываем, что вероятность того, что объекта с нужными свойствами не существует, меньше 1. Но это и означает, что хотя бы один такой объект существует.



Лекция №4

Тема 4.1 Иерархия сложностных классов

Напомним, что мы отождествляем языки и предикаты, как описано в лекции 1. В частности, запись означает .

Определение 4.1. Пусть -- некоторый класс языков. Класс дополнений составляют дополнения ко всем языкам из . Формально

Непосредственно из определений классов следует, что , , .

Игры, в которые играют машины.

Рассмотрим игру, в которую играют два игрока, будем их называть белые (Б) и черные (Ч). Игрокам сообщается некоторое слово , и они делают ходы по очереди ( -- первый ход белых, -- первый ход черных и т.д.). Каждый ход может быть описан словом длины , где -- некоторый полином. Игра завершается после некоторого, заранее заданного, числа ходов1) Результат игры описывается некоторым предикатом , истинность которого означает, что выиграли белые (ничьих не бывает, так что ложность означает, что выиграли черные). Предикат зависит от исходного слова и ходов, сделанных игроками: -- белыми, -- черными. Поскольку замкнут относительно дополнений, предикат , утверждающий выигрыш черных, также принадлежит .

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

Многие сложностные классы можно определить как множества (или ), соответствующие тем или иным видам игр. Например, получаем следующие классы.

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

: множества для игр, в которых белые делают 1 ход. Другими словами, это множества вида

: множества для игр, в которых белые делают 1 ход. Другими словами, это множества вида

: множества для игр из 2 ходов: 1 ход белых, 1 ход черных. Другими словами, это множества вида

Словами это можно сказать так: есть такой ход белых, что, как бы ни сыграли черные, белые выигрывают.

: множества для игр из 2 ходов. Другими словами, это множества вида

: множества для игр из ходов (в зависимости от четности последними ходят либо черные, либо белые). Другими словами, это множества вида

(если четное, то , , если нечетное, то , ).

: множества для игр из ходов (в зависимости от четности последними ходят либо черные, либо белые). Другими словами, это множества вида

(если четное, то , , если нечетное, то , ).

Классы и взаимно дополнительны: , .

Теорема 4.1 (Лаутеман [35]). .

Доказательство. Поскольку класс BPP замкнут относительно дополнений, достаточно показать, что .

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

(4.1)

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

Если

(4.2)

условие (4.1) заведомо ложно.

Условие (4.1) заведомо истинно, если для случайных независимых вероятность события больше 0. Другими словами, . Вероятность того, что случайный сдвиг не покрывает (не содержит) некоторый фиксированный элемент, равна по очевидным причинам . Вероятность того, что случайных сдвигов не покрывают фиксированный элемент, равна (покрытия разными сдвигами -- независимые события). Поскольку покрывается элементов, вероятность события не больше (вероятность объединения событий не больше суммы вероятностей этих событий). Итак, при

(4.3)

условие (4.1) заведомо выполняется.

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

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

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

Условие (4.2) в этом случае имеет вид , а условие (4.3): . Эти условия выполняются при подходящем выборе параметров. Можно взять порядка и порядка .

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

Существуют ли псевдослучайные генераторы, неизвестно. Их заведомо нет, если . Но в этом случае .

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

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

Тема 4.2 Класс PSPACE

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

Теорема 4.2. тогда и только тогда, когда существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что Б имеет выигрышную стратегию .

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

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

Чтобы было проще описывать игру, потребуем, чтобы после завершения вычисления МТ сохраняла без изменений достигнутое состояние.

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

Игра заканчивается, когда длина промежутка становится равной 1. Результат определяется так: для обоих концов этого промежутка в процессе игры были названы состояния . Если состояние правого конца получается из состояния левого конца за один такт работы , то Б выиграли, иначе выиграли Ч.

Если ответ на слове действительно "да", то белым нужно все время говорить правду, это гарантирует им выигрыш.

Если ответ на слове -- "нет", то при любом ходе белых на одном из промежутков (или на обоих) будет содержаться ошибка. Ч должен указывать каждый раз именно этот промежуток.

Задача 4.1. Докажите, что класс языков, распознаваемых недетерминированными машинами, работающими на памяти , содержится в классе языков, распознаваемых детерминированными машинами, работающими на памяти .

В качестве следствия теоремы 4.2 получаем включения всех определенных выше классов , в класс . Взаимное соотношение этих классов можно изобразить диаграммой включений, показанной ниже. На этой диаграмме от большего класса к меньшему можно пройти, двигаясь по стрелкам. Внизу располагается класс , отвечающий играм с 0 ходов, затем идут дополняющие друг друга классы, отвечающие играм с конечным числом ходов (для одного хода это NP и co-NP, для двух ходов -- и и т.д.). Завершается эта диаграмма классом , который определяется произвольными играми с одним естественным условием -- время игры должно быть полиномиально ограничено размером входного слова. Мы уже доказали все включения, изображенные на этой диаграмме. Ни про одно из включений, следующих из этой диаграммы, неизвестно, является ли оно строгим. Быть может, скажем, . С другой стороны, возможно и так, что , где обозначает (не рассматривавшийся нами) класс языков, вычислимых за экспоненциальное время . Впрочем, наиболее популярна гипотеза о том, что все включения, изображенные на диаграмме -- строгие.

Рис. 4.1.

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

Докажите, что .

В классе существуют полные задачи (относительно полиномиальной сводимости). Простейший вариант получается применением предыдущей теоремы.

Задача . Задается предикатом

есть истинная булева формула с кванторами (True Quantified Boolean Formula), т.е. формула вида

где , -- некоторая логическая формула, а -- либо , либо . По определению, , а .

Теорема 4.3. -полна.

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

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

Чтобы превратить в булеву формулу, добавим новые переменные (значение, вычисленное при -м присваивании в схеме) и заменим на формулу вида

где -- размер схемы, -- правая часть -го присваивания.

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



Лекция №5

Тема 5.1 Квантовые вычисления

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

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

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

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

Пространство состояний для такой системы -- конечномерное (размерности ) пространство над полем комплексных чисел.

Состояния

Обычного компьютера

квантового компьютера

биты

q-биты

базисное:

произвольное:

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

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

Классический случай:

Квантовый случай:

преобразования -- это функции из в

преобразования -- это унитарные операторы, то есть операторы, сохраняющие длину вектора .

Замечание. Все сказанное относится только к замкнутым системам. Реальный квантовый компьютер -- это часть большой системы (Вселенной), взаимодействующая с остальным миром. Квантовые состояния и преобразования открытых систем будут рассмотрены в разделах 9-10.

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

Тема 5.2 Определения и обозначения

Пространство состояний системы из q-битов можно записать в виде тензорного произведения . Сомножители соответствуют пространству состояний одного q-бита.

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

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



Другими словами, указанные векторы считаются равными 0.

Можно доказать, что данные определения эквивалентны.

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

Мы будем использовать (и уже использовали) принятые в физике обозначения, относящиеся к векторам и скалярному произведению в гильбертовом пространстве (их ввел Дирак). Векторы обозначаются , скалярное произведение -- . Если и , то . (Здесь и далее обозначает комплексное сопряжение.) В записи векторов скобки нужны лишь "для красоты" -- они указывают на тип объекта и придают симметрию обозначениям (см. ниже). Вместо можно было бы написать просто , хотя это и не принято. Поэтому -- и то, и другое обозначает вектор .

Скалярное произведение антилинейно по первому аргументу1) и линейно по второму, т.е.

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

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

Унитарный оператор -- это линейный оператор, сохраняющий скалярное произведение. Условие



эквивалентно тому, что (где -- тождественный оператор).

Наше определение скалярного произведения в согласовано с тензорным произведением:

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

Если операторы заданы в матричном виде в некотором базисе, т.е.

(легко понять, что -- линейный оператор: ), то матричные элементы оператора имеют вид .

Вычисление состоит из преобразований, считаемых элементарными (выполняемых за единицу времени).

Элементарное преобразование в классическом случае: такая функция из в , которая зависит от небольшого (не зависящего от ) числа битов и изменяет также небольшое число битов.

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

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

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

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

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



Очевидно, что

(5.1)

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

Определение 5.1. Квантовая схема. Пусть -- некоторое множество унитарных операторов (базис). Тогда квантовая схема в базисе -- это последовательность , где -- множества q-битов,

Оператор, реализуемый квантовой схемой. Это оператор , равный .

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

Оператор , реализуемый схемой в расширенном смысле. Это такой оператор, что произведение

действующее на q-битов, , для любого вектора удовлетворяет условию .

Таким образом, мы "берем напрокат" дополнительную память, заполненную нулями, и должны возвратить ее в прежнем состоянии. Какой смысл имеет такое определение? Зачем нужно требовать, чтобы дополнительные q-биты вернулись в состояние ? На самом деле это условие чисто техническое, однако важно, чтобы вектор состояния в конце вычисления был разложим, т.е. имел вид (с произвольным ). Если это так, то первая подсистема находится в определенном состоянии , поэтому про вторую подсистему (дополнительную память) можно забыть. В противном случае, совместное состояние двух подсистем оказывается "запутанным" (entangled), поэтому первую подсистему нельзя отделить от второй.



Лекция №6

Тема 6.1 Соотношение между классическим и квантовым вычислением

Классический объект, соответствующий унитарному оператору, -- перестановка. Любой перестановке естественно сопоставляется унитарный оператор в пространстве , действующий по правилу .

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

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

Перестановка, реализуемая обратимой схемой. Это произведение перестановок .

Перестановка , реализуемая схемой в расширенном смысле. Это такая перестановка, что произведение перестановок

(действующее на битов, ) для любого удовлетворяет условию .

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

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

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

Задача 6.1. Докажите для обратимых схем полноту базиса, состоящего из отрицания и элемента Тоффоли.

Лемма 6.1. Пусть функция реализуется булевой схемой размера в некотором базисе . Тогда можно реализовать функцию обратимой схемой размера в базисе { , состоящем из функций ( ), а также функции .

Замечание 6.1. Помимо "полезного" ответа схема, указанная в формулировке леммы, производит "мусор" .

Замечание 6.2. Содержательный смысл операции -- обратимое копирование бита (если начальное значение равно ). В литературе эта операция обычно называется Controlled NOT по причинам, которые станут ясными из дальнейшего.

Замечание 6.3. Применяя функцию можно менять биты местами в записи. Обратите внимание, что для перестановок битов достаточно также иметь в базисе , так как

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

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

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

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

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

Лемма 6.2. (очистка мусора). В условиях леммы можно произвести вычисление функции обратимой схемой размера (с использованием дополнительных битов).

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

Замечание 6.4. Обратимыми вычислениями заинтересовались при попытке ответить на вопрос, какая энергия необходима для вычислений (классических). Анализ показал, что потери энергии можно устремить к нулю для всех вычислительных операций, кроме необратимых. Когда производится необратимая операция (например, стирание бита), два различных логических значения ( и ) становятся одинаковыми ( ). Однако физические законы на микроуровне являются обратимыми, поэтому отличие между старыми состояниями ( и ) должно сохраниться в каких-то неконтролируемых физических степенях свободы. Это можно интерпретировать как возрастание беспорядка (энтропии), которое в конечном счете проявится в окружающей среде в виде тепла. Величина энергии, требуемой для стирания одного бита, очень мала ( ), но конечна. Потеря энергии из-за необратимого стирания информации при форматировании жесткого диска емкостью 1 Гб равна Дж, что примерно соответствует затратам энергии на сдвиг головки диска на половину диаметра атома водорода. Это на много порядков меньше реального перемещения головки при форматировании.

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

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

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

Поскольку задача TQBF PSPACE-полна, то достаточно вычислять на небольшой памяти значение формулы

(6.1)

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

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

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

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

Теорема 6.1. Пусть и вычислимы булевыми схемами размеров . Тогда реализуется обратимой схемой размера .

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



Лекция №7

Тема 7.1 Базисы для квантовых схем

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

Точная реализация.

Теорема 7.1. Базис, содержащий все унитарные операторы, действующие на парах q-битов, позволяет реализовать любой унитарный оператор в расширенном смысле.

Для доказательства этой теоремы введем важный класс операторов: операторы с квантовым управлением.

Определение 7.1. Определим по оператору оператор с квантовым управляющим q-битом (первый сомножитель) следующими соотношениями:

(7.1)

Графически будем изображать оператор с квантовым управлением как показано на рисунке. Верхняя линия соответствует первому сомножителю, нижняя линия -- второму. Направление стрелок соответствует направлению перемножения операторов (справа налево).