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

Процедура нахождения делителя.

Вход: число .

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

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

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

Шаг 4. Если , то ответ " ", в противном случае ответ " -- простое".

Анализ процедуры нахождения делителя.

Докажем, что вероятность получить делитель числа в результате работы процедуры нахождения делителя не меньше, чем , где -- число различных простых делителей . (Заметим, в частности, что эта вероятность равна~0 для простого , так что данная процедура может также использоваться и как тест простоты числа.) При доказательстве нам потребуется китайская теорема об остатках и тот факт, что мультипликативная группа вычетов по модулю , где простое, -- циклическая (см. [2, Гл. 6, 3]).

Если -- четное, то . Так что в этом случае процедура выдаст ответ " -- простое" только тогда, когда .

Запишем разложение на простые множители и введем обозначения



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

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

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

Тема 12.3: Квантовый алгоритм нахождения периода: основная идея

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

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

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

Собственные числа для , где -- период.

Собственные векторы для .

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

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

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

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

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

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

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

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

Задача 12.2. Используя оператор , реализуйте оператор для любого , взаимно простого с .

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

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

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

Это равенство гарантирует равномерное распределение числителей дробей. Проведем измерение в этом состоянии, тогда по формуле полной вероятности получаем

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

Условно работу машины можно представить в виде такого процесса:

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

Тема 12.4 Построение измеряющего оператора

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

Ищем информацию о , где

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

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

Как получать информацию о собственном числе.

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

а его действие в виде

так что для условных вероятностей получаем выражение

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

Сложность реализации операторов и зависит от сложности реализации оператора , которая ненамного выше сложности реализации оператора (см. задачу 12.2).

Оценка условных вероятностей.

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

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

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

Как было доказано в лекции 11, условные вероятности в таком случае перемножаются. Для оператора

условные вероятности будут равны (здесь через обозначено значение в -ом бите).

Далее с битами, в которых записаны результаты "экспериментов", будут уже производиться классические действия. Поскольку условные вероятности перемножаются, можно считать, что мы оцениваем вероятность выпадения 1 в серии испытаний Бернулли.

Если монета брошена раз, то доля выпавших единиц примерно равна . С какой точностью верна такая оценка? Из теории вероятностей известно, что

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

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



Тема 12.5 Обсуждение алгоритма

Обсудим два естественно возникающих вопроса по поводу изложенного алгоритма.

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

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

-- Какие собственные числа мы находим?

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

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

Задача 12.3. Постройте квантовую схему размера , реализующую преобразование Фурье на группе при любом с точностью . (Определение см. в задаче 8.4. Указание: воспользуйтесь результатом задачи 11.2).

Задача о скрытой подгруппе в .

Алгоритмы, открытые Саймоном и Шором, обобщаются на довольно широкий класс задач, связанных с абелевыми группами. Самой общей из них является задача о скрытой подгруппе в [23]. К ней сводится задача о скрытой подгруппе в любой конечно-порожденной абелевой группе , поскольку можно представить как фактор-группу (для некоторого ).

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

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

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

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

задается набором чисел по модулю . Это рациональные числа со знаменателями не больше .

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

(12.3)

Последнее условие гарантирует, что суммарная вероятность ошибки будет не больше, чем .

Выберем достаточно большое число (конкретная оценка получается из анализа алгоритма). Мы будем работать с целыми числами в диапазоне от до .

Приготовим в одном квантовом регистре длины состояние

В другой регистр поместим . Применим квантовый оракул (12.2) и выбросим второй регистр. Получится смешанное состояние

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

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

Вероятность того, что реализуется данный набор , равна



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

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

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

Сложность алгоритма.

Tребуется обращений к оракулу, каждый вопрос имеет длину . Размер квантовой схемы оценивается как .

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



Лекция №13

Тема 13.1 Модификация классических определений

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

Частично определенная булева функция -- это функция

В этом разделе всюду под булевыми функциями подразумеваются частично определенные булевы функции.

И еще одно замечание по поводу обозначений: мы использовали обозначение P и для класса полиномиально вычислимых функций, и для класса полиномиально разрешимых предикатов; теперь поступим аналогично, используя обозначения P, NP и т.п. для классов частично определенных функций.

