|
.
#13 (251)
.
March 2019
55
Computer Science
Краткие теоретические сведения:
аналогично биту, кубит имеет два состояния
|0
⟩
и
|1
⟩
. Кубит может находиться
также и в квантовой суперпозиции этих двух состояний:
|
ѱ⟩
=
𝛼𝛼
|0
⟩
+
𝛽𝛽
|1
⟩
, где
𝛼𝛼
и
𝛽𝛽
— комплексные числа, удовле-
творяющие так называемому условию нормировки
|
𝛼𝛼
|
2
+ |
𝛽𝛽
|
2
= 1. Вероятность обнаружить кубит в состоянии |
0
⟩
равна
|
𝛼𝛼
|
2
, а вероятность обнаружить его в состоянии |
1
⟩
равна
|
𝛽𝛽
|
2
. Пространство состояний квантовой системы —
это векторное пространство. Такие векторные пространства относятся к классу гильбертовых пространств. [1, 2]
Для описания состояния кубита используются скобки
| …
⟩
в соответствии с так называемой нотацией Дирака. Эта
система обозначений векторных величин также называется “bracket” (скобка) на два слога: bra («бра») вектор —
строки и ket («кет») вектор –столбцы. Запись кет — вектора выглядит как
|
𝑏𝑏⟩
, а бра — вектор записывается как
⟨𝑎𝑎
|.
В обозначении скалярного произведения два вектора оказываются заключенными в своеобразные скобки, например,
〈𝑎𝑎
|
𝑏𝑏〉
. В матричной форме бра-векторы принято обозначать следующим образом:
⟨
0| =
(1 0),
⟨
1| =
(0 1). [1, 2]
В матричной форме кет-векторы принято обозначать следующим образом: |
0
⟩
=
�
10
�
, |
1
⟩
=
�
01
�
.
Одним из преимуществ записи векторов в дираковской системе является ее компактность, n — кубитовое базис-
ное состояние описывается
2
𝑛𝑛
— мерным вектором. В рамках дираковской системы обозначений этот вектор будет
представлен цепочкой длиной n, а вектор — столбец будет составлен из
2
𝑛𝑛
компонентов. Записать состояние 12 ку-
битов с помощью вектор столбца представляется достаточно трудоемким, так как число элементов в нем составит
2
12
= 4096
. Использование дираковской системы обозначений имеет и другие преимущества, которые становятся
очевидными при работе с такими понятиями, как операторы и разного рода векторные произведения.
Ещё одним представлением состояния кубита является его наглядная геометрическая интерпретация в виде точки
на единичной сфере, — сфере Блоха (рисунок 4). [2]
Северный и южный полюса сферы обычно выбираются под базисные состояния |
0
⟩
и |
1
⟩
. Координатами точки слу-
жат два параметра
𝜃𝜃
и
𝜙𝜙
, которыми можно описать состояние кубита используя следующую формулу:
|
𝜓𝜓⟩
= (cos
𝜃𝜃
2 |0
⟩
+
𝑒𝑒
𝑖𝑖𝑖𝑖
sin
𝜃𝜃
2 |1
⟩
)
Квантовый компьютер является многокубитовым вычислительным устройством. Система из нескольких кубитов обра-
зует квантовый регистр. В классическом компьютере в каждый момент времени регистр представляет собой конкретную
последовательность из 0 и 1 (рисунок 5). В квантовом компьютере регистр до измерения состояния не является точно опре-
деленным и описывается линейной композицией с комплексными числами n-битовых состояний вида:
|
𝜓𝜓⟩
=
𝑦𝑦
1
|00. .00
⟩
+
𝑦𝑦
2
|00. .01
⟩
+
𝑦𝑦
3
|00. .10
⟩
…
𝑦𝑦
𝑛𝑛
|11. .11
⟩
.
Вероятность обнаружения квантового компьютера в состоянии
|00. .00
⟩
равна
|
𝑦𝑦
1
|
2
, вероятность нахождения
в состоянии
|00. .10
⟩
равна
|
𝑦𝑦
2
|
2
, и т. д.
К примеру, вектор состояния регистра из двух кубитов вычисляется с помощью произведения Кронекера (тензор-
ного произведения) двух вектор-столбцов, описывающих состояния перемножаемых кубитов:
|
ѱ⟩
=
�
𝛼𝛼
1
𝛽𝛽
1
� ⨂ �
𝛼𝛼
2
𝛽𝛽
2
�
=
�
𝛼𝛼
1
∙ �
𝛼𝛼
2
𝛽𝛽
2
�
𝛽𝛽
1
∙ �
𝛼𝛼
2
𝛽𝛽
2
�
�
=
�
𝛼𝛼
1
𝛼𝛼
1
𝛽𝛽
1
𝛽𝛽
1
𝛼𝛼
2
𝛽𝛽
2
𝛼𝛼
2
𝛽𝛽
2
�
.
"
⨂
"
−
тензорное произведение.
|
01
⟩
= |0
⟩
⨂
|1
⟩
=
�
1
∙ �
01
�
0
∙ �
01
�
�
=
�
0
1
0
0
�
,
|
11
⟩
= |1
⟩
⨂
|1
⟩
=
�
0
∙ �
01
�
1
∙ �
01
�
�
=
�
0
0
0
1
�
.
Любая логическая операция с кубитами называется квантовым вентилем, или гейтом. По числу кубитов преобра-
зователи делятся на однокубитные и многокубитные. Преобразователь переводит одно состояние кубита (а
в многокубитном случае — квантового регистра) в другое. Квантовым преобразованием называют унитарное преоб-
разование вектора состояния квантовой системы. С квантовыми системами можно производить только линейные уни-
тарные преобразования, при этом любое линейное унитарное преобразование допустимо. [5]
Скорее всего, все разработанные и реализованные к моменту создания квантового компьютера алгоритмы будут упако-
ваны в некий «Фонд алгоритмов и программ», библиотеку квантовых алгоритмов, которая будет связана с устройством,
выполняющим квантовые вычисления. Вполне вероятно, что это будет некий «квантовый сопроцессор», которым управля-
ет обычный процессор при помощи каких-либо хитроумных устройств, которые позволяют выполнять две основные задачи:
подготовка необходимых унитарных преобразований для выбранного квантового алгоритма и инициализация входных куби-
тов. На выходе этого «квантового сопроцессора» будут производиться измерения, а их результат сообщаться основному
процессору, производящему вычисления. Таким образом, программировать само квантовое вычислительное устройство
никто не будет; его будет «программировать» классический компьютер — настраивать гейты, связывать их друг с другом,
инициализировать кубиты и запускать квантовые вычисления. [3]
Квантовая схема алгоритма Гровера представлена на рис. 6.
Рассмотрим неупорядоченную базу данных схемотехнических решений, содержащую 25000 файлов. Необходимо,
быстро найти ровно один файл. Для того чтобы решить эту задачу на обычном компьютере, в худшем случае, придётся
перебрать все 25000
файлов, а в среднем 12500. На квантовом компьютере необходимо и достаточно произвести 158
итераций, чтобы найти данный файл. В общем случае алгоритм Гровера позволяет выполнить поиск требуемой файла
за
𝑂𝑂�√𝑁𝑁�
шагов. [6]
Do'stlaringiz bilan baham: |
