М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 180
Текст из файла (страница 180)
'1аким образом, построена 0(бз)-сеть для Я,з; для завершения доказательства леммы следует применить шаг переноса, аналогичный использованному в основной части доказательства теоремы Соловея-Китаева, что дает 0(сз)-приближение к лю- бомУ элементУ из ЯО<,агз> с помоЩью 51 элементов. Рис. П3.2. Основная идея доказательства леммы ПЗ 2 За счет взятия групповых коммутаторов элементов Уг и Уз в Я, можно заполнить Я«з гораздо плотнее Обратите внимание на то,.что плотность кругов, возникающих в правой части рисунка, должна быть гораздо выше, чем зто показано, поскольку для каждой пары кругов в левой части рисунка должен появиться один справа; меньшая плотность используется здесь исключительно для удобства восприятия.
Доказательство леммы завершается применением шага переноса (который на рисунке не показан) для получения хорошего приближения к произвольному элементу из Янгмзгз. 'Упражнение ПЗ.2. Пусть А и  — такие эрмитовы матрицы, что сг[А[, 1г [В[ < с. Докажите, что для любого достаточно малого с выполняется неравенство (П3.9) Р ~[ -«А -«В~ -[А,В[) ~ 4 3 (здесь Н вЂ” константа), вз которого следует формула (П3.6).
(Замечание: для практических целей интересно получить достаточно жесткую оценку величи- ны Н.) 'Упражнение ПЗ.З. Пусть У и 17 — векторы с действительными компонента- ми. Покажите, что Р(и(У), и(у)) = 2т/2 1 — соз(х/2) соз(у/2) — зш(х/2) эш(у/2)х ° у, (П3.10) где х ж [[х[[, р гн [[у~[; х и р — единичные векторы соответственно в направлении векторов х и у. 'Упражнение ПЗ.4. Покажите, что если у = О, то формула для Р(и(У), и(Д) упрощается и принимает вид Р(п(У)г1) = 4в1пн. (П3.11) Приложение 3.
Теорема Соловея-Китаева 755 Упражнение П3.5. Покажите, что если х, у < е, то Р(и(х),и(у)) = [[х — у1]+0(ез). (П3.12) Доиазанзелъснзео (леммы П3.2). Пусть Д является е~-сетью в Я,. Первый шаг доказательства состоит в демонстрации того факта, что [й, й]зр есть Сез-сеть для множества Я,з и некоторой константы С. Пусть У е Я,ю Выберем такой вектор х, что У = и(х). Согласно упр. П3.4, х ( ег + 0(ее). Выберем такую пару векторов у и у длиной не более е+ 0(ез), что х = у х У. Поскольку Я является ег-сетью для Я„можно взять такие У1 и Уг из Й П Я~, что Р(Уми(у)) < о~+0(е~), Р(Уг, и(з)) < з + О(е ).
(П3.13) (П3.14) Выберем такие векторы уо и Уо, что У1 = и(уо) и Уг = и(Уо). Из упр. П3.4 следу- ет, что уо, го < о+0(ез). Наша задача — показать, что величина Р(У, [Уг, Уг]зр) меньше, чем Се~. Воспользуемся неравенством треугольника: Р(У1 [Уг Уг]зр) ( Р(У, и(Уо х Уо)) + Р(и(Уо х зо) [Ум Уг]з ) (ПЗ 15) Второй член не превьппает величины Уез (см. упр. П3.2), где 4' — константа, немного большая Ы, из-за возможного вклада, связанного с неравенством уо, зо < е+ 0(е') (вместо уш зо < е). Подставив У = и(х), используя результат упр.
П3.5, введя подходящую константу 4э и проведя элементарные алгебраические преобразования, можно увидеть, что Р(и(х),и(уо х зо)) + й'е (П3.16) []х — уо х Уо][+ 4эез (П3.17) []у х У вЂ” уо х Уо][+ 1"е' (П3.18) ][[(у — уо) + уо] х [(у — уо) + зо] — уо х 4[[+ с(эез (ПЗ.19) ( (э+ 2) 3+ 0(,4) (П3.20) Сз (П3.21) Р(У, [Ум Уг]зр) ( Р([И;,И;]„У;У) < С", (П3.22) что завершает доказательство.
где С вЂ” константа, выбранная подходящим обрезом. Второй этап доказательства леммы состоит в применении шага переноса, аналогичного использованному в основной части доказательства тесремы Соловея-Китаева. Говоря конкретнее, если задан элемент У Е Я,~Уз, то можно найти такой элемент И из Й, что Р(У, р') < е~, а следовательно, УУ1 б Я,~, После этого можно отыскать И~г и И1г из д, так что Р([1ум руг]зр, уИ1) ( Сез, а следовательно, 756 Приложение 3.
Теорема Соловея — Китаева Ъгпражнение П3.6. Зафиксировав множество и базисных элементов, опишите алгоритм, который по заданному описанию унитарного оператора У на одном кубите и требуемой точности е ) 0 эффективным образом вьгчисляет последовательность элементов из м, которая аппроксимирует У с точностью ю Анализ в этом приложении является достаточно грубым, можно было бы провести более тонкое исследование. Особый интерес представляет, например, вопрос о наилучшем из возможных показателей степени с в оценке О(1оя'(1/с) ) .
Несложно убедиться в том, что с не может быть меньше единицы. Чтобы понять это, представьте, что в ЯУ(2) взято Ф маленьких шаров радиуса ю Суммарный объем этих шаров имеет порядок с с некоторой (несущественной в данном рассмотрении) константой д. Таким образом, если шары должны покрывать все пространство ЯУ(2), то число Ф должно быть порядка П(1/сс). Предположим, выбраны все возможные последовательности У~ Уз...
Ую состоящие из д элементов, взятых из и'. Очевидно, что зта последовательность может породить не больше [м[э различных унитарных операций. Таким образом, должна выполняться оценка [и'[э = Й(1/е ), отсюда нижняя оценка на количество элементов выглядит как д=й 1оя (П3.23) Задача П3.1. Данная задача описывает усовершенствованную конструкцию, которая дает оценку 0(1об~(1/с) 1об'(1об(1/с))) на количество элементов для приближения требуемого элемента с точностью е (при произвольной константе с, большей двойки). 1.
Пусть Л( — 5-сеть в Я„причем 0 < Б < с < сс, где сс — достаточно малое число. Покажите, что [Л/,Л() р — Ий-сеть в Я,а (где а — некоторая константа). 2. Пусть Я вЂ” Б-сеть в Я„причем 0 < Б < с < сс, Покажите, что Д~м есть сьссэ ~-сеть в я,, 3. Определим число й формулой 1об(1/с) (П3.24) (здесь квадратные скобки означают взятие целой части действительного числа) и будем считать, что можно найти такое 1, что 0~ — Бс-сеть в Я„, где а"сс = сс.
(П3.25) ПокажнтВ~ что Д4м е сеть в Я ра Еор 4. С использованием уже доказанной версии теоремы Соловея-Китаева покажите, что 1 = О(й') подходит для предыдущего пункта (здесь с = Приложение 3. Теорема Соловея-Китаева 757 !ой 5/ !ой(3/2) — константа, появляющаяся в показателе степени в уже до- казанной версии теоремы Соловея-Китаева). 5. Соедините вместе предыдущие утверждения, чтобы доказать, что с помощью О(!ой (1/е) !ой'(1/е))) элементов можно построить е-приближение к любому элементу из Я!7(2).
6. Покажите, что в предыдущем пункте подойдет любая константа с > 2. Задача П3.2 (исследование). Найдите (если она существует) асимптотически более быструю процедуру приближения, чем в предыдущей задаче. В идеале — найдите процедуру, для которой 1. достигается нижняя оценка Й(!оя(1/е) ) на количество элементов для выполнения приближения; 2. получается эффективный алгоритм для построения таких приближающих последовательностей элементов. Задача ПЗ.З (исследование).
Зафиксируйте конечное множество Д элементов на одном кубите, которые можно выполнить устойчивым к ошибкам образом и которые порождают множество, плотное во множестве элементов на одном кубите; например, (я/8)-оператор и оператор Адамара. Разработайте элегантный, аффективный и достаточно компактный метод, который по произвольному элементу У на одном кубите и некоторому числу е > 0 вьщает последовательность элементов из устойчивого к ошибкам набора, дающую е-приближение к (7 (с точностью до общего фазового множителя). История и дополнительная литература Результаты этого приложения были доквзелы Соловеем в 1995 г.
(неопубликованная работа) и независимо Китаевым, который схематично изложил доказательство в работе !213!. Кроме того, Китаев заметил, что результат может быть обобщен на многие группы Ли, отличные от Я!7(2); главное использовавшееся в доказательстве свойство группы ЯУ(2) — это утверждение, что [Я... Яер 2 Яп!,з!, поэтому для других групп Ли, обладающих таким же свойством, тоже выполняется некоторый аналог теоремы Соловея-Китаева. Например, эта теорема верна для группы Ли ЯУ(а) — группы унитарных матриц размера И х а с единичным детерминантом. После знакомства с этим фактом Соловей впоследствии обобщил свое доказательство сходным образом. Наше изложение данного материала существенно выиграло от лекции Фридмана, прочитанной в 1999 г., а также от обсуждений с Фридманом, Китаевым и Соловеем.
Приложение 4 ТЕОРИЯ ЧИСЕЛ Для понимания криптографических систем и способов их «взлома» с помощью квантовых компьютеров необходимо знание элементарной теории чисел. В этом приложении приводится обзор некоторых основных утверждений теории чисел. П4.1 Начальные сведения Введем некоторые обозначения. Множеством целых чисел называется множество 1..., — 2, — 1, О, 1, 2,...) (для него используется обозначение Е). Иногда мы будем использовать термин натрральнме числа, имея в виду неотрицательные целые числа, но чаще мы будем употреблять понятия неотрицательные целые или положительные целые числа, чтобы подчеркнуть различие между множеством, включающим нуль, и множеством, не содержащим нуля. Пусть и — целое число.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
