Решения задач

1.9 Приведем идею написания такой программы.

Будем писать программу, моделирующую работу универсальной машины Тьюринга. Поскольку значение переменной может быть сколь угодно велико, то в одной переменной можно хранить всю ленту машины (цифры $$|\calS|$$ -ичного представления числа, где $$\calS$$ — алфавит машины). Указатель положения головки — это еще одна переменная, состояние управляющего устройства — третья.

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

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

Замечание. Когда значения переменных не ограничены, в одной переменной можно хранить целый массив таких переменных:$$(x_1,\dots, x_n) \mapsto 2^{x_1}3^{x_2}\dots p_n^{x_n},$$ $$p_j$$ — простые числа. Поэтому ограничение на число переменных несущественно.

1.10 Будем искать все функции от двух переменных, которые выражаются формулами в базисе $$\calF$$. Вначале есть две такие функции (проекции): $$p_1(x,y)=x$$ и $$p_2(x,y)=y$$. Далее к множеству уже построенных функций $$\calF'$$ применяется следующая процедура. Добавляем к множеству $$\calF'$$ все функции вида $$f(g_1(x_1,x_2),g_2(x_3,x_4),\dots,g_k(x_{2k-1},x_{2k}))$$, где $$x_j\in\{x,y\}$$, $$g_j\in\calF'$$, $$f\in\calF$$. Если множество $$\calF'$$ увеличилось, повторяем процедуру еще раз. В противном случае возможны два варианта: либо уже получены все функции от двух переменных (тогда базис полон), либо — нет (тогда базис не является полным).

Оценим время работы этого алгоритма. Расширять множество $$\calF'$$ можно лишь 14 раз (всего есть 16 булевых функций от двух переменных). Каждый раз нужно проверить не более $$|\calF'|^m\cdot2^m=(2^m)^{1+\log|\calF'|}$$ вариантов, где $$m$$ — максимальное количество аргументов у базисных функций. Длина входа (длина записи базиса) не превосходит $$|\calF|2^m$$, а $$|\calF'|=O(1)$$. Так что алгоритм работает за время, ограниченное полиномом от длины входа.

1.11 Верхняя оценка $$n2^n<2{,}01^{n}$$ (при $$n\geq2000$$ ) для $$c_n$$ сразу следует из представления функции в дизъюнктивной нормальной форме (см. 1.1).

Для получения нижней оценки подсчитаем число различных схем размера $$s$$ и сравним его с количеством функций от $$n$$ переменных. Для определенности считаем, что используется стандартный полный базис. Тогда для $$k$$ -го присваивания схемы есть не более$$2\cdot(n+k)(n+k-1)/2+(n+k-1)<(n+k)^2$$ возможностей (конъюнкция и дизъюнкция — симметрические функции, а выбирать мы можем из $$n+k-1$$ переменной), поэтому количество $$N_s$$ различных схем размера $$s$$ не больше, чем$$\prod_{k=1}^{s}(n+k)^2\leq \prod_{k=1}^{s}2n^2k^2\leq (2n^2)^s (s!)^2\leq 2^{s(1+2\log n)+2s\log s}.$$

А число булевых функций от $$n$$ переменных равно $$2^{2^n}$$. При$$2^n>s(1+2\log n)+2s\log s$$ функций больше, чем схем, поэтому $$c_n>s$$. Если $$s=1{,}99^n$$, то неравенство $$(*)$$ выполняется при $$n\geq3000$$.

1.12 Снова используем дизъюнктивную нормальную форму. Если строить по формуле 1.1 схему из элементов $$\AND$$ и $$\OR$$, имеющих произвольное число входов, то понадобится не более 3 слоев элементов: один слой на отрицания, один — на конъюнкции, и один — на итоговую дизъюнкцию.

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

Длина ориентированного пути в графе схемы не превосходит глубины схемы $$d$$. Для схемы в стандартном базисе входная степень каждой вершины не больше 2. Поэтому ориентированных путей, ведущих в выходные вершины, не больше чем $$2^d=O(n^{O(1)})$$ (двигаемся от выходной вершины против направления стрелок и применяем индукцию).

1.14. Результатов сравнения двух чисел $$x$$ и $$y$$ три — $$x>y$$, или $$x=y$$, или $$x<y$$. Будем строить схему, которая выдает два бита результата, кодирующие эти три возможности.

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

Схему сравнения $$n$$ -разрядных чисел будем собирать из двух схем, сравнивающих числа, образованные первыми $$n/2$$ разрядами и последними $$n/2$$ разрядами. Зная результаты сравнения этих двух пар чисел, можно восстановить и результат сравнения исходных чисел.

Конструкция схемы изображена на рис. 15.1 .

Схема $$Cmp_n$$ для сравнения $$n$$ -разрядных чисел (размер схемы $$O(n)$$, глубина — $$O(\log n)$$ )

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

Схему сравнения n-разрядных чисел будем собирать из двух схем, сравнивающих числа, образованные первыми n/2 разрядами и последними n/2 разрядами. Зная результаты сравнения этих двух пар чисел, можно восстановить и результат сравнения исходных чисел.

Конструкция схемы изображена на рис. 15.1. Оценим ее размер и глубину. Выполняются следующие рекуррентные соотношения$$s_n=2s_{n/2}+3,\qquad h_n=h_{n/2}+2.$$ Из них получаем $$s_n= O(n)$$ и $$h_n=O(\log n)$$.

Замечание. Сравнение $$n$$ -значных двоичных чисел $$x$$ и $$y$$ равносильно определению старшего разряда числа $$x+(2^n-1-y)$$, а число $$2^n-1-y$$ находится по $$y$$ схемой глубины $$O(1)$$ линейного размера (нужно применить отрицание ко всем переменным). Поэтому достаточно было бы решить следующую задачу 1.15. Мы, наоборот, будем использовать сравнение чисел для сложения.

1.15. Введем обозначения: пусть $$x_{n-1}, \dots,x_0$$ — двоичные разряды первого слагаемого; $$y_{n-1}, \dots,y_0$$ — второго; $$s_n,s_{n-1}, \dots,s_0$$ — разряды результата; $$r_{n-1}, \dots,r_0$$ — биты переноса в следующий разряд. Введем дополнительные переменные $$t_i=x_i\oplus y_i$$, $$t_0=0$$. Тогда $$s_0=t_0$$, $$s_i=$$ $$r_{i-1}\oplus t_i$$ при $$i>0$$ ; $$r_{-1}=0$$, $$r_i=(r_{i-1}\wedge t_i)\vee x_i$$ при $$i\geq0$$ (если биты в слагаемых различны, то бит переноса такой же, как в предыдущем разряде; если одинаковы — бит переноса совпадает с их (общим) значением).

Пока мы вводили обозначения, мимоходом решилась задача пункта а). Действительно, присваиваний по приведенным выше формулам нужно сделать $$O(n)$$ штук.

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

Заметим, что если есть схема размера $$S$$ и глубины $$H$$, вычисляющая биты переноса, то из нее легко строится схема размера $$S+O(n)$$ и глубины $$H+O(1)$$, вычисляющая сумму (все $$t_i$$ могут быть найдены параллельно, и, при известных битах переноса $$r_i$$, все $$s_i$$ также могут быть найдены параллельно).

Вычисление битов переноса равносильно сравнению, так что достаточно научиться сравнивать параллельно все "суффиксы" чисел, т.е. для каждого $$i$$ сравнить числа $$x_ix_{i-1}\dots x_0$$ и $$\neg y_i\neg y_{i-1}\dots\neg y_0$$.

Вначале сравним числа $$x_{n-1}x_{n-2}\dots x_0$$ и $$\neg y_{n-1}\neg y_{n-2}\dots\neg y_0$$ по схеме, описанной в предыдущей задаче. Заметим, что при работе этой схемы на нижнем уровне мы сравниваем биты, на следующем — двузначные числа, затем — четырехзначные и т.д. Получаем "сужающееся дерево". Оно дает результаты сравнения блоков по $$2^k$$ битов, в частности, для суффиксов длин $$1$$, $$2$$, $$\dots$$, $$2^m=n$$. Это числа, двоичная запись которых содержит ровно одну единицу. Комбинируя результаты сравнения суффиксов длины $$2^k$$ и соседних с ними блоков, получим результаты сравнения суффиксов, двоичная запись длин которых содержит две единицы. Продолжая этот процесс, мы получим результаты сравнения всех суффиксов. Поскольку количество единиц в двоичной записи длины суффикса не превосходит $$\log n$$, глубина полученной схемы $$O(\log n)$$. Размер схемы линеен — помимо схемы сравнения $$x$$ и $$2^n-1-y$$ (линейного размера) мы используем дополнительно для каждого суффикса один блок, изображенный в центре рис. 15.1, который комбинирует результаты предыдущих сравнений.

1.16 Для вычисления функции $$\MAJ$$ достаточно научиться подсчитывать число единиц среди значений переменных: дальше можно использовать схему из задачи 1.14. Общее число единиц равно сумме числа единиц среди значений переменных от $$x_1$$ до $$x_{\lfloor n/2\rfloor}$$ и числа единиц среди значений переменных от $$x_{\lfloor n/2\rfloor+1}$$ до $$x_n$$. Представляя это в виде схемы, получим схему глубины $$\log n$$, элементами которой должны быть функции, вычисляющие сумму двух чисел. Поскольку эти числа не превосходят $$n$$, их двоичная длина не превосходит $$\log n$$. Из решения задачи 1.15 вытекает, что глубина таких схем $$O(\log\!\log n)$$. Глубина всей схемы поэтому $$O(\log n\log\!\log n)$$ (а размер $$O(n)$$ ).

1.17 Для графов можно определить операцию возведения в степень. В графе $$G^k$$ столько же вершин, сколько и в $$G$$, а две вершины связаны ребром, если в $$G$$ их можно соединить путем не длиннее $$k$$ (в частности, $$G^1=G$$ ).

Графы будем задавать матрицами смежности. Строки и столбцы матрицы смежности $$A(G)$$ графа $$G$$ индексированы вершинами графа. Если $$(jk)$$ — ребро $$G$$, то $$a_{jk}=1$$, в противном случае $$a_{jk}=0$$. Нам будет удобно полагать $$a_{jj}=1$$ и считать элементы матрицы булевыми переменными.

Легко понять, что если между вершинами в графе $$G$$ есть путь, то есть и путь не длиннее $$n$$, где $$n$$ — число вершин в графе $$G$$. Так что для решения задачи достаточно построить схему, вычисляющую матрицу $$A(G^k)$$ для какого-нибудь $$k\geq n$$, и схему, выбирающую матричный элемент по заданным номерам строки и столбца.

Для любых положительных $$k$$, $$j$$, $$m$$, таких что $$k=j+m$$, справедливо тождество$$A(G^k)_{uv}=\bigvee_{w\in V(G)} A(G^j)_{uw}\wedge A(G^m)_{wv}.$$

Если сказать словами, то это тождество означает, что на любом пути длины $$k$$ в графе $$G$$, связывающем вершины $$u$$ и $$v$$, есть вершина $$w$$ такая, что длина пути от $$u$$ до $$w$$ равна $$j$$, а длина пути от $$w$$ до $$v$$ равна $$m$$. В обратную сторону, если есть пути между $$u$$ и $$w$$, $$w$$ и $$v$$ длины $$j$$ и $$m$$ соответственно, то их объединение дает путь длины $$j+m=k$$ из $$u$$ в $$v$$.

Вычисление матричного элемента по формуле $$(*)$$ легко записать в виде схемы глубины $$O(\log n)$$. Вычисляя последовательность матриц $$A(G^1)$$, $$A(G^2)$$, $$A(G^4)$$, $$\dots$$ последовательным возведением в квадрат, через $$\lceil \log n\rceil$$ шагов мы получим матрицу $$A(G^{2^k})$$, где $$2^k\geq n$$. Глубина построенной схемы $$\log^2n$$, а размер полиномиален по $$n$$.

Теперь покажем, как извлекать из набора матричных элементов элемент $$a_{jk}$$, если $$j$$ и $$k$$ заданы двоичными представлениями $$\overline{j_l\dots j_0}$$, $$\overline{k_l\dots k_0}$$, $$l=\lceil \log n\rceil$$. Заметим, что равенство двух битов $$x$$ и $$y$$ проверяется в стандартном базисе формулой $$x\eqrel y\bydef (\neg x\wedge\neg y)\vee (x\wedge y)$$. Поэтому значение, вычисленное по формуле$$\bigvee_{s_l\dots s_0, t_l\dots t_0} a_{\overline{s_l\dots s_0}, \overline{t_l\dots t_0}} \bigwedge_{m=0}^{l} \left(s_m\eqrel j_m\right)\wedge\left(t_m\eqrel k_m\right),$$ всегда равно $$a_{\overline{j_l\dots j_0}, \overline{k_l\dots k_0}}$$. Размер формулы $$(**)$$ полиномиален по $$n$$. Легко представить эту формулу схемой глубины $$O(\log n)$$. Можно также сослаться на результат задачи 1.19.

1.18 Используя тождества де Моргана$$\neg \bigvee x_i=\bigwedge \neg x_i, \qquad \neg \bigwedge x_i=\bigvee \neg x_i,$$ можно добиться, чтобы отрицания применялись первыми. А поскольку $$\neg f=f\oplus1$$, применяя при необходимости тождества де Моргана еще раз, можно добиться, чтобы последней применялась дизъюнкция.

