Квантовые вычисления для программистов



Скачать 385.26 Kb.
Pdf просмотр
Дата13.02.2017
Размер385.26 Kb.
Просмотров102
Скачиваний0

Квантовые вычисления для программистов
Васильев А.В.
1 Введение
Начало работ в области квантовых вычислений связывается со статьей [6], опубликованной
Ричардом Фейнманом в 1982 году и посвященной компьютерному моделированию квантово- механических процессов на вычислительных машинах. Он заметил, что с ростом размерности физической задачи пространство состояний возрастает экспоненциально, поэтому эффектив- ное моделирование многочастичной квантовой механики на классическом компьютере невоз- можно. Исходя из этого, Фейнман выдвинул идею квантового компьютера  компьютера,
использующего в своей основе квантовые эффекты, такие, как суперпозиция и, главное, за- путанность. С этой работы начались современные исследования проблемы использования квантово механических эффектов при решении задач, требующих больших вычислительных ресурсов.
Впервые формальная модель универсального квантового компьютера (квантовая машина
Тьюринга) была предложена П. Бениоффом году и развита Д. Дойчем [4]. Более наглядная модель квантовых вычислений (эквивалентная квантовой машине Тьюринга)  квантовые схемы, была предложена Д. Дойчем [5].
Отметим, что квантовые модели вычислений не нарушают тезис Тьюринга-Черча, т.к. мо- гут быть промоделированы на детерминированных аналогах. Различие между классическими и квантовыми моделями проявляются лишь в эффективности вычислений.
В чем же преимущества квантовых вычислений и какие у них слабости?
Наибольшие надежды возлагаются на квантовый параллелизм  возможность кванто- вого регистра находиться одновременно во всех своих состояниях. Так, если классический n
-битный регистр находится ровно в одном из своих состояний, то n-битный квантовый ре- гистр сразу во всех 2
n базисных состояниях. С одной стороны, это позволяет производить вычисления сразу на множестве наборов, в том числе на всех наборах сразу. Однако непо- средственное применение этого приема ничего не дает, поскольку достоверно извлечь нужный ответ не удастся. Потребуется преобразование состояния таким образом, чтобы нужный ответ получил бы большую амплитуду, а значит проявился при измерении с большой вероятностью.
В решении указанной проблемы может помочь другая особенность квантовых вычислителей 
наличие интерференции между состояниями, возникающей из-за того, что новые амплитуды базисных состояний оказываются линейными комбинациями старых амплитуд. Это позволяет строить алгоритмы таким образом, чтобы неверные решения исчезали за счет деструктивной интерференции (уменьшающей амплитуду), в то время как желаемые состояния усиливались при конструктивной интерференции (увеличивающей амплитуду).
Важной особенностью также является возможность создавать запутанные состояния
(entangled states) совокупности кубит, когда невозможно приписать определенное состояние каждому из них. Запутанные состояния можно задать экспоненциальным числом комплекс- нозначных амплитуд, а для не запутанного состояния достаточно их линейного числа. При
1
этом квантовая запутанность является необходимым условием для экспоненциального уско- рения в квантовых вычислениях. Джозса и Линден показали [7], что если максимальный ранг
Шмидта (дискретная мера двухчастичной запутанности) при квантовых вычислениях явля- ется константой (не зависит от числа кубит), то такое вычисление можно за полиномиальное время смоделировать на квантовом компьютере. Более сильный результат был получен Вида- лом [11]. Результат состоит в том, что эффективное (за полиномиальное время) классическое моделирование возможно, даже если максимальное число Шмидта полиномиально зависит от числа кубит.
Слабости квантовых вычислений являются продолжением их сильных сторон. Так, кван- товые вычисления происходят в черном ящике, а ответ можно получить лишь в результате измерения, которое является вероятностным процессом и приводит к безвозвратной потере информации об амплитудах полученных базисных состояний (об их величине можно судить лишь по статистике многократных экспериментов). Кроме того, в классических алгоритмах можно прервать вычисления, если ответ уже получен. Квантовые же алгоритмы всегда вы- полняются до конца (в модели с единственным финальным измерением), что также требует специальной их организации. Поэтому разработка квантовых алгоритмов требует особой ин- туиции  классические подходы срабатывают далеко не всегда.
Еще одна особенность квантовых вычислений  обратимость используемых преобразова- ний  не представляет проблемы, если нет ограничений на размер квантового регистра. Од- нако при довольно умеренных ограничениях (порядка O(log n) кубит, где n  длина входного набора) вычисление многих функций оказывается затруднено, а соответствующие задачи в таких моделях с ограничениями могут иметь экспоненциальную сложность [9].
Отметим также, что многочастичная запутанность, будучи необходимым условием кванто- вого ускорения, является и главным останавливающим фактором на пути к созданию кван- тового компьютера. Для эффективных вычислений необходимо не только управлять, но и сохранять квантовую запутанность, чему мешает процесс декогерентности. В современной трактовке декогерентность  разрушение квантового состояния (и, главное, его запутанно- сти) под действием внешней среды.
2 Математический аппарат квантовых вычислений  Ли- нейная алгебра
Квантовые вычисления основываются на том, что носителями информации являются квантово- механические системы из микромира, а, следовательно, их состояния и преобразования опи- сываются постулатами квантовой механики. Приведем необходимые обозначения и сведения из книги [8].
Пусть H
d
 d-мерное гильбертово пространство (комплексное линейное векторное про- странство с определенным в нем скалярным произведением). Для обозначения элементов пространства H
