Главная » Просмотр файлов » М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация

М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 179

Файл №1156771 М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация) 179 страницаМ. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771) страница 1792019-09-18СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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(с )-приближение к У.

Характеристики

Тип файла
DJVU-файл
Размер
11,78 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее