Квантовый компьютер: современное состояние



Скачать 118.66 Kb.

Дата13.02.2017
Размер118.66 Kb.
Просмотров75
Скачиваний0

Квантовый компьютер: современное состояние
Ю.И.Ожигов
1,2 1 Московский Государственный Университет им. М.В.Ломоносова
Факультет ВМК, Кафедра суперкомпьютеров и квантовой информатики
2 Физико-Технологическсий институт РАН, лаборатория физики квантовых компьтеров ozhigov@cs.msu.su
1 / 31

Содержание
Краткое описание квантовой механики
Быстрые квантовые алгоритмы
Реализация квантовых гейтов
Декогерентность - главное препятствие на пути к QC
2 / 31

Квантовые состояния как линейные комбинации классических
Процедура квантования - переход к линейной оболочке. L(K) состоит из линейных комбинаций |? =
j
?
j
|j
, где все |j ? K считаются взаимно ортогональными с единичной нормой. Объединение реальных систем приводит к тензорному произведению
- что ведет к экспоненциальному росту размерности пространства квантовых состояний.
Основная проблема: Сколько элементов может быть в множестве классических состояний K?
Q
X
K
(K)
K
1
(K
1
)
K
2
(K
2
)
Figure:
Объединение реальных систем приводит к тензорному произведению
3 / 31

Дискретизация
Для перехода к квантовой механике необходимо дискретизировать пространство-время,
выбрав зерно разрешения dx, dt. От этого зависят пробные заряды и массы частиц. Если устремить dx ? 0, dt ? 0, пробные заряды и массы будут меняться, но предстазания наблюдений будут только уточняться (теорема Боголюбова о перенормировках квантовой механики).
Это доказывает математическую корректность квантовой теории одной частицы,
взаимодействующей с полем. Эксперимент (например, вычисленное значение электронного спина) показывает точность предсказаний квантовой теории до 10 7
- в случае одной частицы.
Для многих частиц ситуация неясна. Для 3 частиц найден эффективный алгоритм вычисления квантовой динамики (Л.Фаддеев и его группа, 2007). Для большего числа частиц есть только проект квантового компьютера.
4 / 31

Размерность тензорного произведения пространств есть произведение их размерностей.
Размерность пространства квантовых состояний растет как экспонента от числа реальных частиц.
Квантовый процесс невозможно имитировать в точности классическими средствами даже на одном шаге.
5 / 31

Эволюция квантового состояния во времени
1. Эволюция в присутствии наблюдателя, который измеряет систему. Измерение системы, находящейся в состоянии |? =
j
?
j
|j есть случайная величина, принимающая значения |j с вероятностями p j
= |?
j
|
2 2. Эволюция в отсутствии наблюдателя: решение уравнения Шредингера ih ?
|? = H|?
|?(t) = U
t
|?(
0) , U
t
= e
?
i h
Ht
U
t
: |?(
0) ? |?(t) - оператор эволюции, H = E
kin
+ E
pot
- эрмитов оператор энергии;
для одной частицы в потенциале V гамильтониан H =
p
2 2m
+ V (r ), p = ?ih
. Для конечномерного приближения H и U
t
- матрицы, |? - столбец, зависящий от времени.
6 / 31

В чем трудность моделирования на квантовом уровне
Операция z, x, y ? z, x, y ? x. В классическом случае она затронет только x и y.
В квантовом случае нам придется записывать ее результат для всевозможных z, которые непосредственно в этой операции не участвуют! Потому что квантовая операция z, x, y ? z, x, y ? x действует не на одном наборе x, y, z, а на всех таких наборах,
при любых z.
7 / 31

Что такое алгоритм и что такое вычисление
Алгоритм - это рецепт, что надо делать, точный рецепт, по шагам, но в сжатой форме, то есть с указанием возможных развилок и зацикливаний. Алгоритм, как правило, короткий, его можно написать на бумаге ручкой.
Вычисление - это практическая реализация рецепта. Она даже не всегда ведет к какому-то результату, и может длиться вечно.
Вычисление, как правило, нельзя воспроизвести вручную, за исключением математических формул, которые обладают сакральным смыслом. В прочих случаях для вычисления нужен специальный прибор - компьютер.
8 / 31

Описать квантовый алгоритм очень просто: это просто классический алгоритм, указывающий, какие именно операции и над какими кубитами надо проделать.
Но осуществить вычисление по квантовому алгоритму (квантовое вычисление) - классическим путем - НЕВОЗМОЖНО из за непреодолимого сложностного барьера.
9 / 31