d принято использовать bra-ket нотацию Дирака: |? и ?| для вектора- столбца и вектора-строки, соответственно. Также будем использовать ?
1
| ?
2
для скалярного произведения.
Тензорное произведение. Введем обозначение A ? B  тензорное (правое кронекерово)
произведение матриц A, B.
2

Для A =
?
?
?
a
11
· · ·
a
1n a
m1
· · ·
a mn
?
?
?
и B =
?
?
?
b
11
· · ·
b
1k b
l1
· · ·
b lk
?
?
?
A ? B =
?
?
?
a
11
B
· · ·
a
1n
B
a m1
B · · ·
a mn
B
?
?
?
Для векторов |a
1
, . . . , |a q
?
H
2
будем также использовать обозначения
|a
1
? · · · ? |a q
= |a
1
. . . a q
?
H
2
q
Стандартный вычислительный базис в H
2
q
В качестве стандартного базиса в H
2
рас- сматривается следующий:
|0 =
1 0
,
|1 =
0 1
Для пространств H
d большей размерности вводятся дополнительные обозначения:
|1
= |00 . . . 0
= (100 . . . 0 . . . 0)
T
|2
= |00 . . . 1
= (010 . . . 0 . . . 0)
T
|i
= |bin(i ? 1)
= (000 . . . 1 . . . 0)
T
|d
= |11 . . . 1
= (000 . . . 0 . . . 1)
T
Здесь у вектора |i на i-й позиции 1, а все остальные компоненты нулевые.
Указанные равенства легко проверить. Например, рассмотрим вектор-столбец, соответ- ствующий |010 = |3 :
|10 = |1 ? |0 =
0 1
?
1 0
=
?
?
?
?
0 ·
1 0
1 ·
1 0
?
?
?
?
=
?
?
?
?
0 0
1 0
?
?
?
?
|010 = |0 ? |10 =
?
?
?
?
?
?
?
?
?
?
?
?
1 ·
?
?
?
?
0 0
1 0
?
?
?
?
0 ·
?
?
?
?
0 0
1 0
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
=
?
?
?
?
?
?
?
?
?
?
?
?
0 0
1 0
0 0
0 0
?
?
?
?
?
?
?
?
?
?
?
?
= |3 .
Очевидно, что система векторов |1 , |2 , . . . , |i , . . . , |d образует ортонормированный ба- зис в пространстве H
d
. Будем также обозначать указанные векторы через |00 . . . 0 , |00 . . . 1 ,
. . . , |bin(i ? 1) , . . . , |11 . . . 1 , где bin(i)  это двоичное представление числа i. Такая система векторов называется стандартным вычислительным базисом. В дальнейшем будем рассмат- ривать вычисления только в этом базисе.
3

Пространство состояний. Согласно первому постулату, с любой изолированной физиче- ской системой можно связать гильбертово пространство, называемое пространством состоя- ний системы. Состояние системы полностью описывается единичным вектором из простран- ства состояний, называемым вектором состояния (или, сокращенно, состоянием).
Квантовый бит (кубит) является ключевым понятием теории квантовых вычислений. Он рассматривается как квантово-механическая система, состояние которой описывается ком- плекснозначным вектором двумерного гильбертова пространства H
2
, т.е.
|? = ? |0 + ? |1 ,
где векторы |0 и |1 образуют ортонормированный базис в H
2
, а комплексные числа ? и
?
удовлетворяют условию |?|
2
+ |?|
2
= 1
. Таким образом, в отличие от классического бита кубит может одновременно находиться в суперпозиции своих базисных состояний |0 и |1 с амплитудами ? и ? соответственно.
Каждое состояние кубита |? = ? |0 + ? |1 можно представить в виде
|? = cos
?
2
|0 + e i?
sin
?
2
|1 ,
где 0 ? ? < 2?, 0 ? ? ? ?.
Пусть e i? ?
2
= x + iy и обозначим z = cos
?
2
. Тогда x
2
+ y
2
+ z
2
= 1
, т.е. каждое состояние кубита соответствует точке на единичной сфере, задаваемой полярными координатами ? и ?
и называемой сферой Блоха.
VCPC
EUROPEAN CENTRE FOR PARALLEL COMPUTING AT VIENNA
'
&
$
%
The Bloch Sphere
QIA Meeting, TechGate
5
Ian Glendinning / February 16, 2005
Описанное представление иллюстрирует состояние кубита в общем случае. Однако в слу- чае вещественных амплитуд условие нормировки ?
2
+ ?
2
= 1
есть уравнение единичной окружности, и, следовательно, кубит может быть представлен точкой на ней:
4

|?
?
|0
?
|1
?
?
Таким образом, состояние кубита в вещественном случае вырождается в
|? = cos ? |0 + sin ? |1
для некоторого ? ? [0, 2?).
Составные системы. При рассмотрении квантового регистра (т.е. совокупности отдель- ных кубит), квантовая механика постулирует, что пространство состояний такой составной системы будет описываться тензорным произведением пространств состояний подсистем. На- пример, если n кубит находятся в состояниях |?
1
, |?
2
, . . . , |?
n
, то состояние |? квантового регистра, состоящего из этих кубит, будет выражаться через тензорное произведение их со- стояний:
|? = |?
1
? |?
2
? · · · ? |?
n
Такие состояния называются разложимыми.
В то же время существуют так называемые неразложимые или запутанные состояния квантовых регистров, которые не могут быть представлены тензорным произведением состо- яний отдельных кубит. Такими состояниями являются, например, ЭПР-пары или состояния
Белла, играющие ключевую роль в квантовой телепортации и сверхплотном кодировании.
Таким образом, постулируется, что регистр из n кубит в общем случае может быть описан единичным вектором из пространства H
2
n
:
2
n i=1
?
i
|i
, где
2
n i=1
|?
i
|
2
= 1.
Такие линейные комбинации принято называть суперпозициями базисных состояний |i с амплитудами ?
i
Измерение. На классическом компьютере считывание значений переменных не представ- ляет сложности. В квантовых моделях вычислений ситуация сложнее. Квантовая система должна функционировать изолированно  любое вмешательство в ее работу (в том числе считывание результатов вычисления) приводит к изменению состояния.
И, хотя кубиты и могут одновременно находиться в различных состояниях, информация об этом доступна лишь опосредованно  путем измерения состояния. Причем это вероятностный процесс, т.е., измеряя суперпозицию (состояние системы) |? =
i
?
i
|i
, мы получим любое из состояний |i с вероятностью |?
i
|
2 5

При этом состояния, отличающиеся лишь фазовым множителем e i?
считаются неотличи- мыми, поскольку при измерении |? и e i?
|?
имеют одинаковое распределение вероятностей получения базисных состояний.
Таким образом, из бесконечного объема информации, который можно сохранить в ам- плитудах квантового бита, доступен лишь единственный бит, соответствующий базисному состоянию.
Другой вариант извлечения большого объема информации из одного кубита состоит в многократном копировании результатов вычислений и статистическом анализе результатов вычислений. Однако и этот вариант невозможен ввиду того, что в общем случае нельзя клонировать неизвестное квантовое состояние.
Впрочем, это не означает бесполезность квантовых суперпозиций, а лишь указывает на невозможность их классического использования.
Мы будем использовать вариант квантового измерения, называемый проективным изме- рением. Для задания такого измерения достаточно перечислить полный набор ортогональных проекторов P
m
, удовлетворяющих соотношениям m
P
m
= I
и
P
m
P
m
=
P
m
,
если m = m
I,
иначе
Вероятность исхода m в таком случае можно выразить как
P r(m) = ||P
m
|? ||
2 2
= ?| P

