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

ПРИМЕНЕНИЯ СЦЕПЛЕННЫХ СОСТОЯНИЙ3.3Квантовая телепортацияДо сих пор говорилось о передаче классической информации через квантовый канал связи. Такая информация может быть “записана” в квантовомсостоянии и передана через физический канал. Однако квантовое состояние и само по себе является информационным ресурсом постольку, поскольку имеет статистическую неопределенность.

Оказывается, что информация,содержащаяся в неизвестном квантовом состоянии, имеет качественные отличия от классической, и поэтому заслуживает специального термина квантовая информация. Наиболее ярким отличием квантовой информации является невозможность копирования (no cloning). Очевидно, что классическая информации может воспроизводиться в любом количестве. Но физический прибор, который бы выполнял аналогичную задачу для квантовойинформации, противоречит принципам квантовой механики, так как преобразование|ψi → |ψi ⊗ · · · ⊗ |ψi|{z}nявляется нелинейным, и не может быть осуществлено унитарным оператором. Конечно, это можно сделать каждый раз специальным прибором дляданного конкретного состояния (и даже для фиксированного набора ортогональных состояний), но не существует универсального прибора, которыйбы размножал произвольное квантовое состояние.Каким образом может быть передано квантовое состояние? Очевидно,что можно просто физически переслать саму систему.

Гораздо более интересный и нетривиальный способ — телепортация квантового состояния,при которой сама система физически не передается, а передается лишьклассическая информация1 . При этом существенным дополнительным ресурсом, который вновь играет роль “катализатора,” является ЭПР-корреляциямежду входом и выходом канала связи. Заметим, что свести передачу произвольного квантового состояния к только передаче классической информации, не используя дополнительного квантового ресурса, невозможно: поскольку классическая информация копируема, это означало бы возможность копирования и квантовой информации.Пусть имеются две квантовые системы A и B, описывающие, соответственно, вход и выход канала связи. На вход A поступает произвольноесостояние |ψi; можно описать процедуру, при которой исходное состояниеB перейдет в |ψi, а входное |ψi с необходимостью разрушится (иначе мыимели бы копирование).В простейшей (и основной) версии системы A и B являются двухуровневыми(q-битами).1.

Перед началом передачи система AB приготовляется в состоянии |00i+|11i.1 C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, W. K. Wootters, “Teleportingan unknown quantum state via dual classical and Einstein-Podolsky-Rosen channel,” Phys.Rev. Lett., vol 70, 1895-1899 1993.3.3. КВАНТОВАЯ ТЕЛЕПОРТАЦИЯ392. C посылает A произвольное чистое состояние|ψi = a|0i + b|1i.Совокупность трех систем CAB описывается состоянием(a|0i + b|1i) ⊗ (|00i + |11i) = a|000i + b|100i + a|011i + b|111i.3. Затем(a) A производит некоторое обратимое преобразование состояния cистемы CA;(b) A производит измерение (с 4 исходами, что составляет 2 битаклассической информации).

Преобразование и измерение будутописаны ниже.4. A посылает результат измерения B по классическому каналу связи.5. В зависимости от полученного результата измерения B производитнекоторое преобразование и получает это произвольное |ψi.Производимые преобразования являются характерными примерами логических операций, используемых в квантовом компьютинге.

На 3-м шагенад системой CA производится операция CNOT (контролирумое “нет”):|00i → |00i,|01i → |01i,|10i → |11i,|11i → |10i,при которой состояние первого q-бита сохраняется, а состояние второго qбита не изменяется, либо изменяется на противоположное, в зависимостиот состояния первого q-бита. При этом базис переходит в базис, следовательно, в 4-х мерном пространстве CA этому преобразованию соответствует унитарный оператор. Затем к q-биту C применяется операция АдамараH с унитарной матрицей·¸1 1 1H=√.2 1 −1Тогда1|0i → √ (|0i + |1i),21|1i → √ (|0i − |1i),2т.е.

базис поворачивается на угол π/4.Начальное состояние всей системы CAB естьa|000i + b|100i + a|011i + b|111i.После действия CNOT на CA получаемa|000i + b|110i + a|011i + b|101i.40Глава 3. ПРИМЕНЕНИЯ СЦЕПЛЕННЫХ СОСТОЯНИЙПотом H действует на Ca(|000i + |100i) + b(|010i − |110i) + a(|011i + |111i) + b(|001i − |101i).Выделяя состояние системы CA, получаем|00i(a|0i + b|1i) + |01i(a|1i + b|0i) + |10i(a|0i − b|1i) + |11i(a|1i − b|0i).Теперь производится измерение в системе CA, проецирующее на одиниз 4-х базисных векторов |00i, .