Интеграл Фейнмана по путям - непрерывный аналог матричной механики
Если есть k шагов продолжительности dt: U
t
= U
k
U
k?
1
. . . U
0
, матричный элемент перехода будет u
t
(i , j ) =
q
1
,q
2
,...,q k
u dt
(q
1
, j )u dt
(q
2
, q
1
) . . . u dt
(i , q k
)
что в непрерывном случае дает оператор эволюции в виде фейнмановского ядра
K (
2, 1) =
?:
1?2
exp(
i h
S [?])D?
где действие S вдоль траектории ? есть
S [?] =
t
1
t
0
L( ?
x , x , t)dt, L = E
kin
? E
pot
, ? : x = x (t), t
0
? t ? t
1
. Эволюция имеет вид
?(
2) =
K (
2, 1)?(1)d1, 1 = x
1
,
2 = x
2 10 / 31

Классическая механика как следствие интерференции амплитуд
Классическая траектория ?
cl отличается от прочих тем, что на ней
?S[?
cl
]
??
=
0. Поэтому в интеграле
K (
2, 1) =
?:
1?2
exp(
i h
S [?])D?
окрестности классической траектории складываются конструктивно, а окрестности прочих
- деструктивно, если среднее действие на элементарном шаге превосходит постоянную
Планка h ? 10
?
27
erg sec
. Если же среднее действие мало, неклассические траектории могут дать серьезный вклад.
Необходимость применять квантовую механику зависит от продолжительности dt элементарного шага моделирования процесса, то есть от сценария процесса.
Например, в задаче вычисления возможных состояний ассоциации молекул можно считать ядра классическими, а электроны нужно считать - квантовыми (модель
Борна-Оппергеймера).
11 / 31

Р.Ф.Фейнман (1918-1988)
12 / 31

Квантовый компьютер как вызов квантовой теории
1. Квантовый алгоритм есть рецепт специально огранизованного классического управления Гамильтонианом H = H(t). Квантовое вычисление - соответствующая этому гамильтониану эволюция волновой функции квантового состояния определенной системы частиц.
Предположим, что нет никаких ограничений на размер множества K
классических состояний, подлежащих квантованию. Тогда эволюция волновой функции |? при этом может привести к непредсказуемому результату, который невозможно получить никаким классическим алгоритмом в обозримое время. Такие способы управления называются быстрыми квантовыми алгоритмами.
2. Всем математическим методам квантовой теории можно придать форму эффективных классических алгоритмов.
3. Физика квантовых компьютеров требует новых методов и более общего взгляда на область приложений квантовой механики.
4. Критерий качества математической модели: неизбежная редукция волновой функции от унитарной эволюции в ходе вычисления должна совпадать с наблюдаемой в экспериментах декогерентностью - спонтанным отклонением наблюдаемыой динамики от унитарного закона.
13 / 31

П.С.Шор
14 / 31

Л.К.Гровер
15 / 31

Квантовые гейты и подпрограммы
Гейты - элементарные унитарные операторы, затрагивающие явно 1-3 кубита. Из них комбинируются унитарные квантовые подпрограммы, реализующие полезные операции.
Примеры гейтов: NOT: x ? x ? 1. CNOT: x, y ? x, y ? x. CNOT- пример условного гейта. Любой гейт можно сделать условным, добавив управляющий кубит.
Примеры подпрограмм:
1). I
Ї
a
: |Ї
b ? (?
1) |Їb , где = 0, если a|b = 0 и = 1 в противном случае.
2). Оператор Гровера G = ?I
?
0
I
x tar
, где |?0 =
1
?
N
N?
1
j =
0
|j
, x tar
- решение уравнения f (x) = 1.
Реализация I
x tar
: добавляем анциллу в состоянии
1
?
2
(|
0 ? |1 ), и делаем преобразование x , anc ? x , anc ? f (x )
. Затем анциллу выбрасываем.
Оператор Гровера есть поворот на угол ? = 2 arcsin(N
?
1/2
)
по направлению к |x tar
16 / 31

Алгоритм Гровера: квадратичное квантовое ускорение
Задача на перебор: найти решение x tar уравнения f (x) = 1, где f - булевская функция от n переменных, заданная в виде схем из функциональных элементов.
Оператор Гровера G - поворот на угол arcsin(N
?
1/2
)
. Реализуется с помощью двух зеркальных отражений: вдоль вектора |?0 =
1
?
N
j
|j и вдоль неизвестного вектора |x tar
Последнее можно представить как |x, y ? |x, y ? f (x) - реализуется, исходя из классической схемы для функции f .
Алгоритм Гровера:
повторение оператора G
?
?
N
4
раз
Grover L.K., Proceedings,
28th Annual ACM Symposium on the Theory of Computing,
1996 17 / 31