После таких преобразований мы получим схему, которая есть ДНФ. И задача свелась к тому, чтобы убедиться, что количество конъюнктов (аргументов дизъюнкции) в любой ДНФ, задающей функцию $$\PARITY$$, экспоненциально велико.

Легко понять, что любой конъюнкт в такой ДНФ должен содержать $$n$$ сомножителей (в противном случае функция, которую задает эта ДНФ, иногда не будет меняться при изменении ровно одного из ее аргументов). Конъюнкт, содержащий $$n$$ сомножителей, равен 1 ровно на одном наборе значений переменных. Поэтому число конъюнктов не меньше числа единиц функции $$\PARITY$$, которое равно $$2^{n-1}$$.

Замечание. Можно доказать, что схемы любой фиксированной глубины из элементов $$\NOT$$ и $$\OR$$, $$\AND$$ с произвольным числом входов, вычисляющие функцию $$\PARITY$$, имеют экспоненциальный размер. Доказательство строится по индукции, основание которой дают схемы глубины 2 и 3 (изложенный выше случай).

Доказательство этого утверждения можно найти в [24]. Приведем краткое изложение основной идеи. Заметим, что применение дизъюнкции и конъюнкции в схеме минимального размера должно чередоваться. Заменяя дизъюнкцию конъюнкций на конъюнкцию дизъюнкций, можно уменьшить глубину схемы на 2. Однако размер схемы может при этом увеличиться квадратично, поэтому никакой разумной оценки так не получается. Для получения оценки случайным образом присвоим значения части переменных. Полученная функция от меньшего числа переменных — либо $$\PARITY$$, либо ее отрицание. Схемная сложность для отрицания $$\PARITY$$ такая же, как и для самой $$\PARITY$$. А с некоторой вероятностью наша схема упростится и перестановка конъюнкций и дизъюнкций не приведет к большому увеличению размера схемы.

1.19 а) $$\Longrightarrow$$ б). Граф, представляющий формулу, можно сделать деревом, если размножить входные переменные. Размер при этом увеличится не более, чем вдвое.

Для построения схемы глубины $$O(\log n)$$, вычисляющей формулу $$X$$ размера $$n$$, используем идею, примененную в решении задач 1.14 и 1.15.

Двигаясь от корня дерева, представляющего формулу, и выбирая каждый раз вершину, соответствующую подформуле большего размера, мы найдем рано или поздно подформулу $$Z$$, размер которой лежит между $$n/3$$ и $$2n/3$$. Заменяя в формуле $$X$$ подформулу $$Z$$ независимой переменной $$z$$, получаем формулу $$Y$$ с такими же оценками на размер.

Пусть для $$Z$$ и $$Y$$ есть вычисляющие их схемы глубины не больше $$h$$. Построим для всей формулы $$X$$ схему глубины не больше $$h+3$$. Вычислим 3 переменные подсхемами глубины не больше $$h$$: $$y_0$$ — значение формулы $$Y$$ при $$z=0$$, $$y_1$$ — значение формулы $$Y$$ при $$z=1$$, $$s$$ — значение формулы $$Z$$. Значение $$f$$ всей формулы равно$$f =\left(y_0\wedge \neg s\right)\vee \left(y_1\wedge s\right).$$ Это формула глубины 3.

Итак, для $$h(L)$$ — минимальной глубины схемы, вычисляющей формулу размера $$L$$, выполнено рекуррентное соотношение:$$h(L)\leq h(\frac{2L}3)+3.$$ Из него следует $$h(L)=O(\log L)$$.

б) $$\Longrightarrow$$ а). Это совсем просто. Превратим граф схемы в дерево, размножая при необходимости вершины. Размер этого дерева не будет превышать количества ориентированных путей от выхода ко входам. А таких путей не более $$2^h$$.

1.20 Вспомним конструкцию неразрешимого предиката $$f_\ph(x)$$, принадлежащего P/poly, которая приведена в замечании 1.1.

Сейчас мы будем строить такой предикат $$f_\ph(x)$$, чтобы он был разрешим, но не принадлежал P. Мы построим такую вычислимую функцию $$\ph(n)$$, что любой алгоритм ее вычисления работает дольше, чем $$2^n$$. Другими словами, есть алгоритм распознавания принадлежности языку $$H$$, состоящему из двоичных записей тех чисел $$n$$, для которых $$\ph(n)=1$$ ; но время работы в наихудшем случае любого такого алгоритма на словах длины $$m$$ растет быстрее, чем $$2^{2^m}$$.

Докажем более общее утверждение. Пусть $$f(n)$$ — вычислимая функция. Обозначим через $$\calM_f$$ язык, состоящий из таких пар $$([M],x)$$, что машина $$M$$ на входе $$x$$ останавливается за время $$f(|x|)$$. Принадлежность этому языку разрешима (запустим универсальную машину Тьюринга со входом $$([M],x)$$, отсчитаем $$f(|x|)$$ тактов работы $$M$$ и посмотрим — остановилась ли $$M$$ ). Но быстро проверить эту разрешимость нельзя, как показывает следующее рассуждение, почти дословно повторяющее решение задачи 1.3.

Пусть машина $$A$$ распознает принадлежность языку $$\calM_f$$ слов длины $$n$$ за время $$T(n)$$. Тогда есть и такая машина $$A'$$, которая на входе $$X$$ запускает $$A$$ на входе $$(X,X)$$, после чего в случае ответа "да" переходит в состояние, в котором головка двигается вправо (и машина не останавливается), а в случае ответа "нет" останавливается. Смоделировать работу $$A$$ за время $$T(n)$$ можно за время $$T'(n)=O(T^2(n))$$. Если $$T'(n)<f(n)$$, то что скажет $$A$$ о слове $$([A'],[A'])$$? Если "да", то приходим к противоречию с определением машины $$A'$$, если "нет" — тоже приходим к противоречию. Поэтому $$T'(n)\geq f(n)$$, а $$T(n)\double=\Omega(f^{1/2}(n))$$.

Итак, мы доказали, что время работы любого алгоритма, распознающего принадлежность слова языку $$\calM_f$$ не меньше, чем $$\Omega(f^{1/2})$$.

Взяв в качестве $$f$$ функцию $$2^{2^n}$$, получим решение задачи.

Из раздела 2

2.1 Напомним, что литералом называется переменная или ее отрицание. Литералы будем обозначать $$l_1, l_2,\dots$$. Алгоритм решения задачи 2-КНФ будет работать в три этапа.

Этап 1. Перебираем все пары дизъюнкций. Если встречаем пару $$l_1\vee x$$, $$l_2\vee \neg x$$, то добавляем к КНФ дизъюнкцию $$l_1\vee l_2$$. Если все пары (включая добавленные дизъюнкции) просмотрены, то переходим к этапу 2.

Этап 2. Проверяем для каждой пары переменных, сколько дизъюнкций использует эту пару. Если каждая пара используется не более одного раза, то выдаем ответ "да" (КНФ выполнима). Если нашлась пара переменных, используемая по крайней мере в двух дизъюнкциях, выполняем сокращение: делаем подстановку равенств, указанных в третьей строчке следующей таблицы, во все дизъюнкции и если получаем противоречие ( $$(x=0)\wedge(x=1)$$ или $$(x=\neg y)\wedge(x=y))$$, то выдаем ответ "нет", в противном случае переходим к этапу 3.$$\begin{array}{llllll} x\vee y x\vee y x\vee y \neg x\vee y \neg x\vee \neg y \neg x\vee \neg y \\ \wedge \wedge \wedge \wedge \wedge \wedge \\ x\vee \neg y \neg x\vee y \neg x\vee \neg y x\vee \neg y \neg x\vee y x\vee \neg y \\ \hline x=1 y=1 x=\neg y x=y x=0 y=0 \end{array} }$$

Этап 3. Решаем полученную на этапе 2 задачу с меньшим числом переменных и повторяем ее ответ.

Корректность такого алгоритма вытекает из следующих наблюдений. Во-первых, в силу логического тождества$$\bigl((l_1\vee x)\wedge (l_2\vee \neg x)\bigr) \Longrightarrow (l_1\vee l_2),$$ на первом этапе мы добавляем следствия уже имеющихся конъюнкций. Во-вторых, для каждого столбца приведенной выше таблицы легко проверить, что конъюнкция первых двух строчек эквивалентна равенству в третьей строчке. Поэтому выполнимость исходной КНФ эквивалентна выполнимости сокращенной КНФ.

Наконец, докажем, что если на каждой паре переменных есть не более одной дизъюнкции, то КНФ, полученная ко второму этапу, выполнима. Присвоим значение переменной $$x_1$$ произвольным образом, затем учтем все следствия этого присвоения. Первой из переменных, которой не присвоено значение, также присвоим значение произвольным образом и т.д. Когда мы не получим выполняющего набора значений переменных? Только в том случае, если для некоторой переменной из значений ранее определенных переменных будут следовать и 0, и 1. Рассмотрим самое раннее такое противоречие. Оно означает, что имеются дизъюнкции $$l_1\vee x$$ и $$l_2\vee \neg x$$, а также, что $$l_1\vee l_2=0$$. Но это невозможно, так как в этом случае дизъюнкция $$l_1\vee l_2$$ также входит в КНФ после этапа 1.

Теперь оценим время работы алгоритма в худшем случае. Обозначим его через $$T(n)$$, где $$n$$ — число переменных (число переменных заведомо не превосходит длины входа). По построению имеем следующее рекуррентное соотношение$$T(n)\leq O(n^4)+T(n-1),$$ откуда следует $$T(n)=O(n^5)$$.

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

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

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

Если все вершины графа $$G$$ четной степени, то выберем в нем какой-нибудь замкнутый путь $$C$$. Выбросив ребра $$C$$ из графа $$G$$, получим некоторое количество связных графов $$G_1, \dots, G_r$$, у которых все степени вершин четные. Так что в каждом из этих графов есть эйлеров путь (по индукции). Каждый из таких графов имеет хотя бы одну вершину на $$C$$ (иначе $$G$$ был бы несвязным). Поэтому можно применить изложенную выше конструкцию, чтобы построить из $$C$$ и эйлеровых путей в графах $$G_j$$ эйлеров путь в $$G$$.

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

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

2.3. Рассмотрим предикат $$Q\in\NP$$. По определению$$Q(x)=\exists\, y\;\big((|y|<q(|x|))\wedge R(x,y)\big),$$ где $$q(\cdot)$$ — полином, а $$R(\cdot,\cdot)\in\P$$. В другой интерпретации слово $$y$$ — это сообщение Мерлина, доказывающее истинность $$Q(x)$$.

Предположим, что Артур полностью доверяет Мерлину, а тот имеет право отвечать только одним битом (и всегда дает правильный ответ на поставленный вопрос). Тогда Артур может восстановить слово $$y$$, выясняя его биты от первого до последнего, следующим образом. Если уже известны первые $$k$$ битов, образующие слово $$u$$, то Артур может поинтересоваться у Мерлина, существует ли слово $$u0z$$, такое что $$R(x,u0z)$$. При положительном ответе $$(k+1)$$ -й бит полагается равным 0, при отрицательном — 1.

Если $$\P=\NP$$, то Артур может имитировать Мерлина.

2.4 Принадлежность задачи о паросочетаниях классу NP очевидна: Мерлину достаточно разбить мальчиков и девочек на пары, после чего Артур сможет убедиться, что пар ровно $$n$$ и все выбранные пары согласны танцевать.

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

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

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

Обозначим текущее паросочетание через $$C$$, а множество вершин, инцидентных ребрам из $$C$$, — через $$W(C)$$. Предположим, что в графе есть паросочетание $$C'$$ большего размера. Рассмотрим граф $$A$$, образованный объединением ребер $$C$$ и $$C'$$. Степени вершин в таком графе не превосходят 2, поэтому его компоненты связности — это пути (возможно, длины 1, т.е. ребра) и циклы (см. рис. 15.2, где сплошными линиями изображены ребра из $$C$$, а штриховыми — из $$C'$$, на стрелки пока не нужно обращать внимание). Так как $$C'$$ имеет больше ребер, чем $$C$$, то в $$A$$ найдется компонента связности, содержащая больше ребер из $$C'$$, чем из $$C$$. Такая компонента является, как нетрудно видеть, чередующим путем.

Итак, проверка максимальности заданного паросочетания $$C$$ равносильна проверке существования чередующего пути. Последнюю можно сделать, например, так. Обозначим доли графа через $$V$$ и $$U$$. Ориентируем ребра графа согласно следующему правилу: ребра, входящие в $$C$$, направлены из $$V$$ в $$U$$, а все остальные ребра направлены противоположно (эта ориентация также изображена на рис. 15.2). Тогда существование чередующего пути равносильно существованию такой пары вершин $$u\in U\setminus W(C)$$ и $$v\in V\setminus W(C)$$, что из $$u$$ в $$v$$ есть ориентированный путь. Существование ориентированного пути с началом и концом в заданных вершинах проверяется способом, описанным в решении задачи 1.17, который работает и в случае ориентированного графа (матрица смежности становится несимметричной, что никак не влияет на вычисления).

Итак, мы доказали, что задача о паросочетаниях принадлежит $$\P$$. Описанный выше алгоритм не оптимален, читателю предлагается подумать, как можно его ускорить.

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

Очевидно, что задача клика для графа $$G$$ эквивалентна задаче независимое множество для дополнительного графа $$\bar G$$ (в дополнительном графе ребра и неребра меняются местами).

Возьмем 3-КНФ из $$m$$ дизъюнкций, в которые входят $$n$$ переменных. Граф, который сопоставляется этой КНФ, имеет $$2n+4m$$ вершин. Каждой переменной $$x_i$$ соответствуют две вершины, связанные ребром. Пометим их $$x_i$$ и $$\neg x_i$$ (см. рис. 15.3a). Каждой дизъюнкции соответствуют четыре вершины, попарно связанные ребрами между собой. Вершины, соответствующие переменным и дизъюнкциям, связаны между собой так, как показано на рис. 15.3б), (нарисован пример для дизъюнкции $$l_1\vee l_2\vee l_3$$ ).

