Теорема Соловея–Китаева.

В области квантовой информации и вычислений теорема Соловея-Китаева гласит, что если набор однокубитных квантовых вентилей порождает плотную подгруппу SU (2) , то этот набор можно использовать для аппроксимации любых желаемых квантовых вентилей с помощью короткой последовательности вентилей. это также можно найти эффективно. Эта теорема считается одним из наиболее важных результатов в области квантовых вычислений . Впервые она была анонсирована Робертом Соловеем в 1995 году и независимо доказана Алексеем Китаевым в 1997 году. Майкл Нильсен и Кристофер М. Доусон отметили его важность в этой области.

Следствием этой теоремы является то, что квантовая схема $m$ вентили с постоянным кубитом можно аппроксимировать как $\varepsilon$ ошибка (в операторной норме ) квантовой схемой $O(m\log ^{c}(m/\varepsilon ))$ элементы из желаемого конечного универсального набора элементов (где c — константа). Для сравнения, знание того, что набор вентилей является универсальным, означает лишь то, что вентили с постоянным кубитом могут быть аппроксимированы конечной схемой из набора вентилей без ограничений на его длину. Итак, теорема Соловея-Китаева показывает, что это приближение можно сделать удивительно эффективным , тем самым оправдывая, что квантовым компьютерам достаточно реализовать только конечное число вентилей, чтобы получить всю мощь квантовых вычислений.

Заявление

Позволять ${\mathcal {G}}$ — конечное множество элементов из SU(2), содержащее свои собственные обратные (поэтому $g\in {\mathcal {G}}$ подразумевает $g^{-1}\in {\mathcal {G}}$) и такой, что группа $\langle {\mathcal {G}}\rangle$ они порождают, плотно в SU(2). Рассмотрим некоторые $\varepsilon >0$. Тогда есть константа $c$ такой, что для любого $U\in \mathrm {SU} (2)$, существует последовательность $S$ ворот из ${\mathcal {G}}$ длины $O(\log ^{c}(1/\varepsilon ))$ такой, что $\|S-U\|\leq \varepsilon$. То есть, $S$ приближает $U$ к ошибке оператора нормы. Более того, существует эффективный алгоритм для поиска такой последовательности. В более общем смысле, теорема справедлива и в SU(d) для любого фиксированного d.

Эта теорема справедлива и без предположения, что ${\mathcal {G}}$ содержит свои собственные обратные значения, хотя в настоящее время с большим значением $c$ которое также увеличивается с увеличением размерности $d$.

Количественные границы

Константа $c$ можно сделать так, чтобы быть $\log _{(1+{\sqrt {5}})/2}2+\delta =1.44042\ldots +\delta$ для любого фиксированного $\delta >0$. Однако существуют определенные наборы вентилей, для которых мы можем принять $c=1$, что делает длину последовательности вентилей оптимальной с точностью до постоянного коэффициента.

Идея доказательства

Каждое известное доказательство полностью общей теоремы Соловея-Китаева основано на рекурсивном построении последовательности вентилей, дающей все более хорошие приближения к $U\in \operatorname {SU} (2)$. Предположим, у нас есть приближение $U_{n-1}\in \operatorname {SU} (2)$ такой, что $\|U-U_{n-1}\|\leq \varepsilon _{n-1}$. Наша цель — найти последовательность вентилей, аппроксимирующую $UU_{n-1}^{-1}$ к $\varepsilon _{n}$ ошибка, ибо $\varepsilon _{n}<\varepsilon _{n-1}$. Объединив эту последовательность ворот с $U_{n-1}$, мы получаем последовательность гейтов $U_{n}$ такой, что $\|U-U_{n}\|\leq \varepsilon _{n}$.

Основная идея оригинального рассуждения Соловая и Китаева состоит в том, что коммутаторы элементов, близких к единице, можно аппроксимировать «лучше, чем ожидалось». В частности, для $V,W\in \operatorname {SU} (2)$ удовлетворяющий $\|V-I\|\leq \delta _{1}$ и $\|W-I\|\leq \delta _{1}$ и приближения ${\tilde {V}},{\tilde {W}}\in \operatorname {SU} (2)$ удовлетворяющий $\|V-{\tilde {V}}\|\leq \delta _{2}$ и $\|W-{\tilde {W}}\|\leq \delta _{2}$, затем