. . , |11i. Результат измерения 00, 01, 10, 11посылается от A к B по классическому (идеальному) каналу связи. В зависимости от полученного результата B применяет к своему состоянию одиниз унитарных операторов·¸·¸·¸0 11 00 −1I = σ0 , σx =, σz =, −iσy =,1 00 −11 0преобразующих состояние B в a|0i + b|1i.Возможность телепортации состояния поляризации фотона была продемонстрирована экспериментально Цайлингером в 1997 г.

С тех пор былипроведены десятки экспериментов, включая телепортацию состояний массивных частиц (впервые в 2004 г.)3.4Квантовые алгоритмыИдея квантового компьютера была предложена Фейнманом в 1981 г. для моделирования квантовомеханических систем. Вопрос: не может ли квантовоеустройство решать какие-либо задачи более эффективно, чем классическийкомпьютер, был впервые затронут в книге Ю.И. Манина “Вычислимое иневычислимое”, 1980 г.) Простейшие, но довольно искусственные примерытаких задач рассмотрели Дейч и Джоза. Их усовершенствованием является алгоритм Саймона, который лежит в основе и алгоритма Шора, эффективно решающего важную и практически интересную (по крайней мере, сточки зрения криптографии) задачу разложения большого натуральногочисла на простые множители.3.4.1Алгоритм СаймонаОбозначим B = {0, 1}, B n = B ×n .

Пусть задано отображение f : B n → B n .Известно, что функция f является периодической, то есть f (x) = f (y) ⇔y = x ⊕ ξ, где ξ ∈ B n — двоичный (булев) вектор. Здесь ⊕ обозначает покомпонентное двоичное сложение векторов. Мы предполагаем ξ 6= 0, случайперестановки ξ = 0 может быть рассмотрен аналогично.Требуется найти период ξ за наименьшее возможное число шагов (принимая за шаг каждый акт вычисления функции f ). Классическое решениезадачи сводится к перебору и требует число шагов O(2n/2 ), растущее экспоненциально с n. (После вычисления s значений функции f , сравнивая3.4. КВАНТОВЫЕ АЛГОРИТМЫ41значения во всевозможных парах точек, мы можем исключить не болееs(s − 1)/2 из 2n − 1 значений ξ, так что в худшем случае s(s − 1)/2 = 2n − 1,откуда s ∼ 2n/2 ).

Можно доказать, что и применение вероятностных алгоритмов, которые дают правильный ответ лишь с заданной вероятностью1 − ε, не позволяет добиться ускорения.Квантовый алгоритм требует всего O(n) шагов, если считать за шагквантовое вычисление функции f . При этом решение носит вероятностныйхарактер. Для описания квантового алгоритма нам понадобится n-мерноеобобщение операции Адамара Hn = H ⊗ · · · ⊗ H . Рассмотрим квантовый|{z}nрегистр — физическую систему из n q-битов; информация будет задаватьсясостоянием этой системы. Если x — набор нулей или единиц длины n, товекторы |xi образуют о.н.б.

Действие Hn в этом базисе задается формулой1 X(−1)x·y |yi,Hn |xi = √2n y∈B nгде x · y — скалярное произведение векторов x ∈ B n , y ∈ B n по модулю 2.Оператор Hn унитарный, эрмитов и Hn2 = I.Алгоритм Саймона состоит из следующих шагов:1.

Сначала квантовый регистр приготовляется в основном состоянии |0i =|00 . . .i, затем применяется операция Адамара:1 XHn√|00 . . .i −→|yi.2n y∈B nВ результате получается суперпозиция всевозможных базисных состояний с одинаковыми коэффициентами.2. Затем к этой суперпозиции применяется унитарный оператор, обратимо вычисляющий функцию f :Ã!XUf X|xi ⊗ |zi −→|xi ⊗ |z ⊕ f (x)i,xxгде ⊕ обозначает сложение по модулю 2, т.е. логическую операцию“XOR”. Предполагается, что такой унитарный оператор дан “свыше”(поэтому его принято называть “оракулом”). Отметим, что в алгоритме Шора соответствующее вычисление описывается эффективно. Впринципе, он может быть составлен из некоторых элементарных однои двух-кубитных операций, если известно, как само отображение f составлено из элементарных логических операций. Здесь |zi cостояниевспомогательного регистра, который введен, чтобы сделать операциювычисления функции обратимой. Если исходно этот регистр находится в основном состоянии |0i, тоÃ!XX|xi ⊗ |f (x)i.|xi ⊗ |00 .