Очевидно, что такой граф строится по 3-КНФ полиномиальным алгоритмом.

По построению графа ясно, что любое независимое множество его вершин содержит не более $$n+m$$ элементов. Докажем, что независимые множества размера $$n+m$$ находятся во взаимно однозначном соответствии с выполняющими наборами значений для 3-КНФ, которое задается правилом: если из пары вершин, помеченных $$x_i$$ и $$\neg x_i$$, в независимое множество входит вершина $$x_i$$, то в соответствующем этому независимому множеству наборе значений $$x_i=1$$, в противном случае $$x_i=0$$.

Из рис. 15.3б) легко усматривается корректность такого соответствия. В независимое множество размера $$n+m$$ обязана входить хотя бы одна вершина из четверки, соответствующей дизъюнкции. Но это означает, что хотя бы одна из вершин, помеченных $$\neg l_1$$, $$\neg l_2$$, $$\neg l_3$$, в это множество не входит. И наоборот, если взять множество $$S$$ вершин, соответствующих выполняющему набору для 3-КНФ, то оно однозначно дополняется до независимого множества размера $$n+m$$ (проверьте по рис. рис. 15.3б), что для каждого набора значений $$l_1,l_2,l_3$$ (кроме нулевого набора!) из четверки, соответствующей дизъюнкции, однозначно выбирается вершина, которую можно добавить к $$S$$ ).

2.6 б). Заметим, что число раскрасок в 3 цвета по очевидным причинам кратно 6: перестановка цветов сохраняет правильную раскраску.

Пусть есть 3-КНФ из $$m$$ дизъюнкций, в которые входят $$n$$ переменных. Граф, который сопоставляется этой КНФ, имеет $$7m+2n+3$$ вершин. Для описания структуры графа удобно пометить часть вершин. Во-первых, пометим три вершины числами 0, 1, 2. Во-вторых, пометим каждым литералом (переменной или ее отрицанием) по одной вершине. Остальные $$7m$$ вершин разобьем на группы по 7, каждая группа соответствует одной из дизъюнкций.

Теперь опишем ребра этого графа. Как показано на рис. 15.4а), вершины 0, 1 и 2 соединены между собой ребрами. На рис. 15.4б) показаны еще $$n$$ треугольников в этом графе. И, наконец, рис. 15.4в) показывает, как соединены ребрами вершины, соответствующие каждой дизъюнкции. На этом рисунке $$l_1$$, $$l_2$$, $$l_3$$ обозначают литералы, входящие в дизъюнкцию. Заметим, что некоторые ребра мы перечислили по нескольку раз.

Очевидно, что описанное выше построение можно выполнить за полиномиальное от $$n$$ и $$m$$ время. Докажем его корректность.

Рассмотрим, какие правильные раскраски в 3 цвета возможны для такого графа. Без ограничения общности можно считать, что вершины 0, 1 и 2 покрашены в цвета 0, 1 и 2 (из шести раскрасок, различающихся перестановками цветов мы выбрали одну). Тогда вершины, помеченные $$x_i$$ и $$\neg x_i$$, покрашены в цвета 0 и 1, причем их цвета должны быть противоположны (см. рис. 15.4б).

Прямым перебором вариантов можно проверить, что граф, изображенный на рис. 15.4в) удовлетворяет следующему свойству: если красить вершины, отмеченные литералами, в цвета 0 или 1, а вершины, отмеченные отрицаниями литералов, — в противоположные цвета 1 или 0, то правильная раскраска остальных вершин этого графа в 3 цвета существует (и единственна!) тогда и только тогда, когда хотя бы одно из значений литералов отлично от 0.

Поэтому правильные 3-раскраски построенного графа, для которых вершины $$0$$, $$1$$, $$2$$ покрашены в цвета $$0$$, $$1$$, $$2$$ соответственно, находятся во взаимно однозначном соответствии с выполняющими наборами значений переменных исходной 3-КНФ.

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

Итак, назовем данную задачу ("restricted puzzle"). Задача ("unrestricted puzzle") получается, если отказаться от ограничения на число типов квадратиков и требовать сложить прямоугольник заданных размеров, причем не из всего набора квадратиков, а из некоторого его подмножества.

Опишем неформально цепочку сводимостей$$\text{3-КНФ}\propto \text{UP}\propto \text{RP},$$ которая доказывает NP-полноту исходной задачи.

$$\text{3-КНФ}\propto \text{UP}$$. Для описания этой сводимости будем считать квадратики роботами, которые могут получать и передавать сообщения через стороны. Пара букв допустима, если одна из них означает передачу сообщения, а вторая — прием того же сообщения.

Итак, пусть есть 3-КНФ, множество переменных которой обозначим через $$X$$, а множество дизъюнкций — через $$\calD$$. Через $$\calD'$$ обозначим множество выполнимых дизъюнкций, получаемых из $$\calD$$ подстановкой значений некоторых переменных.

Будем теперь описывать множество квадратиков и их типы, из которых нужно будет складывать прямоугольник размера $$|X|\times|\calD|$$. Одна сторона этого прямоугольника (для определенности — левая) соответствует переменным КНФ, а другая (нижняя) — дизъюнкциям. Роботы-квадратики получают слева сообщения " $$x_j=1$$ " или " $$x_j=0$$ ", $$x_j\in X$$ ; передают вправо то же самое сообщение; получают снизу дизъюнкцию из $$\calD'$$ ; подставляют в нее, если возможно, переменную $$x_j$$ и передают полученную дизъюнкцию вверх, если не получено нулевое значение (другими словами, отсутствуют типы, получающие слева сообщения вида " $$x_j=\alpha$$ ", а снизу — " $$\alpha\oplus x_j$$ "). Все эти типы не содержат граничных букв. А есть еще 4 угловых типа, двум сторонам которых разрешено выходить на границу, и $$2|X|+2|\calD|$$ граничных типов (одна сторона может выходить на границу), которые нумеруются переменными и дизъюнкциями соответственно. Буквы, написанные на сторонах квадратиков граничных типов, обеспечивают однозначную сборку контура прямоугольника. Квадратик каждого типа один. А всего типов $$O(|X|\cdot|\calD|)$$.

Таким образом, выполнимость КНФ эквивалентна возможности сложить прямоугольник размера $$(|X|+2)\times(|\calD|+2)$$ из описанного выше набора типов квадратиков.

$$\text{UP}\propto \text{RP}$$. Пусть есть множество квадратиков, принадлежащих множеству типов $$T$$, каждого типа $$t$$ по $$n(t)$$ штук ( $$\sum_{t\in T}^{}n(t)=N$$ ), из которых нужно сложить прямоугольник $$m\times k$$. Без ограничения общности можно считать, что $$N>5$$. Добавим квадратиков: по 2 штуки из $$m+k$$ дополнительных типов $$c_j$$ и $$r_l$$, чтобы выложить внешний контур прямоугольника $$m\times k$$, $$4(N-mk)$$ квадратиков еще одного типа $$u$$, чтобы можно было использовать квадратики, не вошедшие в прямоугольник, и $$(5N+3)^2-5N-2(m+k)+4mk$$ квадратиков типа $$v$$ для получения квадрата. Поскольку $$5N+3> |T|+2(m+k)+2$$, ограничение числа типов длиной стороны квадрата будет выполнено.

Сформулированные условия прямо переводятся на язык букв и их сочетаний. На сторонах квадратиков типа $$v$$ написана одна и та же буква $$v$$, которая может соседствовать только сама с собой; на одной стороне квадратика типа $$u$$ написана буква $$u$$, которая может соседствовать со всеми буквами, а на остальных — $$v$$ ; наконец, на одной стороне квадратиков типов $$c_j$$ и $$r_j$$ написана буква $$v$$, а на остальных сторонах написаны буквы, обеспечивающие сборку контура прямоугольника $$m\times k$$.

Таким образом, чтобы собрать квадрат $$(5N+3)\times(5N+3)$$ из нового набора квадратиков $$1\times1$$, необходимо и достаточно уметь собирать прямоугольник $$m\times k$$ из некоторого подмножества исходного набора.

2.8. Поскольку умножение чисел можно произвести за полиномиальное время, Мерлин может сообщить Артуру любое разложение числа $$n$$ на два множителя.

2.9 Докажем принадлежность задачи ПРОСТОТА ЧИСЛА классу NP, построив для решения этой задачи недетерминированную машину Тьюринга $$N$$, которая рекурсивно вызывает саму себя.

На вход машине $$N$$ подается двоичная запись числа $$p$$, простоту которого нужно проверить. Машина недетерминированно дописывает первообразный корень $$g$$ по модулю $$p$$ и разложение на простые множители числа $$p-1$$, т.е. такие числа $$p_1$$, $$\dots$$, $$p_s$$, $$\alpha_1, \dots$$, $$\alpha_s$$, что$$p-1= \prod_{j=1}^{s}p_j^{\alpha_j}.$$ После этого машина проверяет равенство $$(*)$$ (на это хватит времени $$O(n^3)$$, где $$n=\log p$$, даже если умножать большие числа в "столбик"), проверяет равенство $$g^{p-1}\equiv1\pmod p$$ и все неравенства$$g^{(p-1)/p_j}\not\equiv1\pmod p.$$

Для этих проверок потребуется время $$O(n^4)$$, так как $$s=O(n)$$, а возведение в степень $$q$$ требует $$O(\log q)$$ умножений. Далее машина проверяет простоту всех $$p_j$$, рекурсивно вызывая саму себя.

Описанные выше проверки гарантируют, что порядок числа $$g$$ в группе $$(\ZZ/p\ZZ)^*$$ равен $$p-1$$, что эквивалентно простоте $$p$$.

Оценим теперь время работы такой НМТ на входе длины $$n$$. Оно складывается из времени, затрачиваемого на детерминированные действия, и времени, затрачиваемого на недетерминированные действия. Как следует из приведенных выше оценок, количество детерминированных действий ограничено полиномом от длины записей всех чисел, проверяемых на простоту за время работы. Длина записей первообразных корней и кратностей также ограничена полиномом (и даже линейно) от длины записей всех чисел, проверяемых на простоту.

Таким образом, осталось оценить длину записей чисел, проверяемых на простоту. Если взять произведение всех чисел, проверяемых на простоту на $$k$$ -м уровне рекурсии, то оно заведомо меньше исходного числа $$p$$. Поэтому суммарная длина записей этих чисел не более чем вдвое превышает длину записи $$p$$ (длина записи произведения двух чисел разве что на 1 меньше суммы длин сомножителей). Максимальное из чисел, проверяемых на простоту на $$k$$ -м уровне рекурсии, по крайней мере вдвое меньше, чем максимальное из чисел, проверяемых на $$(k-1)$$ -м уровне. Поэтому максимальный уровень рекурсии не превосходит $$\log p$$. Следовательно, общая длина записей всех чисел, проверяемых на простоту при входе $$p$$, равна $$O(\log^2p)$$.

Из раздела 4

4.1 Заметим прежде всего, что $$S$$ заведомо не меньше длины входа в силу иcпользуемых определенийБывают и другие определения. Так, например, класс log-SPACE определяется с помощью двухленточных машин, у которых на одной ленте записан вход и с нее можно только читать, а на второй ленте используется память $$O(\log n)$$ . .

Предположим, что доказана верхняя оценка вида $$2^{\poly(S)}$$ на время работы недетерминированной машины. Тогда можно дословно повторить доказательство теоремы 4.2, построить игру длины $$\poly(S)$$, и вычислить ее результат детерминированной машиной на памяти $$\poly(S)$$.

Пусть есть НМТ, работающая на памяти $$S$$. В процессе работы она может находиться не более чем в $$N=|\calA|^S\cdot|\calQ|\cdot S$$ состояниях, где $$\calQ,\calA$$ — множество состояний управляющего устройства и внешний алфавит, соответственно. Хотя у НМТ может быть несколько вариантов перехода из данного состояния, из последовательности переходов всегда можно выбросить циклы (ни к чему делать вначале неправильный переход, а затем, вернувшись в то же состояние, — правильный). Так что время работы НМТ ограничено $$2^{O(S)}$$, как и для детерминированной МТ.

4.2 Легко сообразить, как имитировать оракул $$F$$ из $$\Sigma_k$$, имея возможность заказывать оракул из $$\Pi_k$$. Нужно заказать оракул $$\neg F$$, а дальше брать отрицание от каждого результата его работы.

Класс $$P^{\Sigma_k}$$, как и $$\P$$, замкнут относительно взятия дополнений. Так что осталось доказать включение $$P^{\Sigma_k}\subseteq \Sigma_{k+1}$$. Это удобно делать, используя игровое определение классов $$\Sigma_k$$.

Пусть есть предикат $$F\in P^{\Sigma_k}$$, а вычисляющий его полиномиальный алгоритм использует оракул $$G\in \Sigma_k$$. Игру, которая задает $$G(x)$$, обозначим $$\calG(x)$$. Опишем теперь игру $$\calF(x)$$, выигрыш белых в которой (точнее, наличие выигрышной стратегии) эквивалентен $$F(x)$$.