Алгоритм Залки-Визнера
На квантовом компьютере можно моделировать решение уравнение Шредингера в случае простого потенциала за время O(t
2
)
, где t- время реального процесса, с памятью O(n),
где n- число частиц в реальной системе.
exp(?
i h
(H
kin
+ V (r ))t ? (exp(?
i h
H
kin dt)exp(?
i h
V (r )dt))
t/dt
(Формула Троттера, ошибка O(dt
2
)
). Оператор exp(?
i h
V (r )dt))
диагонален, и его можно выполнить с помощью квантового алгоритма с памятью порядка размера реальной системы. Оператор exp(?
i h
H
kin dt)
приводится к диагональному переходом к импульсному базису. Квантовое преобразование Фурье требует ресурса O(n) по времени и по памяти
(Шор); достижение малой результирующей ошибки потребует dt = O(1/t), что даст квадратичное замедление по времени по сравнению с реальным процессом.
C.Zalka, Proc.Roy.Soc.Lond. A454 (1998) 313-322, S.Wiesner, arXiv:quant-ph/9603028 18 / 31

Реализация обратного квантового преобразования Фурье |a ?
1
?
N
N?
1
b=
0
exp(
2?iab
N
)|b
19 / 31

Окружности здесь обозначают преобразование Адамара
|
0 ?
1
?
2
(|
0 + |1 ), |1 ?
1
?
2
(|
0 ? |1 ), матрица которого имеет вид:
H =
1/
?
2 1/
?
2 1/
?
2 ?1/
?
2
,
(1)
двухкубитовые операции имеют вид:
U
k,j
=
?
?
?
?
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 e i ?/
2
k?j
?
?
?
?
, k > j .
(2)
20 / 31

Набросок доказательства
В данной схеме вентилей амплитуда перехода от a =
j a
j
2
j к b =
j b
j
2
j имеет вид
?
l >k>j ?
0
a j
b k
2
k?j
+ ?
l >j ?
0
a j
b j
=
2?
l >j +k?
0
a j
b k
2
j +k
2
l
=
2?
l >j ,k?
0
a j
b k
2
j +k
2
l
=
2?
2
l l >j ?
0
a j
2
j l >k?
0
b k
2
j
=
2?
2
l
(3)
что в точности соотвествует обратному преобразованию Фурье.
21 / 31

Главное назначение квантового компьютера - моделирование реальности на квантовом уровне
Квантовый компьютер способен находить решение уравнения Шредингера для n частиц за время O(t
2
)
с использованием памяти O(n), в дискретном приближении с зерном разрешения dx, dt, от которого зависят константы времени и памяти.
Создание QC означало бы новый этап в точном естествознании, так как появилась бы возможность моделировать сложные системы на квантовом уровне.
Существование QC не противоречит никаким законам физики.
22 / 31

Теоретические пределы возможностей квантового компьютера
Generic Machine Simulation Problem (GMSP): Нахождение результата t- кратного применения заданной функции F к данному аргументу x. GMSP- P-полная проблема, не допускающая распараллеливания (
Limits to Parallel Computation: P-Completeness Theory,
R.Greenlaw et al., University of New Hampshire, 1995
).
На квантовом компьютере в модели F как "черного ящика" при t = O(N
1/7
)
(N- число всех состояний машины) с вероятностью 1 GSMP не допускает квантового ускорения даже на 1 шаг. Без ограничения на t квантовое время решения GSMP проблемы с вероятностью 1 не может быть больше ?(
?
t)
(
Ozhigov Y.I., Chaos, Solitons and Fractals, 1999,
10 and Proc.R.Soc.Lond. A 1999, 455
).
Квантовый параллелизм оказывается тесно связан с классическим. Быстрые квантовые алгоритмы есть редкий феномен, имеющий место лишь для классических алгоритмов,
допускающих распараллеливание (FNC класс сложности).
Гроверовское ускорение является типичным верхним пределом для большинства задач.
Этот предел может превышаться только для отдельных частных случаев, например,
факторизация целых чисел (алгоритм Шора
P. W. Shor, Algorithms for quantum computation:
Discrete logarithms and factoring, Proc. 35nd Annual Symposium on Foundations of Computer
Science, IEEE Computer Society Press , 1994
).
23 / 31

CNOT гейт: |x, y ? |x, x ? y . на зарядовых состояниях
К.А.Валиев, Л.Е.Федичкин, Квантовые компьютеры и квантовые вычисления, т.9, 1, 2009
Для реализации произвольного унитарного оператора достаточно реализовать все однокубитные и какую-либо запутывающую двух-кубитную операцию, например, CNOT.
Figure:
А. NOT на квантовой точке с двух-ямным потенциалом. Собственные состояния
|?
0
=
1
?
2
(|
0 + |1 ) и |?
1
=
1
?
2
(|
0 ? |1 ).
Б. CNOT. Состояние точки x определяет высоту барьера в точке y (зеленый цвет), и скорость туннелирования в y.
Квантовые точки на NV- центрах в алмазе
F.Jelezko, S.Kilin, A.Nizovtsev, J.Wrachtrup, C.Tietz,
A.Gruber, I.Popa, Single Molecules, 2001, vol.2, 4, 255 24 / 31

