А.С. Холево - Введение в квантовую теорию информации, страница 8
Описание файла
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) + δ) чтобы закодировать всеδ-типичные слова и отбрасывая не-типичные (или кодируя их одним и темже добавочным символом). Вероятность ошибки при таком кодированиибудет меньше или равна ².