ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
+ ψ 2 ψ 1 + ψ 2 ψ 3 P 12 H 123 Рис. 4.1: Квантовые операторы CNOT P 21 и Тоффоли H 123 Трехкубитный оператор - вентиль Тоффоли определяется следующим выражением: H 123 |x,y,zi = |x,y,x&y ⊕ zi , с таблицей истинности 4.5. Зацепленные квантовые состояния 223 Вход Выход |xi |yi |zi |xi |yi |x&y ⊕ zi 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 Пример 4.23. Найти Квантовое состояние |ψi = P 12 |ψ 1 i ⊗ |ψ 2 i и |Φi = P 21 |ψ 1 i ⊗ |ψ 2 i если |ψ 1 i = α |0i + β |1i и |ψ 2 i = β |0i − α |1i . Решение. Найдем результат действия операторов P 12 и P 21 на суперпозицию |ψ 1 i ⊗ |ψ 2 i: |ψ 1 i ⊗ |ψ 2 i = (α |0i + β |1i) ⊗ (β |0i − α |1i) = αβ |00i − α 2 |01i + β 2 |10i − αβ |11i ; P 12 |ψ 1 i ⊗ |ψ 2 i = P 12 αβ |00i − α 2 |01i + β 2 |10i − αβ |11i = αβ |00i − α 2 |01i + β 2 |11i − αβ |10i ; P 21 |ψ 1 i ⊗ |ψ 2 i = P 21 αβ |00i − α 2 |01i + β 2 |10i − αβ |11i = αβ |00i − α 2 |11i + β 2 |10i − αβ |01i . N Задача 4.11. Найти Квантовое состояние |ψi = P 12 |ψ 1 i ⊗ |ψ 2 i и |Φi = P 21 |ψ 1 i ⊗ |ψ 2 i если 1. |ψ 1 i = R π 2 |0i и |ψ 2 i = R π 3 |0i , 2. |ψ 1 i = R π 3 |0i и |ψ 2 i = R π 4 |0i , 3. |ψ 1 i = R π 4 |0i и |ψ 2 i = R π 6 |0i , 4. |ψ 1 i = R π 6 |0i и |ψ 2 i = R π 3 |0i . 224 Глава 4. Квантовая информация 4.6 Квантовые алгоритмы Рассмотрим некоторые квантовые алгоритмы, показывающие особенности, присущие исключительно квантовым вычислениям. Все алгоритмы основаны на использовании запутанных квантовых состояний. Это означает, что действие некоторого оператора на один из кубитов забита автоматически изменяет состояние других членов ансамбля. Возникает квантовый параллелизм - фундаментальное свойство квантовых вычислений, позволяющее за одно обращение к функции f(x) вычислять ее значения при различных аргументах x одновременно. 4.6.1 Алгоритм Дойча Пусть имееются четыре функции f i (x) от двоичной переменной x = 0, 1. Результаты действия функций на переменные показаны в таблице. Вход Выход x f 1 (x) f 2 (x) f 3 (x) f 4 (x) 0 0 1 0 1 1 0 1 1 0 Функции f 1 (x) и f 2 (x) называются "постоянными", поскольку они принимают одинаковое значение независимо от изменения аргумента. Функции f 3 (x) и f 4 (x) называются "сбалансированными". Задача Дойча ставится следующим образом: определить, к какой группе относится данная функция f (постоянной или сбалансированной)? При классическом решении данной задачи мы должны определить отдельно f(0) и f(1), т.е. выполнить два обращения к функции f. Использование квантового параллелизма позволяет решить эту задачу за один проход. Для решения задачи рассмотрим квантовый компьютер, состоящий из двух кубитов |xi и |yi. Функциям f i (x) поставим в соответствие операторы U i : U 1 = 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 , U 2 = 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 , U 3 = 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 , U 4 = 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 Работа компьютера происходит следующим образом. На первом этапе нам необходимо приготовить запутаное состояние квантовых регистров |xi и |yi. Например, создадим 4.6. Квантовые алгоритмы 225 Шредингеровскую пару последовательностью действия операторами Адамара H и CNOT P 12 на нулевые кубиты ψ prep = |xyi = |00i: |00i → P 12 H 1 |00i = P 12 ( |00i + |10i) 1 √ 2 = 1 √ 2 ( |00i + |11i). Аналогично, можно получить Шредингеровскую пару с обратной фазой из состояния ψ prep = |xyi = |10i: |10i → P 12 H 1 |10i = P 12 ( |00i − |10i) 1 √ 2 = 1 √ 2 ( |00i − |11i). Запишем эти состояния выражением ψ in = P 12 H 1 |ψ prep i = P 12 H 1 |x0i = 1 √ 2 ( |00i + (−) x |11i). Вычисления квантового компьютера Дойча осуществляется действием оператором U i на входное состояние |ψ in i. В результате, на выходе мы получим: для ψ prep = |00i U i |ψ in i |ψ out i P 12 |ψ out i H 1 P 12 |ψ out i U 1 1 √ 2 ( |00i + |11i) 1 √ 2 ( |00i + |11i) 1 √ 2 ( |00i + |10i) |00i U 2 1 √ 2 ( |00i + |11i) 1 √ 2 ( |11i + |00i) 1 √ 2 ( |10i + |00i) |00i U 3 1 √ 2 ( |00i + |11i) 1 √ 2 ( |10i + |01i) 1 √ 2 ( |11i + |01i) |01i U 4 1 √ 2 ( |00i + |11i) 1 √ 2 ( |01i + |10i) 1 √ 2 ( |01i + |11i) |01i 226 Глава 4. Квантовая информация для ψ prep = |10i U i |ψ in i |ψ out i P 12 |ψ out i H 1 P 12 |ψ out i U 1 1 √ 2 ( |00i − |11i) 1 √ 2 ( |00i − |11i) 1 √ 2 ( |00i − |10i) |10i U 2 1 √ 2 ( |00i − |11i) 1 √ 2 ( |11i + |00i) 1 √ 2 ( |10i − |00i) − |10i U 3 1 √ 2 ( |00i − |11i) 1 √ 2 ( |10i + |01i) 1 √ 2 ( |11i − |01i) − |11i U 4 1 √ 2 ( |00i − |11i) 1 √ 2 ( |01i + |10i) 1 √ 2 ( |01i − |11i) |11i После распутывания выходных кубитов, их можно измерить. Измерение второго кубита |zi дает решение задачи. Если |zi = |0i, то функция f i принадлежит к первому классу (постоянная), если же |zi = |1i, то функция будет сбалансированной. С учетом фазы результат ψ sol будет иметь вид: ψ sol = (−) (x⊕y)f(x) |xi |zi . Если в качестве запутанного состояния использовать состояние Эйнштейна-Подольского- Розена, которое создается последовательностью действия операторами Адамара H и CNOT P 12 на кубиты |ψ prep i = |xyi = |x1i: ψ in = P 12 H 1 |ψ prep i = P 12 H 1 |x1i = 1 √ 2 ( |01i + (−) x |10i), то на выходе мы получим |ψ out i = U i |ψ in i, а распутанные состояния ψ sol = σ 3 P 12 H 1 ψ out = (−) (x⊕y)f(x) |xi |zi , позволяют определить класс функции измерением второго кубита |zi. 4.6. Квантовые алгоритмы 227 x + 0 + x z P 12 H P 12 H U i Рис. 4.2: Квантовый компьютер Дойча. 4.6.2 Квантовое плотное кодирование Перед процессом кодирования получателю и отправителю информации передается по одной части запутанного кубита (состояние типа Шредингеровского кота): |ψi = 1 √ 2 ( |00i + |11i) . Каждому значению передаваемой последовательности ставится в соответствие однокубитовый оператор I = σ 0 , X = σ x , Y = iσ y , Z = σ z , которым отправитель действует на первый кубит забита. Значение Преобразование Новое состояние 0 ψ 0 = (I ⊗ I) ψ 0 1 √ 2 ( |00i + |11i) 1 ψ 1 = (X ⊗ I) ψ 0 1 √ 2 ( |10i + |01i) 2 ψ 2 = (Y ⊗ I) ψ 0 1 √ 2 ( − |10i + |01i) 3 ψ 3 = (Z ⊗ I) ψ 0 1 √ 2 ( |00i − |11i) Затем получателю по квантовому каналу отправляется первая, преобразованная часть забита.Получатель применяет CNOT операцию к полученному забиту. 228 Глава 4. Квантовая информация Значение Первоначальное C-NOT Первый Второй состояние кубит кубит 0 1 √ 2 ( |00i + |11i) 1 √ 2 ( |00i + |10i) 1 √ 2 ( |0i + |1i) |0i 1 1 √ 2 ( |10i + |01i) 1 √ 2 ( |11i + |01i) 1 √ 2 ( |1i + |0i) |1i 2 1 √ 2 ( − |10i + |01i) 1 √ 2 ( − |11i + |01i) 1 √ 2 ( − |1i + |0i) |1i 3 1 √ 2 ( |00i − |11i) 1 √ 2 ( |00i − |10i) 1 √ 2 ( |0i − |1i) |0i Далее получатель применяет оператор Адамара к первому кубиту H = 1 √ 2 (σ x + σ z ) № Первый C-NOT Первый Второй кубит кубит кубит 0 1 √ 2 ( |0i + |1i) 1 √ 2 1 √ 2 ( |0i + |1i) + 1 √ 2 ( |0i − |1i) |0i |0i 1 1 √ 2 ( |1i + |0i) 1 √ 2 1 √ 2 ( |0i − |1i) + 1 √ 2 ( |0i + |1i) |0i |1i 2 1 √ 2 ( − |1i + |0i) 1 √ 2 − 1 √ 2 ( |0i − |1i) + 1 √ 2 ( |0i + |1i) |1i |1i 3 1 √ 2 ( |0i − |1i) 1 √ 2 1 √ 2 ( |0i + |1i) − 1 √ 2 ( |0i − |1i) |1i |0i 4.6. Квантовые алгоритмы 229 Для раскодирования информации получателю необходимо теперь измерить отдельно первый и второй кубиты. 0 X 0 preparation + H + H out ψ encoding decoding Например, для передачи значения «3» отправитель кодирует свою часть Ш-забита Z-преобразованием и передает получателю. Получатель действует на Ш-забит сначала CNOT оператором, затем оператором Адамара. Полученное состояние получатель подвергает измерению. Пусть измерительное устройство настроено на проецирование входящего кубита на состояние |ψ Π i = |0i , т.е. описывается проекционным оператором Π = |ψ Π i hψ Π | = |0i h0| . Тогда после измерения первого кубита имеем |ψ 0 i = Π |1i 1 = |0i h0| |1i 1 = 0. Такой результат говорит, что состояние кубита и измеряющего устройства были ортогональны. Мы потеряли 1 кубит (он был поглощен измерительным устройством), однако мы получили 1 bit классической информации: оказывается кубит был в состоянии |1i. Измеряя второй кубит тем же измерительным устройством получим |ψ 0 i = Π |0i 2 = |0i h0| |0i 2 = |0i . Это означает, что кубит не взаимодействует с измерительным устройством, поглощается детектором и дает нам 2-ой bit классической информации, что кубит был в состоянии |0i. Из последней таблицы определяем, что значение передаваемой информации было равно «3». Очевидно, что для передачи всей последовательности из 4 классических бит информации нам необходимо предварительно приготовить 4 Ш-забита и с каждым проделать все описанные выше операции. Аналогичная схема может быть построена и для передачи 2 кубитов. Для этого создается запутанное состояние |ψi = 1 √ 2 ( |0000i + |1111i) половина из которого должна быть у получателя. Каждому значению передаваемой последовательности ставится в соответствие суперпозиция однокубитовых операторов I = σ 0 , X = σ x , Y = iσ y , Z = σ z , 230 Глава 4. Квантовая информация 0 X 0 preparation H out ψ encoding decoding 0 0 H + + X + + H H которым отправитель действует на первые два кубита забита. Результат работы протокола показан в таблице. 4.6. Квантовые алгоритмы 231 Значение Кодирование Декодирование 0 ψ 0 = (I ⊗ I ⊗ I ⊗ I)ψ 0 |0000i 1 ψ 1 = (I ⊗ X ⊗ I ⊗ I)ψ 0 |0001i 2 ψ 2 = (I ⊗ Y ⊗ I ⊗ I)ψ 0 |0101i 3 ψ 3 = (I ⊗ Z ⊗ I ⊗ I)ψ 0 |0100i 4 ψ 4 = (X ⊗ I ⊗ I ⊗ I)ψ 0 |0010i 5 ψ 5 = (X ⊗ X ⊗ I ⊗ I)ψ 0 |0011i 6 ψ 6 = (X ⊗ Y ⊗ I ⊗ I)ψ 0 |0111i 7 ψ 7 = (X ⊗ Z ⊗ I ⊗ I)ψ 0 |0110i 8 ψ 8 = (Y ⊗ I ⊗ I ⊗ I)ψ 0 |1010i 9 ψ 9 = (Y ⊗ X ⊗ I ⊗ I)ψ 0 |1011i 10 ψ 10 = (Y ⊗ Y ⊗ I ⊗ I)ψ 0 |1111i 11 ψ 11 = (Y ⊗ Z ⊗ I ⊗ I)ψ 0 |1110i 12 ψ 12 = (Z ⊗ I ⊗ I ⊗ I)ψ 0 |1000i 13 ψ 13 = (Z ⊗ X ⊗ I ⊗ I)ψ 0 |1001i 14 ψ 14 = (Z ⊗ Y ⊗ I ⊗ I)ψ 0 |1101i 15 ψ 15 = (Z ⊗ Z ⊗ I ⊗ I)ψ 0 |1100i Очевидное обобщение данной схемы позволяет, передавая по квантовому каналу k кубитов, получить на выходе k 2 классических бит информации. 232 Глава 4. Квантовая информация 4.6.3 Квантовая телепортация Другим эффективным алгоритмом, который может реализовываться исключительно квантовыми методами яляется алгоритм квантовой телепортации [ ?]. Перед процессом телепортации получателю и отправителю информации передается по одной части Шредингеровского забита |ψi = 1 √ 2 ( |00i + |11i) . Отправитель создает суперпозицию передаваемого кубита |φi = a |0i + b |1i и Ш-забита: |Ψi = |φi ⊗ |ψi = 1 √ 2 (a |000i + a |011i + b |100i + b |111i) . Действуя на первые два свои кубита CNOT операцией, а затем оператором Адамара на первый кубит отправитель получает состояние Ψ out = H 1 P 12 Ψ in 123 = 1 √ 2 H 1 (a |000i + a |011i + b |110i + b |101i) = 1 2 |00i (a |0i + b |1i) + |10i (a |0i − b |1i) + |01i (a |1i + b |0i) + |11i (a |1i − b |0i) Измерение двух первых кубитов отправителем влечет за собой изменение состояния Ш-забита получателя: Результат Состояние ЭПР-забита Преобразование измерения получателя |00i a |0i + b |1i Iφ |01i a |1i + b |0i Xφ |10i a |0i − b |1i Zφ |11i a |1i − b |0i Yφ Результат измерения отправитель сообщает получателю по классическому каналу. Эта информация определяет преобразование, которым необходимо подействовать на Ш-забит получателя. + H X 0 0 ψ H + ψ 4.7. Коррекция ошибок в квантовых каналах информации 233 Например, отправитель после проведения операций CNOT, H и измерения получил результат |10i, и передал его по классическому каналу. Тогда, получатель действует согласно таблице, на свой Ш-забит преобразованием Z |φi = Z (a |0i − b |1i) = a |1i + b |0i и восстанавливает телепортируемый кубит. 4.7 Коррекция ошибок в квантовых каналах информации При передачи информации по каналам связи она может искажаться. Алгоритм квантовой коррекции ошибок аналогичен классическому и требует введения дополнительных кубитов для обнаружения и коррекции ошибки. Рассмотрим тривиальный корректирующий код C, отоброжающий |0i → |000i |1i → |111i С помощью этого кода мы можем корректировать единичную ошибку отдельного кубита: E = {I ⊗ I ⊗ I, X ⊗ I ⊗ I, I ⊗ X ⊗ I, I ⊗ I ⊗ X} . Пример 4.24. По квантовому каналу информации передается кубит |ψ 0 i = 1 √ 2 ( |0i + |1i) . Какое квантовое состояние будет зарегистрировано на приемнике, если оператор ошибки данного канала информации имеет вид E = 1 2 X ⊗ I ⊗ I + √ 3 2 I ⊗ I ⊗ X. Решение. Перед отправлением на исходный кубит |ψ 0 i = 1 √ 2 ( |0i + |1i) действует корректирующий код, поэтому на входе квантового канала информации мы имеем ψ in = 1 √ 2 ( |000i + |111i) . Действие оператора ошибки на передаваемый кубит есть E |ψ in i = 1 2 X ⊗ I ⊗ I + √ 3 2 I ⊗ I ⊗ X 1 √ 2 ( |000i + |111i) = = 1 2 √ 2 ( |100i + |011i) + √ 3 2 √ 2 ( |001i + |110i) 234 Глава 4. Квантовая информация Поэтому на выходе из квантового канала информации будет зарегистрировано состояние ψ out = 1 2 √ 2 |100i + |011i + √ 3 |001i + √ 3 |110i . N Задача 4.12. 1. По квантовому каналу информации передается кубит |ψi = |0i. Какое квантовое состояние будет зарегистрировано на приемнике, если оператор ошибки данного канала информации имеет вид E = 1 √ 2 I ⊗ I ⊗ I + 1 √ 2 I ⊗ X ⊗ I. 2. По квантовому каналу информации передается кубит |ψi = 1 2 |0i + √ 3 |1i Какое квантовое состояние будет зарегистрировано на приемнике, если оператор ошибки данного канала информации имеет вид E = X ⊗ I ⊗ I. 3. По квантовому каналу информации передается кубит |ψi = α|0i + β|1i. Какое квантовое состояние будет зарегистрировано на приемнике, если оператор ошибки данного канала информации имеет вид E = √ 3 2 X ⊗ I ⊗ I + 1 2 I ⊗ I ⊗ X. 4. По квантовому каналу информации передается кубит |ψi = α|0i + β|1i. Какое квантовое состояние будет зарегистрировано на приемнике, если оператор ошибки данного канала информации имеет вид E = 1 2 I ⊗ X ⊗ I + √ 3 2 I ⊗ I ⊗ X. Если мы приняли сигнал ψ F = |e 1 , e 2 , e 3 i , то оператор выделения ошибки есть S|e 1 , e 2 , e 3 i → |e 1 , e 1 ⊕ e 2 , e 1 ⊕ e 3 i и его действие представлено в таблице. Инвертированный бит Признак ошибки Коррекция ошибки - |000i I ⊗ I ⊗ I 0 |110i X ⊗ I ⊗ I 1 |101i I ⊗ X ⊗ I 2 |011i I ⊗ I ⊗ X 4.7. Коррекция ошибок в квантовых каналах информации 235 0 ψ P 13 0 0 0 ψ P 12 P 12 P 13 T 321 Для обнаружения и исправления единичной ошибки удобнее пользоваться следующим оператором |ψ 0 i ⊗ |z 2 z 3 i = T 231 S ψ F |e 1 , e 2 , e 3 i = T 231 P 12 P 13 ψ F |e 1 , e 2 , e 3 i . Пример 4.25. Определить, какой кубит был передан по зашумленному квантовому каналу информации, если на выходе он имеет состояние ψ out = 1 2 √ 2 |100i + |011i + √ 3 |001i + √ 3 |110i Решение. Действуя на выходное состояние оператором выделения ошибки, получим |ψ 0 i ⊗ |z 1 z 2 i = T 231 P 12 P 13 1 2 √ 2 |100i + |011i + √ 3 |001i + √ 3 |110i = T 231 P 12 1 2 √ 2 |101i + |011i + √ 3 |001i + √ 3 |111i = T 231 1 2 √ 2 |111i + |011i + √ 3 |001i + √ 3 |101i = 1 2 √ 2 |011i + |111i + √ 3 |001i + √ 3 |101i = 1 2 √ 2 ( |011i + |111i) + 1 2 √ 2 √ 3 |001i + √ 3 |101i = 1 2 √ 2 ( |0i + |1i) ⊗ |11i + √ 3 2 √ 2 ( |0i + |1i) ⊗ |01i = 1 2 1 √ 2 ( |0i + |1i) ⊗ |11i + √ 3 2 1 √ 2 ( |0i + |1i) ⊗ |01i = 1 √ 2 ( |0i + |1i) ⊗ 1 2 |11i + √ 3 2 |01i ! = |ψ 0 i ⊗ |z 1 z 2 i Измеряя два последние бита этого состояния, мы получим |11i (с вероятностью 1/4) или |01i (с вероятностью 3/4). В любом случае мы востанавливаем первый кубит 236 Глава 4. Квантовая информация в исходное состояние |ψ 0 i = 1 √ 2 ( |0i + |1i) . N Задача 4. 13. Определить, какой кубит был передан по зашумленному квантовому каналу информации, если на выходе он имеет состояние 1. |ψ out i = 1 √ 2 ( |111i + |101i). 2. |ψ out i = 1 2 |100i + √ 3 |011i 3. |ψ out i = 1 2 √ 3(α |100i + β|011i) + α|0010i + β|110i 4. |ψ out i = 1 2 α |010i + √ 3α |001i + √ 3β |110i + β|101i 4.8 Клонирование квантовой информации В 1982 г. Вуттерсом и Зуреком [15] была сформулирована следующая Теорема. Точное копирование произвольного кубита запрещено. Доказательство. Действительно, для этого необходимо найти такое унитарное преобразование, которое создает из одного кубита |ψi два таких же |ψi|ψi. Т.е. мы должны найти оператор U, действующий на два кубита (один из которых нулевой) так, что U |ψi|0i = |ψi|ψi. Возьмем ортогональный для |ψi кубит |ϕi U |ϕi|0i = |ϕi|ϕi. Из этих кубитов составим третий |φi = 1 √ 2 ( |ψi + |ϕi) , для которого U |φi|0i = U 1 √ 2 ( |ψi|0i + |ϕi|0i) = 1 √ 2 ( |ψi|ψi + |ϕi|ϕi) . С другой стороны U |φi|0i = |φi|φi = 1 2 ( |ψi + |ϕi) (|ψi + |ϕi) = 1 2 ( |ψi|ψi + |ψi|ϕi + |ψi|ϕi + |ϕi|ϕi) . Поскольку два последних выражения не равны, мы делаем вывод что такого преобразования не существует. Несмотря на запрет точного клонирования кубитов, использование квантового запутывающего оператора CNOT позволяет построить квантовую клонирующую машину, которая создает из одного кубита два одинаковых. 4.8. Клонирование квантовой информации 237 Простейшая квантовая клонирующая машина может быть построена из единственного оператора CNOT. Подавая на один вход машины произвольное квантовое состояние |ψ 0 i |ψ 0 i = α|0i + β|1i, а на другой – кубит в состоянии |0i получим Ψ in = |ψ 0 i|0i = α|00i + β|10i. Работа квантовой клонрующей машины 0 ψ |