ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.11.2023
Просмотров: 125
Скачиваний: 5
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Глава 5. Некоторые алгоритмы квантовой информатики
5.1. Сверхплотное кодирование.
Алгоритмы сверхплотного кодирования и телепортации (разд. 5.2) идейно близки между собой.
Сверхплотное кодирование (dense coding) применяют для того, чтобы посредством физического перемещения одного кубита в ЭПР - паре осуществить передачу двух классических битов информации.
Телепортацию (teleportation), наоборот, используют для того, чтобы с помощью двух классических битов информации осуществить передачу произвольного неизвестного квантового состояния одного кубита. В этом случае не происходит перемещение квантового бита в пространстве от передающей к принимающей стороне. Передача неизвестного квантового состояния кубита на расстояние, в силу теоремы о невозможности клонирования, неизбежно сопровождается разрушением квантового состояния исходного кубита.
Рассмотрим алгоритм сверхплотного кодирования. Алиса и Боб стремятся наладить между собой линию связи. Каждый из них получает одну из частиц в
ЭПР- паре:
(
)
11 00 2
1
+
Допустим, что Алиса получает первую частицу, а Боб – вторую. Пока частицы разделены, Алиса может делать преобразования только над своей частицей (кубитом), а Боб только над своей.
Пусть Алиса хочет передать сообщение из двух бит классической информации. Это эквивалентно передаче целого числа от 0 до 3. В зависимости от этого числа Алиса выполняет над своим кубитом одно из четырех преобразований {I, X, Y, Z}. При этом второй кубит, принадлежащий
110
Бобу, испытывает тождественное преобразование. Трансформация квантового состояния в зависимости от кодируемого Алисой значения представлена в таблице 5.1.
Таблица 5.1 Двухбитовое кодирование ЭПР состояния
Алисой
Значение
Преобразование Новое состояние
0
I
I
⊗
(
)
11 00 2
1
+
1
I
X
⊗
(
)
01 10 2
1
+
2
I
Y
⊗
(
)
01 10 2
−
i
3
I
Z
⊗
(
)
11 00 2
1
−
Затем Алиса посылает свой кубит Бобу. Боб пркладывает CNOT к системе двух кубитов, которые находятся в запутанном состоянии. После операции
CNOT состояние перестает быть запутанным (см. табл.5.2).
Таблица 5.2 Результат действия CNOT при декодировании информации Бобом
Исходное состояние
CNOT
Первый кубит
Второй кубит
(
)
11 00 2
1
+
(
)
10 00 2
1
+
(
)
1 0
2 1
+
0
(
)
01 10 2
1
+
(
)
01 11 2
1
+
(
)
0 1
2 1
+
1
(
)
01 10 2
−
i
(
)
01 11 2
−
i
(
)
0 1
2
−
i
1
(
)
11 00 2
1
−
(
)
10 00 2
1
−
(
)
1 0
2 1
−
0
111
Заметим, что теперь Боб может безбоязненно измерить второй кубит, не нарушая квантового состояния. Если в результате измерения он получит
0
, то это значит, что Алиса послала 0 или 3. Если, напротив, он получит
1
, то это значит, что Алиса послала 1 или 2.
Далее Боб совершает преобразование Адамара H над первым кубитом
(табл.5.3)
Таблица 5.3. Результат действия оператора Адамара на первый кубит
Первый бит H
(
)
1 0
2 1
+
(
)
0 1
0 1
0 2
1
=
−
+
+
(
)
0 1
2 1
+
(
)
0 1
0 1
0 2
1
=
+
+
−
(
)
0 1
2
−
i
(
)
1 1
0 1
0 2
i
i
−
=
−
−
−
(
)
1 0
2 1
−
(
)
1 1
0 1
0 2
1
=
+
−
+
Теперь Боб сможет отличить 0 от 3, а также 1 от 2.
Заметим, что для реализации протокола сверхплотного кодирования принципиально важным является наличие ресурса запутанности. Другими словами, для того, чтобы Алиса смогла закодировать в свой кубит два бита классической информации, необходимо, чтобы ее кубит был изначально запутан с кубитом, имеющимся у Боба. Поскольку кубит, изначально имевшийся у Боба, не использовался для передачи информации, то, очевидно, суммарно мы получаем передачу двух битов классической информации посредством двух кубитов.
112
Задача 5.1
Пусть исходное двухкубитовое состояние является незапутанным. Покажите, что рассмотренный выше протокол кодирования не сможет привести к передаче более чем одного бита классической информации
(тем самым, Вы обоснуете принципиально важную роль ресурса запутанности в рассматриваемом протоколе).
Задача 5.2
Нарисуйте квантовую цепь, соответствующую рассмотренному выше протоколу сверхплотного кодирования.
5.2. Телепортация
Цель телепортации заключается в том, чтобы передать на расстояние квантовое состояние частицы, используя классические биты и реконструируя точно квантовое состояние в приемнике.
Поскольку квантовое состояние не может быть клонировано, квантовое состояние исходной частицы обязательно будет разрушено.
Рассмотрим алгоритм квантовой телепортации с использованием ЭПР – пар.
Пусть Алиса хочет переслать неизвестное состояние кубита Бобу
1 0
b
a
+
=
φ
Алиса и Боб имеют также по одному кубиту из ЭПР – пары:
(
)
11 00 2
1
+
Стартовое состояние есть:
(
)
(
)
(
)
111 100 011 000 2
1 11 00 2
1 1
0
b
b
a
a
b
a
+
+
+
=
=
+
⊗
+
В этом состоянии Алиса может управлять первыми двумя кубитами, а Боб
– третьим.
113
Пусть теперь Алиса прикладывает CNOT к своим кубитам, а затем преобразование Адамара H к первому кубиту.
После действия CNOT на первые два кубита имеем:
(
)
101 110 011 000 2
1
b
b
a
a
+
+
+
После приложения оператора Адамара H к первому кубиту получим следующее состояние:
(
)
(
)
(
)
(
)
(
)
(
)
0 1
11 1
0 10 0
1 01 1
0 00 2
1 101 001 110 010 111 011 100 000 2
1
b
a
b
a
b
a
b
a
b
b
b
b
a
a
a
a
−
+
−
+
+
+
+
=
−
+
−
+
+
+
+
Теперь Алиса измеряет свои два кубита (разрушая квантовое состояние исходной частицы). Она получает при этом один из возможных результатов измерения:
00 01 10 11
. Именно эту информацию она и посылает
Бобу. Для декодирования Бобу остается проделать соответственно всего одну из операций: I, X, Z, iY
Задача 5.3
Нарисуйте квантовую цепь, соответствующую рассмотренному выше протоколу телепортации.
5.3. Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозса.
Пусть функция
( )
x
f
имеет однобитовую область определения и однобитовое множество значений. Нетрудно видеть, что таких функций всего четыре. Две из них постоянны:
1.
( )
0 0
=
f
,
( )
0 1
=
f
, 2.
( )
1 0
=
f
,
( )
1 1
=
f
Две другие функции переменны:
3.
( )
0 0
=
f
,
( )
1 1
=
f
, 4.
( )
1 0
=
f
,
( )
0 1
=
f
114
Квантовая реализация функции
( )
x
f
состоит в том, что двухкубитовое состояние
y
x,
преобразуется в состояние
( )
x
f
y
x
⊕
,
, т.е.
( )
x
f
y
x
y
x
f
⊕
→ ,
,
Здесь символ
⊕
означает сложение по модулю 2.
В частности, если во втором кубите исходно записан ноль (
0
=
y
), то функция
( )
x
f
задает следующее преобразование:
( )
x
f
x
x
f
,
0
,
→
Графическое представление для квантового вычисления функции
( )
x
f
показано на рисунке.
Рис.5.1 Схема квантового вычисления функции
( )
x
f
Рассмотрим для примера четвертую из представленных выше функций:
( )
1 0
=
f
,
( )
0 1
=
f
. Нетрудно видеть, что рассматриваемая функция задает следующее преобразование:
( )
1
,
0 0
0
,
0 0
,
0
=
⊕
→
f
( )
0
,
0 1
1
,
0 0
1
,
0 1
,
0
=
⊕
=
⊕
→
f
115
( )
0
,
1 1
0
,
1 0
,
1
=
⊕
→
f
( )
1
,
1 1
1
,
1 1
,
1
=
⊕
→
f
Задача 5.4
Покажите, что введенное определение квантовой реализации функции задает унитарное преобразование входного состояния в выходное.
Найдите соответствующие унитарные матрицы для каждой из четырех представленных выше функций.
Принцип суперпозиции позволяет подавать на вход схемы квантового вычисления функций не только определенное базисное состояние
x
, но и произвольную суперпозицию таких состояний. Эта возможность обеспечивает так называемый квантовый параллелизм, которой означает, что (в определенном смысле) квантовый алгоритм позволяет вычислять функцию
( )
x
f
для многих значений аргумента
x
одновременно. Квантовый параллелизм, таким образом, обеспечивает принципиально важное преимущество квантовых схем вычислений над классическими. Заметим, в то же время, что результаты квантовых параллельных вычислений не могут быть непосредственно экстрагированы из квантовой системы из-за неизбежной редукции квантового состояния при измерениях.
Задача 5.5
Докажите справедливость результата, представленного на следующем рисунке.
Рис. 5.2 Демонстрация квантового параллелизма для функции с однокубитовой областью определения.
116
Результаты, полученные в задаче, являются простейшей демонстрацией свойства квантового параллелизма. Благодаря действию элемента Адамара
H
на первый кубит, на вход вычислителя функции
f
U
поступает суперпозиция состояний
(
)
1 0
2 1
+
. В итоге, выходное состояние системы представляет собой суперпозицию результатов вычислений при значениях аргумента
0
=
x
и
1
=
x
Представленный результат может быть обобщен на вычисление функции
( )
x
f
с
n
- битовой областью определения и
1
- битовым множеством значений. Квантовая реализация функции
( )
x
f
в этом случае определяется тем же преобразованием
( )
x
f
y
x
y
x
f
⊕
→ ,
,
, где символ
⊕
означает сложение по модулю 2, но теперь
x
- не один кубит, а
n
- кубитовый регистр данных.
Задача 5.6
Докажите справедливость результата, представленного на рисунке.
Рис.5.3 Демонстрация квантового параллелизма для функции с
n
- кубитовой областью определения.
Указание к задаче: воспользуйтесь результатами задачи 4.10.
117
Здесь обозначение символизирует
n
- кубитовый провод (регистр запроса).
Каждый кубит рассматриваемого провода подвергается преобразованию Адамара
H
, что обеспечивается тензорным произведением
n
H
⊗
. Область определения функции
( )
x
f
задана
n
2
базисными состояниями
1 2
,...,
1
,
0
−
=
n
x
. Множество значений функции
( )
x
f
определяется всего двумя состояниями
0
и
1
. Квантовый параллелизм обеспечивает одновременное вычисление функции в
n
2
точках от
0
=
x
до
1 2
−
=
n
x
Алгоритм Дойча описывается квантовой схемой, приведенной на рисунке.
Рис.5.4 Квантовая схема для алгоритма Дойча
Задача 5.7
Покажите, что состояние на выходе схемы Дойча есть:
(
)
2 1
0 0
−
±
=
ψ
out
, когда функция постоянна, т.е.
( ) ( )
1 0
f
f
=
118
(
)
2 1
0 1
−
±
=
ψ
out
, когда функция переменна, т.е.
( ) ( )
1 0
f
f
≠
Указание к задаче: покажите, что действие оператора
f
U
на состояние
(
)
2 1
0
−
x
приводит к состоянию
( )
( )
(
)
2 1
0 1
−
−
x
x
f
Произведем измерение первого кубита выходного состояния
out
ψ
, полученного в представленной выше задаче. В результате измерения с достоверностью получится
0
, если функция постоянна и
1
, если функция переменна. Полученный результат весьма поучителен: посредством одного- единственного вычисления мы смогли идентифицировать определенное глобальное свойство функции (ее постоянство или переменность). При классическом рассмотрении задачи нам, очевидно, потребовалось бы два вычисления для решения той же самой задачи.
Заметим, что схема Дойча не ставит цели восстановить неизвестную функцию целиком: она ориентирована только на идентификацию рассматриваемого глобального свойства неизвестной функции.
Можно констатировать, что в алгоритме Дойча двухбитовая неопределенность, соответствующая четырем возможным функциям
f
, снижается до однобитовой неопределенности, соответствующей только двум возможным функциям
f
. Измерение на выходе схемы Дойча позволяет отличить пару функций (1,2) от пары (3,4). Очевидно, что для того, чтобы отличить пару (1,3) от пары (2,4), достаточно измерить
( )
0
f
. Аналогично, что для того, чтобы отличить пару (1,4) от пары (2,3), достаточно измерить
119
( )
1
f
. Два последних алгоритма аналогичны в классическом и квантовом случае. Возникает резонный вопрос: почему нет аналога алгоритму Дойча в классической теории информации? Дело в том, что в действительности нет двух раздельных теорий информации (классической и квантовой). Существует только одна последовательная теория информации- это квантовая информатика. Классическая теория информации- есть «урезанная» версия квантовой (в классической теории бит может находиться только в состояниях
0
или
1
, но не их суперпозиции). Такое «урезание», как мы видим уже на примере алгоритма Дойча, делает теорию логически менее привлекательной, менее последовательной и фактически неполной.
Напомним, что точно в таком же отношении друг к другу находятся классическая и квантовая теории вероятностей. Это неслучайно: ведь любое количественное определение информации (например, определение Шеннона) базируется на статистических соображениях.
Оказывается, что задача Дойча допускает простое обобщение на многокубитовый случай. Рассмотрим функцию
( )
x
f
с
n
- битовой областью определения и
1
- битовым множеством значений. Теперь переменная
x
может принимать
N
различных значений
1
,...,
1
,
0
−
=
N
x
, где
n
N 2
=
Предположим, что нам заранее известно, что функция
( )
x
f
может быть только одного из двух типов: постоянная функция или так называемая сбалансированная функция.
Для постоянной функции
( )
(
)
1
)
1
(
0
−
=
=
=
N
f
f
f
. Если функция сбалансирована, то
( )
0
=
x
f
для некоторых
x
и
( )
1
=
x
f
для остальных значений аргумента, причем значения
( )
0
=
x
f
и
( )
1
=
x
f
встречаются одинаково часто (в этом и
5.1. Сверхплотное кодирование.
Алгоритмы сверхплотного кодирования и телепортации (разд. 5.2) идейно близки между собой.
Сверхплотное кодирование (dense coding) применяют для того, чтобы посредством физического перемещения одного кубита в ЭПР - паре осуществить передачу двух классических битов информации.
Телепортацию (teleportation), наоборот, используют для того, чтобы с помощью двух классических битов информации осуществить передачу произвольного неизвестного квантового состояния одного кубита. В этом случае не происходит перемещение квантового бита в пространстве от передающей к принимающей стороне. Передача неизвестного квантового состояния кубита на расстояние, в силу теоремы о невозможности клонирования, неизбежно сопровождается разрушением квантового состояния исходного кубита.
Рассмотрим алгоритм сверхплотного кодирования. Алиса и Боб стремятся наладить между собой линию связи. Каждый из них получает одну из частиц в
ЭПР- паре:
(
)
11 00 2
1
+
Допустим, что Алиса получает первую частицу, а Боб – вторую. Пока частицы разделены, Алиса может делать преобразования только над своей частицей (кубитом), а Боб только над своей.
Пусть Алиса хочет передать сообщение из двух бит классической информации. Это эквивалентно передаче целого числа от 0 до 3. В зависимости от этого числа Алиса выполняет над своим кубитом одно из четырех преобразований {I, X, Y, Z}. При этом второй кубит, принадлежащий
110
Бобу, испытывает тождественное преобразование. Трансформация квантового состояния в зависимости от кодируемого Алисой значения представлена в таблице 5.1.
Таблица 5.1 Двухбитовое кодирование ЭПР состояния
Алисой
Значение
Преобразование Новое состояние
0
I
I
⊗
(
)
11 00 2
1
+
1
I
X
⊗
(
)
01 10 2
1
+
2
I
Y
⊗
(
)
01 10 2
−
i
3
I
Z
⊗
(
)
11 00 2
1
−
Затем Алиса посылает свой кубит Бобу. Боб пркладывает CNOT к системе двух кубитов, которые находятся в запутанном состоянии. После операции
CNOT состояние перестает быть запутанным (см. табл.5.2).
Таблица 5.2 Результат действия CNOT при декодировании информации Бобом
Исходное состояние
CNOT
Первый кубит
Второй кубит
(
)
11 00 2
1
+
(
)
10 00 2
1
+
(
)
1 0
2 1
+
0
(
)
01 10 2
1
+
(
)
01 11 2
1
+
(
)
0 1
2 1
+
1
(
)
01 10 2
−
i
(
)
01 11 2
−
i
(
)
0 1
2
−
i
1
(
)
11 00 2
1
−
(
)
10 00 2
1
−
(
)
1 0
2 1
−
0
111
Заметим, что теперь Боб может безбоязненно измерить второй кубит, не нарушая квантового состояния. Если в результате измерения он получит
0
, то это значит, что Алиса послала 0 или 3. Если, напротив, он получит
1
, то это значит, что Алиса послала 1 или 2.
Далее Боб совершает преобразование Адамара H над первым кубитом
(табл.5.3)
Таблица 5.3. Результат действия оператора Адамара на первый кубит
Первый бит H
(
)
1 0
2 1
+
(
)
0 1
0 1
0 2
1
=
−
+
+
(
)
0 1
2 1
+
(
)
0 1
0 1
0 2
1
=
+
+
−
(
)
0 1
2
−
i
(
)
1 1
0 1
0 2
i
i
−
=
−
−
−
(
)
1 0
2 1
−
(
)
1 1
0 1
0 2
1
=
+
−
+
Теперь Боб сможет отличить 0 от 3, а также 1 от 2.
Заметим, что для реализации протокола сверхплотного кодирования принципиально важным является наличие ресурса запутанности. Другими словами, для того, чтобы Алиса смогла закодировать в свой кубит два бита классической информации, необходимо, чтобы ее кубит был изначально запутан с кубитом, имеющимся у Боба. Поскольку кубит, изначально имевшийся у Боба, не использовался для передачи информации, то, очевидно, суммарно мы получаем передачу двух битов классической информации посредством двух кубитов.
112
Задача 5.1
Пусть исходное двухкубитовое состояние является незапутанным. Покажите, что рассмотренный выше протокол кодирования не сможет привести к передаче более чем одного бита классической информации
(тем самым, Вы обоснуете принципиально важную роль ресурса запутанности в рассматриваемом протоколе).
Задача 5.2
Нарисуйте квантовую цепь, соответствующую рассмотренному выше протоколу сверхплотного кодирования.
5.2. Телепортация
Цель телепортации заключается в том, чтобы передать на расстояние квантовое состояние частицы, используя классические биты и реконструируя точно квантовое состояние в приемнике.
Поскольку квантовое состояние не может быть клонировано, квантовое состояние исходной частицы обязательно будет разрушено.
Рассмотрим алгоритм квантовой телепортации с использованием ЭПР – пар.
Пусть Алиса хочет переслать неизвестное состояние кубита Бобу
1 0
b
a
+
=
φ
Алиса и Боб имеют также по одному кубиту из ЭПР – пары:
(
)
11 00 2
1
+
Стартовое состояние есть:
(
)
(
)
(
)
111 100 011 000 2
1 11 00 2
1 1
0
b
b
a
a
b
a
+
+
+
=
=
+
⊗
+
В этом состоянии Алиса может управлять первыми двумя кубитами, а Боб
– третьим.
113
Пусть теперь Алиса прикладывает CNOT к своим кубитам, а затем преобразование Адамара H к первому кубиту.
После действия CNOT на первые два кубита имеем:
(
)
101 110 011 000 2
1
b
b
a
a
+
+
+
После приложения оператора Адамара H к первому кубиту получим следующее состояние:
(
)
(
)
(
)
(
)
(
)
(
)
0 1
11 1
0 10 0
1 01 1
0 00 2
1 101 001 110 010 111 011 100 000 2
1
b
a
b
a
b
a
b
a
b
b
b
b
a
a
a
a
−
+
−
+
+
+
+
=
−
+
−
+
+
+
+
Теперь Алиса измеряет свои два кубита (разрушая квантовое состояние исходной частицы). Она получает при этом один из возможных результатов измерения:
00 01 10 11
. Именно эту информацию она и посылает
Бобу. Для декодирования Бобу остается проделать соответственно всего одну из операций: I, X, Z, iY
Задача 5.3
Нарисуйте квантовую цепь, соответствующую рассмотренному выше протоколу телепортации.
5.3. Квантовый параллелизм. Алгоритмы Дойча и Дойча- Джозса.
Пусть функция
( )
x
f
имеет однобитовую область определения и однобитовое множество значений. Нетрудно видеть, что таких функций всего четыре. Две из них постоянны:
1.
( )
0 0
=
f
,
( )
0 1
=
f
, 2.
( )
1 0
=
f
,
( )
1 1
=
f
Две другие функции переменны:
3.
( )
0 0
=
f
,
( )
1 1
=
f
, 4.
( )
1 0
=
f
,
( )
0 1
=
f
114
Квантовая реализация функции
( )
x
f
состоит в том, что двухкубитовое состояние
y
x,
преобразуется в состояние
( )
x
f
y
x
⊕
,
, т.е.
( )
x
f
y
x
y
x
f
⊕
→ ,
,
Здесь символ
⊕
означает сложение по модулю 2.
В частности, если во втором кубите исходно записан ноль (
0
=
y
), то функция
( )
x
f
задает следующее преобразование:
( )
x
f
x
x
f
,
0
,
→
Графическое представление для квантового вычисления функции
( )
x
f
показано на рисунке.
Рис.5.1 Схема квантового вычисления функции
( )
x
f
Рассмотрим для примера четвертую из представленных выше функций:
( )
1 0
=
f
,
( )
0 1
=
f
. Нетрудно видеть, что рассматриваемая функция задает следующее преобразование:
( )
1
,
0 0
0
,
0 0
,
0
=
⊕
→
f
( )
0
,
0 1
1
,
0 0
1
,
0 1
,
0
=
⊕
=
⊕
→
f
115
( )
0
,
1 1
0
,
1 0
,
1
=
⊕
→
f
( )
1
,
1 1
1
,
1 1
,
1
=
⊕
→
f
Задача 5.4
Покажите, что введенное определение квантовой реализации функции задает унитарное преобразование входного состояния в выходное.
Найдите соответствующие унитарные матрицы для каждой из четырех представленных выше функций.
Принцип суперпозиции позволяет подавать на вход схемы квантового вычисления функций не только определенное базисное состояние
x
, но и произвольную суперпозицию таких состояний. Эта возможность обеспечивает так называемый квантовый параллелизм, которой означает, что (в определенном смысле) квантовый алгоритм позволяет вычислять функцию
( )
x
f
для многих значений аргумента
x
одновременно. Квантовый параллелизм, таким образом, обеспечивает принципиально важное преимущество квантовых схем вычислений над классическими. Заметим, в то же время, что результаты квантовых параллельных вычислений не могут быть непосредственно экстрагированы из квантовой системы из-за неизбежной редукции квантового состояния при измерениях.
Задача 5.5
Докажите справедливость результата, представленного на следующем рисунке.
Рис. 5.2 Демонстрация квантового параллелизма для функции с однокубитовой областью определения.
116
Результаты, полученные в задаче, являются простейшей демонстрацией свойства квантового параллелизма. Благодаря действию элемента Адамара
H
на первый кубит, на вход вычислителя функции
f
U
поступает суперпозиция состояний
(
)
1 0
2 1
+
. В итоге, выходное состояние системы представляет собой суперпозицию результатов вычислений при значениях аргумента
0
=
x
и
1
=
x
Представленный результат может быть обобщен на вычисление функции
( )
x
f
с
n
- битовой областью определения и
1
- битовым множеством значений. Квантовая реализация функции
( )
x
f
в этом случае определяется тем же преобразованием
( )
x
f
y
x
y
x
f
⊕
→ ,
,
, где символ
⊕
означает сложение по модулю 2, но теперь
x
- не один кубит, а
n
- кубитовый регистр данных.
Задача 5.6
Докажите справедливость результата, представленного на рисунке.
Рис.5.3 Демонстрация квантового параллелизма для функции с
n
- кубитовой областью определения.
Указание к задаче: воспользуйтесь результатами задачи 4.10.
117
Здесь обозначение символизирует
n
- кубитовый провод (регистр запроса).
Каждый кубит рассматриваемого провода подвергается преобразованию Адамара
H
, что обеспечивается тензорным произведением
n
H
⊗
. Область определения функции
( )
x
f
задана
n
2
базисными состояниями
1 2
,...,
1
,
0
−
=
n
x
. Множество значений функции
( )
x
f
определяется всего двумя состояниями
0
и
1
. Квантовый параллелизм обеспечивает одновременное вычисление функции в
n
2
точках от
0
=
x
до
1 2
−
=
n
x
Алгоритм Дойча описывается квантовой схемой, приведенной на рисунке.
Рис.5.4 Квантовая схема для алгоритма Дойча
Задача 5.7
Покажите, что состояние на выходе схемы Дойча есть:
(
)
2 1
0 0
−
±
=
ψ
out
, когда функция постоянна, т.е.
( ) ( )
1 0
f
f
=
118
(
)
2 1
0 1
−
±
=
ψ
out
, когда функция переменна, т.е.
( ) ( )
1 0
f
f
≠
Указание к задаче: покажите, что действие оператора
f
U
на состояние
(
)
2 1
0
−
x
приводит к состоянию
( )
( )
(
)
2 1
0 1
−
−
x
x
f
Произведем измерение первого кубита выходного состояния
out
ψ
, полученного в представленной выше задаче. В результате измерения с достоверностью получится
0
, если функция постоянна и
1
, если функция переменна. Полученный результат весьма поучителен: посредством одного- единственного вычисления мы смогли идентифицировать определенное глобальное свойство функции (ее постоянство или переменность). При классическом рассмотрении задачи нам, очевидно, потребовалось бы два вычисления для решения той же самой задачи.
Заметим, что схема Дойча не ставит цели восстановить неизвестную функцию целиком: она ориентирована только на идентификацию рассматриваемого глобального свойства неизвестной функции.
Можно констатировать, что в алгоритме Дойча двухбитовая неопределенность, соответствующая четырем возможным функциям
f
, снижается до однобитовой неопределенности, соответствующей только двум возможным функциям
f
. Измерение на выходе схемы Дойча позволяет отличить пару функций (1,2) от пары (3,4). Очевидно, что для того, чтобы отличить пару (1,3) от пары (2,4), достаточно измерить
( )
0
f
. Аналогично, что для того, чтобы отличить пару (1,4) от пары (2,3), достаточно измерить
119
( )
1
f
. Два последних алгоритма аналогичны в классическом и квантовом случае. Возникает резонный вопрос: почему нет аналога алгоритму Дойча в классической теории информации? Дело в том, что в действительности нет двух раздельных теорий информации (классической и квантовой). Существует только одна последовательная теория информации- это квантовая информатика. Классическая теория информации- есть «урезанная» версия квантовой (в классической теории бит может находиться только в состояниях
0
или
1
, но не их суперпозиции). Такое «урезание», как мы видим уже на примере алгоритма Дойча, делает теорию логически менее привлекательной, менее последовательной и фактически неполной.
Напомним, что точно в таком же отношении друг к другу находятся классическая и квантовая теории вероятностей. Это неслучайно: ведь любое количественное определение информации (например, определение Шеннона) базируется на статистических соображениях.
Оказывается, что задача Дойча допускает простое обобщение на многокубитовый случай. Рассмотрим функцию
( )
x
f
с
n
- битовой областью определения и
1
- битовым множеством значений. Теперь переменная
x
может принимать
N
различных значений
1
,...,
1
,
0
−
=
N
x
, где
n
N 2
=
Предположим, что нам заранее известно, что функция
( )
x
f
может быть только одного из двух типов: постоянная функция или так называемая сбалансированная функция.
Для постоянной функции
( )
(
)
1
)
1
(
0
−
=
=
=
N
f
f
f
. Если функция сбалансирована, то
( )
0
=
x
f
для некоторых
x
и
( )
1
=
x
f
для остальных значений аргумента, причем значения
( )
0
=
x
f
и
( )
1
=
x
f
встречаются одинаково часто (в этом и