$\|VWV^{-1}W^{-1}-{\tilde {V}}{\tilde {W}}{\tilde {V}}^{-1}{\tilde {W}}^{-1}\|\leq O(\delta _{1}\delta _{2}),$

где большое обозначение O скрывает члены более высокого порядка. Можно наивно связать приведенное выше выражение как $O(\delta _{2})$, но структура группового коммутатора приводит к существенному подавлению ошибок.

Мы можем использовать это наблюдение для аппроксимации $UU_{n-1}^{-1}$ в качестве группового коммутатора $V_{n-1}W_{n-1}V_{n-1}^{-1}W_{n-1}^{-1}$. Это можно сделать так, чтобы оба $V_{n-1}$ и $W_{n-1}$ близки к тождеству (поскольку $\|UU_{n-1}^{-1}-I\|\leq \varepsilon _{n-1}$). Итак, если мы рекурсивно вычисляем последовательности вентилей, аппроксимирующие $V_{n-1}$ и $W_{n-1}$ к $\varepsilon _{n-1}$ ошибка, мы получаем последовательность вентилей, аппроксимирующую $UU_{n-1}^{-1}$ до желаемой лучшей точности $\varepsilon _{n}$ с $\varepsilon _{n}$. Мы можем получить базовое приближение с константой $\varepsilon _{0}$ с исчерпывающим поиском последовательностей вентилей ограниченной длины.

Доказательство теоремы Соловея-Китаева.

Выберем начальное значение $\varepsilon _{0}$ так что $\varepsilon _{0}<\varepsilon '$ чтобы иметь возможность применить итерированную лемму о «сжатии». Кроме того, мы хотим $s\varepsilon _{0}<1$ чтобы убедиться, что $\varepsilon _{k}$ уменьшается по мере увеличения $k$. Более того, мы также следим за тем, чтобы $\varepsilon _{0}$ достаточно мал, чтобы $\varepsilon _{k}^{2}<\varepsilon _{k+1}$.

С $\langle G\rangle$ плотный в $\operatorname {SU} (2)$, мы можем выбрать $l_{0}$ достаточно большой так что $G^{l_{0}}$ это $\varepsilon _{0}^{2}$-сеть для $\operatorname {SU} (2)$ (и, следовательно, для $\operatorname {S} _{\varepsilon _{0}}$, а также), каким бы маленьким он ни был $\varepsilon _{0}$ является. Таким образом, учитывая любой $U\in \operatorname {SU} (2)$, мы можем выбрать $U_{0}\in G^{l_{0}}$ такой, что $||U-U_{0}||<\varepsilon _{0}^{2}$. Позволять $\Delta :=UU_{0}^{+}$ быть «разницей» $U$ и $U_{0}$. Затем

$\|\Delta _{1}-I\|=\|(U-U_{0})U_{0}^{+}\|=\|U-U_{0}\|<\varepsilon _{0}^{2}<\varepsilon _{1}.$

Следовательно, $\Delta _{1}\in \operatorname {S_{\varepsilon _{1}}}$. Применяя повторяемую лемму о «сжатии» с $k=1$, там существует $U_{1}\in G^{l_{1}}$ такой, что

$\|\Delta _{1}-U_{1}\|=\|UU_{0}^{+}-U_{1}\|=\|U-U_{1}U_{0}\|<\varepsilon _{1}^{2}.$

Аналогично пусть $\Delta _{2}:=\Delta _{1}U_{1}^{+}=UU_{0}^{+}U_{1}^{+}$. Затем

$\|\Delta _{2}-I\|=\|(U-U_{1}U_{0})U_{0}^{+}U_{1}^{+}\|=\|U-U_{1}U_{0}\|<\varepsilon _{1}^{2}<\varepsilon _{2}.$

Таким образом, $\Delta _{2}\in \operatorname {S_{\varepsilon _{2}}}$ и мы можем вызвать повторную лемму о «сжатии» (с $k=2$ на этот раз), чтобы получить $U_{2}\in G^{l_{2}}$ такой, что $\|\Delta _{2}-U_{2}\|=\|UU_{0}^{+}U_{1}^{+}-U_{2}\|=\|U-U_{2}U_{1}U_{0}\|<\varepsilon _{2}^{2}.$