Первый ход белых в этой игре состоит в объявлении последовательности пар $$(f_j, x_j)_{j=1}^q$$. Белые утверждают, что эта последовательность есть протокол обращений к оракулу в процессе работы алгоритма с оракулом $$G$$, вычисляющего $$F(x)$$. Более точно это означает, что алгоритм обращается к оракулу $$q$$ раз, $$j$$ -й запрос делается о слове $$x_j$$, оракул отвечает на это запрос $$f_j$$, и окончательный результат $$F(x)=1$$. Следующим ходом черные объявляют индекс $$j$$ и, если $$f_j=0$$, то дополнительно первый ход белых в игре $$\calG(x_j)$$. Далее, если $$f_j=1$$, то разыгрывается игра $$\calG(x_j)$$, а если $$f_j=0$$, то разыгрывается игра $$\calG(x_j)$$ со сдвигом "на темп": $$(i+1)$$ -й ход белых в $$\calF(x)$$ в этом случае соответствует $$i$$ -у ходу черных в $$\calG(x_j)$$, а $$(i+1)$$ -й ход черных — $$(i+1)$$ -у ходу белых в $$\calG(x_j)$$, $$(k+1)$$ -й ход черных на результат влияния не оказывает.

Белые выигрывают в этой игре, если $$(x_j)_{j=1}^q$$ — правильная последовательность аргументов при обращениях к оракулу, результат игры $$\calG(x_j)$$ совпадает с $$f_j$$, а результат работы алгоритма для вычисления $$F$$ на входе $$x$$ с ответами оракула $$(f_j)_{j=1}^q$$ равен 1.

Достаточно ясно, что если $$F(x)=1$$, то у белых есть выигрышная стратегия в $$\calF(x)$$: первым ходом сказать правду, а дальше играть в $$\calG(x_j)$$ по стратегиям, существование которых вытекает из равенства $$f_j=G(x_j)$$. Если же $$F(x)=0$$, то в каком-то члене $$(f_m, x_m)$$ последовательности $$(f_j, x_j)_{j=1}^q$$ белые должны отклониться от истины. Черные своим ходом должны объявить $$m$$ (и, дополнительно, первый ход за белых в игре $$\calG(x_m)$$ при необходимости), дальнейшая их стратегия состоит в том, чтобы доказывать $$f_j\ne G(x_j)$$, пользуясь соответствующими стратегиями для $$\calG(x_j)$$.

Из раздела 6

6.1. Поскольку конъюнкция и отрицание образуют полный базис для обычных схем, из лемм 6.1, 6.2 следует, что достаточно реализовать функции $$\neg_\oplus\colon(x,y)\mapsto(x,x\oplus y\oplus 1)$$ и $$\qxor$$. Заметим, что $$\neg_\oplus[1,2]\double=\neg[2]\qxor[1,2]$$, поэтому достаточно реализовать $$\qxor$$. Для этого заведем вспомогательный бит $$u$$, содержащий константу 1 (для этого в самом начале и в самом конце применяем $$\neg[u]$$ ). Тогда $$\qxor\:[1,2]=\wedge_\oplus[u,1,2]$$.

Из раздела 7

7.1 Из доказательства теоремы 7.1 следует, что достаточно научиться реализовывать все операторы вида $$\Lambda(X)$$, $$X\inU(2)$$ (управляемый двумя q-битами фазовый сдвиг на $$-i$$ является частным случаем: $$\Lambda^2(-i)=\Lambda(K^{-1})$$ ). Для алгоритма построения схемы требуется также конструктивное доказательство леммы 7.1.

Сперва реализуем управляемый фазовый сдвиг:$$\Lambda(P(\phi))[1,2]=E(\phi)[1], \quad \text{где } P(\phi)=\begin{pmatrix} e^{i\phi}0\\ 0e^{i\phi} \end{pmatrix},\quad E(\phi)=\begin{pmatrix} 10\\ 0e^{i\phi} \end{pmatrix}.$$ Поскольку $$\Lambda(XY)=\Lambda(X)\Lambda(Y)$$, то остается реализовать операторы $$Y$$ из $$U(2)/U(1)$$, где $$U(1)$$ — подгруппа фазовых сдвигов. Можно считать, что $$Y\in\SU(2)$$. Эта реализация изображена на рис. 15.5. Используемые в ней операторы $$A$$ и $$B$$ должны удовлетворять уравнению$$A\sx A^{-1} B\sx B^{-1}=Y.$$ Геометрически уравнение $$(*)$$ эквивалентно такому утверждению: любое вращение трехмерного пространства есть композиция двух поворотов на угол $$180^\circ$$. Доказательство этого утверждения можно усмотреть из рис. 15.6.

Осталось доказать лемму 7.1 конструктивно. Для начала заметим, что для любых чисел $$c_1,c_2$$ существует унитарная матрица $$V$$ размера $$2\times 2$$ (эффективно вычислимая с любой заданной точностью $$\delta$$ ), такая что$$V \left(\begin{array}{@{}c@{}} c_1\\c_2 \end{array}\right) = \left(\begin{array}{@{}c@{}} \sqrt{|c_1|^2+|c_2|^2}\\0 \end{array}\right).$$ Следовательно, для любого единичного вектора $$\ket\xi\in\CC^M$$ существует последовательность унитарных матриц $$V^{(1)},\dots,V^{(M-1)}$$, такая что $$V^{(1)}\cdot\ldots\cdot V^{(M-1)}\ket{\xi}=\ket{1}$$, где $$V^{(s)}$$ действует на подпространстве $$\CC\bigl(\ket{s},\,\ket{s+1}\bigr)$$ (как матрицы в условии леммы 7.1) и оставляет неизменными остальные базисные векторы.

Пусть теперь задана унитарная матрица $$U$$ размера $$M\times M$$. Умножая $$U^{-1}$$ слева на подходящие матрицы $$U^{(1,1)},\dots,U^{(1,M-1)}$$, можно перевести первый столбец в вектор $$\ket{1}$$. При этом столбцы остаются ортогональными, поэтому первая строка переходит в $$\bra{1}$$. Действуя таким же образом с остальными столбцами, получаем набор матриц $$U^{(j,s)}$$ \, ( $$1\le j\le s\le M-1$$ ) (где $$U^{(j,s)}$$ действует на $$\ket{s}$$ и $$\ket{s+1}$$ ), удовлетворяющий условию$$U^{(M-1,M-1)}U^{(M-2,M-2)}U^{(M-2,M-1)}\cdot\ldots\cdot U^{(1,1)}\cdot\ldots\cdot U^{(1,M-1)}\, U^{-1} = I.$$ Этот набор строится алгоритмом сложности $$O(M^3)\cdot\poly(\log(1/\delta))$$.

7.2 Неравенство (7.6) следует из цепочки неравенств, справедливых для любого $$\ket\xi$$:$$\big\| XY\ket\xi\big\|\leq \| X\|\cdot \big\|Y\ket\xi\big\|\leq \| X\|\cdot \|Y \|\cdot\big\|\ket\xi\big\|.$$

Для доказательства равенства (7.7) заметим, что собственные числа операторов $$XX^\dagger$$ и $$X^\dagger{}X$$ совпадают.

И, наконец, равенство (7.8) следует из того, что собственные числа оператора $$(X\otimes Y)^\dagger(X\otimes Y)\double=X^\dagger X\otimes Y^\dagger Y$$ имеют вид $$\lambda_j\mu_k$$, где $$\lambda_j$$ и $$\mu_k$$ — собственные числа $$X^\dagger X$$ и $$Y^\dagger Y$$, соответственно.

7.3. Достаточно проверить для двух сомножителей. Имеем$$\begin{align*} \tilde U_2\tilde U_1\left(\ket\xi\otimes\ket{0^{N-n}}\right)= \tilde U_2\left(U_1\ket\xi\otimes\ket{0^{N-n}}+\ket{\eta_1}\right)= \\= U_2U_1\ket\xi\otimes\ket{0^{N-n}}+\ket{\eta_2}+\tilde U_2\ket{\eta_1}, \end{align*}$$ где $$\big\|\ket{\eta_j}\big\|\le\delta_j$$, ( $$j=1,2$$ ). Поэтому$$\bigl\|\tilde U_2\tilde U_1\bigl(\ket\xi\otimes\ket{0^{N-n}}\bigr)- U_2U_1\ket\xi\otimes\ket{0^{N-n}}\bigr\| \le \delta_1+\delta_2.$$

7.4 Обозначим $$\calM=\BB^{\otimes n}\otimes\ket{0^{N-n}}$$. Будем искать оператор в виде $$W=(U\otimes I_{[n+1,\dots,N]})\Pi_\calM +\tilde W(I-\Pi_\calM)$$, где унитарный оператор $$\tilde W$$ сохраняет $$\calM^\perp$$. Для такого $$W$$, очевидно, выполняется равенство$$W\left(\ket\xi\otimes\ket{0^{N-n}}\right)= (U\ket\xi)\otimes\ket{0^{N-n}},$$ а $$\|W-\tilde U\|\le O(\delta)$$ эквивалентно тому, что для всех $$\ket\eta\in\calM^\perp$$ выполняется $$\rlap{\phantom{\raise1.5pt\hbox{\big\|}}} \big\|(\tilde W-\tilde U)\ket\eta\big\|=O(\delta)$$. Представляя $$\tilde W= X\tilde U$$, получаем эквивалентные условия на унитарный оператор $$X$$:$$\|X-I\|=O(\delta),\qquad X\calL^\perp=\calM^\perp,$$ где $$\calL=\tilde U\calM$$.

Теперь нам потребуется следующая лемма.

Лемма. Пусть $$\calL$$ и $$\calM$$ — подпространства конечномерного пространства $$\calN$$, такие что $$\|\Pi_\calL-\Pi_\calM\|\leq\delta$$, $$\delta<\slashfrac{1}{2}$$. Тогда найдется унитарный оператор $$X$$, такой что $$\|X-I\|=O(\delta)$$ и $$X\calL=\calM$$. (Значит, и $$X\calL^\perp=\calM^\perp$$.)

Доказательство. Возьмем оператор $$Y=\Pi_\calM\Pi_\calL+(I-\Pi_\calM)(I-\Pi_\calL)$$. Сразу видно, что он переводит $$\calL$$ в $$\calM$$ и $$\calL^\perp$$ в $$\calM^\perp$$. Для нормы $$\|Y-I\|$$ имеем оценку$$\begin{multiline*} \|Y-I\|=\|\Pi_\calM\Pi_\calL-\Pi_\calM-\Pi_\calL+\Pi_\calM\Pi_\calL\|\leq \\ \leq \|(\Pi_\calM-\Pi_\calL)\Pi_\calL\|+ \|\Pi_\calM(\Pi_\calM-\Pi_\calL)\|\leq 2\delta<1. \end{multiline*}$$ Оператор $$Y$$ не унитарный. Но из приведенной оценки следует, что он невырожденный. Рассмотрим унитарный оператор $$X\double=Y(Y^\dagger Y)^{-1/2}$$. Оператор $$Y^\dagger Y$$ сохраняет подпространство $$\calL$$, поэтому $$X$$ переводит $$\calL$$ в $$\calM$$. Для оценки нормы $$X$$ разложим $$(Y^\dagger Y)^{-1/2}$$ в ряд Тейлора$$(Y^\dagger Y)^{-1/2} =I+\frac{1}{2}Z+\frac{3}{8}Z^2+\dots,\qquad \text{где } Z=I-Y^\dagger Y.$$ Поэтому $$\|(Y^\dagger Y)^{-1/2}-I\|\leq (1-\|Z\|)^{-1/2}-1=O(\delta)$$, отсюда получаем $$\|X-I\|=O(\delta)$$.

Чтобы применить лемму, необходимо оценить величину $$\|\Pi_\calL-\Pi_\calM\|$$. Имеем $$\|(\tilde U-U\otimes I)\Pi_\calM\|\le\delta$$ ( $$\tilde U$$ приближает $$U$$ в расширенном смысле с точностью $$\delta$$ ). Обозначая $$V=U\otimes I$$, получаем$$\|\Pi_\calL-\Pi_\calM\|= \|\tilde U\Pi_\calM\tilde U^\dagger-V\Pi_\calM V^\dagger\|\le 2\delta.$$ Итак, условие леммы выполнено (и задача решена) при $$\delta<1/4$$.

