Как выбрать базис для вычислений в квантовых схемах? Унитарных операторов бесконечно много, поэтому либо полный базис должен содержать бесконечное количество элементов, либо мы должны ослабить условие точной реализуемости оператора схемой, заменив его на условие приближенной реализуемости. Мы рассмотрим обе возможности.
Теорема 7.1. Базис, содержащий все унитарные операторы, действующие на парах q-битов, позволяет реализовать любой унитарный оператор в расширенном смысле.
Для доказательства этой теоремы введем важный класс операторов: операторы с квантовым управлением.
Определение 7.1. Определим по оператору $$U\colon{}\BB^{\otimes n}\to\BB^{\otimes n}$$ оператор $$\Lambda(U)\colon{} \BB\otimes\BB^{\otimes n}\to\BB\otimes\BB^{\otimes n}$$ с квантовым управляющим q-битом (первый сомножитель) следующими соотношениями:$$\begin{aligned} \Lambda(U)\, |0\rangle \otimes|\xi\rangle = |0\rangle\otimes|\xi\rangle,\\ \Lambda(U)\, |1\rangle \otimes|\xi\rangle = |1\rangle\otimes\, U|\xi\rangle. \end{aligned}$$
Графически будем изображать оператор $$\Lambda(X)$$ с квантовым управлением как показано на рисунке. Верхняя линия соответствует первому сомножителю, нижняя линия — второму. Направление стрелок соответствует направлению перемножения операторов (справа налево).
Нам потребуются также операторы с несколькими управляющими q-битами:$$\begin{equation}\label{Lk-def} \Lambda^k(U)\, |x_1,\dots,x_k\rangle \otimes|\xi\rangle = \left\{ \begin{array}{ll} |x_1,\dots,x_k\rangle \otimes|\xi\rangle, \; \mbox{если}\ x_1\cdot\ldots\cdot x_k=0, \\ |x_1,\dots,x_k\rangle \otimes\,U|\xi\rangle, \; \mbox{если}\ x_1\cdot\ldots\cdot x_k=1. \end{array} \right. \end{equation}$$
Пример 7.1. Пусть $$\sx\bydef{\widehat\neg}=\begin{pmatrix}01\\10\end{pmatrix}$$. Тогда $$\Lambda(\sx)=\widehat{\ovst\bigcirc\oplus}$$, а $$\Lambda^2(\sx)\double=\widehat{\wedge_\oplus}$$ (элемент Тоффоли).
Теперь построим элемент Тоффоли, используя преобразования двух q-битов. Для начала найдем пару операторов, удовлетворяющих следующему соотношению $$XYX^{-1}Y^{-1}=\ii\sx$$. Например, годится такая пара:$$X=\frac{1}{\sqrt2}\begin{pmatrix} 1i\\ i1\end{pmatrix};\quad Y=\leftp\begin{array}{rr} 10\\ 0-1\end{array}\rightp.$$
Поясним геометрический смысл этой конструкции. Унитарная группа $$\U(2)$$ действует на трехмерном евклидовом пространстве. Чтобы описать это действие, заметим, что эрмитовы матрицы $$2\times2$$ с нулевым следом образуют трехмерное
При этом действии $$\sx$$ соответствует поворот вокруг оси $$x$$ на $$180^\circ$$, $$X$$ соответствует поворот вокруг $$x$$ на $$90^\circ$$, а $$Y$$ соответствует поворот вокруг $$z$$ на $$180^\circ$$.
На рис. рис. 7.1 изображено графическое представление схемы, вычисляющей элемент Тоффоли с помощью операторов $$\Lambda(X)$$, $$\Lambda(Y)$$ и $$\Lambda^2(-i)$$. Последний — это управляемый двумя битами фазовый сдвиг (умножение на $$-i$$ ). Проверим эту схему. Пусть на вход подается вектор $$\ket{a}\otimes\ket{b}\otimes\ket\xi$$, где $$a,b\in\cb$$, $$\ket\xi\in\BB$$. Если $$a=b=1$$, то к $$\ket\xi$$ будет применен оператор $$-iXYX^{-1}Y^{-1}=\sx$$, т.е. $$\ket0$$ и $$\ket1$$ в третьем q-бите переставляются. Если же хотя бы один из управляющих битов равен 0, то к $$\ket\xi$$ будет применен тождественный оператор. Это и есть действие элемента Тоффоли.
(рис 7.1) С помощью элемента Тоффоли можно реализовать любую перестановку
Покажем, как реализовать оператор $$\Lambda^k(U)$$ для любого $$k$$, действуя только на пары q-битов. Для этого также потребуется дополнительная память. Будем строить оператор $$W$$, действующий в пространстве $$N$$ q-битов $$\BB^{\otimes N}$$ и удовлетворяющий условию$$W\left(\ket\eta\otimes\ket{0^{N-k-1}}\right)= \Lambda(U)\ket\eta\otimes\ket{0^{N-k-1}}.$$ (Предостережение: это условие не означает, что $$W=\Lambda(U)\otimes I$$.)
Существует обратимая схема $$P$$ размера $$O(k)$$, вычисляющая произведение входных битов (с мусором); графически она представлена на рис. рис. 7.2 (сверху обозначено число битов в каждом из выделенных фрагментов памяти).
(рис 7.2) На рис. 7.3 показано, как с помощью схемы $$P$$ и оператора с одним управляющим q-битом построить оператор $$\Lambda^k(U)$$. Мы применяем схему $$P$$, а затем — обратную схему $$P^{-1}$$, после чего все вспомогательные биты возвращаются в исходное состояние. В промежутке самой верхней линии соответствует бит со значением $$x_1\cdot\ldots\cdot x_k$$. Его мы и используем для управления оператором $$U$$, действующим на самой нижней линии. Другим способом $$\Lambda^k(U)$$ можно записать как $$P^{-1} \Lambda(U)P$$.
(рис 7.3) Действие $$\Lambda^k(U)$$ можно описать так: на подпространстве, порожденном векторами $$\ket{1,\dots,1,0}$$ и $$\ket{1,\dots,1,1}$$, действует оператор $$U$$, а на ортогональном дополнении к этому подпространству — тождественный оператор. Наша следующая задача: реализовать оператор, который устроен так же, но нетривиальное действие осуществляется на подпространстве, натянутом на произвольную пару
Итак, на парах
Лемма 7.1. Любая унитарная матрица $$U$$ в пространстве $$\CC^M$$ может быть представлена в виде произведения $$M(M-1)/2$$ матриц вида$${\def\arraystretch{1.05}\begin{pmatrix} 10\hdotsfor{5} \\ \vdots\ddots0\hdotsfor{4} \\ 0\hdotsfor{1}1 0\hdotsfor{3}\\ 0\hdotsfor{2}\begin{pmatrix}ab\\ cd\end{pmatrix}0\hdotsfor{2} \\ 0\hdotsfor{3}100 \\ \hdotsfor{5}\ddots0 \\ 0\hdotsfor{5} 1 \end{pmatrix}, }\ \text{где } \begin{pmatrix} ab\\ cd \end{pmatrix} \in U(2).$$
Заметим, что в нашем случае $$M=2^n$$, так что получаем представление в виде произведения экспоненциального большого числа базисных операторов.
Теперь перейдем к конечным базисам. В этом случае возможно только приближенное представление операторов произведениями базисных. Чтобы определить приближенную реализацию, нам потребуется норма на пространстве операторов.
На
$$\big\| |\xi\rangle +|\eta\rangle \big\|\leq \big\| |\xi\rangle \big\| + \big\| |\eta\rangle \big\|;$$
$$\big\| c|\xi\rangle \big\|= |c| \big\| |\xi\rangle \big\|.$$
Введем теперь норму на пространстве операторов. Пусть $$\calN$$ — пространство с нормой. Пространство операторов, действующих на нем, можно представить как $$\LL(\calN)=\calN\otimes\calN^*$$ (
Определение 7.2. Норма оператора $$X$$ (так называемая операторная норма\, вообще говоря, есть и другие) равна$$\|X\|\ =\ \sup_{|\xi\rangle\not=0} \frac{\big\|X |\xi\rangle\big\|}{\big\| |\xi\rangle\big\|}.$$
Заметим, что $$\|X\|^2$$ — наибольшее
Эта норма обладает всеми перечисленными выше свойствами нормы, а кроме того, еще несколькими специфическими:$$\| XY\|\leq \|X\|\, \|Y\|;\label{опнорм1}$$
$$\|X^\dagger\|=\| X\|; \label{опнорм2}$$
$$\| X\otimes Y\|=\|X\|\, \|Y\|, \text{где } X\in\LL(\calN),\Y\in\LL(\calM).\label{опнорм3}$$
Доказательства этих свойств нормы получаются непосредственно из определения и оставляются в качестве упражнения.
Дадим теперь определение приближенной реализуемости. Если искомый оператор — $$U$$, то его приближенная реализация будет обозначаться $$\tilde U$$.
Определение 7.3. Оператор $$\tilde U$$ представляет оператор $$U$$ с точностью $$\delta$$, если $$\| \tilde U-U\|\le\delta$$.
У этого определения есть два замечательных свойства. Во-первых, если мы имеем произведение нескольких операторов $$U= U_L\cdot\ldots\cdot U_2U_1$$, каждый из которых имеет свое приближение $$\tilde U_k$$ с точностью $$\delta_k$$, то произведение этих приближений $$\tilde U= \tilde U_L\cdot\ldots\cdot \tilde U_2\tilde U_1$$ приближает $$U$$ с точностью $$\sum_{}^{}\delta_k$$ ( ошибки накапливаются линейно ):$$\big\| \tilde U_L\cdot\ldots\cdot\tilde U_1 - U_L\cdot\ldots\cdot U_1\big\|\le\sum_{j}^{}\delta_j .$$
Достаточно рассмотреть пример с двумя операторами:
$$\begin{multline*} \| \tilde U_2 \tilde U_1 -U_2U_1\|= \|\tilde U_2(\tilde U_1-U_1)+(\tilde U_2-U_2)U_1\|\leq\\ \leq \|\tilde U_2(\tilde U_1-U_1)\|+\|(\tilde U_2-U_2)U_1\| \leq \|\tilde U_2\|\, \|(\tilde U_1-U_1)\|+\|(\tilde U_2-U_2)\|\,\|U_1\|= \\ = \|(\tilde U_1-U_1)\|+\|(\tilde U_2-U_2)\|. \end{multline*}$$В этой выкладке последнее равенство справедливо благодаря унитарности операторов. (Если рассматривать неунитарные операторы, то ошибки приближения могут накапливаться гораздо быстрее, например, экспоненциально.)
Замечание 7.1. Всякая модель, претендующая на решение сложных задач какими-то реальными физическими процессами, должна обязательно изучаться на предмет устойчивости к ошибкам приближения. (В реальной жизни параметры любого физического процесса можно задать лишь с некоторой точностью.) В частности, вычисление с экспоненциальным накоплением ошибок почти заведомо бесполезно с практической точки зрения.
Второе свойство понятия " $$\tilde U$$ представляет $$U$$ с точностью $$\delta$$ " мы сформулируем в более общем контексте.
Определение 7.4. Оператор $$U\colon\BB^{\otimes n} \to\BB^{\otimes n}$$ приближается в расширенном смысле оператором $$\tilde U\colon\BB^{\otimes N} \to\BB^{\otimes N}$$ с точностью $$\delta$$, если для любого $$\ket\xi$$ из $$\BB^{\otimes n}$$ выполнено$$\big\|\tilde U\left(\ket\xi\otimes\ket{0^{N-n}}\right)- U\ket\xi\otimes\ket{0^{N-n}}\big\|\le\delta \big\| \ket\xi\big\|.$$
Сформулируем это определение еще одним способом. Введем оператор $$V\colon\BB^{\otimes n}\to \BB^{\otimes N}$$, который действует по правилу $$V\colon\ket\xi\mapsto \ket\xi\double\otimes\ket{0^{N-n}}$$. Оператор $$V$$ не унитарный, но изометричный. Условие из последнего определения можно переписать так$$\| \tilde UV-VU\|\le\delta.$$
Рассуждение про накопление ошибок проходит и в этом случае (что, конечно, следует проверить).
Справедливо следующее утверждение: если $$\tilde U$$ приближает (в расширенном смысле) $$U$$ с точностью $$\delta$$, то $$\tilde U^{-1}$$ приближает $$U^{-1}$$ с той же точностью $$\delta$$. Это следует из того, что $$\| W_1XW_2\|=\|X\|$$ для унитарных операторов $$W_1,\, W_2$$. Умножая выражение под нормой в (7.10) слева на $$\tilde U^{-1}$$, а справа — на $$U^{-1}$$, получим следствие из неравенства (7.10): $$\| \tilde U^{-1}V-VU^{-1}\|\le\delta$$.
Определение 7.5. Будем называть базис $$\calA$$ полным, если любой унитарный оператор $$U$$ можно с любой точностью представить в расширенном смысле квантовой схемой в базисе $$\calA$$.
Теорема 7.2. (см. [4]). Базис $$\calQ=\{H,K,\QXOR,\Lambda^2(\sx)\}$$, где$$H\ =\ \frac{1}{\sqrt{2}} \leftp\begin{array}{rr} 11\\ 1-1 \end{array} \rightp, \qquad K\ =\ \leftp\begin{array}{cc} 10\\ 0\ii \end{array} \rightp,$$ является полным. (Такой базис будем называть стандартным.)
Доказательство этой теоремы следует из решения задач 7.5-7.9.
Замечание 7.2. Если убрать из базиса $$\calQ$$ квантовый элемент Тоффоли, он перестает быть полным. Однако многие важные вычисления можно делать и в таком усеченном базисе. В частности, как будет видно в дальнейшем, схемы, исправляющие ошибки, можно реализовать без элемента Тоффоли.
Можно оценить сложность реализации оператора $$U$$ в этом базисе. Если $$U\colon{} \BB^{\otimes n}\to\BB^{\otimes n}$$, то можно реализовать этот оператор с точностью $$\delta$$ квантовой схемой в базисе $$\calQ$$ размера $$L=\exp(O(n))\cdot \poly(\log(\slashfrac{1}{\delta}))$$. Если матричные элементы $$U$$ заданы в двоичной записи, то эта схема строится по $$U$$ с помощью некоторого алгоритма примерно за то же время (множители и степени полинома могут отличаться). Идея построения такого алгоритма легко усматривается из задач 7.1 и 7.11.
Пусть $$\calM$$ — унитарное пространство размерности $$\ge 3$$. Рассмотрим подгруппу $$H\subset\U(\calM)$$ — стабилизатор одномерного подпространства, порожденного некоторым единичным вектором $$|\xi\rangle\in\calM$$. Пусть $$V$$ — произвольный унитарный оператор, не сохраняющий подпространство $$\CC(|\xi\rangle)$$. Докажите, что множество операторов $$H\cup V^{-1}HV$$ порождает всю группу $$U(\calM)$$.
(Заметим, что в условии этой задачи $$U(\calM)$$ и $$H$$ можно профакторизовать по подгруппе фазовых сдвигов $$U(1)$$ ).
Докажите, что любой оператор $$U$$, действующий на одном q-бите, может быть приближенно реализован в расширенном смысле с точностью $$\delta$$ схемой размера $$O(\log^3(1/\delta))$$ в стандартном базисе, и есть полиномиальный алгоритм построения этой схемы по описанию $$U$$.
Эта задача довольно сложна, к ее решению лучше приступать после знакомства с разделами 11 и 12 и решения задачи 12.3 (квантовое преобразование Фурье). Предлагаемый путь решения является достаточно изощренным. В статье [4] был использован более прямой (но тоже неочевидный) подход, при котором получается схема размера $$\poly(\log(1/\delta))$$.
Как выбрать базис для вычислений в квантовых схемах? Унитарных операторов бесконечно много, поэтому либо полный базис должен содержать бесконечное количество элементов, либо мы должны ослабить условие точной реализуемости оператора схемой, заменив его на условие приближенной реализуемости. Мы рассмотрим обе возможности.
Теорема 7.1. Базис, содержащий все унитарные операторы, действующие на парах q-битов, позволяет реализовать любой унитарный оператор в расширенном смысле.
Для доказательства этой теоремы введем важный класс операторов: операторы с квантовым управлением.
Определение 7.1. Определим по оператору $$U\colon{}\BB^{\otimes n}\to\BB^{\otimes n}$$ оператор $$\Lambda(U)\colon{} \BB\otimes\BB^{\otimes n}\to\BB\otimes\BB^{\otimes n}$$ с квантовым управляющим q-битом (первый сомножитель) следующими соотношениями:$$\begin{aligned} \Lambda(U)\, |0\rangle \otimes|\xi\rangle = |0\rangle\otimes|\xi\rangle,\\ \Lambda(U)\, |1\rangle \otimes|\xi\rangle = |1\rangle\otimes\, U|\xi\rangle. \end{aligned}$$
Графически будем изображать оператор $$\Lambda(X)$$ с квантовым управлением как показано на рисунке. Верхняя линия соответствует первому сомножителю, нижняя линия — второму. Направление стрелок соответствует направлению перемножения операторов (справа налево).
Нам потребуются также операторы с несколькими управляющими q-битами:$$\begin{equation}\label{Lk-def} \Lambda^k(U)\, |x_1,\dots,x_k\rangle \otimes|\xi\rangle = \left\{ \begin{array}{ll} |x_1,\dots,x_k\rangle \otimes|\xi\rangle, \; \mbox{если}\ x_1\cdot\ldots\cdot x_k=0, \\ |x_1,\dots,x_k\rangle \otimes\,U|\xi\rangle, \; \mbox{если}\ x_1\cdot\ldots\cdot x_k=1. \end{array} \right. \end{equation}$$
Пример 7.1. Пусть $$\sx\bydef{\widehat\neg}=\begin{pmatrix}01\\10\end{pmatrix}$$. Тогда $$\Lambda(\sx)=\widehat{\ovst\bigcirc\oplus}$$, а $$\Lambda^2(\sx)\double=\widehat{\wedge_\oplus}$$ (элемент Тоффоли).
Теперь построим элемент Тоффоли, используя преобразования двух q-битов. Для начала найдем пару операторов, удовлетворяющих следующему соотношению $$XYX^{-1}Y^{-1}=\ii\sx$$. Например, годится такая пара:$$X=\frac{1}{\sqrt2}\begin{pmatrix} 1i\\ i1\end{pmatrix};\quad Y=\leftp\begin{array}{rr} 10\\ 0-1\end{array}\rightp.$$
Поясним геометрический смысл этой конструкции. Унитарная группа $$\U(2)$$ действует на трехмерном евклидовом пространстве. Чтобы описать это действие, заметим, что эрмитовы матрицы $$2\times2$$ с нулевым следом образуют трехмерное
При этом действии $$\sx$$ соответствует поворот вокруг оси $$x$$ на $$180^\circ$$, $$X$$ соответствует поворот вокруг $$x$$ на $$90^\circ$$, а $$Y$$ соответствует поворот вокруг $$z$$ на $$180^\circ$$.
На рис. рис. 7.1 изображено графическое представление схемы, вычисляющей элемент Тоффоли с помощью операторов $$\Lambda(X)$$, $$\Lambda(Y)$$ и $$\Lambda^2(-i)$$. Последний — это управляемый двумя битами фазовый сдвиг (умножение на $$-i$$ ). Проверим эту схему. Пусть на вход подается вектор $$\ket{a}\otimes\ket{b}\otimes\ket\xi$$, где $$a,b\in\cb$$, $$\ket\xi\in\BB$$. Если $$a=b=1$$, то к $$\ket\xi$$ будет применен оператор $$-iXYX^{-1}Y^{-1}=\sx$$, т.е. $$\ket0$$ и $$\ket1$$ в третьем q-бите переставляются. Если же хотя бы один из управляющих битов равен 0, то к $$\ket\xi$$ будет применен тождественный оператор. Это и есть действие элемента Тоффоли.
(рис 7.1) С помощью элемента Тоффоли можно реализовать любую перестановку
Покажем, как реализовать оператор $$\Lambda^k(U)$$ для любого $$k$$, действуя только на пары q-битов. Для этого также потребуется дополнительная память. Будем строить оператор $$W$$, действующий в пространстве $$N$$ q-битов $$\BB^{\otimes N}$$ и удовлетворяющий условию$$W\left(\ket\eta\otimes\ket{0^{N-k-1}}\right)= \Lambda(U)\ket\eta\otimes\ket{0^{N-k-1}}.$$ (Предостережение: это условие не означает, что $$W=\Lambda(U)\otimes I$$.)
Существует обратимая схема $$P$$ размера $$O(k)$$, вычисляющая произведение входных битов (с мусором); графически она представлена на рис. рис. 7.2 (сверху обозначено число битов в каждом из выделенных фрагментов памяти).
(рис 7.2) На рис. 7.3 показано, как с помощью схемы $$P$$ и оператора с одним управляющим q-битом построить оператор $$\Lambda^k(U)$$. Мы применяем схему $$P$$, а затем — обратную схему $$P^{-1}$$, после чего все вспомогательные биты возвращаются в исходное состояние. В промежутке самой верхней линии соответствует бит со значением $$x_1\cdot\ldots\cdot x_k$$. Его мы и используем для управления оператором $$U$$, действующим на самой нижней линии. Другим способом $$\Lambda^k(U)$$ можно записать как $$P^{-1} \Lambda(U)P$$.
(рис 7.3) Действие $$\Lambda^k(U)$$ можно описать так: на подпространстве, порожденном векторами $$\ket{1,\dots,1,0}$$ и $$\ket{1,\dots,1,1}$$, действует оператор $$U$$, а на ортогональном дополнении к этому подпространству — тождественный оператор. Наша следующая задача: реализовать оператор, который устроен так же, но нетривиальное действие осуществляется на подпространстве, натянутом на произвольную пару
Итак, на парах
Лемма 7.1. Любая унитарная матрица $$U$$ в пространстве $$\CC^M$$ может быть представлена в виде произведения $$M(M-1)/2$$ матриц вида$${\def\arraystretch{1.05}\begin{pmatrix} 10\hdotsfor{5} \\ \vdots\ddots0\hdotsfor{4} \\ 0\hdotsfor{1}1 0\hdotsfor{3}\\ 0\hdotsfor{2}\begin{pmatrix}ab\\ cd\end{pmatrix}0\hdotsfor{2} \\ 0\hdotsfor{3}100 \\ \hdotsfor{5}\ddots0 \\ 0\hdotsfor{5} 1 \end{pmatrix}, }\ \text{где } \begin{pmatrix} ab\\ cd \end{pmatrix} \in U(2).$$
Заметим, что в нашем случае $$M=2^n$$, так что получаем представление в виде произведения экспоненциального большого числа базисных операторов.
Теперь перейдем к конечным базисам. В этом случае возможно только приближенное представление операторов произведениями базисных. Чтобы определить приближенную реализацию, нам потребуется норма на пространстве операторов.
На
$$\big\| |\xi\rangle +|\eta\rangle \big\|\leq \big\| |\xi\rangle \big\| + \big\| |\eta\rangle \big\|;$$
$$\big\| c|\xi\rangle \big\|= |c| \big\| |\xi\rangle \big\|.$$
Введем теперь норму на пространстве операторов. Пусть $$\calN$$ — пространство с нормой. Пространство операторов, действующих на нем, можно представить как $$\LL(\calN)=\calN\otimes\calN^*$$ (
Определение 7.2. Норма оператора $$X$$ (так называемая операторная норма\, вообще говоря, есть и другие) равна$$\|X\|\ =\ \sup_{|\xi\rangle\not=0} \frac{\big\|X |\xi\rangle\big\|}{\big\| |\xi\rangle\big\|}.$$
Заметим, что $$\|X\|^2$$ — наибольшее
Эта норма обладает всеми перечисленными выше свойствами нормы, а кроме того, еще несколькими специфическими:$$\| XY\|\leq \|X\|\, \|Y\|;\label{опнорм1}$$
$$\|X^\dagger\|=\| X\|; \label{опнорм2}$$
$$\| X\otimes Y\|=\|X\|\, \|Y\|, \text{где } X\in\LL(\calN),\Y\in\LL(\calM).\label{опнорм3}$$
Доказательства этих свойств нормы получаются непосредственно из определения и оставляются в качестве упражнения.
Дадим теперь определение приближенной реализуемости. Если искомый оператор — $$U$$, то его приближенная реализация будет обозначаться $$\tilde U$$.
Определение 7.3. Оператор $$\tilde U$$ представляет оператор $$U$$ с точностью $$\delta$$, если $$\| \tilde U-U\|\le\delta$$.
У этого определения есть два замечательных свойства. Во-первых, если мы имеем произведение нескольких операторов $$U= U_L\cdot\ldots\cdot U_2U_1$$, каждый из которых имеет свое приближение $$\tilde U_k$$ с точностью $$\delta_k$$, то произведение этих приближений $$\tilde U= \tilde U_L\cdot\ldots\cdot \tilde U_2\tilde U_1$$ приближает $$U$$ с точностью $$\sum_{}^{}\delta_k$$ ( ошибки накапливаются линейно ):$$\big\| \tilde U_L\cdot\ldots\cdot\tilde U_1 - U_L\cdot\ldots\cdot U_1\big\|\le\sum_{j}^{}\delta_j .$$
Достаточно рассмотреть пример с двумя операторами:
$$\begin{multline*} \| \tilde U_2 \tilde U_1 -U_2U_1\|= \|\tilde U_2(\tilde U_1-U_1)+(\tilde U_2-U_2)U_1\|\leq\\ \leq \|\tilde U_2(\tilde U_1-U_1)\|+\|(\tilde U_2-U_2)U_1\| \leq \|\tilde U_2\|\, \|(\tilde U_1-U_1)\|+\|(\tilde U_2-U_2)\|\,\|U_1\|= \\ = \|(\tilde U_1-U_1)\|+\|(\tilde U_2-U_2)\|. \end{multline*}$$В этой выкладке последнее равенство справедливо благодаря унитарности операторов. (Если рассматривать неунитарные операторы, то ошибки приближения могут накапливаться гораздо быстрее, например, экспоненциально.)
Замечание 7.1. Всякая модель, претендующая на решение сложных задач какими-то реальными физическими процессами, должна обязательно изучаться на предмет устойчивости к ошибкам приближения. (В реальной жизни параметры любого физического процесса можно задать лишь с некоторой точностью.) В частности, вычисление с экспоненциальным накоплением ошибок почти заведомо бесполезно с практической точки зрения.
Второе свойство понятия " $$\tilde U$$ представляет $$U$$ с точностью $$\delta$$ " мы сформулируем в более общем контексте.
Определение 7.4. Оператор $$U\colon\BB^{\otimes n} \to\BB^{\otimes n}$$ приближается в расширенном смысле оператором $$\tilde U\colon\BB^{\otimes N} \to\BB^{\otimes N}$$ с точностью $$\delta$$, если для любого $$\ket\xi$$ из $$\BB^{\otimes n}$$ выполнено$$\big\|\tilde U\left(\ket\xi\otimes\ket{0^{N-n}}\right)- U\ket\xi\otimes\ket{0^{N-n}}\big\|\le\delta \big\| \ket\xi\big\|.$$
Сформулируем это определение еще одним способом. Введем оператор $$V\colon\BB^{\otimes n}\to \BB^{\otimes N}$$, который действует по правилу $$V\colon\ket\xi\mapsto \ket\xi\double\otimes\ket{0^{N-n}}$$. Оператор $$V$$ не унитарный, но изометричный. Условие из последнего определения можно переписать так$$\| \tilde UV-VU\|\le\delta.$$
Рассуждение про накопление ошибок проходит и в этом случае (что, конечно, следует проверить).
Справедливо следующее утверждение: если $$\tilde U$$ приближает (в расширенном смысле) $$U$$ с точностью $$\delta$$, то $$\tilde U^{-1}$$ приближает $$U^{-1}$$ с той же точностью $$\delta$$. Это следует из того, что $$\| W_1XW_2\|=\|X\|$$ для унитарных операторов $$W_1,\, W_2$$. Умножая выражение под нормой в (7.10) слева на $$\tilde U^{-1}$$, а справа — на $$U^{-1}$$, получим следствие из неравенства (7.10): $$\| \tilde U^{-1}V-VU^{-1}\|\le\delta$$.
Определение 7.5. Будем называть базис $$\calA$$ полным, если любой унитарный оператор $$U$$ можно с любой точностью представить в расширенном смысле квантовой схемой в базисе $$\calA$$.
Теорема 7.2. (см. [4]). Базис $$\calQ=\{H,K,\QXOR,\Lambda^2(\sx)\}$$, где$$H\ =\ \frac{1}{\sqrt{2}} \leftp\begin{array}{rr} 11\\ 1-1 \end{array} \rightp, \qquad K\ =\ \leftp\begin{array}{cc} 10\\ 0\ii \end{array} \rightp,$$ является полным. (Такой базис будем называть стандартным.)
Доказательство этой теоремы следует из решения задач 7.5-7.9.
Замечание 7.2. Если убрать из базиса $$\calQ$$ квантовый элемент Тоффоли, он перестает быть полным. Однако многие важные вычисления можно делать и в таком усеченном базисе. В частности, как будет видно в дальнейшем, схемы, исправляющие ошибки, можно реализовать без элемента Тоффоли.
Можно оценить сложность реализации оператора $$U$$ в этом базисе. Если $$U\colon{} \BB^{\otimes n}\to\BB^{\otimes n}$$, то можно реализовать этот оператор с точностью $$\delta$$ квантовой схемой в базисе $$\calQ$$ размера $$L=\exp(O(n))\cdot \poly(\log(\slashfrac{1}{\delta}))$$. Если матричные элементы $$U$$ заданы в двоичной записи, то эта схема строится по $$U$$ с помощью некоторого алгоритма примерно за то же время (множители и степени полинома могут отличаться). Идея построения такого алгоритма легко усматривается из задач 7.1 и 7.11.
Пусть $$\calM$$ — унитарное пространство размерности $$\ge 3$$. Рассмотрим подгруппу $$H\subset\U(\calM)$$ — стабилизатор одномерного подпространства, порожденного некоторым единичным вектором $$|\xi\rangle\in\calM$$. Пусть $$V$$ — произвольный унитарный оператор, не сохраняющий подпространство $$\CC(|\xi\rangle)$$. Докажите, что множество операторов $$H\cup V^{-1}HV$$ порождает всю группу $$U(\calM)$$.
(Заметим, что в условии этой задачи $$U(\calM)$$ и $$H$$ можно профакторизовать по подгруппе фазовых сдвигов $$U(1)$$ ).
Докажите, что любой оператор $$U$$, действующий на одном q-бите, может быть приближенно реализован в расширенном смысле с точностью $$\delta$$ схемой размера $$O(\log^3(1/\delta))$$ в стандартном базисе, и есть полиномиальный алгоритм построения этой схемы по описанию $$U$$.
Эта задача довольно сложна, к ее решению лучше приступать после знакомства с разделами 11 и 12 и решения задачи 12.3 (квантовое преобразование Фурье). Предлагаемый путь решения является достаточно изощренным. В статье [4] был использован более прямой (но тоже неочевидный) подход, при котором получается схема размера $$\poly(\log(1/\delta))$$.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.