Если продолжить в том же духе, то через k шагов получим $U_{k}\in \operatorname {G} ^{l_{k}}$ такой, что

$\|U-U_{k}U_{k-1}...U_{0}\|<\varepsilon _{k}^{2}.$

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

$L=\sum _{m=0}^{k}l_{m}=\sum _{m=0}^{k}5^{m}l_{0}={\frac {5^{k+1}-1}{4}}l_{0}<{\frac {5}{4}}5^{k}l_{0}$

ворота, которые приближаются $U$ к точности $\varepsilon _{k}^{2}$. Чтобы определить ценность $k$, мы установили $\varepsilon _{k}^{2}=\left((s\varepsilon _{0})^{(3/2)^{k}}/s\right)^{2}=\varepsilon$ и решим относительно k:

$\left({\frac {3}{2}}\right)^{k}={\frac {{\text{log}}(1/s^{2}\varepsilon )}{2{\text{log}}(1/s\varepsilon _{0})}}.$

Теперь мы всегда можем выбрать $\varepsilon _{0}$ немного меньше, чтобы полученное значение из $k$ является целым числом. Позволять $c={\text{log}}5/{\text{log}}(3/2)\approx 3.97$ так что $5^{k}=\left({\frac {3}{2}}\right)^{kc}$. Затем

$L<{\frac {5}{4}}5^{k}l_{0}={\frac {5}{4}}\left({\frac {3}{2}}\right)^{kc}l_{0}={\frac {5}{4}}\left({\frac {{\text{log}}(1/s^{2}\varepsilon )}{2{\text{log}}(1/s\varepsilon _{0})}}\right)^{c}l_{0}$

Следовательно, для любого $U\in \operatorname {SU} (2)$ существует последовательность $L=O({\text{log}}^{c}(1/\varepsilon ))$ ворота, которые приближает $U$ к точности $\varepsilon$.

Алгоритм Соловея-Китаева для кубитов

Здесь представлены основные идеи, которые используются в алгоритме SK. Алгоритм SK может быть выражен в девяти строках псевдокода. Каждый из этих строки подробно объяснены ниже, но мы приведем их здесь полностью как для справки читателя, так и для того, чтобы подчеркнуть концептуальную простоту алгоритма:

функция Соловая-Китаева(Gate $U$, глубина $n$)

если ( $n$ == 0)

Верните базовое приближение в $U$

еще

Набор $U_{n-1}$ = Соловай-Китаев( $U$, $n-1$)

Набор $V,W$ = GC-Разложение( $UU_{n-1}^{+}$)

Набор $V_{n-1}$ = Соловай-Китаев( $V,n-1$)

Набор $W_{n-1}$ = Соловай-Китаев( $W,n-1$)

Возвращаться $U_{n}=V_{n-1}W_{n-1}V_{n-1}^{+}W_{n-1}^{+}U_{n-1}$;

Разберем каждую из этих линий подробно. Первая строка:

функция Соловая-Китаева(Gate $U$, глубина $n$)

указывает, что алгоритм представляет собой функцию с двумя входами: произвольный однокубитный квант ворота, $U$, который мы хотим аппроксимировать, и неотрицательное целое число, $n$, который контролирует точность приближения. Функция возвращает последовательность инструкций, которые приближает $U$ с точностью $\varepsilon _{n}$, где $\varepsilon _{n}$ является убывающей функцией $n$, так что как $n$ получает чем больше, тем выше точность. $\varepsilon _{n}$→ 0 как $n$ → ∞. $\varepsilon _{n}$ подробно описано ниже.

Функция Соловая-Китаева рекурсивная, так что для получения $\varepsilon _{n}$-приближение к $U$, он позвонит себе, чтобы получить $\varepsilon _{n-1}$-приближения к некоторым унитариям. Рекурсия завершается в $n=0$, за пределами которого дальнейшие рекурсивные вызовы не выполняются:

если ( $n$ == 0)

Верните базовое приближение в $U$