P, естественно, обозначает класс полиномиально вычислимых частично определенных функций. Приведем модифицированное определение класса NP.

Определение 13.1. Функция принадлежит классу NP, если есть частично определенная функция от двух переменных, такая что

Как и раньше, -- полином.

Что будет, если в определении 13.1 заменить условие на условие ? Получится другой, скорее всего, более широкий класс, который можно было бы обозначить BNP. Однако для этого класса есть другое, стандартное, обозначение -- MA, указывающее на то, что он входит в иерархию классов, определяемых играми Артура - Мерлина. Об играх, которыми задаются сложностные классы, мы уже говорили в лекции 4; игры Артура - Мерлина отличаются тем, что Артур -- вероятностная полиномиальная машина Тьюринга. Порядок букв в обозначении MA указывает на порядок ходов: вначале Мерлин сообщает , затем Артур проверяет выполнение предиката .

Квантовое определение по аналогии.

Определение 13.2. Функция принадлежит классу , если существует однородная последовательность квантовых схем полиномиального по размера, реализующих такие операторы , что

Здесь -- ограничение на слова длины , , , , а для и должно выполняться условие , .

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

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

Если вместо чистых состояний рассматривать смешанные, то получается эквивалентное определение: максимум вероятности все равно достигается на чистом состоянии.

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

Обсудим теперь соотношения между пороговыми вероятностями. Из приведенного в определении 13.2 соотношения следует гораздо более сильное условие на и .

Лемма 13.1 (усиление вероятностей). Если , то она удовлетворяет также и такому варианту определения 13.2, где условие заменено на , , , .

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

(13.1)

где , . Но теперь появляется дополнительная трудность -- Мерлин может пытаться обмануть Артура, сообщая ему неразложимую в тензорное произведение подсказку.

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

(13.2)

где

(13.3)

Здесь -- проектор на подпространство состояний, имеющих в первом q-бите (т.е. ).

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

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

(13.4)

Здесь .

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

В случае, когда -- пороговая функция (13.1),

(13.5)

где . Согласно условию, , если , и , если . Оценим величину в этих случаях, соответственно, снизу и сверху.

Будем использовать неравенство Чернова (см. [18]). Пусть



Тогда при получаем

а при --

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

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

Тема 13.2 Полные задачи

В классе BQNP, как и в NP, есть полные задачи относительно той же самой полиномиальной сводимости, которую мы рассматривали раньше. Вот простейший пример.

Задача 0. Зададим функцию следующим образом. Пусть -- множество троек вида

где под описанием схемы понимается ее приближенная реализация в стандартном базисе, а ( , -- размер описания схемы). Тогда для

если существует вектор , при действии на который мы получим в первом бите 1 с вероятностью, большей ;

если для всех вероятность получить в первом бите 1 меньше .

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

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

Определение 13.3. Оператор называется k-локальным гамильтонианом, если он выражается в виде

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

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

Задача 1: локальный гамильтониан. Пусть -- множество троек вида

где , , , ( ). Тогда для

если у есть собственное число, не большее ,

если все собственные числа больше .

Утверждение 13.2. Задача локальный гамильтониан принадлежит BQNP.

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

а если все собственные числа больше , то

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

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

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



(13.6)

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

(Здесь обозначает базисный вектор во вспомогательном -мерном пространстве.) Проводя вычисления аналогично (13.6), получаем

(13.7)

Утверждение 13.3. Задача локальный гамильтониан полна в классе BQNP относительно полиномиальной сводимости.

Идея доказательства восходит к Фейнману [29]: замена унитарной эволюции не зависящим от времени гамильтонианом (т.е. переход от схемы к локальному гамильтониану).

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

Гамильтониан, сопоставляемый схеме. Он действует на пространстве

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

Слагаемое отвечает начальному состоянию и равно

(13.8)

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

Слагаемое отвечает конечному состоянию и равно

(13.9)

здесь мы считаем, что бит результата -- первый.

И, наконец, слагаемое описывает эволюцию системы и состоит, как и следовало ожидать, из слагаемых, каждое из которых отвечает за переход от к :



(13.10)

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

Замена базиса. Произведем замену базиса, задаваемую оператором

Полезно обратить внимание на то, что -- измеряющий оператор: измеряется значение счетчика и к q-битам пространства состояний схемы применяется оператор эволюции за время .

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