7.5 Схему для оператора $$\Lambda(U)$$ можно построить, используя элемент Фредкина $$F=\Lambda(\leftrightarrow)$$ — управляемый обмен битами. Элемент Фредкина задается соотношениями$$F\colon |a,b,c\rangle\,\mapsto \left\{ \begin{array}{ll} |0,b,c\rangle \quad \mbox{если}\ a=0, \\ |1,c,b\rangle \quad \mbox{если}\ a=1. \end{array} \right.$$ Его можно реализовать следующим образом:$$F[1,2,3]=\Lambda(\qxor)[1,2,3]\ \Lambda(\qxor)[1,3,2]\ \Lambda(\qxor)[1,2,3]$$ (заметим, что $$\Lambda(\qxor)=\Lambda^2(\sigma_x)$$ — это элемент Тоффоли).

На рис. 15.7 показано, как из схемы для оператора $$U$$, сохраняющего $$\ket0$$, построить схему для $$\Lambda(U)$$. В прямоугольниках происходит управляемый обмен q-битами (параллельно действует нужное количество элементов Фредкина). Если управляющий q-бит равен $$\ket1$$, то на вход схемы, вычисляющей $$U$$, будет подан $$\ket\xi$$, в противном случае — $$\ket0$$.

7.6 Каждый из рассматриваемых поворотов порождает всюду плотное подмножество в подгруппе поворотов относительно фиксированной прямой. Поэтому осталось доказать, что повороты относительно двух различных прямых порождают $$\SO(3)$$. Для этого достаточно доказать, что подгруппа, порожденная всеми поворотами относительно двух различных прямых, действует транзитивно на сфере (или на проективной плоскости — множестве одномерных подпространств). Справедливость этого факта очевидна из рис. 15.8 (если можно перемещаться по двум семействам параллелей, то из любой точки на сфере можно попасть в любую другую). Строгое доказательство получается аналогично решению задачи 7.7.

Замечание. Это решение неконструктивно: нельзя дать никакой верхней оценки на количество поворотов $$X,X^{-1},Y,Y^{-1}$$, композиция которых приближает заданный элемент $$U\in\SO(3)$$ с заданной точностью $$\delta$$. Причина неконструктивности состоит в следующем. Поворот на угол $$2\pi\alpha$$, где $$\alpha$$ — иррациональное, порождает всюду плотное подмножество в группе поворотов относительно фиксированной прямой (эта группа, очевидно, изоморфна $$\RR/\ZZ$$ ). Однако число $$\alpha$$ может очень хорошо приближаться рациональными числами (это имеет место, когда коэффициенты цепной дроби, представляющей $$\alpha$$, очень быстро растут). Тогда любое $$r\in\RR/\ZZ$$ приближается элементами вида $$n\alpha$$ ( $$n\in\ZZ$$ ) с любой точностью $$\delta>0$$, но число $$n$$ может быть сколь угодно велико: больше, чем любая наперед заданная функция $$\delta$$.

Конструктивное доказательство и эффективный (при фиксированных $$X$$ и $$Y$$ ) алгоритм построения аппроксимаций довольно сложны [4].

7.7 Обозначим $$\ket{\xi'}=V^{-1}\ket\xi$$, тогда $$H'=V^{-1}HV$$ — стабилизатор $$\CC(\ket{\xi'})$$. Так что утверждение задачи приобретает вид: объединение стабилизаторов двух несовпадающих одномерных подпространств порождает $$U(\calM)$$.

Достаточно показать, что группа $$G$$, порожденная $$H\cup H'$$, действует транзитивно на множестве единичных векторов. Действительно, пусть для каждого $$\ket\psi\in\calM$$ найдется оператор $$U_\psi\in G$$, такой что $$U_{\psi}\ket\xi=\ket\psi$$. Тогда$$U(\calM)=\bigcup\limits_{\ket\psi\in\calM} U_{\psi} H.$$

Доказываем транзитивность действия группы $$G$$. Заметим, что$$\begin{equation*} H\ket\psi=Q(\vartheta)\bydef\{\ket\eta : |\langle \eta\,|\, \xi \rangle| = \cos\vartheta \}, \\ H'\ket\psi=Q'(\vartheta')\bydef\{\ket\eta : |\langle \eta\,|\, \xi' \rangle| = \cos\vartheta'\}, \end{equation*}$$

где $$\vartheta,\vartheta'$$ обозначают углы между $$\ket\psi$$ и $$\ket\xi$$, $$\ket\xi'$$ соответственно: $$\cos\vartheta\double=|\langle \psi\,|\, \xi\rangle|$$, $$\cos\vartheta'=|\langle \psi\,|\, \xi'\rangle|$$, $$0\leq \vartheta,\vartheta'\leq\pi/2$$. В последующих формулах используется также угол $$\alpha$$ между векторами $$\ket\xi$$ и $$\ket\xi'$$: $$\cos\alpha= |\langle \xi\,|\, \xi'\rangle|$$,\, $$0\leq \alpha\leq\pi/2$$.

Можно проверить, что при $$\dim\calM\geq3$$$$\begin{equation*} HQ'(\vartheta')=\bigcup_{|\alpha-\vartheta'|\leq \vartheta\leq\min(\alpha+\vartheta',\pi/2)} Q(\vartheta),\\ H'Q(\vartheta)=\bigcup_{|\alpha-\vartheta|\leq \vartheta'\leq\min(\alpha+\vartheta,\pi/2)} Q'(\vartheta'). \end{equation*}$$ Поэтому$$\begin{equation*} H'\ket\xi = Q'(\alpha),\\ HH'\ket\xi = \bigcup_{0\leq\vartheta\leq\min(2\alpha,\pi/2)} Q(\vartheta),\\ H'HH'\ket\xi = \bigcup_{0\leq\vartheta'\leq\min(3\alpha,\pi/2)} Q'(\vartheta'), \end{equation*}$$ и т.д. Таким образом, действуя на вектор $$\ket\xi$$ попеременно элементами из $$H'$$ и $$H$$ достаточное количество раз, можно получить любой единичный вектор $$\ket\psi$$.

7.8 Поскольку $$\sx=HK^2H$$, то стандартный базис содержит полный базис для классических обратимых вычислений (см. задачу 6.1). Это, благодаря задаче 7.5, позволяет реализовать операторы $$\Lambda(U)$$ для всех элементов базиса, кроме $$H$$.

Теперь рассмотрим оператор $$X=\Lambda(HKH)=H\Lambda(K)H$$, который, в силу сказанного, реализуется в стандартном базисе (оператор $$K$$ сохраняет $$\ket0$$ ). Подействуем им на $$\BB^{\otimes2}$$ двумя возможными способами: $$X_1=X[1,2]$$, $$X_2=X[2,1]$$. Операторы $$Y_1=X_1X_2^{-1}$$, $$Y_2=X_2^{-1}X_1$$ также реализуются в стандартном базисе.

Заметим, что операторы $$X_1$$, $$X_2$$ (следовательно, и $$Y_1$$, $$Y_2$$ ) сохраняют векторы $$\ket{00}$$ и $$\ket{\eta} =\ket{01}+\ket{10}+\ket{11}$$. Кроме того, вычислениями проверяется, что $$Y_1$$, $$Y_2$$ не коммутируют и имеют, помимо 1, собственные числа $$\lambda_{1,2}=(1\pm\sqrt{-15})/4=e^{\pm i\ph/2}$$. В $$\SO(3)\cong U(2)/U(1)$$ оператору с такими собственными числами соответствует поворот на угол $$\ph$$. Поскольку $$\lambda_{1,2}$$ не являются корнями из $$1$$ (и даже целыми алгебраическими числами, так как их след равен $$1/2$$ ), угол $$\ph$$ несоизмерим с $$\pi$$. А поскольку эти операторы не коммутируют, им соответствуют повороты вокруг различных прямых. Поэтому $$Y_1$$, $$Y_2$$ порождают всюду плотное подмножество в $$U(\calL)/U(1)$$, где $$\calL=\CC(\ket{00},\ket{\eta})^\perp$$ (см. задачу 7.6).

Для завершения доказательства дважды применим результат задачи 7.7. Операторы $$Y_1$$, $$Y_2$$ порождают всюду плотное множество в $$U(\calL)/U(1)$$, оператор $$V=\Lambda(K)$$ сохраняет $$\CC(\ket{00})$$ и не сохраняет $$\CC(\ket{\eta})$$. Так что $$Y_1$$, $$Y_2$$, $$V^{-1}Y_1V$$, $$V^{-1}Y_2V$$ порождают всюду плотное множество в $$U\bigl(\calL\oplus\CC(\ket\eta)\bigr)/U(1)$$. Оператор $$H[1]$$ не сохраняет $$\CC(\ket{00})$$ ; применяя результат задачи 7.7 еще раз, получаем всюду плотное множество в $$U(\BB^{\otimes2})/U(1)$$.

7.9 Из предыдущей задачи следует, что можно реализовать оператор $$\Lambda(c)$$ с точностью до фазового множителя, $$\Lambda(c)=e^{i\ph}U$$. Оператор $$\sx$$ реализуется точно. Возьмем дополнительный q-бит в состоянии $$\ket0$$ и применим $$\sx U\sx U^{-1}\colon \ket0\mapsto c\ket0$$. Неизвестный фазовый множитель сокращается.

7.10 В базисе $$\ket\xi=\frac{1}{\sqrt2}(\ket0+\ket1)$$, $$\ket\eta=\frac{1}{\sqrt2}(\ket0-\ket1)$$ оператор $$\sx$$ диагонализуется, так что в этом базисе $$R$$ имеет вид$$R=-i\exp(\pi i\alpha\sx)= -i \begin{pmatrix} e^{\pi i\alpha}0\\ 0e^{-\pi i\alpha} \end{pmatrix}\,.$$ А раз $$\alpha$$ — иррациональное число, степенями $$R$$ можно приближенно реализовать любой оператор вида $$i^s\exp(i\phi\sx)$$, который в указанном выше базисе имеет матрицу $$i^s\begin{pmatrix} z0\\ 0z^{-1} \end{pmatrix}$$, где $$s=0,1,2,3$$, $$|z|=1$$. В геометрической интерпретации эти операторы соответствуют поворотам вокруг оси $$x$$. При $$s=3$$ и $$z=i$$ получаем элемент Тоффоли: $$\bigl(\Lambda^2(R)\bigr)^k\approx\Lambda^2(\sigma^x)$$ (при подходящем $$k$$ ), так что уже имеем полный классический базис. При $$s=1$$ и $$z=1$$ получаем $$\Lambda^2(i)=\Lambda(K)$$ (на третий q-бит этот оператор действует тождественным образом). Из $$\Lambda(K)$$ можно сделать $$K$$, подавая на управляющий q-бит константу $$\ket{1}=\sigma^x\ket{0}$$. С точностью до фазового множителя $$K$$ — это поворот на $$90^\circ$$ вокруг оси $$z$$, а композициями поворотов вокруг $$x$$ и одного поворота вокруг $$z$$ представляются все элементы $$\SO(3)$$ (аналогично задаче 7.7).

Итак, мы получили реализацию всех операторов из $$U(2)$$ с точностью до фазового множителя. Осталось использовать задачу 7.9 для того, чтобы реализовать $$H$$.

7.11 Любое вращение трехмерного пространства представляется как композиция трех поворотов: на угол $$\alpha$$ вокруг оси $$z$$, затем на угол $$\beta$$ вокруг оси $$x$$, затем на угол $$\gamma$$ вокруг оси $$z$$. Поэтому любой оператор, действующий на одном q-бите, представляется в виде$$U=e^{i\phi}e^{i(\gamma/2)\sz}e^{i(\beta/2)\sx}e^{i(\alpha/2)\sz}.$$

Каждый из операторов в правой части $$(*)$$ выражается через $$H$$ и управляемые фазовые сдвиги:$$\begin{align*} e^{i\phi}=\Lambda(e^{i\phi})\sx\Lambda(e^{i\phi})\sx, e^{i\phi\sz}=\Lambda(e^{-i\phi})\sx\Lambda(e^{i\phi})\sx,\\ \sx=H\Lambda(e^{i\pi})H, e^{i\phi\sx}=He^{i\phi\sz}H. \end{align*}$$

Таким образом, для решения задачи достаточно построить схему, представляющую управляемый фазовый сдвиг $$\Lambda(e^{i\theta})$$ с точностью $$O(\delta)$$.

Выберем такое $$q=2^n$$, что $$\slashfrac{1}{\delta}\leq q<\slashfrac{2}{\delta}$$. Предположим, что у нас в распоряжении есть $$n$$ -битовый регистр в состоянии$$\ket{\psi_n(q,k)}=\frac{1}{\sqrt{q}}\sum_{j=0}^{q-1} \exp\bigl(2\pi i\frac{kj}{q}\bigr)\ket{j}.$$ Заметим, что $$\ket{\psi_n(q,k)}$$ — собственный вектор классического оператора $$V\colon\ket{j}\mapsto\ket{(j-1)\bmod q}$$:$$V^l\ket{\psi_n(q,k)} = e^{2\pi i (kl/q)}\ket{\psi_n(q,k)}.$$ Применяя к $$\ket{\psi_n(q,k)}$$ оператор $$V^l$$, управляемый дополнительным q-битом, получаем искомый фазовый сдвиг на этом q-бите:$$\Lambda(V^l)\bigl(\ket\xi\otimes\ket{\psi_n(q,k)}\bigr) = \Lambda(e^{2\pi i (kl/q)})\ket\xi\otimes\ket{\psi_n(q,k)}.$$

(Классический) оператор $$\Lambda(V^l)$$ можно задать схемой линейного размера в стандартном базисе. Если $$k$$ — нечетно, то выбором подходящего $$l$$ можно представить оператор $$\Lambda(e^{i\theta})$$ с точностью $$\slashfrac{2\pi}{q}=O(\delta)$$.

Вместо того, чтобы строить схему, порождающую $$\ket{\psi_n(q,k)}$$, будем брать смесь $$\ket{\psi_n(q,k)}$$ при разных $$k$$, измерять значение $$k$$ и выбирать $$l$$, соответствующее этому измеренному значению. Опишем требуемые действия.

Чтобы вероятность ошибки была меньше $$\delta^2$$, нужны $$O(\log(1/\delta))$$ элементарных измерений для каждого из операторов $$V$$, $$V^2$$ $$,\dots$$, $$V^{2^{n-1}}$$. Поскольку $$n=O(\log(1/\delta))$$, общий размер схемы — $$O(\log^3(1/\delta))$$.

Из раздела 8

