ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2020
Просмотров: 179
Скачиваний: 1
Семинар 7. Квантовые вычисления
7.1
Введение
Из предыдущего изложения ясно, что необходимость построения квантового компьютера
и разработка схемы квантовых вычислений возникает по двум причинам. Первая причина
—
технологическая. Фактическое развитие полупроводниковых технологий и технологий
изготовления больших интегральных схем неизбежно приводит к тому, что для записи
бита классической информации требуются все более и более микроскопические объекты
приходя по существу к отдельным атомам и молекулам. Поведение этих объектов уже
не укладывается в рамки классического описания и потому приходится либо считать, что
достигнут технологический предел миниатюризации, либо решать проблему организации
вычислений на квантовых объектах.
Вторая причина, которая стимулирует исследования в области квантовых компьютеров
—
это
проявляющиеся
принципиальные
ограничения,
которые
возникают
при
использовании классических компьютеров, когда речь идет о возрастающем числе данных и
экспоненциальном росте времени вычисления для многих, практически интересных и важных
классических алгоритмов. Среди этих примеров приводится задача факторизации числа
N
на
простые множители. В классической теории вычислений "приемлемыми" рассматриваются
такие алгоритмы вычислений, в которых число шагов растет как полином небольшой степени
от размера входных данных (например, полином второй или третьей степени).
Для задачи факторизации входными данными является число
N
, которое необходимо
разложить на множители. Поэтому "длина" входных данных на классическом "двоичном"
компьютере есть
log
2
N
. Основание 2 логарифма связано с использованием двоичной
системы исчисления. Известно, что лучшие алгоритмы факторизации выполняются за число
шагов,
k
, которое имеет следующий порядок
k
=
Const
·
exp
(64
/
9)
1
/
3
(ln
N
)
1
/
3
(ln ln
N
)
2
/
3
.
(7.1)
То есть алгоритм вычислений приводит к экспоненциальному росту числа шагов по мере
роста числа входных данных. Так в 1994 году 129-значное число было факторизовано на
1600 рабочих станциях, распределенных по всему миру
. Время факторизации составило
8 месяцев. Используя результаты этого эксперимента можно качественно оценить порядок
величины
Const
в (7.1). Оценка числа времени, которое потребуется для факторизации
250-значного числа на тех же 1600 рабочих станциях дает
∼
10
6
лет (миллион лет!).
Соответственно для факторизации 1000-значного числа потребуется
10
25
лет, что на
11
−
12
порядков больше (триллион лет) возраста вселенной, который оценивается в
10
12
−
10
13
лет.
Сама по себе абстрактная задача факторизации очень больших чисел, помимо
академического (считай никому не нужного) интереса имеет прямое отношение к системам
криптографии с открытым ключом, нашедшим широкое применение в банковских системах.
Забегая вперед, можно сказать, что факторизация 1000-значного числа с помощью
квантового алгоритма потребует всего лишь несколько миллионов шагов и, следовательно,
если квантовые алгоритмы удастся реализовать в реальном устройстве, то криптосистемы
1
A.M. Odiyzko. AT&T Bell Laboratories, preprint 1995.
2
S.L. Branstein. Encyclopedia of Applied Physics, Update, WILEY-VCH, 1999.
60
с открытым ключом, основанные на сложности факторизации чисел с приблизительно
250
знаками будут взломаны. Но естественно, не только задача "продажи" секретов банковским
мошенникам стоит перед квантовыми вычислениями. Принципиальным фактом развития
квантовых вычислений является возможность осуществления параллелизма в квантовых
вычислениях, принципиально не доступного в классических устройствах.
7.2
Логические однокубитовые гейты
Классические компьютерные цепи состоят из проводов и набора логических гейтов
(совокупности транзисторов). Провода служат для передачи стандартных напряжений по
электрическим цепям, а логические гейты осуществляют преобразование "проходящей" через
них информации. При этом единственным не тривиальным логическим гейтом, который
преобразует 1 бит классической информации является NOT-гейт, действие которого сводится
к преобразованиям битов вида:
0
→
1
и
1
→
0
.
Одиночный кубит, по определению, является суперпозицией двух квантовых состояний
|
0
i
и
|
1
i
, каждое из которых может рассматриваться как носитель одного бита классической
информации
|
ψ
i
=
a
|
0
i
+
b
|
1
i
.
(7.2)
В соответствии с определением классического NOT-гейта, квантовый NOT-гейт (т.е. гейт
преобразующий информацию внутри кубита) может быть определен по аналогии:
N OT
:
|
ψ
i →
N OT
: (
a
|
0
i
+
b
|
1
i
)
→
a
|
1
i
+
b
|
0
i
.
(7.3)
На основании теории представлений, квантовому состоянию кубита
|
ψ
i
соответствует столбец
|
ψ
i →
a
b
.
(7.4)
Поэтому квантовым аналогом классического NOT-гейта является матрица вида:
x
≡
0 1
1 0
,
x
a
b
=
b
a
,
(7.5)
которая совпадает с матрицей Паули
σ
x
в
s
z
-представлении.
В соответствии с (7.4) квантовые гейты, преобразующие однокубитовое состояние
являются унитарными матрицами размерности
2
×
2
. В отличие от классических систем,
для кубита можно построить неограниченное число гейтов. Однако, в силу полноты системы
матриц Паули и единичной матрицы
I
, любая
2
×
2
матрица может быть разложена по этой
полной системе матриц. Поэтому для практического использования представляют интерес
сами матрицы Паули
X
≡
σ
x
,
Y
≡
σ
y
,
Z
≡
σ
z
и некоторые их специальные комбинации,
среди которых выделим следующие три:
H
≡
1
√
2
1
1
1
−
1
;
S
≡
1 0
0
i
;
T
≡
1
0
0
e
iπ/
4
.
(7.6)
61
Матрицы (7.6) определяют соответственно
H
–
гейт Адамара,
S
–
фазовый гейт, а
T
называется
π/
8
-гейт. Из определения перечисленных гейтов следует, что:
H
=
1
√
2
(
σ
x
+
σ
z
)
≡
1
√
2
(
X
+
Z
);
S
=
T
2
.
(7.7)
Название
T
-гейта (
π/
8
-гейт) определяется историческими причинами и возможностью
представления матрицы этого гейта с точностью до общего фазового множителя
exp(
iπ/
8)
в виде:
T
≡
exp(
iπ/
8)
exp(
−
iπ/
8)
0
0
exp(
iπ/
8)
(7.8)
Гейт Адамара является одним из наиболее полезных квантовых гейтов. Этот гейт иногда
определяют как "квадратный корень от NOTгейт. Это связано с тем, что данный гейт
преобразует
a
|
0
i
-часть кубита в
(
|
0
i
+
|
1
i
)
/
√
2
–
"половина пути" между
|
0
i
и
|
1
i
состояниями
в геометрической интерпретации кубита на сфере Блоха. Соответственно в
|
1
i
-части кубита
преобразуется гейтом Адамара в комбинацию
(
|
0
i − |
1
i
)
/
√
2
, что также "половина пути"
между
|
0
i
и
|
1
i
. Однако
H
2
-гейт не приводит к NOT-гейту, так как алгебраические
вычисления дают
H
2
≡
I
. То есть двухкратное применение гейта
H
возвращает систему в
исходное положение.
Графическое обозначение однокубитовых гейтов представляют в виде:
a
|
0
i
+
b
|
1
i
X
b
|
0
i
+
a
|
1
i
a
|
0
i
+
b
|
1
i
Y
−
i
{
b
|
0
i −
a
|
1
i}
a
|
0
i
+
b
|
1
i
Z
a
|
0
i −
b
|
1
i
a
|
0
i
+
b
|
1
i
H
a
|
0
i
+
|
1
i
√
2
+
b
|
0
i − |
1
i
√
2
a
|
0
i
+
b
|
1
i
S
a
|
0
i
+
ib
|
1
i
a
|
0
i
+
b
|
1
i
T
a
|
0
i
+
e
iπ/
4
b
|
1
i
=
=
e
iπ/
8
{
e
−
iπ/
8
a
|
0
i
+
e
iπ/
8
b
|
1
i}
(7.9)
Произвольный однокубитовый унитарный оператор может быть записан в виде:
U
= exp(
iα
)
R
~
n
(
θ
)
,
(7.10)
где
R
~
n
(
θ
)
–
оператор поворота на угол
θ
вокруг оси, определенной единичным вектором
~
n
,
α
и
θ
–
действительные числа.
Используя вид оператора поворота можно установить, что
T
≡
R
z
(
π/
4)
, а гейт Адамара
с точностью до глобального фазового множителя, является произведением операторов
поворота
R
x
и
R
z
. С учетом условия антикоммутации матриц Паули
σ
x
σ
y
=
−
σ
y
σ
x
можно
установить, что
X R
y
(
θ
)
X
=
R
y
(
−
θ
)
.
(7.11)
62
В алгебре матриц Паули доказывается теорема, которая называется
теоремой
X
−
Y
разложения
для однокубитового гейта (или оператора). Содержание теоремы утверждает,
что существуют действительные числа
α
,
β
,
γ
,
δ
такие, что унитарный оператор
U
может быть
представлен в виде:
U
=
e
iα
R
z
(
β
)
R
y
(
γ
)
R
z
(
δ
)
.
(7.12)
Обобщение этой теоремы может быть выполнено для двух произвольных направлений,
определенных векторами
~
m
и
~
n
. В этом случае однокубитовая унитарная матрица может быть
записана в виде
U
=
e
iα
R
n
(
β
1
)
R
m
(
γ
1
)
R
n
(
β
2
)
R
m
(
γ
1
)
. . .
(7.13)
Для дальнейшего (с целью изучения квантовых цепей) полезно отметить следующие
равенства
HXH
=
Z
;
HY H
=
−
Y
;
HZH
=
X
;
HT H
=
e
iα
R
x
(
π/
4)
(7.14)
7.3
Контролируемые квантовые гейты
Простейшим двухкубитовым контролируемым гейтом в классическом компьютере
является CNOT-гейт. В квантовых вычислениях водится, по сути подобный, гейт, который
имеет два входных кубита и два кубита на выходе. Как и в классическом случае один из пары
кубитов называется контролирующим, а второй контролируемым или кубитом-мишенью.
Буквенное обозначение CNOT-квантового гейта не отличается от классического. Логика
выполнения операции при этом определяется следующим образом: если контролирующий
кубит находится в состоянии
|
1
i
, тогда контролируемый кубит подвергается квантовой
операции NOT, в противном случае контролируемый кубит остается без изменения.
Графически "цепь" квантового CNOT-гейта изображается в виде:
CN OT
=
(7.15)
Для пары кубитов
|
a
i
и
|
b
i
в качестве базисных можно выбрать вектора, являющиеся
прямым произведением базисных векторов отдельных кубитов:
|
0
a
0
b
i
=
|
0
a
i ⊗ |
0
b
i
=
1
0
⊗
1
0
≡
1
0
0
0
.
(7.16)
Аналогично оставшиеся 3 базисных состояния имеют вид:
|
0
a
1
b
i ≡
0
1
0
0
;
|
1
a
0
b
i ≡
0
0
1
0
;
|
1
a
1
b
i ≡
0
0
0
1
.
(7.17)
63
Чистое двухкубитовое квантовое состояние такой системы в общем виде определяется
суперпозицией двухкубитовых базисных состояний
|
ψ
ab
i
=
α
|
0
a
0
b
i
+
β
|
0
a
1
b
i
+
γ
|
1
a
0
b
i
+
δ
|
1
a
1
b
i ≡
α
β
γ
δ
.
(7.18)
Таким образом матрица квантового CNOT-гейт имеет следующий вид в базисе кубитов
|
0
i
и
|
1
i
CN OT
=
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
(7.19)
Если выбирать в качестве оператора некоторый произвольный унитарный оператор,
действующий на одиночный кубит, то контролируемая U-операция или CONTROLLED U-
гейт можно графически определить следующим образом
(7.20)
И в более общем случае
контролирующие кубиты
контролируемые кубиты
,
(7.21)
наиболее важным из которых является Тоффоли гейт или CCNOT-гейт
CCN OT
≡
В этом гейте управляющими являются кубиты
A
и
B
, а
C
–
является управляемым. В
пространстве базисных состояний 3-х кубитов
|
0
,
0
,
0
i
,
|
0
,
0
,
1
i
,
|
0
,
1
,
0
i
,
|
1
,
0
,
0
i
,
|
1
,
0
,
1
i
,
64