Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » А.С. Холево - Введение в квантовую теорию информации

А.С. Холево - Введение в квантовую теорию информации, страница 8

PDF-файл А.С. Холево - Введение в квантовую теорию информации, страница 8 Квантовые вычисления (53189): Книга - 7 семестрА.С. Холево - Введение в квантовую теорию информации: Квантовые вычисления - PDF, страница 8 (53189) - СтудИзба2019-09-18СтудИзба

Описание файла

PDF-файл из архива "А.С. Холево - Введение в квантовую теорию информации", который расположен в категории "". Всё это находится в предмете "квантовые вычисления" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 8 страницы из PDF

. .i −→xx42Глава 3. ПРИМЕНЕНИЯ СЦЕПЛЕННЫХ СОСТОЯНИЙ3. Вновь применяя операцию Адамара, получаем вектор состояния1 X X(−1)x·y |yi ⊗ |f (x)i.2nx∈Bn y∈Bn4. Поскольку ξ 6= 0, отображение f принимает 2n−1 разных значений.Измеряя оба регистра, получаем 2n−1 разных исходов (y, f (x)) с вероятностьюµ ¶21[(−1)x·y + (−1)(x+ξ)·y ]2 ,2nравной 2−(2n−2) , если y · ξ = 0, и 0 в противном случае.Таким образом, получается случайный равномерно распределенныйвектор y(ω) из булевой “гиперплоскости ” y · ξ = 0.

Если повторить этупроцедуру n − 1 раз, то с положительной вероятностью полученныевекторы будут линейно независимы, что позволяет найти вектор ξ.Л е м м а 1. Пусть y1 (ω), . . . , yn−1 (ω) вероятностно независимые, равномерно распределенные случайные векторы из гиперплоскости y · ξ = 0.ТогдаP{y1 (ω), . . . , yn−1 (ω) } ≥ e−1 .Доказательство. Вектор y(ω) принимает 2n−1 равновероятных значений. Если y1 (ω), .

. . , yk−1 (ω) линейно независимы, то имеется 2k−1 их различных линейных комбинаций. Поэтому получаем следующие значения условных вероятностейP{yk (ω) линейно независим от y1 (ω), . . . , yk−1 (ω)|y1 (ω), . . . , yk−1 (ω)линейно независимы} ==2n−1 − 2k−11= 1 − n−k .n−122ТогдаP{y1 (ω), . . . , yk (ω) линейно независимы}= P{yk (ω) линейно независим от y1 (ω), . . . , yk−1 (ω);µ= 1−12n−k¶y1 (ω), . .

. , yk−1 (ω) линейно независимы}P{y1 (ω), . . . , yk−1 (ω) линейно независимы}.СледовательноP{y1 (ω), . . . , yn−1 (ω) линейно независимы}¶µ¶µ11= 1 − n−1 . . . 1 −22"n−1 µ#" n−1 #¶X 1X1= exp≥ exp −≥ e−1 .ln 1 − k22kk=1k=13.4. КВАНТОВЫЕ АЛГОРИТМЫ435) Повторяем всю процедуру m раз, где (1 − e−1 )m ≤ ε. Тогда с вероятностью 1 − ε получим по крайней мере n − 1 линейно независимыхбулевых векторов, ортогональных ξ, а значит, и сам вектор ξ.Квантовый алгоритм требует лишь O(n) применений оператора Uf вместо O(2n/2 ) вычислений значения f для классического алгоритма. За счетчего достигается такое радикальное ускорение? Очевидно, за счет того, чтооднократное применение оператора Uf дает состояние, которое в латентной форме содержит все значения функции f , и из которого интересующаянас информация может быть извлечена посредством квантового измерения.

Такой прием называют “квантовым параллелизмом”. Важно, однако,подчеркнуть, что в отличие от параллелизма в классическом компьютинге,речь отнюдь не идет об одновременном вычислении всех значений функции.3.4.2Замечания об алгоритме ШораАлгоритм, предложенный Шором в 1994 г., эффективно решает задачу нахождения множителя большого натурального числа N ∼ 2n . Задача факторизации — разложения на множители — одна из фундаментальных проблем математики, имеющая далеко не только академический интерес: трудность решения этой задачи лежит в основе надежности криптографии с открытым ключом.

Наилучший из известных в настоящее время алгоритмов1/32/3имеет экспоненциальную сложность O(2cn log n ). Есть (но не доказано)предположение, что полиномиальное решение этой задачи не существует.Квантовый алгоритм Шора имеет полиномиальную сложностьO(n2 log n log log n). Представление о его эффективности дает следующаягрубая оценка: задача факторизации числа N ∼ 2800 не решаема за разумное время на классическом компьютере, тогда как применение квантового алгоритма при тактовой частоте 1 Мгц потребовало бы пару дней. Алгоритм использует сведение задачи факторизации к нахождению периодафункции f (x) = ax (mod N ), где a выбирается случайным образом.

Можно показать, что в большинстве случаев период r является четным и числоar/2 ±1 имеет общий множитель с N , который находится с помощью классического алгоритма Евклида. Алгоритм Шора включает детальное описаниеэффективного выполнения операции Uf . Нахождение периода f (x) использует квантовую модификацию быстрого преобразования Фурье (роль которого в более простой задаче Саймона выполняло преобразование АдамараHn ). Подробнее об алгоритме Шора и квантовых вычислениях см. в [5, 2].3.4.3Алгоритм ГровераЭтот алгоритм решает задачу поиска. Более точно, предполагается, чтозадана булева функция F : B n → B, такая что F (x0 ) = 1, F (x) = 0,x 6= x0 . Требуется найти x0 , причем вычисление значения функции F влюбой заданной точке принимается за один шаг. Классический алгоритмсводится к перебору значений x и проверки для них равенства F (x) = 1,44Глава 3.

