Теорема Соловая – Китаева. - Solovay–Kitaev theorem - Wikipedia

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

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

Заявление

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

Количественные оценки

Постоянная ${\displaystyle c}$ можно сделать ${\displaystyle 3+\delta }$ для любых фиксированных ${\displaystyle \delta >0}$.^[4] Однако существуют определенные наборы вентилей, для которых мы можем взять ${\displaystyle c=1}$, что делает длину последовательности ворот плотной до постоянного множителя.^[5]

Доказательство идеи

Доказательство теоремы Соловея-Китаева проводится путем рекурсивного построения последовательности вентилей, дающей все более хорошие приближения к ${\displaystyle U\in \operatorname {SU} (2)}$.^[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}=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. Китаев, А Ю (1997-12-31). «Квантовые вычисления: алгоритмы и исправление ошибок». Российские математические обзоры. 52 (6): 1191–1249. Дои:10.1070 / rm1997v052n06abeh002155. ISSN  0036-0279.
2. Доусон, Кристофер М .; Нильсен, Майкл (01.01.2006). «Алгоритм Соловая-Китаева». Квантовая информация и вычисления. arXiv:Quant-ph / 0505030.
3. Nielsen, Michael A .; Чуанг, Исаак Л. (2010). «Теорема Соловая – Китаева». Квантовые вычисления и квантовая информация: 10-летие издания. Дои:10.1017 / cbo9780511976667.019. Получено 2020-05-20.
4. Китаев Алексей Ю .; Шен, Александр; Вялый, Михаил Н. (2002). Классические и квантовые вычисления. Провиденс, Род-Айленд: Американское математическое общество. ISBN  0-8218-2161-X. OCLC  48965167.
5. Харроу, Арам В .; Рехт, Бенджамин; Чуанг, Исаак Л. (20 августа 2002 г.). «Эффективные дискретные приближения квантовых вентилей». Журнал математической физики. 43 (9): 4445–4451. arXiv:Quant-ph / 0111031. Дои:10.1063/1.1495899. ISSN  0022-2488.