На слагаемое сопряжение не влияет:

(13.11)

Действие на слагаемое :

(13.12)

Слагаемое состоит из трех. Вначале запишем действие сопряжения на первое из слагаемых в (13.10):



Сопряжение двух других слагаемых происходит аналогично, в итоге получаем

и

(13.13)

Где

Оценка собственного числа при ответе "да". Предположим, что схема, на вход которой подан вектор , дает ответ 1 с вероятностью не меньше, чем . Это, по определению, означает, что

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

В пространстве счетчика выберем вектор

(13.14)

Искомый вектор равен . Оценим .

Очевидно, что . Поэтому

Поскольку все вспомогательные q-биты вначале установлены в 0, то непосредственно из определяющей формулы (13.8) получаем

Осталось оценить последнее слагаемое

Итак, мы доказали, что

поэтому у есть собственное число с такой же верхней оценкой.

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

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

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

(13.15)

Лемма 13.4. Пусть , -- неотрицательные операторы, , -- их нулевые подпространства, причем . Пусть также ненулевые собственные числа и не меньше . Тогда

(13.16)

где -- угол между и .

Обозначение ( -- оператор, -- число) нужно понимать как сокращение от . Другими словами, если , то все собственные числа не меньше .

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

Доказательство (леммы 13.4). Очевидно, что и , поэтому достаточно доказать неравенство . Оно, в свою очередь, эквивалентно такому неравенству:

(13.17)

Пусть -- собственный вектор оператора , отвечающий собственному числу . Тогда

где и -- единичные векторы, а и -- неотрицательные вещественные числа. Отсюда находим

Следовательно,



Таким образом, .

Теперь получим упомянутые выше оценки. Нулевые подпространства и представляются в виде

(13.18)

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

(13.19)

где вектор определен формулой (13.14).

Для оценки

(13.20)

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

Для оценки нужно найти первое положительное собственное число матрицы . Собственные векторы и собственные числа даются формулами

где \, ( ). Отсюда следует, что

(13.21)

Наконец, нужно оценить угол между подпространствами и . Будем оценивать квадрат косинуса угла

(13.22)

Представим в виде . Проектор на распадается на сумму трех проекторов. Совсем легко подсчитать вклад второго слагаемого, он равен . Первое и третье слагаемые в сумме дают

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

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

Следовательно, , как и утверждалось выше.

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

Этот недостаток можно преодолеть, если вложить пространство счетчика в большее пространство. Возьмем q-битов, занумерованных от до . Искомое вложение выглядит так:

Используемые в конструкции гамильтониана операторы на пространстве счетчика заменяются согласно схеме

(13.23)

Теперь они 3-локальные (а сам гамильтониан, с учетом действия на q-биты исходной схемы, -- 5-локальный).

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

Теперь возникает новая проблема: что делать с лишними состояниями в расширенном пространстве счетчика? Мы справимся с этой проблемой, добавив еще одно слагаемое к гамильтониану :



Нулевое подпространство оператора совпадает со старым рабочим пространством , поэтому дополнительное слагаемое не меняет верхней оценки минимального собственного числа при ответе "да".

При ответе "нет" требуемую нижнюю оценку для собственных чисел оператора можно получить следующим образом. Оба слагаемых оставляют инвариантным подпространство , поэтому можно оценивать независимо на и его ортогональном дополнении . На имеем и , а на -- и . (Здесь мы пользуемся тем, что каждое из слагаемых гамильтониана, (13.8), (13.9) и (13.10), остается неотрицательным при замене (13.23)). В любом случае

Это завершает доказательство полноты задачи о локальном гамильтониане в классе BQNP.

Место BQNP среди других сложностных классов.

Прямо из определения следует, что класс BQNP содержит класс MA (а, значит, и BPP, и NP). Ничего более определенного о силе "недетерминированных" квантовых алгоритмов сказать пока нельзя1)

Не слишком много можно сказать и об их "слабости".

Утверждение 13.5. .

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

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

Пусть -- собственные числа оператора (здесь -- длина подсказки). Имеем оценку

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

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

Замечание 13.3. Полученный результат можно усилить: . Доказательство полностью аналогично решению задачи 8.3.