m
P
m
|? ,
а состоянием |? системы после измерения будет
|? =
P
m
|?
P r(m)
Динамика изменения. Следующий постулат гласит, что динамика изменения состояния замкнутой квантовой системы описывается унитарными преобразованиями. Другими слова- ми, состояние |?
1
системы в момент времени t
1
связано с состоянием |?
2
в момент времени t
2
следующим образом:
|?
1
= U |?
2
,
где U  это унитарный оператор.
Унитарные операторы. Множество унитарных операторов континуально, но их можно сколь угодно точно представить в виде произведения унитарных операций из некоторого конечного универсального набора [8].
Таковым набором является, например, совокупность следующих операторов:
H =
1
?
2 1
1 1 ?1
; S =
1 0 0
i
; T = ?/8 = e i?/8
e
?i?/8 0
0
e i?/8
;
CNOT =
?
?
?
?
1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0
?
?
?
?
6

Известно [8], что любое однокубитное унитарное преобразование можно с произвольной точностью представить в виде произведения O(log c
1/ )
операторов H и ?/8 (константа c приблизительно равна 2), а произвольное унитарное преобразование, действующее на q куби- тах может быть представлено в виде произведения O(q
2 4
q
)
однокубитных и CNOT операто- ров. Фазовый оператор S включается в стандартный набор для реализации контролируемых операторов и для организации помехоустойчивых вычислений.
Следующие унитарные операторы называются операторами вращения, потому что соот- ветствуют вращениям на угол ? вокруг осей €x, €y и €z сферы Блоха:
R

x
(?) =
cos
?
2
?i sin
?
2
?i sin
?
2
cos
?
2
;
R

y
(?) =
cos
?
2
? sin
?
2
sin
?
2
cos
?
2
;
R

z
(?) =
e
?
i?
2 0
0
e i?
2
Вообще, т.к. любой унитарный оператор сохраняет норму вектора, он может интерпрети- роваться на сфере Блоха как вращение вокруг некоторой оси [8]. Заметим, что R

n
(?)·R

n
(?) =
R

n
(? + ?)
для любой фиксированной оси €n.
Кроме того, известно, что любой унитарный оператор U представим в виде:
U = e i?
R

z
(?)R

y
(?)R

z
(?)
для некоторых вещественных чисел ?, ?, ? и ?. Это соответствует тому факту, что любое вращение точки на трехмерной сфере можно сконструировать из ортогональных вращений.
Заметим, что вращения на угол 2? не приводят к тождественному преобразованию  для этого требуется поворот на угол 4?:
R

z
(2?) = ?I,
R

z
(4?) = I.
Получаемые в результате применения таких операторов состояния отличаются лишь на множитель ?1, не проявляющийся при измерении, и поэтому соответствуют одной и той же точке на сфере Блоха.
Таким образом, каждому вращению на сфере Блоха соответствуют два различных уни- тарных преобразования, что формализуется в теории групп как двойное покрытие группы
SO(3)
группой SU(2).
Контролируемые операторы, реализующие некоторое преобразование при выполнении определенного условия, являются основой для квантового параллелизма. Пусть кубиты |c
1
,
|c
2
, . . . , |c q
находятся в некотором базисном состоянии. Оператор C
q
(U )
, управляемый ку- битами |c
1
, |c
2
, . . . , |c q
, можно задать уравнением вида
C
q
(U ) |c
1
|c
2
. . . |c q
|? = |c
1
|c
2
. . . |c q
U
c
1
·c
2
···c q
|? ,
т.е. унитарное преобразование U применяется к целевому кубиту |? , если все управляющие кубиты |c
1
, |c
2
, . . . , |c q
находятся в базисном состоянии |1 , в противном случае применя- ется тождественное преобразование I. В квантовых схемах из функциональных элементов
7
такие операторы принято обозначать следующим образом:
|c
1

|c
2

|c q

|?
U
Известно, что произвольный контролируемый оператор C
q
(U )
, где U  однокубитное уни- тарное преобразование, можно реализовать при помощи O(q
2
)
однокубитных и CNOT опера- торов.
Контролируемые операторы можно обобщить на случай, когда для срабатывания управ- ляющие кубиты должны находиться в состоянии |0 , а не |1 . Для этого до и после применения контролируемого оператора соответствующий кубит инвертируется при помощи оператора отрицания X. Кроме того, вводится специальное обозначение:
|c
1

|c
2

|c q

|?
U
=
|c
1
X

X
|c
2

|c q
X