Нелинейный фазовый сдвиг в оптической полости
Figure:
NPS: optical cavity, which the two-level atom ies through. The energy of the eld in the cavity does not exceed 2?
c
. We choose the appropriate time ?
0
= ?s/v for nding the atom in the cavity for the realization of NFS: |0 ? |0 , |1 ? |1 , |2 ? ?|2
H.Azuma, Quantum computation with the JaynesCummings model, Prog. Theor. Phys. 126 (2011),
369385.
25 / 31

CSign |x, y ? (?1)
xy
|x, y на фотонных состояниях.
Добротность можно довести до 90%. Используется 2 полости для нелинейных фазовых сдвигов и 2 линейные светоделители, действующие так:
|n a
1
|m a
2
=
1
?
n!m!
(a
+
1
)
n
(a
+
2
)
m
|
0
a
1
|
0
a
2
??
??
1
?
n!m!
[
1
?
2
(a
+
1
+ a
+
2
)]
n
[
1
?
2
(a
+
1
? a
+
2
)]
m
|
0
a
1
|
0
a
2
(4)
Figure:
C-Sign gate array
26 / 31

Tavis-Cummings-Hubbard model
Hamiltonian of TCH model has the form:
H
TCH
=
i h?
c a
+
i a
i
+
i ,j h?
ij a
?
+
ij
?
?
ij
+ k i
(a
+
i +
1
a i
+ a
+
a i +
1
) +
i ,j
µ
ij
(a i
+ a
+
i
)(?
+
ij
+ ?
?
ij
)
(5)
where i designes cavity, j - atom, a
(+)
i are operators of creation-annihilation of photons in i-th cavity, ?
(±)
ij are operators of creation-annihilation of excitation of j-th atom in i-th cavity,
?
c
? ?
a
= d
?
a
. If µ
ij h?
a summands not conserving energy can be omitted (RWA
approximation).
Inuence of thermal phonons gives the deposit in the form of dephasing b
(+)
mk are phonon operators, S
ikj
- Juang-Rhys factors for interaction between j-th atom in i-th cavity with phonon mode k:
H = H
TCH
+ H
B
+ H
I
, H
B
=
m,k
E
mk b
+
mk b
mk
,
H
I
=
1 2
i ,k,j
S
ikj
?
k
(b
+
ik
+ b ik
)?
+
ij
?
?
ij
+ h.c.
(6)
27 / 31

Jaynes-Tavis-Cummings-Hubbard-Dick model with dephasing noise
Figure:
JC model with noise.
28 / 31

Декогерентность - главное препятствие на пути к QC
Отклонение от унитарного закона в отсутствии наблюдателя называется декогерентностью.
Математически декогетентность означает подавление недиагональных элементов матрицы плотности системы, переводящей ее из чистого (когерентного) состояния в классическую смесь различных состояний.
Принято считать, что декогерентность вызвана контактом рассматриваемой системы с ее окружением, которого полностью избежать невозможно.
29 / 31

Частичное описание декогерентности
Если декогерентность вызвана контактом с окружением, она проявляется в виде подавления недиагональных элементов в матрице плотности ?(t), которая в случае определенного (чистого) квантового состояния имеет вид ? = |? ?|, а в случае классической неопределенности (например, в результате частичного измерения состояния) - вид ?
mix
=
i p
i
|? ?|
, где p i
- вероятность того, что система находится в состоянии |? .
Динамика матрицы плотности в случае отсутствия памяти у окружения подчиняется квантовой марковской динамике - удовлетворяет уравнению
Коссаковского-Линдблада-Глаубера-Сударшана:
ih ?
? = [H, ?] + i
N
2
?
1
j =
1
g j
(L
j
?L
+
j
?
1 2
{L
+
j
L
j
, ?})
где g j
?
0, L
j вместе с тождественным оператором образуют ортогональный базис в операторном пространстве Лиувилля. Для особо интересного случая немарковской динамики нет подобного общего подхода, есть только отдельные частные результаты.
30 / 31

Выводы
Квантовый компьютер - долговременный проект, в котором теоретические разработки и эксперименты одинаково важны.
Квантовая теория в области многих тел еще не разработана в должной мере.
Компьютерное и суперкомпьютерное моделирование - ключевой момент в развитии теории QC.
31 / 31

Document Outline

  • ??????? ???????? ????????? ????????
  • ??????? ????????? ?????????
  • ?????????? ????????? ??????
  • ??????????????? - ??????? ??????????? ?? ???? ? QC


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


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

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


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