ПРИМЕНЕНИЯ СЦЕПЛЕННЫХ СОСТОЯНИЙчто в наименее благоприятном случае требует N ∼√2n шагов. Квантовыйалгоритм Гровера позволяет решить задачу за ≈ N = 2n/2 шагов, приэтом решение носит вероятностный характер.Предполагается, что в гильбертовом пространстве, натянутом на базис|xi, x ∈ B n , задан “оракул” – унитарный оператор UF , такой чтоUF |xi = |xi, x 6= x0 ,UF |x0 i = −|x0 i.Введем обозначения|x̄0 i = √X1|xi,N − 1 x6=x01θ0 = arcsin √ .NАлгоритм состоит из следующих шагов:1. К основному состоянию применяется операция Адамара1 XHn√|0i −→|xi = |ψ (θ0 )i,N xгде введено обозначение|ψ(θ)i = sin θ|x0 i + cos θ|x̄0 i.Эта операция переводит вектор |0i в вектор, лежащий в плоскости,натянутой на базис |x0 i, |x̄0 i.2.

К полученному состоянию применяется унитарный операторU = Hn JHn UF , где J — оператор, действующий по формулам J|0 . . . 0i =|0 . . . 0i, J|xi = −|xi, x 6= 0.З а д а ч а 13. Проверьте, чтоU |ψ(θ)i = |ψ(θ + ϕ)i,где√N −1,Nт. е. U осуществляет поворот на угол ϕ в плоскости, натянутой на натянутойна базис |x0 i, |x̄0 i.√После применения оператора U m раз, где m ≈ (π/4) N , конечное состояние |ψ(θm )i, θm = θ0 + mϕ ≈ π/2 становится очень близким к искомому:|ψ(θm )i ≈ |x0 i, причем тем ближе, чем больше N .В этом алгоритме квантовый параллелизм проявляется в том, что вычисления функции F в отдельных точках заменяются действием унитарного оператора UF на суперпозицию базисных состояний, что и позволяетдостичь полиномиального ускорения.sin ϕ = 2Глава 4Классически-квантовыеканалы4.14.1.1Основные понятия классической теории информацииЭнтропия и сжатие данныхПусть X дискретная случайная величина, принимающая значения в конечном множестве X = {1, .

. . , |X |}, и имеющая распределение вероятностейp{px }, так что значение x ∈ X появляется с вероятностью px . Энтропияслучайной величины X определяется соотношениемXH(X) = −px log px ,(4.1)x∈Xс соглашением 0 log 0 = 0 (далее log, как правило, обозначает двоичныйлогарифм).З а д а ч а 14. 0 ≤ H(X) ≤ log |X |, причем минимальное значение принимается на вырожденных распределениях, а максимальное — на равномерном.Обычно H(X) интерпретируется как мера неопределенности, изменчивости или информационного содержания случайной величины X.

Пояснимпоследнее утверждение.Рассмотрим случайный источник, который порождает последовательность независимых одинаково распределенных случайных величин с распределением p. Последовательность w = (x1 , . . . , xn ) букв алфавита X называется словом длины n.

Общее количество таких слов |X |n = 2n log |X | .Поэтому можно закодировать все эти слова, используя двоичные последовательности длины n log |X |, т.e. n log |X | бит. Однако, используя то обстоятельство, что p в общем случае не-равномерное распределение, можно4546Глава 4. КЛАССИЧЕСКИ-КВАНТОВЫЕ КАНАЛЫпредложить лучший способ кодирования. Возможность сжатия данных тесно связана со свойством асимптотической равнораспределенности, котороеявляется прямым следствием закона больших чисел:Т е о р е м а 11. Если X1 , . . . , Xn , .

. . независимые и одинаково распределенные случайные величины с распределением p = {px }, тоn−1Xlog pxi −→ H(X)n i=1по вероятности.(4.2)Таким образом, для любых δ, ² > 0 найдется n0 , такое что для всехn ≥ n0 имеет место½¯¾n¯¯ 1X¯P ¯−log pxi − H(X)¯ < δ > 1 − ².n i=1(4.3)Замечая, что вероятность появления слова w = (x1 , . . . , xn ) равна¡pw = px1 · . .

. · pxn = 2−n1−nPni=1¢log pxi(4.4)мы теперь можем использовать соотношение (4.3) чтобы ввести понятие типичного слова: cлово w, имеющее вероятность pw , называется δ-типичным,если2−n(H(X)+δ) < pw < 2−n(H(X)−δ) .(4.5)Непосредственнослов:устанавливаютсяследующиесвойстватипичных1. Существует не более 2n(H(X)+δ) типичных слов.2.

Для достаточно больших n существует, по крайней мере,(1 − ²)2n(H(X)−δ) типичных слов.3. Множество не-типичных слов имеет вероятность ≤ ².Теперь можно осуществить эффективное сжатие данных, используя вседвоичные последовательности длины n(H(X) + δ) чтобы закодировать всеδ-типичные слова и отбрасывая не-типичные (или кодируя их одним и темже добавочным символом). Вероятность ошибки при таком кодированиибудет меньше или равна ².

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