8.1 Пусть $$\sum_{z}^{} \Bigl|\langle F(x),z|\,U\,|x,0^{N-n}\rangle\Bigr|^2 = 1-\eps_x$$, и $$\eps_x\leq\eps<1/2$$ для всех $$x$$. Нам нужно оценить величину$$p(x)=\mkern-15mu\sum_{\scriptstyle\begin{gathered} \scriptstyle f_1,\dots,f_k\\[-8pt] \scriptstyle z_1,\dots,z_k\end{gathered}}^{} \Bigl| \langle f_1,z_1,\dots,f_k,z_k, F(x), 0^{s} |\,MU^{\otimes k}\,| (x,0^{N-n})^{k}, 0^{m+s}\rangle \Bigr|^2,$$ где $$M$$ — оператор, реализующий применение функции MAJ к соответственным битам $$k$$ регистров ответа исходной схемы и записывающий значение этой функции в регистр окончательного ответа. (Длина ответа равна $$m$$, а $$s$$ дополнительных битов используются при вычислении MAJ).

Если более половины регистров ответа исходной схемы содержат $$F(x)$$, то результатом применения $$M$$ обязательно будет $$F(x)$$. Поэтому, аналогично (3.1), имеем$$\begin{multiline*} 1-p(x)\leq\\ \leq\mkern-5mu \sum_{\scriptstyle \begin{gathered} \scriptscriptstyle S\subseteq\{1,\dots,k\},\\[-7pt] \scriptscriptstyle|S|\leq k/2\end{gathered}} \sum_{\scriptstyle \begin{gathered} \scriptscriptstyle f_1,\dots,f_k,\\[-7pt] \scriptscriptstyle f_j=F(x)\,\Leftrightarrow\,j\in S\end{gathered}} \sum_{z_1,\dots,z_k} \Bigl| \langle f_1,z_1,\dots,f_k,z_k |U^{\otimes k}| (x,0^{N-n})^{k}\rangle \Bigr|^2=\\ =\mkern-5mu \sum_{\scriptstyle\begin{gathered} \scriptscriptstyle S\subseteq\{1,\dots,k\},\\[-6pt] \scriptscriptstyle|S|\leq k/2\end{gathered}} (1-\eps_x)^{|S|}\eps_x^{k-|S|}= \bigl((1-\eps_x)\eps_x\bigr)^{k/2} \sum_{\scriptstyle\begin{gathered} \scriptscriptstyle S\subseteq\{1,\dots,k\},\\[-6pt] \scriptscriptstyle|S|\leq k/2\end{gathered}} \left(\frac{\eps_x}{1-\eps_x}\right)^{k/2-|S|}\leq\\ \leq\left(\sqrt{(1-\eps_x)\eps_x}\right)^k 2^k\,\leq\,\lambda^k, \quad \text{где }\lambda=2\sqrt{(1-\eps)\eps.} \end{multiline*}$$

8.2 Поскольку $$H^2=I$$, имеем цепочку равенств:

Оператор $$\Lambda(\sz)$$ умножает $$\ket{1,1}$$ на $$-1$$, а остальные базисные векторы не меняет.

Если сделать замену базиса только в управляющем q-бите, как показано на рисунке ниже, то получится оператор, который является произведением отрицаний в обоих q-битах и "оператора диффузии" (в лекции 8 мы обозначали его $$V$$ ). Действительно,$$\begin{equation*} H[1]\Lambda(\sx)[1,2]H[1]\ket{a,b}= H[1]\Lambda(\sx)[1,2] \frac{1}{\sqrt2}\sum_{c}^{}(-1)^{ac}\ket{c,b}=\\ =H[1]\frac{1}{\sqrt2}\sum_{c}^{}(-1)^{ac}\ket{c,b\oplus c}= \frac{1}{2}\sum_{c,d}^{}(-1)^{(a+d)c}\ket{d,b\oplus c}=\\ =\frac{1}{2}\sum_{c,b'}^{}(-1)^{(a+d)(b+b')}\ket{d,b'}. \end{equation*}$$

На рисунке слева показана схема вычисления такого оператора, а справа — его матрица в стандартном базисе:

8.3 $$\BPP\subseteq\BQP$$. Классическое вероятностное вычисление можно представить обратимой схемой $$(U_1,\dots,U_L)$$, которая, наряду со входом $$x$$, использует случайную последовательность нулей и единиц $$r\in\cb^s$$. (Кроме полезного ответа, схема может создавать мусор — это неважно). Заменим перестановки $$U_j$$ на соответствующие унитарные операторы $$\hat U_j$$, а вместо случайного слова $$r$$ приготовим состояние$$\ket\psi = H^{\otimes s}\ket{0^s} = 2^{-s/2}\sum_{r\in\cb^s}\ket{r}.$$

$$\BQP\subseteq \PPP$$. Пусть схема $$(U_1,\dots, U_L)$$ вычисляет предикат $$F(x)$$ с вероятностью ошибки $$\le 1/3$$, общее число битов в схеме равно $$N$$, а $$|x|=n$$. Вероятность получения ответа 1 выражается через проектор $$\Pi^{(1)}=\ket{1}\bra{1}$$, примененный к первому q-биту:$$\begin{equation*} p(x) =\, \langle x,0^{N-n} | U_1^\dagger U_2^\dagger\cdot\ldots\cdot U_L^\dagger \,\Pi^{(1)}[1]\, U_LU_{L-1}\cdot\ldots\cdot U_1 | x,0^{N-n} \rangle =\\ =\, 2^{-h} \langle x,0^{N-n} | V_{L}V_{L-1}\cdot\ldots\cdot V_{-L+1}V_{-L} | x,0^{N-n} \rangle. \end{equation*}$$ Здесь $$V_{L},\dots,V_{-L}$$ — перенумерованные операторы $$U_1^\dagger,\dots,\Pi^{(1)}[1],\dots$$ $$\dots,U_1$$ с одним исключением: если $$U_k=H[m]$$ (или $$U_k^\dagger=H[m]$$ ), то соответствующий оператор $$V_j$$ равен $$\sqrt{2}H[m]$$ ; количество элементов $$H$$ в схеме обозначено через $$h$$.

Матричные элементы операторов $$V_j\in\{\sqrt{2}H,K,K^\dagger,\QXOR,\Lambda^2(\sx)$$, $$\Pi^{(1)}\}$$ принадлежат множеству$$M=\{0,\, +1,\, -1,\, +i,\, -i\}.$$ Перемножая матрицы, мы получаем сумму чисел из множества $$M$$. Поскольку интересующая нас величина $$p(x)$$ вещественная, мы можем ограничиться суммированием $$\pm 1$$. Кратности слагаемых будут выражаться в виде$$\#_a(x)=|\{w:C_a(x,w)=1\}|, \quad a\in\{\pm1\},$$ где предикаты $$C_a(x,w)\in\P$$ определены ниже. Получаем представление$$p(x)=2^{-h}(\#_1(x)-\#_{-1}(x)).$$ Дальнейшее приведение условия $$(*)$$ к виду из определения класса PPP уже не будет использовать никакой квантовой специфики.

Теперь опишем предикаты $$C_a(x,w)$$ формально. Матричные элементы произведения $$V_L\cdot\ldots\cdot V_{-L}$$ можно выразить по формуле (5.1)$$\left(V_L\cdot\ldots\cdot V_{-L}\right)_{xy}= \sum_{x_{L-1},\dots, x_{-L+1}}^{} (U_L)_{xx_{L-1}}\cdot\ldots\cdot (U_{-L})_{x_{-L+1}y}.$$ По определению, $$C_a(u_{-L},\dots,u_{L})$$ равно 1, если и только если$$u_{-L}=u_{L}=(x,0^{N-n}),\quad \prod_{j=-L+1}^{L}(V_{j})_{u_{j}u_{j-1}} =a.$$ Легко видеть, что $$C_a\in\P$$: нужно представлять матричные элементы как степени $$i$$ и суммировать показатели степеней по модулю 4.

Если $$F(x)=0$$, то $$p(x)\le 1/3$$ ; если $$F(x)=1$$, то $$p(x)\ge 2/3$$. Итак, $$F(x)=1$$ тогда и только тогда, когда$$p(x)=2^{-h}(\#_1(x)-\#_{-1}(x))>\frac{1}{2}.$$ Это эквивалентно условию$$\#_{-1}(x)+2^{h-1}<\#_{1}(x).$$

Записанное неравенство почти соответствует определению класса $$\PPP$$: остается лишь проверить, что левая часть представима в виде $$f(x)=|\{y:R(x,y)=1\}|$$, $$R(\cdot,\cdot)\in\P$$ (для правой части это уже доказано). Функции $$f$$ такого вида образуют так называемый класс $$\#\P$$. Покажем, что этот класс замкнут относительно сложения. Пусть $$g(x)\double=|\{y:Q(x,y)=1\}|$$, $$Q(\cdot,\cdot)\in\P$$, тогда$$\begin{align*} f(x)+g(x)= |\{y:T(x,zy)=1\}|,\\ \mbox{где } T(x,0y)=R(x,y),\T(x,1y)=Q(x,y). \end{align*}$$ Доказательство закончено.

$$\PPP \subseteq \PSPACE$$. Это очевидно. Заведем два счетчика: один для $$R_0$$, другой — для $$R_1$$. Перебираем все возможные значения $$y$$ и увеличиваем значения счетчиков для $$R_k$$, если $$R_k(x,y)=1$$. Потом сравниваем значения счетчиков.

8.4 Пункт а) следует из пункта б). Для б) приведем схему, которая дает приближенное решение. Прежде всего, запишем рекуррентную формулу$$\rlap{\displaystyle \ket{\psi_n(q)}=\cos\vartheta\ket0\otimes\ket{\psi_{n-1}(q')}+ \sin\vartheta\ket1\otimes\ket{\psi_{n-1}(q'')},$$ где$$q'=2^{n-1}, q''=q-2^{n-1}, \vartheta=\arccos\sqrt{q'/q}, \text{если } q>2^{n-1}; \notag\\[-3pt] q'=q, q''=1, \vartheta=0, \text{если } q\leq2^{n-1}. \notag$$

Организуем рекурсивное вычисление, используя формулу $$(*)$$.

Оператор $$R(\vartheta)$$ реализуется приближенно. Пусть $$\vartheta/\pi=\sum_{k=1}^{l} a_k 2^{-k}$$. Тогда $$R(\vartheta)\approx R(\pi/2^{l})^{a_{l}} \cdot\ldots\cdot R(\pi/2)^{a_{1}}$$ с точностью $$O(2^{-l})$$. Итак, приближенно оператор $$R(\vartheta)$$ представляется произведением операторов $$\Lambda(R(\pi/2^{k}))$$, где $$k$$ -й разряд числа $$\vartheta/\pi$$ управляет применением оператора $$R(\pi/2^{k})$$.

Общая точность такой схемы равна $$\delta=O(n2^{-l})$$ ; размер, выраженный через длину входа и точность, — $$\poly(n+\log(1/\delta))$$.

Пункт в). Приведем реализацию преобразования Фурье, найденную Копперсмитом и, независимо, Дойчем, в изложении П. Шора [39].

Занумеруем q-биты в убывающем порядке от $$n-1$$ до $$0$$. Обозначим$$H_j=H[j],\qquad S_{j,l}=\Lambda^2\bigl(e^{i\pi/2^{l-j}}\bigr)[j,l]\quad (j<l).$$ Тогда оператор$$\begin{multiline*} V_k= H_0S_{0,1}S_{0,2}\cdot\ldots\cdot S_{0,n-2}S_{0,n-1} H_1S_{1,2}\cdot\ldots\cdot S_{1,n-1}\cdot\ldots\\ \ldots\cdot H_{n-3}S_{n-3,n-2}S_{n-3,n-1}H_{n-2}S_{n-2,n-1}H_{n-1} \end{multiline*}$$ дает почти то, что нужно: $$U_k=RV_k$$, где $$R$$ — (классический) оператор, переписывающий двоичное слово в обратном порядке. Размер такой схемы $$O(n^2)$$.

Легко видеть, что модули матричных элементов $$V_k$$ определяются количеством операторов $$H_j$$, так что они равны $$1/\sqrt{k}$$, как и требуется. Осталось проверить фазовые множители. Пусть$$\left(V_k\right)_{(x_{n-1}\dots x_0, y_{n-1}\dots y_0)}= \frac{1}{\sqrt{k}} \exp(i\cdot 2\pi\phi(x_{n-1},\dots, x_0, y_{n-1},\dots, y_0)).$$ Заметим, что каждый матричный элемент $$V_k$$ есть произведение матричных элементов сомножителей. Применение $$H_j$$ меняет фазу на $$\pi$$ тогда и только тогда, когда $$x_j=y_j=1$$ ; применение $$S_{j,l}$$ добавляет к фазе $$\pi/2^{l-j}$$ только в том случае, когда $$x_j=y_l=1$$. Изменение фазы на $$2\pi$$ ни на что не влияет, поэтому вычислим $$\phi$$ по модулю 1.$$\begin{align*} \phi(x_{n-1},\dots,x_0, y_{n-1},\dots,y_0) =\mkern-2mu\sum_{j=0}^{n-1}\frac{x_j y_j}{2}+\mkern-7mu \sum_{0\leq j<l<n}^{}\frac{x_j y_l}{2^{l-j+1}}=\\[-3pt] =\mkern-7mu \sum_{0\leq j\leq l<n}^{}\frac{x_j y_l}{2^{l-j+1}}=\mkern-7mu \sum_{0\leq j+m<n}^{}\frac{x_j y_{n-1-m}}{2^{n-j-m}}=\\ \intertext{(здесь равенство по модулю 1)} =\sum_{j,m=0}^{n-1} \frac{x_j y_{n-1-m}}{2^{n-j-m}} =2^{-n}\sum_{j=0}^{n-1}2^jx_j \sum_{m=0}^{n-1}2^my_{n-1-m}. \end{align*}$$ После того, как мы перепишем слово $$y$$ в обратном порядке, последнее выражение превращается в $$xy/2^n$$.

Из раздела 9

9.1. Пусть $$\rho=\sum_{k}^{}p_k\ket{\xi_k}\bra{\xi_k}$$. Проверим условия 1)—3) для $$\rho$$.

Условие 1): очевидно.