X
|?
U
Пусть d = 2
q
, а |1 , |2 , . . . , |i , . . . , |d  это ортонормированный базис в d-мерном гиль- бертовом пространстве.
Обозначим через C
q i
(U )
(или C
i
(U )
) контролируемый оператор с q управляющими куби- тами, если преобразование U применяется к целевому регистру, только когда управляющий регистр находился в состоянии |i . На схемах будем обозначать такой оператор следующим образом:
|c
1

|c
2

|i
?
?
?
?
?
?
?
?
?
?
?
|c q

|?
U
3 Квантовые модели вычислений
Неформально, квантовые алгоритмы состоят в применении последовательности унитарных операторов к начальному состоянию кубитов, т.е. последовательность умножений унитарных матриц на комплексный вектор. При этом, последовательность матриц можно заменить од- ной (их произведением), из чего следует, что квантовый алгоритм при отсутствии внешнего воздействия, по сути, задается унитарной матрицей. В общем случае, это справедливо лишь для участков квантового алгоритма между взаимодействиями с внешней средой.
3.1 Квантовая машина Тьюринга
Квантовая машина Тюринга (QTM), основанная на использовании квантовой суперпозиции 
квантовый аналог вероятностной машины Тьюринга  впервые была определена Дойчем [4].
8

Дойч предположил, что эта модель может быть эффективнее, чем классическая, для некото- рых задач. Он также показал существование универсальной квантовой машины Тьюринга (а также модели квантовых сетей  квантовый аналог классических схем). Однако его модель универсальной квантовой машины Тьюринга имела один недостаток  моделирование других квантовых машин Тьюринга могло иметь экспоненциальную сложность. Эта проблема бы- ла решена Бернштейном и Вазирани (1993) [3]. Они показали существование универсальной
QTM, способной моделировать другие QTM в полиномиальное время.
Квантовая машина Тьюринга. Как и в случае недерминированных машин Тьюринга в квантовых машинах может быть несколько команд с заданной левой частью:
qa
?
1
?? q
(1)
a
(1)
{L, S, R}
?
2
?? q
(2)
a
(2)
{L, S, R}
· · ·
?
r
?? q
(r)
a
(r)
{L, S, R},
причем каждая из них помечена некоторым комплексным числом. Семантика выполнения таких команд заключается в параллельном их выполнении с амплитудой, заданной числом
?
i
Соответственно, можно задать функцию переходов
? : Q Ч ? Ч Q Ч ? Ч {L, S, R} ? C,
где C  это множество комплексных чисел, а ?(q, a, q , a , d)  амплитуда, с которой машина,
находясь в состоянии q и считывая a на ленте, перейдет в состояние q , запишет a на ленту и сдвинется в направлении d на входной ленте.
Определение 3.1. Квантовая Машина Тьюринга (Quantum Turing Machine)  это пятерка
M = ?, Q, ?, q
1
, q
0
, состоящая из конечного множества состояний Q, начального состоя- ния q
1
? Q
, заключительного состояния q
0
? Q
, конечного входного алфавита ?, и функции переходов ?, удовлетворяющей условию
(q ,a ,d)?QЧ?Ч{L,S,R}
|?(q, a, q , a , d)|
2
= 1
для любых (q, a) ? Q Ч ?.
Аналогично детерминированной модели определяются понятие конфигурации, начальной и заключительной конфигураций. В общем случае конфигурация может рассматриваться как комбинация
?
1
c
1
+ . . . + ?
m c
m
+ . . .
базисных конфигураций. Ассоциируя базисные конфигурации с элементами ортонормирован- ного базиса в гильбертовом пространстве, замечаем, что конфигурации квантовой машины
Тьюринга являются единичными векторами в соответствующем векторном пространстве, а функция переходов задает в нем линейное отображение U
?
Согласно постулатам квантовой механики отображение U
?
должно быть унитарным. Го- ворят, что квантовая машина Тьюринга является хорошо сформированной (well-formed), если линейный оператор U
?
является унитарным.
9