Для реализации этого шага предполагается, что этап предварительной обработки завершен. что позволяет найти основное $\varepsilon _{0}$-приближение к произвольному $U\in \operatorname {SU} (2)$. С $\varepsilon _{0}$ является константой, в принципе этот этап предварительной обработки можно выполнить, просто перечислив и хранения большого количества последовательностей команд из $G$, скажем, до некоторого достаточно большого (но фиксированная) длина $l_{0}$, а затем предоставляя процедуру поиска, которая, учитывая $U$, возвращает ближайшую последовательность.

На более высоких уровнях рекурсии, чтобы найти $\varepsilon _{n}$-приближение к $U$, человек начинает с поиска $\varepsilon _{n-1}$-приближение к $U$:

еще

Набор $U_{n-1}$ = Соловай-Китаев( $U$, $n-1$)

$U_{n-1}$ используется как шаг к поиску улучшенного приближения к $U$. Определение $\Delta$≡ $UU_{n-1}^{+}$, следующие три шага алгоритма направлены на поиск $\varepsilon _{n}$-приближение к $\Delta$, где $\varepsilon _{n}$ представляет собой некоторый повышенный уровень точности, т.е. $\varepsilon _{n}<\varepsilon _{n-1}$. Нахождение такого приближения также позволяет нам получить $\varepsilon _{n}$-приближение к $U$, просто путем объединения точных последовательность инструкций для $U_{n-1}$ с $\varepsilon _{n}$-аппроксимирующая последовательность для $\Delta$.

Как найти такое приближение? Во-первых, заметьте, что $\Delta$ находится на расстоянии $\varepsilon _{n-1}$ личности. Это следует из определения $\Delta$ и тот факт, что $U_{n-1}$ находится на расстоянии $\varepsilon _{n-1}$ из $U$.

Во-вторых, разложить $\Delta$ в качестве группового коммутатора $\Delta =VWV^{+}W^{+}$ унитарных ворот $V$ и $W$. Для любого $\Delta$ оказывается, что это не очевидно и всегда существует бесконечное множество выбор для $V$ и $W$ такой, что $\Delta =VWV^{+}W^{+}$. Для наших целей важно, чтобы мы находить $V$ и $W$ такой, что $d(I,V),d(I,W)<c_{gc}{\sqrt {\varepsilon _{n-1}}}$ для некоторой константы $c_{gc}$. Такое разложение мы называем сбалансированным групповым коммутатором .

Набор $V,W$ = GC-Разложение( $UU_{n-1}^{+}$)

Ниже мы увидим, что для практических реализаций полезно иметь $c_{gc}$ такой маленький, как возможный.

Следующим шагом является поиск последовательностей команд, которые $\varepsilon _{n-1}$-приближения к $V$ и $W$:

Набор $V_{n-1}$ = Соловай-Китаев( $V,n-1$)

Набор $W_{n-1}$ = Соловай-Китаев( $W,n-1$)

Групповой коммутатор $V_{n-1}$ и $W_{n}$ оказывается $\varepsilon _{n-1}$ ≡ $c_{\text{approx}}\varepsilon _{n-1}^{3/2}$-приближение к $\Delta$, для некоторой небольшой константы $c_{\text{approx}}$. Предоставил $\varepsilon _{n-1}<1/c_{\text{approx}}^{2}$, мы видим это $\varepsilon _{n}<\varepsilon _{n-1}$, и поэтому эта процедура обеспечивает улучшенное приближение к $\Delta$, и таким образом $U$.

Константа $c_{\text{approx}}$ важен, поскольку он определяет точность $\varepsilon _{0}$ требуемое от начальных приближений. В частности, мы видим, что для этой конструкции необходимо гарантировать, что $\varepsilon _{0}>\varepsilon _{1}>...$ мы должны иметь $\varepsilon _{0}<1/c_{\text{approx}}^{2}$.

Алгоритм завершается возвратом последовательностей, аппроксимирующих групповой коммутатор, а также $U_{n-1}$:

Возвращаться $U_{n}=V_{n-1}W_{n-1}V_{n-1}^{+}W_{n-1}^{+}U_{n-1}$;

Подводя итог, функция Соловая-Китаева(U, n) возвращает последовательность, которая обеспечивает $\varepsilon _{n}=c_{\text{approx}}\varepsilon _{n-1}^{3/2}$-приближение к искомому унитарному $U$ . Пять составляющих этой последовательности все они получены путем вызова функции в $n-1$уровень рекурсии.