Условие 2): $$\langle\eta|\,\rho\,|\eta\rangle =\sum_{k}^{}p_k\langle \eta|\xi_k\rangle \langle \xi_k|\eta\rangle =\sum_{k}^{}p_k\left|\langle \eta|\xi_k\rangle \right|^2\geq0$$.

Условие 3): $$\Tr\rho=\sum_{k}p_k\langle\xi_k|\xi_k\rangle=\sum_{k}p_k=1$$.

И наоборот, если $$\rho$$ удовлетворяет 1)—3), то $$\rho=\sum_{k}^{}\lambda_k\ket{\xi_k}\bra{\xi_k}$$, где $$\lambda_k$$ — собственные числа, а $$\{\ket{\xi_k}\}$$ — ортонормированный базис из собственных векторов.

9.2 Вектору $$\ket\psi\in\calN\otimes\calF$$ можно естественным образом сопоставить оператор $$\Psi\colon\calF^*\to\calN$$. Пусть $$p_j$$ — ненулевые собственные числа оператора$$\rho=\Psi\Psi^\dagger=\Tr_\calF(\ket\psi\bra\psi)\in\LL(\calN)$$ (каждое собственное число учитывается столько раз, какова его кратность). Поскольку $$\rho$$ является матрицей плотности, $$0<p_j\le 1$$. Положим $$\lambda_j=\sqrt{p_j}$$, а в качестве множества $$\{\ket{\xi_j}\}$$ возьмем любую ортонормированную систему собственных векторов, соответствующих собственным числам $$p_j$$.

Оператор $$\Psi$$ можно представить в виде$$\Psi=\sum_{j}\lambda_j\ket{\xi_j}\bra{\nu_j},$$ где $$\ket{\nu_j}=\lambda_j^{-1}\Psi^\dagger\ket{\xi_j}\in\calF^*$$. Соответственно, $$\bra{\nu_j}\in\calF^{**}=\calF$$. Переобозначив $$\bra{\nu_j}$$ через $$\ket{\eta_j}$$, получаем искомое разложение Шмидта.

9.3 Условие $$\Tr_{\calF}(\ket{\psi_1}\bra{\psi_1})= \Tr_{\calF}(\ket{\psi_2}\bra{\psi_2})$$, как следует из решения предыдущей задачи, позволяет выбрать разложения Шмидта для $$\ket{\psi_1}$$ и $$\ket{\psi_2}$$ с одинаковыми $$\lambda_j$$ и $$\ket{\xi_j}$$. Запишем эти разложения$$\ket{\psi_k}=\sum_{j}^{}\lambda_j\ket{\xi_j} \otimes\ket{\eta_j^{(k)}},\qquad k=1,\,2.$$ Поскольку $$\{\ket{\eta_j^{(k)}}\}$$ — ортонормированные семейства, существует унитарный оператор $$U$$, такой что $$U\ket{\eta_{j}^{(1)}}=\ket{\eta_j^{(2)}}$$ для всех $$j$$. Тогда$$(I_\calN\otimes U)\ket{\psi_1}= \sum_{j}^{}\lambda_j \ket{\xi_j}\otimes U\ket{\eta_j^{(1)}}= \sum_{j}^{}\lambda_j \ket{\xi_j}\otimes \ket{\eta_j^{(2)}}= \ket{\psi_2}.$$

Из раздела 10

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

Лемма. Физически реализуемые преобразования матриц плотности имеют вид$$\rho\mapsto\sum_{m=1}^{s} A^{\ms}_m\rho{}A^\dagger_m, \qquad \sum_{m}^{} A^\dagger_m A^{\ms}_m= I,$$ который будем называть разложением в операторную сумму. А всякое разложение в операторную сумму можно представить в виде $$\rho\mapsto$$ $$\mapsto\Tr_\calF(V\rho{}V^\dagger)$$, где $$V$$ — изометрическое вложение.

Доказательство. План доказательства следующий:

10.2 Пусть $$\rho\in\LL(\calN\otimes\calF)$$, $$U\ket{j}=\ket{\xi_j}$$, $$Y\ket{k}=\ket{\eta_k}$$. Тогда$$\begin{align*} \Tr_\calF\left((U\otimes Y)\rho(U\otimes Y)^\dagger\right)=\\ =\Tr_\calF\Big((U\otimes Y) \sum_{j,k,j',k'}^{}\rho_{jkj'k'}\ket{j,k}\bra{j',k'}\, (U\otimes Y)^\dagger \Big)=\\ = \Tr_\calF\Big( \sum_{j,k,j',k'}^{}\rho_{jkj'k'}\ket{\xi_j}\bra{\xi_{j'}} \otimes \ket{\eta_k}\bra{\eta_{k'}} \Big)=\sum_{jj'k}^{}\rho_{jkj'k}\ket{\xi_j}\bra{\xi_{j'}}=\\ =\;U(\Tr_\calF\rho)U^\dagger. \end{align*}$$

10.3 Пусть $$\sum_{m}^{}\ds A^{\ms}_m\rho{}A_m^\dagger$$ — разложение в операторную сумму преобразования $$T$$ (см. задачу 10.1). Тогда$$T_{(j'j)(k'k)}= \langle j'|\, T\big(\ket{j}\bra{k}\big)\,|\, k'\rangle = \sum_{m}^{} \bra{j'}A^{\ms}_m\ket{j}\cdot\bra{k}A_m^\dagger\ket{k'}.$$ Такое представление позволяет легко проверить сформулированные в условии задачи свойства а)—в).

Свойство а):$$\sum_{k'}^{}T_{(k'j)(k'k)}= \sum_{k'm}^{}\bra{k'}A^{\ms}_m\ket{j}\cdot\bra{k}A_m^\dagger\ket{k'}=\\ =\sum_{k'm}^{}\bra{k}A_m^\dagger\ket{k'}\bra{k'}A^{\ms}_m\ket{j}= \sum_{m}^{}\bra{k}A_m^\dagger{}A^{\ms}_m\ket{j}=\langle k|j\rangle .$$

Свойство б):$$T^*_{(j'j)(k'k)}=\sum_{m}^{} \big(\bra{j'}A^{\ms}_m\ket{j}\bra{k}A_m^\dagger\ket{k'}\big)^*= \\ =\sum_{m}^{}\bra{j}A_m^\dagger\ket{j'}\bra{k'}A^{\ms}_m\ket{k} =T^{\ms}_{(k'k)(j'j)}.$$

Свойство в):$$\sum_{j',j,k',k}^{}T_{(j'j)(k'k)}\ket{j',j}\bra{k',k}= \sum_{m}^{}\ket{\psi_m}\bra{\psi_m},$$

где$$\ket{\psi_m}=\sum_{j',j}\bra{j'}A_m\ket{j}\,\ket{j',j}.$$

И наоборот, всякий неотрицательный оператор можно представить в виде $$T =\sum_{m}^{}\ket{\psi_m}\bra{\psi_m}$$, где $$\ket{\psi_m}$$ — подходящим образом нормированные собственные векторы $$T$$, отвечающие положительным собственным числам. Обозначим$$\begin{align*} \ket{\psi_m}=\sum_{m,j',j}^{}a_{mj'j}\ket{j',j}, A_m\colon\ket{j}\mapsto\sum_{j'}^{}a_{mj'j}\ket{j'}, \end{align*}$$ тогда $$T_{(j'j)(k'k)}=\sum\limits_{m}^{}a^{\ms}_{mj'j}a^*_{mk'k}$$. Из условия $$\sum\limits_{k'}^{}T_{(k'j)(k'k)}=\delta_{jk}$$ следует

$$\begin{multiple} \hbox to\textwidth{\displaystyle\langle k|\, \Big( \sum_{m}^{}A_m^\dagger{}A^{\ms}_m\Big)\,|j\rangle = \langle k|\, \Big(\sum_{m,k'}a^*_{mk'k}a^{\ms}_{mk'j} \Big)\,|j\rangle= \sum_{k'}T_{(k'j)(k'k)}=\delta_{jk}.} \end{multiple}$$ Осталось проверить, что $$T\big(\ket{j}\bra{k}\big)=\sum_{m}^{}A^{\ms}_m\ket{j}\bra{k}A_m^\dagger$$:$$\begin{align*} \sum_{m}^{}A^{\ms}_m\ket{j}\bra{k}A_m^\dagger =\sum_{j',k'}^{}\sum_{m}^{}a^{\ms}_{mj'j}a^*_{mk'k} \ket{j'}\bra{k'} = \sum_{j'k'}^{}T_{(j'j)(k'k)}\ket{j'}\bra{k'}=\\ =\; T\big(\ket{j}\bra{k}\big). \end{align*}$$

10.4 Свойства а) и б) эквивалентны свойствам а) и б) из предыдущей задачи.

Пусть есть физически реализуемое преобразование матриц плотности $$T\colon\rho\mapsto\Tr_\calF(V\rho V^\dagger)$$. Тогда $$T\otimes I_{\LL(\calG)}\colon \rho\mapsto\Tr_\calF\bigl((V\otimes I_{\calG})\rho (V\otimes I_{\calG})^\dagger\bigr)$$ также является физически реализуемым преобразованием и поэтому обладает разложением в операторную сумму. Следовательно, $$T\otimes I_{\LL(\calG)}$$ переводит неотрицательные операторы в неотрицательные.

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

Чтобы доказать неотрицательность матрицы $$T_{(j'j)(k'k)}$$ по парам индексов, взятых в скобки, покажем, что она является матрицей оператора вида $$(I\otimes T)\ket\psi\bra\psi$$, где $$\ket\psi\in \calN\otimes\calN$$ имеет вид $$\ket\psi=\sum_{j}^{}\ket{j}\otimes\ket{j}$$. Действительно,$$(I\otimes T)\ket\psi\bra\psi = \sum_{j',j,k',k}^{}T_{(j'j)(k'k)}\ket{j}\bra{k}\otimes\ket{j'}\bra{k'}= \sum_{j',j,k',k}^{}T_{(j'j)(k'k)}\ket{j'j}\bra{k'k}.$$