Замечание 13.4. Мы ограничились случаем игр Мерлина и Артура, которые продолжаются один раунд. Недавно было показано [45], что уже двух раундов такой квантовой игры достаточно, чтобы получить весь класс PSPACE. В классическом случае для достижения класса PSPACE требуется полиномиальное количество раундов [36, 37], причем в широких кругах узких специалистов господствует мнение, что никакого фиксированного количества раундов недостаточно.



Лекция №14

Тема 14.1 Классические и квантовые коды

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

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

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

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

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

Конструкции, необходимые для организации вычислений без потери точности, довольно сложны. Подробно они изложены в [41, 19, 34, 4, 32], а здесь мы в основном ограничимся более простым вопросом: как сохранять неограниченно долго заданное квантовое состояние? (Легко понять, что это -- частный случай предыдущего вопроса, когда реализуется последовательность тождественных операторов.) Для решения такой упрощенной задачи конкретный вид кодирующего отображения неважен; нужно задать лишь подпространство .

Определение 14.1. Квантовый код типа -- это подпространство размерности . (Число -- количество закодированных q-битов -- не обязательно должно быть целым).

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

Классические коды.

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

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

(14.1)

Здесь -- расстояние Хэмминга (число различных битов).

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

(14.2)

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

Введем обозначения:

-- множество входов,

-- множество выходов,

-- множество переходов (оно же -- множество ошибок),

-- множество .

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

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

В том случае, когда , говорят, что код исправляет k ошибок.

Замечание. Термин "код, исправляющий ошибки" является неточным. Правильнее было бы сказать, что код оставляет возможность для исправления ошибок. Исправляющие преобразование -- это отображение , такое что, если и , то , вычисление значения исправляющего преобразования называется декодированием.

Пример 14.1. Код с повторением:

Такой код исправляет одну ошибку.

Очевидное обобщение примера 14.1 приводит к классическим кодам, исправляющим любое количество ошибок. Построим более интересные примеры классических кодов. Для начала дадим еще одно стандартное определение.

Определение 14.3. Кодовое расстояние -- это

Для кода из примера 14.1 кодовое расстояние равно 3. Имеется очевидное утверждение.

Утверждение 14.1. Код исправляет ошибок тогда и только тогда, когда .



Тема 14.2 Примеры классических кодов

типа ; для него .

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

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

Проверка на четность. Код типа , для него . Состоит из всех четных слов, т.е. слов, содержащих четное число единиц.

Код Хэмминга . Это код типа , где число .

Слова из -- это последовательности битов . Номер каждого бита можно записать в двоичной системе как . Введем множество контрольных сумм



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

Множество слов кода Хэмминга задается условием равенства всех контрольных сумм 0 (т.е. оно является подпространством по модулю 2). Можно показать, что для кода Хэмминга .

Линейные коды.

Пусть есть множество . Линейный код -- это линейное подпространство. Линейные коды удобно задавать двойственным базисом (как множество решений системы линейных уравнений).

Пример 14.2. Код Хэмминга, рассмотренный выше, задается как множество решений системы уравнений

Поэтому код Хэмминга образует подпространство коразмерности 3.

Квантовые коды.

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

(Здесь стоит просто сумма подпространств, не прямая.) В дальнейшем нас будет интересовать именно устойчивость к ошибкам из .

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

Тема 14.3 Модель независимых ошибок в квантовом случае

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

Начнем с того, что выясним, какие нормы пригодны для характеризации близости матриц плотности. Матрица плотности, как мы помним из лекции 9, задает вероятностное распределение на чистых состояниях. Вероятностные распределения естественно сравнивать в -норме: если , -- два распределения, то мерой их различия считаем . Дадим определение аналогичной нормы для матриц плотности.

Определение 14.4. Следовая норма оператора равна

(14.3)

Для эрмитова оператора следовая норма -- это сумма модулей собственных чисел.

Задача 14.1. Проверьте, что (14.3) действительно определяет норму. Докажите, что

(14.4)

( -- операторная норма, см. опр. 7.2).

Задача 14.2. Проверьте выполнение следующих свойств следовой нормы:

,

,

,

,

.

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

Лемма 14.2. Пусть -- разложение пространства в прямую сумму взаимно ортогональных подпространств. Тогда для любой пары матриц плотности ,