Когда машина M, находящаяся в суперпозиции своих конфигураций ? =
?
i c
i изме- ряется, то с вероятностью |?
i
|
2
результатом измерения является конфигурация c i
. Входное слово принимается, если результатом измерения является принимающая конфигурация, и отвергается, если результатом измерения является отвергающая конфигурация. Таким об- разом, результат вычисления является вероятностным. Аналогично вероятностной модели определяются критерии распознавания с ограниченной и неограниченной ошибкой языка L
квантовой машиной Тьюринга.
Заметим, что представление квантовых алгоритмов машинами Тьюринга не являются удо- бочитаемым, поэтому в области квантовых вычислений преобладает схемное представление алгоритмов (в виде квантовых схем из функциональных элементов или квантовых ветвя- щихся программ) ввиду его наглядности. Более того, подавляющее большинство известных квантовых алгоритмов описаны в схемном представлении.
Квантовые классы сложности
• BQP
 класс языков распознаваемых с ограниченной ошибкой квантовой машиной
Тьюринга за полиномиальное время.
• PrQP
 класс языков распознаваемых с неограниченной ошибкой квантовой машиной
Тьюринга за полиномиальное время.
Прежде всего, следует отметить, что квантовые вычислители не могут решать проблемы,
не разрешимые на классической машине Тьюринга. Это следует из того, что все вычислимое в квантовой модели может быть смоделировано на классической машине просто вычислени- ем амплитуд суперпозиции и записи их на рабочую ленту. Различие между классическими и квантовыми вычислениями лежит только в вопросе их сложности. Тривиальное моделиро- вание квантовых вычислений классическим экспоненциально по времени и памяти. Bernstein и Vazirani [3] показали, что моделирование может быть полиномиально по памяти, хотя все еще экспоненциально по времени.
Известны следующие соотношения:
• BQP ? PSPACE
[3]

Соотношение между классами BQP и NP неизвестно.
3.2 Квантовые схемы
Однородные вычислительные модели, такие как машина Тьюринга, конечные автоматы, ори- ентированы на решение вычислительной проблемы с произвольной длиной входа. Далее будут рассмотрены неоднородные модели вычислений, обрабатывающие входные слова фиксиро- ванной длины.
Наиболее распространенной квантовой моделью вычислений являются квантовые схемы
(quantum circuits). В основе определения квантовых схем лежит понятие квантового вентиля
(quantum gate).
Определение 3.2. Квантовым вентилем на q кубитах называется унитарное отображе- ние в гильбертовом пространстве H
2
q
= H
2
? . . . ?
H
2
, воздействующее нетривиальным образом на фиксированное (не зависящее от q) число кубит.
10

Определение 3.3. Квантовая схема на q кубитах  это унитарное отображение в гиль- бертовом пространстве H
2
q
=
H
2
? . . . ?
H
2
, которое может быть представлено в виде соединения конечного числа квантовых вентилей.
Квантовые схемы принято изображать следующим образом:
|?
1
U
1
U
2
· · ·
U
l
NM
|?
2
· · ·
NM
|?
q
· · ·
NM
Сложностью квантовых схем называют число квантовых вентилей в ней. Известно [12],
что полиномиальные по сложности квантовые схемы равномощны полиномиальным по вре- мени квантовым машинам Тьюринга.
3.3 Примеры квантовых алгоритмов
Квантовые алгоритмы на основе ngerprinting. Пусть ? = ?
1
. . . ?
n
 входной набор,
а g(?)  значение характеристической функции, проверяющей наличие некоторого свойства у ?. ? обладает свойством g ?? g(?) = 0 mod m.
Повернем начальное состояние |0 на угол
? =
?g(?)
m
|0 ? cos ? |0 + sin ? |1 ? |0
?? g(?) = 0 mod m
|?
?
|0
?
|1
?
?
Пусть k
1
, . . . , k t
? {1, . . . , m ? 1}
. Повернем t кубит на углы
?
i
=
?k i
g(?)
m
|0 ? cos ?
i
|0 + sin ?
i
|1 ? |0
, если g(?) = 0 mod m
При t = O(log m) существует множество K = {k
1
, . . . , k t
}
, для которого P r error
< 1/m
11

|0
?
|1
?
|0
?
|1
?
|0
?
|1
?
|0
?
|1
?
Используя квантовый параллелизм и интерференцию, можно добиться значительного со- кращения числа кубит.
|0 ? |0 ? · · · ? |0
log t
? |0
?
1
?
t t
i=1
|i cos ?
i
|0 + sin ?
i
|1
?
i
=
2?k i
g(?)
m
|0
?
|1
?
Описанная схема проверки свойства g у входного набора ? реализуется следующим алго- ритмом:
12

