М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 179
Текст из файла (страница 179)
е. быть только полилогарифмически ббльшим, чем в исходном алгоритме. Для многих задач такое полилогарифмическое усложнение вполне приемлемо, тогда как полиномиальный рост, присутствующий в эвристическом доказательстве в гл. 4, гораздо менее желателен. Чтобы сформулировать теорему Соловея-Китаева более точно, следует ввести несколько обозначений. Напомним, что ЯУ(2) — это множество всех действующих на одиночный кубит унитарных матриц с равным единице детерминэнтом.
Мы сфокусируем внимание на ЯУ(2), поскольку все элементы на одном кубвте могут быть записаны в виде произведения элемента из Я7(2) на несущественный общий фазовый множитель. Пусть и — конечный набор элементов из ЯУ(2); и играет роль конечного набора базисных элементов, который использует программист для имитации всех остальных элементов при создании квантового компьютера. Для определенности будем считать, что м содержит устойчивое к ошибкам множество (Н, Я, Т), причем мы провели умножение на подходящую общую фазу, чтобы обеспечить равенство детерминантов единице.
Для удобства будем считать, что и содержитп элемеитм, обратные входящим е него элемеигпам, т. е. если У Е и', то У1 Е Ц. В случае множества, устойчивого к ошибкам, это означает добавление к множеству элементов У = Яэ и Т1 = Тт, которые, по удачному стечению обстоятельств, выражаются через уже входящие в это множество элементы.
Словам длиной 1 из и' называется произведение дауда...д~ Е оУ(2), где д; Е и для любого 1. Множество всех слов длиной не больше 1 обозначим Я, а множество всех слов конечной длины через (и). Нам понадобится понятие расс«вояиия для количественной характеристики того, что мы понимаем под выражением «приближение к унитарной матрицам Конкретный вид метрики не так уж важен. Для наших целей удобно использовать следовую метрику, описанную в гл. 9: Н(У, И) ке Фг ~У вЂ” У~, где ~Х~ ьз ~/Х~Х вЂ” положительный квадратный корень из Х"Х.
На самом деле, данное определение отличается множителем 2 от определения в гл. 9; причина для использования в данном приложении другой нормировки заключается в том, что, как будет показано ниже, это облегчаег геометрическую интерпретацию доказательства теоремы Соловея-Китаева (также полезно представлять себе элементы множества ЯУ(2) как точки в пространстве). Подмножество Я во множестве ЯУ(2) называется плов«нь«м в ЯУ(2), если для любого элемента У Е ЯУ(2) и е > 0 существует такой элемент э Е Я, что Р(е, У) ( е. Предположим, Я и И~ — подмножества в ЯУ(2). Тогда говорят, что Я образует е-сеть в И" (где е > 0), если любая точка из И~ находится на расстоянии Приложение 3.
Теорема Соловея-Китаева 751 не больше з от некоторой точки из Я. Нас интересует, насколько быстро Д «заполняет» ЯУ(2) при возрастании 1. Другими словами, для сколь малого е множество Я образует е-сеть в ЯУ(2)? Теорема Соловея-Китаева гласит, что е уменьшается с ростом 1 очень быстро. упражнение П3.1. В гл. 4 было введено понятие расстояния Е(У,'»') = шах~,»1 ~((У вЂ” г'))ф) )~, где максимум берется по всем чистым состояниям (ф). Покажите, что когда У и У являются поворотами кубита, У = В;„(д) и У = Яа(<р), то выполняется равенство Р(У, У) = 2Е(У, 1/), т.
е. неважно, используем ли мы в теореме Соловея-Китаева расстояние Е(ч ) или следовую метрику. Теорема П3.1 (Соловея — Китаева). Пусть и — конечное множество элементов из ЯУ(2), содержащее обратные ко всем своим элементам, а множество (м) плотно в ЯУ(2). Пусть задано число е > О. Тогда множество Я является е-сетью в ЯУ(2) при 1 = 0(1о3'(1/е)), где с я~ 4. Как отмечалось вьппе, наилучшее возможное значение с немного меньше 4, однако нам удобней привести доказательство для этого частного случая. В задаче П3.1 мы объясним, как можно модифицировать доказательство, чтобы использовать меньшие значения с.
Первая часть доказательства состоит в демонстрации того, что точки множества Д образуют довольно плотное множество в окрестности единичной матрицы Х при увеличении 1 (это утверждение содержится в следующей лемме). Чтобы сформулировать лемму, обозначим через Я«множество всех таких точек У в ЯУ(2), что Р(У, Х) < и Лемма П3.2. Пусть и — конечное множество элементов из ЯУ(2), содержащее обратные ко всем своим элементам и такое, что множество (и) плотно в ЯУ(2). Тогда существует такая универсальная константа зс, не зависящая от й, что для любого е < зо выполняется следующее утверждение: если Д— е -сеть для Я„то 0и является Сз -сетью для Я,~о«»д, где С вЂ” константа.
3 з Приведем краткое доказательство леммы П3.2, однако сначала посмотрим, как нз нее следует теорема Соловея-Китаева. Доказательство состоит нз двух шагов. Первый заключается в итеративном применении леммы П3.2, что позволит показать, что окрестность начала координат быстро заполняется с увеличением длины слова 1.
Поскольку множество (и) плотно в ЯУ(2), можно найти такое 1с, что множество й, является езс-сетью для ЯУ(2), а следовательно и для Я„. Применение леммы П3.2 при е = ее и 1 = 1с демонстрирует, что множество мя» является Сгоз-сетью для Я~о«»у».
Повторное применение леммы П3.2 при е = ~/Сес и 1 = Ыс показывает, что множество Дз»~, есть з/з С(ч Сев ) -сеть для 5~~1 Х вЂ”,»л>»но Повторив процесс й раз, мы обнаружим, г- з/з з что множество Дз»~, является з(й) -сетью для Я,1»1, где ) 1з?з1' е(й) = (П3.1) Вез ограничения общности можно считать, что число ес было выбрано таким образом, что Сзс < 1, а следовательно, с(й) очень быстро стремится к нулю при росте й. Также полезно отметить, что если ес выбрано достаточно малым, то с(й) < з(й+ 1). 752 Приложение 3.
Теорема Соловея — Китаева Рис. П3.1. Шаг переноса, применяемый в доказательстве теоремы Соловел-Китаева. Чтобы приблизить произвольный элемент, в начале нужно построить приближение с точностью е(0)э с использованием!о элементов иэ й Потом следует улучшить приближение, добавив б1п дополнительных элементов, чтобы достичь точность лучше е(й)э; и затем продолжать дальше этот быстро сходящийся к 1т процесс Таким образом, для приближения любого унитарного элемента У с точностью с()с) можно использовать последовательность из 1с+Яе+ ° +5~1о < ~~5~1е элементов.
Чтобы построить приближение с некоторой требуемой точностью с, необходимо выбрать такое Й, что с()с) < с. (П3.2) Подставляя сюда формулу (П3.1) можно получить следующее неравенство: < 3 ~ " 1ОК(1/Сэс) 2 ) 2 1ой(1/Ссо) (ПЗ.З) Перейдем ко второму шагу. Выберем произвольный элемент У из ЯУ(2) и, используя идею переноса, проиллюстрированную на рис. П3.1, аппроксимируем У с помощью элементов из Д. ПУсть Уе Е Да есть с(0)з-пРиближение к У.
Теперь определим У таким образом, что УУе = У, т. е. У = УУе. Следовательно, Р(У 1) = бг )У вЂ” 1! = бг ~(У вЂ” Ус) Уе)) = $г )У вЂ” Уе) < е(0)з < с(1). С помощью обсуждавшегося выше итерационного применения леммы П3.2 можно найти элемент Уэ Е А~о, который является е(1)з-приближением к У. Отсюда следует, что Уэ Уе есть е(1)з-приближение к У.
Теперь определим У' так, что У'УтУс = У, т. е. У' ьи УУе)У~). Тогда РЯ',1) = сг)У вЂ” 1~ = ьг((У вЂ” УэУс)УеюУ~т( = сг (У вЂ” УдУс) < е(1)з < с(2). Из итерационного применения леммы П3.2 следует, что можно найти такое Уэ Е Дээ~„которое является е(2)~-приближением к Г, а следовательно, УэУтУе — это с(2)э-приближение к У. Продолжая действовать подобным путем, можно построить такой элемент Уз е Дэь~ш что УзУа э...
Уе есть е()с)э-приближение к У. Приложение 3. Теорема Соловея-Китаева 753 Отсюда следует, что для приближения с точностью в требуется Ф' элементов, где 4 4 1 2 4 2 1о8(1/Сго) [П У] = (7УП1У1 (П3.5) Предположим, что оба элемента 17 и У близки к единице, т. е. могут быть записаны в виде П = е ьа и У = е 'в, где А и  — такие эрмитовы матрицы, что гг [А[, гг ]В] ( в для некоторого малого в. Разложение еьгл и е+'в в ряд с точностью до квадратичных по А и В членов дает Р([у у] е-(л,в1) 0(вз) (П3.6) где [А, В] = А — ВА — обычный коммутатор матриц (в действительности коммутатор для алгебры Ли ЯП(2)).
Таким образом, в окрестности единицы можно изучать групповой коммутатор, исследуя свойства гораздо более простого коммутатора матриц. В самом деле, для кубитов коммутатор матриц имеет особенно красивую форму. Произвольный элемент из ЯУ(2) может быть записан в риде П = и(а) ш ехр( — 1а ° о/2) для некоторого вектора а с действительными компонентами. Аналогично У = в(Ь) = ехр( — 45 У/2) для некоторого вектора Ь над полем действительных чисел.
Напомним (см. упр. 2.40), что [а о, Ь о] = 21(а х Ь) о, (ПЗ. 7) поэтому из (П3.6) можно заключить, что РЩУ]яр,и(а х Ь)) = 0(в~). (П3.8) Теперь легко понять основную идею доказательства леммы П3.2. Ниже для полноты картины приводятся детали, связанные в основном с оценками приближений. Сейчас мы объясним только основную идею, которая проиллюстрирована на рис. П3.2. Допустим, мы хотим аппроксимировать элемент 17 = и(х) в Яы.
Из упр. П3.4 можно видеть, что следовые метрики вида Р(Ц1) равны (с точностью до небольших поправок) евклидову расстоянию []х[[, поэтому здесь с = 1оя 5/1о8(3/2) ю 4. Таким образом, для приближения с точностью г требуется О(!оя'(1/в)) элементов, т. е. доказательство теоремы Соловея-Китаева завершено. Для доказательства леммы П3.2 используются несколько элементарных фактов об умножении элементов группы ЯУ(2), которые мы сейчас приведем, Основнэл идея леммы заключается в работе в окрестности единицы, что сильно упрощает довольно сложные операции умножения в ЯУ(2). Уточним сказанное.
Пусть У и У вЂ” элементы группы ЯУ(2), определим групповой каммргпагпор этих элементов С помощью следующей формулы: 754 Приложение 3. Теорема Соловея — Китаева для хорошего приближения выполняется неравенство [[У[[ < с~. Всегда можно выбрать такие 17 и У длиной не более с, что У = у х У. Выберем 17с и Уе таким образом, что элементы п(ур) и и(Ус) принадлежат множествам Дп которые соответственно «сз-приближают» иЯ и п(У). Применив формулу (П3.6) к коммутатору [п(йо Ус)[вр получим 0(с )-приближение к У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