10.5 Воспользуемся результатом задачи 10.1. Представим $$T\rho$$ в виде $$\Tr_{\calF'}(V\rho{}V^\dagger)$$. Возьмем $$\ket\psi\in\calN$$. Поскольку состояние$$\begin{align*} \Tr_{\calF\otimes\calF'}\bigl(\ket{V\psi}\bra{V\psi}\bigr) = \Tr_\calF\bigl(\Tr_{\calF'}\bigl(V\ket{\psi}\bra{\psi}V^\dagger\bigr)\bigr)= \Tr_\calF\bigl(T\ket\psi\bra\psi\bigr)= \ket\psi\bra\psi \end{align*}$$ чистое, $$\ket{V\psi}=\ket{\psi,\xi(\psi)}$$ (это следует из замечания, сделанного после формулировки задачи 9.2). Из линейности $$V$$ следует, что $$\ket{\xi(\psi)}=\ket\xi$$ не зависит от $$\ket\psi$$. Поэтому $$TX=X\otimes\gamma$$, где $$\gamma=\Tr_{\calF'}(\ket\xi\bra\xi)$$.

10.6 Будем считать, что сразу же после измерения измеряемые q-биты выбрасываются в "мусорную корзину". Это соответствует преобразованию двух квантовых битов в классические:$$T\colon\rho\mapsto\sum_{a,b}\langle\xi_{ab}|\rho|\xi_{ab}\rangle(a,b).$$ Чтобы реализовать преобразование $$T$$, нужно сначала подействовать унитарным оператором$$H[1]\Lambda(\sx)[1,2]\colon\, \ket{\xi_{ab}}\mapsto\ket{b,a},$$ а затем произвести измерение в базисе $$\{\ket{0},\ket{1}\}$$ ; после этого q-биты выбрасываются.

Без ограничения общности, первый q-бит находится в чистом состоянии $$\ket\psi=z_0\ket0+z_1\ket1$$. (Если мы построим восстанавливающую процедуру для чистых состояний, то она по линейности будет продолжаться на смешанные). На третий q-бит измерение не действует, поэтому можно записать$$\bigl(T\otimes I_{\LL(\BB)}\bigr) \Bigl(\ket\psi\bra\psi\otimes \ket{\xi_{00}}\bra{\xi_{00}}\Bigr) = \sum_{a,b}^{}\bigl(a,b, \ket{\psi_{ab}}\bra{\psi_{ab}}\bigr),$$ где $$\ket{\psi_{ab}}=\bigl(\bra{\xi_{ab}}\otimes I_\BB\bigr) \bigl(\ket\psi\otimes\ket{\xi_{00}}\bigr)$$. Здесь $$\bra{\xi_{ab}}$$ рассматривается как оператор $$\BB^{\otimes2}\to\CC$$, поэтому $$\bra{\xi_{ab}}\otimes I_\BB\colon\BB^{\otimes3}\to\BB$$. Заметим, что квадрат нормы вектора $$\ket{\psi_{ab}}$$ равен вероятности получения пары $$(a,b)$$.

Теперь запишем явное выражение для $$\ket{\psi_{ab}}$$:$$\begin{align*} \ket{\psi_{ab}} = \frac{1}{\sqrt2}\sum_{d}^{} \bigl(\bra{\xi_{ab}}\otimes I_\BB\bigr) \bigl(\ket\psi\otimes\ket{d,d}\bigr) =\frac{1}{\sqrt2}\sum_{d} \bra{\xi_{ab}}\psi,d\rangle\,\ket{d}=\\ =\frac{1}{\sqrt2}\sum_{c,d} z_c \bra{\xi_{ab}}c,d\rangle\,\ket{d} =\frac{1}{2}\sum_{c,d}^{}(-1)^{bc} \delta_{c\oplus a,d} z_c\ket{d}= \frac{1}{2}\sum_{c}^{}(-1)^{bc} z_c\ket{a\oplus c}. \end{align*}$$ Из этого выражения сразу следует, что$$\left(\sz\right)^b\left(\sx\right)^a\ket{\psi_{ab}}=\frac{1}{2}\ket\psi.$$ Так что состояние $$\ket\psi$$ в третьем q-бите получится применением операторов $$\sigma^x$$ и $$\sigma^z$$ с классическим управлением: управляющими параметрами являются измеренные значения $$a$$ и $$b$$.

Схема квантовой телепортации изображена на рис 15.9— второй (q-бит Алисы),— третий (q-бит Боба). Когда Алиса хочет передать q-бит $$\heartsuit$$ Бобу, она совершает измерения над ним и своим q-битом (дальше эти q-биты не используются, и она выбрасывает их в мусорную корзину). Результаты измерений она сообщает Бобу по классическому каналу связи (телефону). Боб, используя сообщение Алисы, превращает свой q-бит в q-бит $$\heartsuit$$.

Из раздела 11

11.1 По определению квантовой вероятности имеем$$\begin{align*} \PP\Bigl(W\bigl(\ket0\bra0\otimes\rho\bigr)W^\dagger,\, \CC(\ket{k})\otimes\calN\Bigr) =\\ = \Tr\Bigl(\Pi_{\CC(\ket{k})\otimes\calN}W\bigl(\ket0\bra0\otimes\rho\bigr) W^\dagger\Bigr)=\\ = \sum_{j} \Tr\Bigl( \bigl(\ket{k}\bra{k}\bigr)R_j\bigl(\ket{0}\bra{0}\bigr)R_j^\dagger \otimes \Pi_{\calL_j}\rho\Pi_{\calL_j} \Bigr) =\\ = \sum_{j} \Tr\Bigl(\bigl(\ket{k}\bra{k}\bigr) R_j\bigl(\ket0\bra0\bigr)R_j^\dagger\Bigr) \Tr\bigl(\Pi_{\calL_j}\rho\Pi_{\calL_j}\bigr)=\\ = \sum_{j}|\bra{k}R_j\ket0|^2 \PP(\rho,\calL_j) \,=\, \sum_{j}\PP(k|j)\PP(\rho,\calL_j). \end{align*}$$

11.2 Если $$W=\sum_{k=1}^{t}\Pi_{\calL_k}\otimes V_k$$, то $$W^{-1}=\sum_{k=1}^{t}\Pi^{\ms}_{\calL_k}\otimes V_k^{-1}$$. Поэтому искомая квантовая схема имеет вид $$W^{-1}YW$$, где оператор $$Y$$ копирует в дополнительный регистр "полезный результат":$$Y\colon\ket{y,z,v}\mapsto\ket{y,z,v\oplus y}.$$ Оценка точности делается так же, как в задаче 7.11.

Из раздела 12

12.1 Интересующую нас вероятность обозначим через $$p(X,l)$$. Если $$h_1,\dots,h_l$$ не порождают всю группу $$X$$, то они содержатся в некоторой максимальной собственной подгруппе $$Y\subset X$$. Для каждого $$Y$$ вероятность такого события не превосходит $$2^{-l}$$, поскольку $$|Y|\le|X|/2$$. Таким образом, мы имеем оценку$$p(X,l)\ge 1-K(X)\cdot 2^{-l},$$ где $$K(X)$$ — число максимальных собственных подгрупп в группе $$X$$.

Подгруппы абелевой группы $$X$$ находятся во взаимнооднозначном соответствии с подгруппами группы характеров $$X^*$$, при этом максимальным собственным подгруппам отвечают минимальные ненулевые подгруппы. Каждая такая подгруппа порождается одним элементом, поэтому $$K(X)\le|X^*|=|X|$$.

12.2 Построим классический оператор $$V_b\in\LL(\BB\otimes\BB^{\otimes n})$$ (базисные векторы в $$\BB^{\otimes n}$$ занумерованы от $$0$$ до $$2^n-1$$ ), такой что$$V_b\ket{0,0}=\ket{0,1},\qquad V_b\ket{1,0}=\ket{1,b}.$$ Тогда схема $$V^{-1}[0,B]\,U[B,A]\,V[0,B]$$ реализует оператор $$\Lambda(U_b)[0,A]$$ в расширенном смысле.

12.3 Обозначим образ вектора $$\ket{x}$$ при преобразовании Фурье через $$\ket{\psi_n(k,x)}$$. В задаче 8.4 мы научились строить вектор $$\ket{\psi_n(k,0)}$$. Как уже отмечалось в решении задачи 7.11, $$\ket{\psi_n(k,x)}$$ — собственный вектор классического оператора $$V\colon\ket{j}\mapsto\ket{(j-1)\bmod k}$$, собственное число которого равно $$\exp(2\pi i x/k)$$.

Используя эти соображения и результат задачи 11.2, построим следующую схему для квантового преобразования Фурье.

Из раздела 14

14.1 Оператор $$A$$ можно представить в виде$$A = \sum_{j} \lambda_j\ket{\xi_j}\bra{\eta_j},\quad\ \lambda_j>0,\quad \langle\xi_j|\xi_k\rangle=\langle\eta_j|\eta_k\rangle= \delta_{jk}.$$ Здесь $$\lambda_j^2$$ — ненулевые собственные числа оператора $$AA^\dagger$$, $$\ket{\xi_j}$$ — его собственные векторы, а $$\ket{\eta_j}=\lambda_j^{-1}A^\dagger\ket{\xi_j}$$. Тогда $$\|A\|_\trr=\sum_j\lambda_j$$.

Для любого оператора $$X$$$$|\Tr AX| \le \sum_{j}\lambda_j\bigl|\Tr\ket{\xi_j}\bra{\eta_j}X\bigr| \le \sum_j \lambda_j\|X\| = \|A\|_\trr\|X\|.$$ С другой стороны, если взять $$X=\sum_j\ket{\eta_j}\bra{\xi_j}$$, то $$\|X\|\le 1$$, а $$\Tr AX\double=\|A\|_\trr$$.

Из доказанного представления для $$\|\cdot\|_\trr$$ легко следует неравенство треугольника, а положительность и однородность $$\|\cdot\|_\trr$$ очевидны.

14.2 Свойство а):$$\|AB\|_\trr= \sup\limits_{X\ne0}\frac{|\Tr ABX|}{\|X\|}\leq \sup\limits_{X\ne0}\frac{\|A\|_\trr\|BX\|}{\|X\|}\leq \|A\|_\trr\|B\|.$$ Аналогично доказывается и свойство б) (воспользуйтесь равенством $$\Tr ABC=\Tr CAB$$ ).

Свойство в):$$|\Tr(A)|=\frac{|\Tr(AI)|}{\|I\|}\leq\|A\|_\trr.$$

Свойство г): для любого $$А\in\LL(\calN\otimes\calM)$$$$\|\Tr_{\calM}A\|_\trr= \sup\limits_{X\ne0}\frac{\left|\Tr\bigl((\Tr_{\calM}A)X\bigr)\right|}{\|X\|}= \sup\limits_{X\ne0} \frac{\left|\Tr\bigl(A(X\otimes I_{\calM})\bigr)\right|} {\|X\otimes I_\calM\|}\le \|A\|_\trr.$$

Свойство д):$$\|A\otimes B\|_\trr= \Tr\sqrt{(A\otimes B)^\dagger(A\otimes B)}= \Tr\left(\sqrt{A^\dagger A}\otimes\sqrt{B^\dagger B}\right)= \|A\|_\trr\|B\|_\trr.$$

14.3 Пусть $$\calF$$ — пространство состояний q-битов из $$A$$, а $$\calN$$ — пространство состояний остальных q-битов. Обозначим$$\calD = I_{\calN}\otimes\calF^*\colon\ \calN\otimes\calF\to\calN.$$ Если $$X,Y\in\calD$$, то $$Y^\dagger X\in I_{\calN}\otimes\LL(\calF)=\calE(A)$$. Следовательно, код $$\calM$$ исправляет ошибки из $$\calD$$.

Преобразование $$T\colon\rho\mapsto\Tr_\calF\rho$$ может быть разложено в операторную сумму ( $$**$$ ), см. решение задачи 10.1. Операторы $$W_m$$ из этого разложения принадлежат пространству $$\calD$$, поэтому $$T\in\calD\cdot\calD^\dagger$$. Осталось воспользоваться теоремой 14.2.

14.4 Пространство $$F$$, соответствующее искомому коду, порождается строками таблицы$$\begin{array}{cc@{\qquad}cc@{\qquad} cc@{\qquad} cc@{\qquad} cc} 10 10 01 01 00 \\ 10 01 10 00 01 \\ 01 00 01 10 01 \\ 01 01 00 01 10 \end{array}$$ Можно проверить, что $$\omega(f_j,f_k)=0$$ для любых двух строк $$f_j,f_k$$. Заметим, что столбцы в таблице разбиты на пары. Если взять любые две пары, то соответствующие 4 столбца линейно независимы. Следовательно, из строк всегда можно составить линейную комбинацию, которая в двух заданных парах позиций содержит заданные числа. Поэтому условия $$\omega(f_j,g)=0$$ ( $$j=1,2,3,4$$ ) при $$|g|\leq2$$ могут выполняться только для $$g=0$$.

14.5 (См. [22, 23].) Допустим, что $$\calM$$ — код типа $$(4,1)$$, исправляющий одну ошибку. Тогда он должен обнаруживать по крайней мере две ошибки, в частности, ошибки в q-битах $$[1,2]$$, а также в q- битах $$[3,4]$$. Это означает, что произвольное состояние $$\rho\in\LL(\calM)$$ можно восстановить как по первым, так и по последним двум $$q$$ -битам (см. задачу 14.3). Покажем, что это невозможно.

Пусть $$\calN_1$$ — пространство состояний q-битов $$[1,2]$$, а $$\calN_2$$ — пространство состояний q-битов $$[3,4]$$, тогда $$\calM$$ — это подпространство в $$\calN_1\otimes\calN_2$$. Вложение $$\calM\to\calN_1\otimes\calN_2$$ обозначим через $$V$$ (это изометрический оператор). Пусть также $$T_1\colon\rho\mapsto\Tr_{\calN_2}\rho$$ и $$T_2\colon\rho\mapsto\Tr_{\calN_1}\rho$$ — преобразования ошибок, а $$P_1\colon\calN_1\to\calM$$ и $$P_2\colon\calN_2\to\calM$$ — соответствующие исправляющие преобразования. Тогда преобразование $$P=(P_1\otimes P_2)(V\cdot V^\dagger)\colon\calM\to\calM\otimes\calM$$ обладает следующим свойством: для любого $$\rho\in\calM$$$$\begin{align*} \Tr_{\calN_2} P\rho =\, \Tr_{\calN_2} \bigl((P_1\otimes P_2)(V\rho V^\dagger)\bigr) = P_1 T_1(V\rho V^\dagger) =\,\rho,\\ \Tr_{\calN_1} P\rho =\, \Tr_{\calN_1} \bigl((P_1\otimes P_2)(V\rho V^\dagger)\bigr) = P_2 T_2(V\rho V^\dagger) =\,\rho .\end{align*}$$ Согласно задаче 10.5 первое тождество означает, что $$P\rho=\rho\otimes\gamma_2$$, где $$\gamma_2$$ не зависит от $$\rho$$. Из второго тождества следует, что $$P\rho=\gamma_1\otimes\rho$$. Получили противоречие: $$\gamma_1\otimes\rho=\rho\otimes\gamma_2$$, где $$\rho$$ —любое.

14.6 Опишем кратко идею решения этой задачи.

Достаточно рассмотреть одно из двух прямых слагаемых торического кода. Компонента синдрома равна 1 для такого узла решетки, в звезду которого входит нечетное число ребер с ненулевыми весами в 1-цепи, соответствующей вектору ошибки $$g^{(z)}$$.

Поэтому получаем такую задачу. Задано некоторое множество $$D$$ узлов решетки. Из всех 1-цепей $$C$$, граница которых совпадает с $$D$$, нужно выбрать ту, в которой наименьшее число ребер ненулевого веса. Нетрудно сообразить, что такая 1-цепь распадается в объединение путей, соединяющих узлы из множества $$D$$ (любые два различных пути не имеют общих ребер), причем эти пути можно считать кратчайшими. Так что задача определения ошибки по синдрому сводится к задаче о взвешенном паросочетании: дан граф $$G$$ (в нашем случае полный), каждому его ребру приписан вес (в нашем случае — расстояние между узлами по решетке), нужно найти паросочетание, на котором достигается минимум суммы весов по ребрам, входящим в паросочетание.

Для задачи о взвешенном паросочетании известны полиномиальные алгоритмы (см., например, [11, гл.11], где описан алгоритм, основанный на идеях линейного программирования).