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

Теорема квантовой теории информации

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

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

Заявление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}$

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

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

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

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

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

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

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

функция Соловая-Китаева(Ворота , глубина ) ${\displaystyle U}$ ${\displaystyle n}$

если ( == 0) ${\displaystyle n}$

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

еще

Set = Соловай-Китаев( , ) ${\displaystyle U_{n-1}}$ ${\displaystyle U}$ ${\displaystyle n-1}$

Set = GC-Decompose( ) ${\displaystyle V,W}$ ${\displaystyle UU_{n-1}^{+}}$

Set = Соловай-Китаев( ) ${\displaystyle V_{n-1}}$ ${\displaystyle V,n-1}$

Set = Соловай-Китаев( ) ${\displaystyle W_{n-1}}$ ${\displaystyle W,n-1}$

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

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

функция Соловая-Китаева(Ворота , глубина ) ${\displaystyle U}$ ${\displaystyle n}$

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

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

если ( == 0) ${\displaystyle n}$

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

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

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

еще

Set = Соловай-Китаев( , ) ${\displaystyle U_{n-1}}$ ${\displaystyle U}$ ${\displaystyle n-1}$

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

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

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

Set = GC-Decompose( ) ${\displaystyle V,W}$ ${\displaystyle UU_{n-1}^{+}}$

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

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

Set = Соловай-Китаев( ) ${\displaystyle V_{n-1}}$ ${\displaystyle V,n-1}$

Set = Соловай-Китаев( ) ${\displaystyle W_{n-1}}$ ${\displaystyle W,n-1}$

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

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

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

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

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

Рекомендации

1. Китаев, А Ю (1997-12-31). «Квантовые вычисления: алгоритмы и коррекция ошибок». Российские математические обзоры . 52 (6): 1191–1249. Бибкод :1997РуМаС..52.1191К. doi : 10.1070/rm1997v052n06abeh002155. ISSN  0036-0279. S2CID  250816585.
2. Китаев, Алексей Ю.; Шен, Александр; Вялый, Михаил Н. (2002). Классические и квантовые вычисления. Провиденс, Род-Айленд: Американское математическое общество. ISBN 0-8218-2161-Х. ОСЛК  48965167.
3. Доусон, Кристофер М.; Нильсен, Майкл (1 января 2006 г.). «Алгоритм Соловая-Китаева». Квантовая информация и вычисления . 6 : 81–95. arXiv : Quant-ph/0505030 . дои : 10.26421/QIC6.1-6.
4. Нильсен, Майкл А.; Чуанг, Исаак Л. (2010). «Теорема Соловея – Китаева». Квантовые вычисления и квантовая информация: издание к 10-летию. стр. 617–624. дои : 10.1017/cbo9780511976667.019. ISBN 9780511976667. Проверено 20 мая 2020 г.
5. Буланд, Адам; Джургика-Тирон, Тюдор (03 декабря 2021 г.), Эффективная универсальная квантовая компиляция: необратимый алгоритм Соловея-Китаева , arXiv : 2112.02040
6. Куперберг, Грег (22 июня 2023 г.), «Преодоление кубического барьера в алгоритме Соловея-Китаева», arXiv : 2306.13158 [quant-ph]
7. Росс, Нил Дж.; Селинджер, Питер. «Оптимальное безвспомогательное приближение Клиффорда + Т z-поворотов». Квантовая информация и вычисления . 16 (11–12): 901–953. arXiv : 1403.2975 . дои : 10.26421/QIC16.11-12-1.
8. Китаев, Ю. «Квантовые вычисления: алгоритмы и коррекция ошибок».
9. Нильсен, Чуанг, Массачусетс, Иллинойс «Квантовые вычисления и квантовая информация (Издательство Кембриджского университета, 2000), Приложение 3, стр. 617–624». {{cite web}}: Отсутствует или пусто |url=( помощь )CS1 maint: multiple names: authors list (link)
10. КРИСТОФЕР М. ДОУСОН, МАЙКЛ А. НИЛЬСЕН. «АЛГОРИТМ СОЛОВАЯ-КИТАЕВА».