Доказательство. Левую часть этого неравенства можно представить в виде , где . Ясно, что . Теперь применим представление следовой нормы в виде (14.4).

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

(14.5)

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

(14.6)

и оценить норму при условии . Если бы выполнялось неравенство , можно было бы буквально повторить оценку (14.2). Однако это неравенство не всегда выполняется.

Пример 14.3. Рассмотрим преобразование

Очевидно, что , однако . (Подействуйте преобразованием на оператор .)

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

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

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

В-третьих, из определения следует, что , поэтому имеем такие неравенства

(14.7)

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

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

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

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

Теорема 14.1. Если , то .

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

Поэтому .

Доказать неравенство в обратную сторону несколько сложнее. Без уменьшения общности, . Инфимум в определении 14.5 достигается при .

Покажем сначала, что существуют три матрицы плотности и , такие что . Пусть

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

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

где положительно, но мало.

Итак, пусть , где . Представим и в виде , , где -- единичные векторы. Здесь мы используем условие и утверждение 9.1. Положим . Очевидно, что .

Докажем, что . Обозначим

тогда

Отсюда, во-первых, следует, что векторы и имеют единичную длину. Во-вторых, найдется унитарный оператор на пространстве , такой что (это утверждение из задачи 9.3). Следовательно,

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

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

Тема 14.4 Основные определения и простейшие следствия

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

Определение 14.6. Квантовый код (подпространство ) исправляет ошибки из , если

(14.8)

Определение 14.7. Физически реализуемое преобразование



называется исправляющим (для кода и пространства ошибок ), если

Если при этом сохраняет след, то .

Теорема 14.2. Если код исправляет ошибки из , то исправляющее преобразование существует.

Доказательство будет дано ниже. Обратное утверждение доказано в [4].

Пример 14.4. Тривиальный код типа : пусть , а , т.е. для кодирования используются первые q-битов, а ошибки действуют на остальные q-биты. Условие (14.8), очевидно, выполнено. В качестве исправляющего преобразования можно взять , где . Преобразование реализуется очень просто: выбрасываем последние q-битов и заменяем их на новые q-биты в состоянии . Практической пользы от такого кода, конечно, мало. Интересно, однако, что любой квантовый код, исправляющий ошибки, в определенном смысле похож на тривиальный (см. лемму 14.3 ниже).

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

Ошибки вида называются классическими, а ошибки вида называются фазовыми.

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

(14.9)

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

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

Заметим, что если , то .

Определение 14.8. Код обнаруживает ошибки из , если

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

Таким образом, код исправляет ошибок, если .

Теперь мы перейдем к доказательству теоремы 14.2.

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



(14.10)

Доказательство. Пусть . Рассмотрим фактор-пространство и естественное отображение . Линейное отображение , удовлетворяющее условию (14.10), строится каноническим образом; нужно лишь проверить его изометричность.

Скалярное произведение на пространстве можно задать при помощи функции из свойства кода (14.9): если и , то . Очевидно, что эта величина не зависит от выбора и . Ясно также, что , если . Формула (14.9) как раз и означает, что отображение является изометрическим.

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

(Функция линейно продолжается на все пространство ).

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

Задача 14.3. Пусть код обнаруживает ошибки из . Докажите, что состояние можно восстановить, не используя q-битов из множества .

Тема 14.5 Код Шора [40]

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

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

(14.11)

Для анализа кода Шора нам потребуется классификация операторов с помощью матриц Паули. Их, вообще говоря, три, но четвертой матрицей Паули будем считать единичную. Введем нестандартную индексацию матриц Паули:

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

(14.12)

Множество индексов образует группу или 2-мерное пространство над полем .

Матрицы Паули образуют базис пространства :

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

Здесь .

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

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

Достаточно показать, что в этом случае

(14.13)

Рассмотрим два случая.

Классическая ошибка отлична от 0. В этом случае каждое базисное состояние



изменяется под действием в некоторых битах, . Поэтому в скалярных произведениях (14.13) все слагаемые будут равны 0.

. Ошибка чисто фазовая: , где . Обозначим . Тогда (см.(14.11))

Нас интересуют значения по модулю 2. Возможны 3 случая:

.

.

.

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

Итак, код Шора обнаруживает ошибку; кодовое расстояние равно~ .

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