|0
? log t
|0
?
1
?
t t
j=1
|j |0
?
1
?
t t
j=1
|j cos
2?k j
g(?)
m
|0 + sin
2?k j
g(?)
m
|1
?
1
t t
l=1
cos
2?k l
g(?)
m
|0
? log t
|0 + . . .
?
g = 0 ??
результат измерений  |0
? log t
|0
Возможно также обобщение данного подхода для проверки одновременного выполнения ряда свойств, закодированных функциями g
1
, g
2
, . . . , g l
. Для этого по входному набору ?
создается квантовая суперпозиция вида h
i
?
(j) = cos
?k i
g j
(?)
m
|0 + sin
?k i
g j
(?)
m
|1 |h
?
=
1
?
t t
i=1
|i h i
?
(1)
h i
?
(2) . . . h i
?
(l)
Неформально, это можно проиллюстрировать следующим образом:
Другими словами, здесь реализуется комбинация классического и квантового паралле- лизма: l кубит используются параллельно (в классическом смысле), и каждый из них парал- лельно (в квантовом смысле) вращается на t различных углов.
4 Квантовые вычисления для программистов
Разработка квантовых компьютеров ставит множество задач как для математиков, так и для инженеров. Причем обе категории исследователей движутся навстречу друг другу: одни раз- рабатывают быстрые и эффективные по памяти квантовые алгоритмы, а вторые продвига- ются в создании полномасштабных квантовых вычислителей, способных устойчиво работать достаточно продолжительное время.
13

Однако на данный момент вычислители сильно ограничены как по времени жизни систе- мы, так и по числу одновременно доступных кубит. Поэтому реалистичным представляется вариант гибридного квантового компьютера, состоящего из небольшого (по памяти) кванто- вого устройства, работающего под управлением классического компьютера, который задает последовательность применения унитарных операций, получает результаты измерения, а так- же может производить вспомогательные расчеты.
4.1 Задачи для программистов
Хотя создание квантовых компьютеров все еще находится в экспериментальной стадии, уже сейчас можно сформулировать задачи в классическом программировании, решение которых будет способствовать развитию области квантовых вычислений.

Эмуляция квантовых вычислений, в том числе эффективное моделирование квантовой запутанности. Последнее позволит решать задачи и проверять гипотезы в теории кван- товой информации.
Одним из вариантов эмуляции квантового сопроцессора могла быть стать разработка виртуального драйвера для популярных операционных систем, который позволит тести- ровать разнообразные квантовые алгоритмы, а также другие программные разработки,
связанные с функционированием квантовых вычислителей.

Разработка системы программирования квантового сопроцессора.
Данная задача тесно связана с предыдущей и может основываться на предположении,
что квантовый сопроцессор предоставляет некоторый интерфейс (через драйвер, уста- новленный в операционной системе), для взаимодействия с которым создается библио- тека классов, скажем на C#.
Такой набор классов основывается на возможности создания (инициализации) регистра квантовых битов в нулевом состоянии, применения базисных операций к произволь- ным кубитам регистра, а также измерение квантового регистра (получение результата вычислений).
Для удобства в библиотеке должны быть также реализованы общеупотребительные
квантовые операторы, поскольку их всегда можно выразить через базис. На основе данной библиотеки можно будет реализовывать известные эффективные квантовые ал- горитмы в виде обычной функции на языке вроде C#.

Разработка визуальной среды для конструирования и анализа квантовых алгоритмов.
Данная задача подразумевает создание инструментальных средств, позволяющих на- глядно представлять квантовые алгоритмы в модели квантовых схем из функциональ- ных элементов. Разрабатываемая среда должна предоставлять средства для разложе- ния отдельных квантовых преобразований по вычислительному базису, а также объеди- нения отдельных частей алгоритма в составные операторы. Кроме того, предполагается реализации оптимизационных процедур для сокращения числа элементарных операто- ров, а также для сокращения числа шагов за счет параллельного выполнения некоторых операторов.
14

Основные обозначения a
 наименьшее целое число, не меньшее a.
a
 наибольшее целое число, не превосходящее a.
log a = log
2
a
|K|
 мощность конечного множества K.
B
n
 множество булевых функций от n переменных.
Нормы вектора a = (a
1
, . . . , a d
)
:
||a||
1
=
d i=1
a i
,
||a||
2
=
d i=1
|a i
|
2
H
d
 d-мерное комплексно-значное векторное (Гильбертово) пространство с нормой ||.|| =
||.||
2
U
?
 матрица, комплексно-сопряженная к U.
U
T
 транспонированная матрица U.
U

= (U
T
)
?
 эрмитово сопряжение к U.
