Квантовый аналог NP: класс BQNP

Лемма 13.1 (усиление вероятностей). Если $$F\in\BQNP$$, то она удовлетворяет также и такому варианту определения 13.2, где условие $$p_1-p_0=\Omega(n^{-\alpha})$$ заменено на $$p_1=1-\eps$$, $$p_0=\eps$$, $$\eps=\exp(-O(n^\beta))$$, $$\beta>0$$.

Доказательство. Общая идея усиления вероятностей остается прежней: рассмотрим большое, но ограниченное полиномом, количество копий схемы, реализующей оператор $$U=U_n$$ (индекс $$n$$ мы будем опускать). К результатам их работы применим функцию голосования с пороговым значением, разделяющим вероятности $$p_0$$ и $$p_1$$:$$\begin{equation}\label{пороговая-функция} G(z_1,\dots,z_k) = \left\{\begin{array}{ll} 1, \text{если}\ \sum\limits_{j=1}^{k} z_j \ge l \\[3pt] 0, \text{если}\ \sum\limits_{j=1}^{k} z_j < l, \end{array}\right. \end{equation}$$ где $$l=pk$$, $$p=(p_0+p_1)/2$$. Но теперь появляется дополнительная трудность — Мерлин может пытаться обмануть Артура, сообщая ему неразложимую в тензорное произведение подсказку.

Пусть мы используем $$k$$ копий схемы $$U$$. Предоставим Мерлину большую свободу, разрешив в качестве подсказки любую матрицу плотности $$\rho\in\LL(\BB^{\otimes km})$$. Вероятность получения ответов $$z_1,\dots,z_k$$ при подсказке $$\rho$$ равна$$\begin{equation}\label{вер-послед} \PP(z_1,\dots,z_k|\,\rho)= \Tr(X^{(z_1)}\otimes\ldots\otimes X^{(z_k)}\rho), \end{equation}$$ где$$\begin{equation}\label{принимающий-оператор} X^{(a)}=\Tr_{[m+1,\dots,N]}\Bigl(U^\dagger\Pi^{(a)}_1 U \bigl(I_{\BB^{\otimes m}}\otimes\ket{x,0^{N-n-m}}\bra{x,0^{N-n-m}}\bigr)\Bigr). \end{equation}$$

Здесь $$\Pi^{(a)}_1$$ — проектор на подпространство состояний, имеющих $$a$$ в первом q-бите (т.е. $$\CC(\ket{a})\otimes\BB^{\otimes (N-1)}$$ ).

Чтобы убедить Артура в правильности $$F(x)=1$$, Мерлин может дать подсказку $$\rho=\rho_x^{\otimes k}$$, где $$\rho_x=\ket{\xi_x}\bra{\xi_x}$$ — сообщение, которое убеждает Артура, действующего по схеме $$U$$, с вероятностью $$p_1$$. По общим свойствам квантовой вероятности, формула (13.2) преобразуется в$$\PP(z_1,\dots,z_k|\,\rho)=\prod_{j=1}^{k} \Tr(X^{(z_j)}\rho_x) =\prod_{j=1}^{k} \PP(z_j|\rho_x).$$

Рассмотрим теперь случай, когда $$F(x)=0$$. Нам нужно оценить вероятность $$\PP(z_1,\dots, z_k)$$ для произвольного сообщения Мерлина $$\rho$$. Выберем в пространстве $$\BB^{\otimes m}$$ ортонормированный базис, в котором диагонализуется оператор $$X^{(1)}$$ (этот оператор, очевидно, эрмитов). Оператор $$X^{(0)}=I-X^{(1)}$$ диагонален в том же базисе. Определим набор "условных вероятностей" $$p(z|d)=\bra{d}X^{(z)}\ket{d}$$, где $$\ket{d}$$ — один из базисных векторов. (Очевидно, что $$p(z|d)\ge 0$$ и $$p(0|d)+p(1|d)=1$$.) Тогда величина $$\PP(z_1,\dots,z_k|\,\rho)$$ приобретает вид$$\begin{equation}\label{разл-вер-на подсказке} \PP(z_1,\dots,z_k|\,\rho)= \sum_{d_1,\dots,d_k}p_{d_1\dots d_k}\,p(z_1|d_1)\dots p(z_k|d_k), \quad \sum_{d_1,\dots,d_k}p_{d_1\dots d_k}=1. \end{equation}$$ Здесь $$p_{d_1\dots d_k}=\bra{d_1\dots d_k}\rho\ket{d_1\dots d_k}$$.

Формула (13.4) имеет следующую интерпретацию. Рассмотрим набор вероятностей $$\PP(z_1,\dots,z_k|\,\rho)$$ для всех последовательностей $$(z_1,\double\dots,z_k)$$ как вектор в $$k$$ -мерном вещественном пространстве. Мы показали, что этот вектор на произвольной подсказке $$\rho$$ принадлежит выпуклой оболочке таких же векторов на разложимых подсказках $$\ket{d_1,\dots,d_n}$$. Поэтому наибольшая вероятность события $$G(z_1,\dots,z_k)=1$$ (для любой функции $$G$$ ) достигается на подсказках такого вида.

В случае, когда $$G$$ — пороговая функция (13.1),$$\begin{equation}\label{наибольшая-вероятность-принятия} p_{\rm max}= \max_{\rho}\Prob\left[G(z_1,\dots,z_k)=1\big|\,\rho\right]= \sum_{j\ge l} \binom{k}{j} p_*^j(1-p_*)^{k-j}, \end{equation}$$ где $$p_*=\max_{\ket{\xi}}\bra{\xi}X^{(1)}\ket{\xi}$$. Согласно условию, $$p_*\ge p_1$$, если $$F(x)=1$$, и $$p_*\le p_0$$, если $$F(x)=0$$. Оценим величину $$p_{\rm max}$$ в этих случаях, соответственно, снизу и сверху.

Будем использовать неравенство Чернова (см. [18]). Пусть$$H(p,q)=-(1-p)\ln\frac{1-q}{1-p}-p\ln\frac{q}{p}.$$ Тогда при $$p_*\ge p_1$$ получаем$$1-p_{\rm max}\le\exp(-H(p,p_1)k),$$ а при $$p_*\le p_0$$ —$$p_{\rm max}\le\exp(-H(p,p_0)k).$$ Из неравенства $$\ln(1+x)\le x$$ следует, что $$H(p,q)\ge 0$$. Используя более точное разложение $$\ln(1+x)\le x-x^2/2+x^3/3$$, можно получить оценку $$H(p,q)=\Omega((p-q)^2)$$. Так что при $$k=n^{2\alpha+\beta}$$ указанные в условии оценки на $$\eps$$ выполнены.

Замечание 13.2. Важным моментом в изложенном доказательстве является тот факт, что $$X^{(0)}$$ и $$X^{(1)}$$ диагонализуются в одном и том же базисе. Вообще, усиление вероятностей для нетривиальных сложностных классов (как квантовых, так и классических) — вещь довольно тонкая.

Полные задачи.

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

Задача 0. Зададим функцию $$F$$ следующим образом. Пусть $$Z$$ — множество троек вида$$(\langle\text{описание квантовой схемы } W\rangle, p_0, p_1),$$ где под описанием схемы понимается ее приближенная реализация в стандартном базисе, а $$p_1-p_0=\Omega(n^{-\alpha})$$ ( $$\alpha>0$$, $$n$$ — размер описания схемы). Тогда для $$z\in Z$$

$$F(z)=1 \Longleftrightarrow$$ если существует вектор $$\ket\xi$$, при действии на который мы получим в первом бите 1 с вероятностью, большей $$p_1$$ ;

$$F(z)=0 \Longleftrightarrow$$ если для всех $$\ket\xi$$ вероятность получить в первом бите 1 меньше $$p_0$$.

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

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

Определение 13.3. Оператор $$H\colon\BB^{\otimes n}\to \BB^{\otimes n}$$ называется k-локальным гамильтонианом, если он выражается в виде$$H=\sum_{j}^{} H_j[S_j],$$ где каждое слагаемое — эрмитов оператор, действующий на множестве q-битов $$S_j$$, $$|S_j|\leq k$$, на остальных q-битах он действует тождественно.

При этом выполнено условие нормировки $$0\leq H_j\leq 1$$ (другими словами, и $$H_j$$, и $$I-H_j$$ — положительно полуопределенные).

Задача 1: локальный гамильтониан. Пусть $$Z$$ — множество троек вида$$(\langle\text{описание k-локального гамильтониана } H\rangle, a, b),$$ где $$k=O(1)$$, $$0\leq a<b$$, $$b-a=\Omega(n^{-\alpha})$$, ( $$\alpha>0$$ ). Тогда для $$z\in Z$$

$$F(z)=1 \Longleftrightarrow$$ если у $$H$$ есть собственное число, не большее $$a$$,

$$F(z)=0 \Longleftrightarrow$$ если все собственные числа $$H$$ больше $$b$$.

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

Доказательство. Опишем вначале основную идею. Мы построим такую схему $$W$$, которая использует подсказку из пространства, в котором действует $$H$$, и выдает ответ "да" (значение 1) на подсказке $$\ket\eta$$ с вероятностью $$p=1-r^{-1}\langle \eta|\,H\,|\eta\rangle$$, где $$r$$ — число слагаемых в гамильтониане $$H$$. Если $$\ket\eta$$ — собственный вектор, соответствующий собственному числу $$a$$, то вероятность ответа "да" будет$$p=1-r^{-1}\langle \eta|\,H\,|\eta\rangle\geq1-r^{-1}a,$$ а если все собственные числа $$H$$ больше $$b$$, то$$p=1-r^{-1}\langle \eta|\,H\,|\eta\rangle\leq1-r^{-1}b.$$

Сперва построим такую схему для одного слагаемого. Пусть это будет $$H_j=\sum_{s}^{}\lambda_s\ket{\psi_s}\bra{\psi_s}$$, действующий на множестве q-битов $$S_j$$. Поскольку размерность пространства, на котором действует $$H_j$$, ограничена константой, мы можем реализовать оператор$$W_j\colon \ket{\psi_s,0}\mapsto \ket{\psi_s}\otimes \left(\sqrt{\lambda_s}\ket0 +\sqrt{1-\lambda_s}\ket1\right),$$ который действует на множестве q-битов $$S_j\cup\{ \langle\text{ответ}\rangle\}$$, где $$\langle\text{ответ}\rangle$$ обозначает q-бит, из которого берется результат работы схемы. На остальных q-битах подсказки $$W_j$$ действует тождественно.

Вычислим вероятность 1 в бите результата после применения $$W_j$$ к состоянию $$\ket{\eta,0}$$ (бит результата установлен в 0 перед началом работы схемы). Пусть $$\ket\eta=\sum_{s}^{}y_s\ket{\psi_s}$$ — разложение $$\ket\eta$$ по ортогональной системе собственных векторов $$H_j$$. Имеем, по определению вероятности,$$\label{localtest} \PP_j(1)=\langle \eta,0|\, W^\dagger_j\bigl(I\otimes\underbrace{\ket1\bra1}_{\scriptstyle \langle\text{ответ}\rangle}\bigr)W_j\,| \eta,0\rangle =\\ =\left(\sum_{s}^{}y^*_s\langle \psi^{\ms}_s,0|\right)\, W^\dagger_j\bigl(I\otimes\underbrace{\ket1\bra1}_{\scriptstyle \langle\text{ответ}\rangle}\bigr)W_j\,\left(\sum_{t}^{} y_t|\psi_t,0\rangle\right) =\\ =\sum_{s,t}^{} \sqrt{1-\lambda_s} y^*_s\sqrt{1-\lambda_t} y_t \langle \psi_s|\psi_t\rangle =\sum_{s}^{}(1-\lambda_s)y^*_sy^{\ms}_s=1-\sum_{s}^{}\lambda_sy^*_sy^{\ms}_s= \\= 1-\langle \eta|\, H\,|\eta\rangle . $$

Общая схема $$W$$ выбирает случайно и равновероятно номер $$j$$, после чего применяет оператор $$W_j$$. Такое действие можно реализовать измеряющим оператором вида $$\sum_{j}^{}\ket{j}\bra{j}\otimes W_j$$, примененным к вектору$$\left(\frac{1}{\sqrt{r}}\sum_{j}^{}\ket{j}\right)\otimes \ket{\eta,0}$$ . (Здесь $$\ket{j}$$ обозначает базисный вектор во вспомогательном $$r$$ -мерном пространстве.) Проводя вычисления аналогично (13.6), получаем$$\begin{equation}\label{globaltest} \PP(1)=\sum_{j}^{}\dfrac{1}{r} \langle j,\eta,0|\, W^\dagger_j\bigl(I\otimes\underbrace{\ket1\bra1}_{\scriptstyle \langle\text{ответ}\rangle}\bigr)W_j\,| j,\eta,0\rangle =\sum_{j}^{}\dfrac{1}{r}\PP_j(1)=\\= 1-r^{-1}\langle \eta|\,H\,|\eta\rangle . \end{equation} \vskip-6pt \end{proof}$$

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

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

Доказательство. Итак, пусть есть схема размера $$L$$: $$U=U_L\cdot\ldots\cdot U_1$$. Будем считать, что $$U$$ действует на пространстве из $$N$$ q-битов, первые $$m$$ из которых — q-биты подсказки, а остальные — вспомогательные (взятые напрокат на время вычислений); считаем также, что схема состоит из операторов, действующих на парах q-битов.

Гамильтониан, сопоставляемый схеме. Он действует на пространстве$$\calL=\BB^{\otimes N}\otimes \CC^{L+1},$$ где первый сомножитель — пространство, на котором действует схема, а второй сомножитель — пространство счетчика шагов (часы). Состоит этот гамильтониан из трех слагаемых$$H=H_{\rm in}+H_{\rm prop}+H_{\rm out}.$$

Слагаемое $$H_{\rm in}$$ отвечает начальному состоянию и равно$$\begin{equation}\label{Hin} H_{\rm in}=\left(\sum_{s=m+1}^{N} \Pi^{(1)}_s\right)\otimes\ket0\bra0, \end{equation}$$ где $$\Pi^{(\alpha)}_s$$ — проектор на подпространство векторов, у которых $$s$$ -й бит равен $$\alpha$$. Второй сомножитель в этой формуле действует в пространстве счетчика.

Слагаемое $$H_{\rm out}$$ отвечает конечному состоянию и равно$$\begin{equation}\label{Hout} H_{\rm out}=\Pi^{(0)}_1\otimes\ket{L}\bra{L}, \end{equation}$$ здесь мы считаем, что бит результата — первый.

И, наконец, слагаемое $$H_{\rm prop}$$ описывает эволюцию системы и состоит, как и следовало ожидать, из $$L$$ слагаемых, каждое из которых отвечает за переход от $$j-1$$ к $$j$$:$$\begin{align*} H_{\rm prop}=\sum_{j=1}^{L} H_j,\nonumber\\ H_j =-\frac{1}{2} U_j\otimes\ket{j}\bra{j{-}1}-\frac{1}{2}U_j^\dagger\otimes \ket{j{-}1}\bra{j}+\frac{1}{2}I\otimes \bigl(\ket{j}\bra{j}+\ket{j{-}1}\bra{j{-}1}\bigr). \label{Hjterms} \end{align*}$$

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

Замена базиса. Произведем замену базиса, задаваемую оператором$$W=\sum_{j=0}^{L} U_j\cdot\ldots\cdot U_1\otimes \ket{j}\bra{j}.$$ Полезно обратить внимание на то, что $$W$$ — измеряющий оператор: измеряется значение счетчика $$j$$ и к q-битам пространства состояний схемы применяется оператор эволюции за время $$j$$.

Гамильтониан при такой замене изменится на сопряженный: $$\tH \double= W^\dagger HW$$. Посмотрим, как действует сопряжение оператором $$W$$ на слагаемые $$H$$.

На слагаемое $$H_{\rm in}$$ сопряжение не влияет:$$\begin{equation}\label{conj-init} \tH_{\rm in}=W^\dagger H_{\rm in} W = H_{\rm in}. \end{equation}$$

Действие на слагаемое $$H_{\rm out}$$:$$\begin{equation}\label{conj-fin} \tH_{\rm out}= W^{\dagger} H_{\rm out} W = \left(U^\dagger \Pi^{(0)}_1 U\right)\otimes \ket{L}\bra{L}. \end{equation}$$

Слагаемое $$H_j$$ состоит из трех. Вначале запишем действие сопряжения на первое из слагаемых в (13.10):$$\begin{multiline*} W^\dagger \left(-\frac{1}{2} U_j\otimes \ket{j}\bra{j-1}\right)W =\\= -\frac{1}{2} \sum_{u,t} \bigl(U_u\cdot\ldots\cdot U_1\otimes\ket{u}\bra{u}\bigr)^\dagger \bigl(U_j\otimes\ket{j}\bra{j-1}\bigr) \bigl(U_t\cdot\ldots\cdot U_1\otimes\ket{t}\bra{t}\bigr)=\\ = -\frac{1}{2} \left((U_j\cdot\ldots\cdot U_1)^\dagger U_j \cdot\ldots\cdot U_1\right) \otimes \left( \bigl(\ket{j}\bra{j}\bigr)^\dagger\, \ket{j}\bra{j-1}\; \bigl(\ket{j-1}\bra{j-1}\bigr)\right)=\\= -\frac{1}{2} I\otimes \ket{j}\bra{j-1}. \end{multiline*}$$ Сопряжение двух других слагаемых происходит аналогично, в итоге получаем$$\begin{multiline*} \tH_j=W^\dagger H_j W=\\= I\otimes \frac{1}{2}\Bigl( \ket{j-1}\bra{j-1}-\ket{j-1}\bra{j}-\ket{j}\bra{j-1}+\ket{j}\bra{j} \Bigr)=I\otimes E_j \end{multiline*}$$ и$$\begin{equation}\label{conj-prop} \tH_{\rm prop}=W^\dagger H_{\rm prop} W=I\otimes E, \end{equation}$$ где

Оценка собственного числа при ответе "да". Предположим, что схема, на вход которой подан вектор $$\ket\xi$$, дает ответ 1 с вероятностью не меньше, чем $$1-\eps$$. Это, по определению, означает, что$$\PP(0)=\langle \xi,0|\, U^\dagger \Pi^{(0)}_1U\, |\xi,0\rangle\leq\eps.$$

Докажем, что в этом случае у $$\tH$$ (а, значит, и у $$H$$ ) есть малое собственное число. Для этого предъявим такой вектор $$\ket\weta$$, что $$\langle \weta|\,\tH\,|\weta\rangle$$ достаточно мало (минимум квадратичной формы $$\langle \cdot|\,\tH\,|\cdot\rangle$$ достигается на собственном векторе).

В пространстве счетчика выберем вектор$$\begin{equation}\label {psidef} \ket\psi=\frac{1}{\sqrt{L+1}}\sum_{j=0}^{L}\ket{j}. \end{equation}$$ Искомый вектор $$\ket\weta$$ равен $$\ket{\xi,0}\otimes\ket\psi$$. Оценим $$\langle \weta|\,H\,|\weta\rangle$$.

Очевидно, что $$E\ket\psi=0$$. Поэтому$$\langle \weta|\,\tH_{\rm prop}\,|\weta\rangle=0= \langle \weta|\,\tH_j\,|\weta\rangle.$$ Поскольку все вспомогательные q-биты вначале установлены в 0, то непосредственно из определяющей формулы (13.8) получаем$$\langle \weta|\,\tH_{\rm in}\,|\weta\rangle=0.$$ Осталось оценить последнее слагаемое$$\langle \weta|\,\tH_{\rm out}\,|\weta\rangle= \langle \weta|\, \left(U^\dagger \Pi^{(0)}_1 U\right)\otimes \ket{L}\bra{L} \,|\weta\rangle=\PP(0)\cdot\frac{1}{L+1}\leq\frac{\eps}{L+1}.$$ Итак, мы доказали, что$$\langle \weta|\,\tH\,|\weta\rangle \leq \frac{\eps}{L+1},$$ поэтому у $$H$$ есть собственное число с такой же верхней оценкой.

Оценка собственного числа при ответе "нет". В этом случае нам нужно доказать, что все собственные числа велики. Пусть для любого вектора $$\ket\xi$$ вероятность ответа 1 не превосходит $$\eps$$, т.е.$$\langle \xi,0|\, U^\dagger\Pi^{(0)}_1 U\,|\xi,0\rangle\geq 1-\eps.$$ Докажем, что в этом случае все собственные числа $$H$$ больше либо равны $$c(1-\sqrt{\eps})L^{-3}$$, где $$c$$ — некоторая константа.

Доказательство довольно длинное, поэтому вначале приведем его краткий план. Представив гамильтониан в виде суммы $$\tH=A_1+A_2$$ операторов $$A_1\double=\tH_{\rm in}+\tH_{\rm out}$$ и $$A_2\double=\tH_{\rm prop}$$, мы оценим снизу наименьшие ненулевые собственные числа $$A_1$$ и $$A_2$$ по отдельности. Получим оценки $$1$$ и $$c'L^{-2}$$ соответственно. Чтобы оценить наименьшее собственное число $$A_1+A_2$$, нам потребуется лемма, которая дает такую оценку для суммы через оценки для слагаемых и угол между их нулевыми подпространствами. Углом между подпространствами $$\calL_1$$ и $$\calL_2$$ с нулевым пересечением будем называть величину $$\vt(\calL_1,\calL_2)$$, задаваемую условиями$$\begin{equation}\label{уголопр} \cos\vt(\calL_1,\calL_2)=\mkern-2mu\max\limits_{\begin{array}{l} \scriptstyle\ket{\eta_1}\in \calL_1\\[-2pt] \scriptstyle\ket{\eta_2}\in \calL_2\end{array}}\mkern-2mu \big|\langle \eta_1\ket{\eta_2}\big|,\qquad 0<\vt(\calL_1,\calL_2)<\frac{\pi}{2}. \end{equation}$$

Лемма 13.4. Пусть $$A_1$$, $$A_2$$ — неотрицательные операторы, $$\calL_1$$, $$\calL_2$$ — их нулевые подпространства, причем $$\calL_1\cap \calL_2=0$$. Пусть также ненулевые собственные числа $$A_1$$ и $$A_2$$ не меньше $$v$$. Тогда$$\begin{equation} A_1+A_2\geq v\cdot 2\sin^2\frac{\vt}{2}, \end{equation}$$ где $$\vt=\vt(\calL_1,\calL_2)$$ — угол между $$\calL_1$$ и $$\calL_2$$.

Обозначение $$A\geq a$$ ( $$A$$ — оператор, $$a$$ — число) нужно понимать как сокращение от $$A-aI\geq0$$. Другими словами, если $$A\geq a$$, то все собственные числа $$A$$ не меньше $$a$$.

В нашем случае мы получим оценки $$1$$ и $$c'L^{-2}$$ для ненулевых собственных чисел $$A_1$$ и $$A_2$$ (об этом уже говорилось выше) и $$\sin^2\vt\double\geq (1-\sqrt{\eps})/(L+1)$$ для угла. Отсюда вытекает искомое неравенство$$H\double\geq c(1-\sqrt{\eps})L^{-3}.$$

Доказательство (леммы 13.4). Очевидно, что $$A_1\ge v(I-\Pi_{\calL_1})$$ и $$A_2\ge v(I-\Pi_{\calL_2})$$, поэтому достаточно доказать неравенство $$(I-\Pi_{\calL_1})\double+(I-\Pi_{\calL_2})\ge 2\sin^2(\vt/2)$$. Оно, в свою очередь, эквивалентно такому неравенству:$$\begin{equation}\label{сумма-проекторов} \Pi_{\calL_1}+\Pi_{\calL_2}\le 1+\cos\vt. \end{equation}$$

Пусть $$\ket\xi$$ — собственный вектор оператора $$\Pi_{\calL_1}+\Pi_{\calL_2}$$, отвечающий собственному числу $$\lambda>0$$. Тогда$$\Pi_{\calL_1}\ket\xi=u_1\ket{\eta_1},\quad\ \Pi_{\calL_2}\ket\xi=u_2\ket{\eta_2},\qquad u_1\ket{\eta_1}+u_2\ket{\eta_2}=\lambda\ket\xi,$$ где $$\ket{\eta_1}\in\calL_1$$ и $$\ket{\eta_2}\in\calL_2$$ — единичные векторы, а $$u_1$$ и $$u_2$$ — неотрицательные вещественные числа. Отсюда находим$$ \lambda=\bra\xi\bigl(\Pi_{\calL_1}+\Pi_{\calL_2}\bigr)\ket\xi=u_1^2+u_2^2,\\ \lambda^2=\bigl(u_1\bra{\eta_1}+u_2\bra{\eta_2}\bigr) \bigl(u_1\ket{\eta_1}+u_2\ket{\eta_2}\bigr)= u_1^2+u_2^2+2u_1u_2\Re\langle\eta_1|\eta_2\rangle. $$ Следовательно,$$(1+x)\lambda-\lambda^2=x(u_1\pm u_2)^2\ge 0,\quad\ \text{где}\,\x=\bigl|\Re\langle\eta_1|\eta_2\rangle\bigr|.$$ Таким образом, $$\lambda\le 1+x\le 1+\cos\vt$$.

Теперь получим упомянутые выше оценки. Нулевые подпространства $$A_1$$ и $$A_2$$ представляются в виде$$\begin{equation} \calL_1=\BB^{\otimes m}\otimes\ket{0^{N-m}}\otimes\ket{0} \oplus \BB^{\otimes N}\otimes\CC(\ket1,\dots,\ket{L-1}) \oplus\\ \oplus U^\dagger\big(\ket1\otimes\BB^{\otimes(N-1)}\big)\otimes\ket{L} \label{L1} \end{equation}$$ (последний сомножитель во всех слагаемых относится к пространству счетчика),$$\begin{equation} \calL_2=\BB^{\otimes N}\otimes\ket\psi, \label{L2} \end{equation}$$ где вектор $$\ket\psi$$ определен формулой (13.14).

Для оценки$$\begin{equation}\label{A1} A_1\restrict{}_{\calL_1^\bot} \geq1 \end{equation}$$ достаточно заметить, что $$A_1$$ является суммой коммутирующих друг с другом проекторов, поэтому все собственные числа этого оператора целые.

Для оценки $$\mkern2mu A_2\restrict{}_{\calL_2^\bot}$$ нужно найти первое положительное собственное число матрицы $$E$$. Собственные векторы и собственные числа $$Е$$ даются формулами$$\ket{\psi_k}=\alpha_k\sum_{j=0}^{L} \cos\Bigl(q_k\bigl(j+\frac{1}{2}\bigr)\Bigr)\,\ket{j},\qquad \lambda_k=1-\cos q_k,$$ где $$q_k=\pi k/(L+1)$$ \, ( $$k=0,\dots,L$$ ). Отсюда следует, что$$\begin{equation}\label{A2} A_2\restrict{}_{\calL_2^\bot}\ge 1-\cos\left(\frac{\pi}{L+1}\right) \ge c'L^{-2}. \end{equation}$$

Наконец, нужно оценить угол между подпространствами $$\calL_1$$ и $$\calL_2$$. Будем оценивать квадрат косинуса угла$$\begin{equation}\label{косинус-оценка} \cos^2\vt= \max\limits_{\begin{array}{l} \scriptstyle\ket{\eta_1}\in \calL_1\\[-2pt] \scriptstyle\ket{\eta_2}\in \calL_2\end{array}}\mkern-4mu \big|\langle \eta_1\ket{\eta_2}\big|^2= \max\limits_{\scriptstyle\ket{\eta_2}\in \calL_2} \langle \eta_2|\Pi_{\calL_1}|\eta_2\rangle. \end{equation}$$ Представим $$\ket{\eta_2}$$ в виде $$\ket\xi\otimes\ket\psi$$. Проектор на $$\calL_1$$ распадается на сумму трех проекторов, в соответствии с (13.18). Совсем легко подсчитать вклад второго слагаемого, он равен $$(L-1)/(L+1)$$. Первое и третье слагаемые в сумме дают$$\frac{1}{L+1}\bra\xi\bigl(\Pi_{\calK_1}+\Pi_{\calK_2}\bigr)\ket\xi \le \frac{1+\cos\phi}{L+1},$$ где $$\calK_1=\BB^{\otimes N}$$, $$\calK_2=U^\dagger\left(\ket{1}\otimes\BB^{\otimes(N-1)}\right)$$, а $$\phi$$ — угол между этими двумя подпространствами. (Здесь используется неравенство(13.17), полученное в ходе доказательства леммы 13.4).

Величина $$\cos^2\phi$$ равна максимальной вероятности получения ответа $$1$$ исходной схемой; по условию она не больше, чем $$\eps$$. Получаем такую, продолжающую (13.22), оценку:$$\langle \eta_2|\Pi_{\calL_1}|\eta_2\rangle \le \frac{L-1}{L+1}+\frac{1+\sqrt{\eps}}{L+1} = 1-\frac{1-\sqrt{\eps}}{L+1}.$$ Следовательно, $$\sin^2\vt=1-\cos^2\vt\ge(1-\sqrt{\eps})/(L+1)$$, как и утверждалось выше.

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

Этот недостаток можно преодолеть, если вложить пространство счетчика в большее пространство. Возьмем $$L$$ q-битов, занумерованных от $$1$$ до $$L$$. Искомое вложение $$\CC^{L+1}\to\BB^{\otimes L}$$ выглядит так:$$\ket{j} \mapsto \ket{% \underbrace{1,\dots, 1}_{\scriptstyle j}, \underbrace{0,\dots, 0}_{\scriptstyle L-j}}.$$ Используемые в конструкции гамильтониана $$H$$ операторы на пространстве счетчика заменяются согласно схеме$$\begin{equation}\label{extend} \begin{aligned} \ket{0}\bra{0} \mathrel{\mathrm{ на }} \Pi^{(0)}_{1}, \quad \ket{0}\bra{1} \mathrel{\mathrm{ на }} \bigl(\ket0\bra1\bigr)_{1}\Pi^{(0)}_{2},\\ \ket{j}\bra{j} \mathrel{\mathrm{ на }} \Pi^{(1)}_{j} \Pi^{(0)}_{j+1}, \quad \ket{j-1}\bra{j} \mathrel{\mathrm{ на }} \Pi^{(1)}_{j-1}\bigl(\ket0\bra1\bigr)_{j} \Pi^{(0)}_{j+1}, \\ \ket{L}\bra{L} \mathrel{\mathrm{ на }} \Pi^{(1)}_{L}, \quad \ket{L-1}\bra{L} \mathrel{\mathrm{ на }}\Pi^{(1)}_{L-1}\bigl(\ket0\bra1\bigr)_{L}. \end{aligned} \end{equation}$$ Теперь они 3-локальные (а сам гамильтониан, с учетом действия на q-биты исходной схемы, — 5-локальный).

Если говорить точнее, мы заменили гамильтониан $$H$$, действовавший на пространстве $$\calL=\BB^{\otimes N}\otimes\CC^{L+1}$$, на новый гамильтониан $$H_{\rm ext}$$, определенный на большем пространстве $$\calL_{\rm ext}=\BB^{\otimes N}\otimes\BB^{\otimes L}$$. Оператор $$H_{\rm ext}$$ отображает подпространство $$\calL\subseteq\cal\calL_{\rm ext}$$ в себя и действует на нем так же, как $$H$$.

Теперь возникает новая проблема: что делать с лишними состояниями в расширенном пространстве счетчика? Мы справимся с этой проблемой, добавив еще одно слагаемое к гамильтониану $$H_{\rm ext}$$:$$H_{\rm stab}=I_{\BB^{\otimes N}}\otimes \sum_{j=1}^{L-1} \Pi^{(0)}_j \Pi^{(1)}_{j+1}.$$

Нулевое подпространство оператора $$H_{\rm stab}$$ совпадает со старым рабочим пространством $$\calL$$, поэтому дополнительное слагаемое не меняет верхней оценки минимального собственного числа при ответе "да".

При ответе "нет" требуемую нижнюю оценку для собственных чисел оператора $$H_{\rm ext}+H_{\rm stab}$$ можно получить следующим образом. Оба слагаемых оставляют инвариантным подпространство $$\calL$$, поэтому можно оценивать независимо на $$\calL$$ и его ортогональном дополнении $$\calL^\perp$$. На $$\calL$$ имеем $$H_{\rm ext}\ge c(1-\sqrt{\eps})L^{-3}$$ и $$H_{\rm stab}=0$$, а на $$\calL^\perp$$ — $$H_{\rm ext}\ge 0$$ и $$H_{\rm stab}\ge 1$$. (Здесь мы пользуемся тем, что каждое из слагаемых гамильтониана, (13.8), (13.9) и (13.10), остается неотрицательным при замене (13.23)). В любом случае$$H_{\rm ext}+H_{\rm stab}\double\geq c(1-\sqrt{\eps})L^{-3}.$$ Это завершает доказательство полноты задачи о локальном гамильтониане в классе BQNP.

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

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

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

Утверждение 13.5. $$\BQNP\subseteq\PSPACE$$.

Доказательство. Максимальная вероятность того, что подсказка Мерлина будет принята Артуром, равна масимальному собственному числу оператора $$X=X^{(1)}$$ (см. формулу (13.3)). Нам нужно вычислить эту величину с точностью $$O(n^{-\alpha})$$, ( $$\alpha>0$$ ).

Заметим, что $$0\le X\le 1$$. Для оценки максимального собственного числа будем использовать следующее предельное равенство:$$\ln\lambda_{\rm max}=\lim_{d\to\infty}\frac{\ln \Tr X^d}{d}.$$ Пусть $$\lambda_{\rm max}=\lambda_1\ge\lambda_2\ge\ldots\ge\lambda_{2^m}$$ — собственные числа оператора $$X$$ (здесь $$m=\poly(n)$$ — длина подсказки). Имеем оценку$$\ln\lambda_{\rm max}\leq\frac{\ln \Tr X^d}{d}=\frac{\ln\sum\limits_{j=1}^{2^m}\lambda_j^d}{d} \leq \ln\lambda_{\rm max}+\frac{m}{d}\ln 2,$$ из которой следует, что для оценки с полиномиальной точностью неотрицательного оператора, действующего на $$m$$ q-битах, достаточно вычислить след от его степени, ограниченной полиномом от $$m$$.

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

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

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