|a
 вектор-столбец (кет-вектор) a.
b| = (|b
T
)
?
 вектор-строка (бра-вектор) b
?
a | b
 скалярное произведение |a и |b .
|a ? |b
 тензорное (правое кронекерово) произведение векторов a, b.
Для |a = (a
1
, . . . , a d
)
T
и |b = (b
1
, . . . , b l
)
T
|a ? |b = (a
1
b
1
, a
1
b
2
, . . . , a
1
b l
, a
2
b
1
, . . . , a d
b l
)
T
|a |b = |ab = |a ? |b
|a b| = |a ? b|
A ? B
 тензорное (правое кронекерово) произведение матриц A, B
Для A =
?
?
?
a
11
· · ·
a
1n a
m1
· · ·
a mn
?
?
? и
B =
?
?
?
b
11
· · ·
b
1k b
l1
· · ·
b lk
?
?
?
A ? B =
?
?
?
a
11
B
· · ·
a
1n
B
a m1
B · · ·
a mn
B
?
?
?
A
?d
= A ? A ? · · · ? A
d
(A ? B)(|? ? |? ) = A |? ? B |?
15

|?
1
? |?
1
, |?
2
? |?
2
= ?
1
| ?
2
?
1
| ?
2
I =
1 0 0 1
 тождественное преобразование в H
2
H =
1
?
2 1
1 1 ?1
 преобразование Адамара (Уолша-Адамара).
R

y
(?) =
cos
?
2
? sin
?
2
sin
?
2
cos
?
2
 вращение на угол ? вокруг оси €y сферы Блоха.
C(R

y
(?)) =
?
?
?
?
1 0 0
0 0 1 0
0 0 0 cos
?
2
? sin
?
2 0 0
sin
?
2
cos
?
2
?
?
?
?
 контролируемое вращение.
f (n) = O(g(n))
 существуют положительные константы c и n
0
, такие, что 0 ? f(n) ? cg(n)
для всех n ? n
0
f (n) = ?(g(n))
 существуют положительные константы c и n
0
, такие, что 0 ? cg(n) ? f(n))
для всех n ? n
0
f (n) = ?(g(n))
, если f(n) = O(g(n)) и f(n) = ?(g(n)).
Список литературы
[1] Bennett, C.H. Logical reversibility of computations / C.H. Bennett // IBM Jounal of Res.
Develop.  1973.  V. 17.  P. 525-532.
[2] Benio, P.A. Quantum mechanical hamiltonian models of turing machines / P.A. Benio //
Journal of Statistical Physics.  1982.  V. 29, N 3.  P. 515-546.
[3] Bernstein, E. Quantum complexity theory / E. Bernstein, U. Vazirani // SIAM J. Comput.
 1997.  V. 26, N 5.  P. 1411-1473.
[4] Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer // Proceedings of the Royal Society of London.  Series A, Mathematical and
Physical Sciences.  1985.  PP. 97117.
[5] Deutsch D. Quantum computational networks // Proceedings of the Royal Society of London.
Series A, Mathematical and Physical Sciences.  1989.  PP. 7390.
[6] Feynman R. Simulation physics with computers // Int. J. of Theor. Phys.  1982.  V. 21. 
No 467.
[7] Jozsa R., Linden N. On the role of entanglement in quantumcomputational speed-up //
Proceedings: Mathematical, Physical and Engineering Sciences.  2003.  Vol. 459, no. 2036.
 PP. 20112032.
16

[8] Нильсен, М. Квантовые вычисления и квантовая информация / М. Нильсен, И. Чанг;
Пер. с англ. под ред. М.Н. Вялого и П.М. Островского с предисловием К.А. Валиева. 
М.: Мир, 2006.  824 с.
[9] Sauerho, M. Quantum branching programs and space-bounded nonuniform quantum complexity / M. Sauerho, D. Sieling // http://xxx.lanl.gov/archive/quant-ph.  ph/0403164.
 2004.
[10] Shor, P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer / P. Shor // SIAM J. on Computing.  1997.  V. 26, N 5.  P. 1484-1509.
[11] Vidal G. Ecient classical simulation of slightly entangled quantum computations // Physical
Review Letters.  2003.  Vol. 91, no. 14.  P. 147902. 120.
[12] Yao A. Quantum circuit complexity / A. Yao // Proc. 34th IEEE Symposium on Foundation of Computer Science.  1993.  P. 352-361.
17


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал