ТМВ-2020-Лекция-19.05.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Тема лекции - Квантовые компьютеры (продолжение)

Повторение

Смотри лекцию №12

Как проводить измерения для одного кубита:

1) Выбираем ортонормированный базис.;

2) Измеряем вектор и получаем

\(\alpha \rightarrow 1\)

\(\beta \rightarrow 0\)

3) При дальнейших измерениях получаем результат из 2

То есть измерение для квантовой системы - это необратимый процесс в отличие от всех остальных изменений, которые мы можем в ней проводить.

Изменения проводятся при помощи унитарного оператора.

Например, оператор Адамара (Hadamard):

$$H = \frac{1}{\sqrt 2} \begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix} $$

Сопряженный оператор:

$$H^* = \frac{1}{\sqrt 2} \begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix} $$\(H*H^* = I\)

Оператор сохраняет длины и углы. Это происходит в Гильбертовом пространстве. Унитарный оператор - афинное преобразование, которое обратимо.

Проверим утверждение о сохранении длин и углов: Подействуем оператором на стандартный базис:

$$ H | 0 > = \frac{1}{\sqrt 2} \begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ \end{pmatrix} = \frac{1}{\sqrt 2} \begin{pmatrix} 1 \\ 1 \\ \end{pmatrix} = \frac{1}{\sqrt 2} | 0 > +\frac{1}{\sqrt 2} | 1 > = | + > $$

\( H | 0 > = | - > \)

Для того, чтобы проверить, что углы сохранятся, необходимо перемножить оба результата скалярно:

\( < - | + > = 0 \)

Рассмотрим ещё несколько операторов, которые позволят управлять эволюцией квантовой системы, то есть воздействовать на векторы так, чтобы они с как можно большей вероятностью получали 1 в состоянии, соответствующему искомому.

Унитарные операторы

Оператор \(NOT\)

На прошлой лекции мы просмотрели оператор \(X\) (соответствует логическому оператору \(NOT\)):

$$X = \begin{pmatrix} 0 & 1\\ 1 & 0\\ \end{pmatrix} $$


$$X | 0 > = \begin{pmatrix} 0 & 1\\ 1 & 0\\ \end{pmatrix} \begin{pmatrix} 1\\ 0\\ \end{pmatrix} = \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = | 1 > $$


$$X | 1 > = \begin{pmatrix} 0 & 1\\ 1 & 0\\ \end{pmatrix} \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = \begin{pmatrix} 1\\ 0\\ \end{pmatrix} = | 0 > $$


$$ XX^* = I = \begin{pmatrix} 1 & 0\\ 0 & 1\\ \end{pmatrix} $$

\(X\) - унитарный оператор

Мы рассматриваем унитарные операторы, потому что они обратимы. Таким образом, состояние квантовой системы обратимо до момента, пока мы не измерим состояние системы.

Оператор \(CNOT\)

Рассмотрим оператор \(CNOT\)(conditional NOT), оперирующий с двумя кубитами:

\(CNOT | 00 > = | 00 > \)

\(CNOT | 01 > = | 01 > \)

\(CNOT | 10 > = | 11 > \)

\(CNOT | 11 > = | 10 > \)

Таким образом, он меняет значение второго кубита в зависимости от значения первого.

Диаграмма 1.png






Пусть у нас есть n кубит. Мы не можем изменить один кубит в отрыве от всей системы.

Примеры

Диаграмма 6.png







То есть \(|x_1>\) управляет \(|x_3>\).

\(CNOT \neq A \otimes B\), где \(\otimes\) - произведение Кронекера

Матрица размерности \(8 \times 8\):

$$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix} = \begin{pmatrix} I & 0 & 0 \\ 0 & X & 0 \\ 0 & 0 & X \\ \end{pmatrix} $$


Диаграмма 3.png






$$I \otimes CNOT = \begin{pmatrix} CNOT & 0 \\ 0 & CNOT \\ \end{pmatrix} $$

$$ CNOT = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \end{pmatrix} $$

Формула, позволяющая \(n\) раз применить оператор Адамара(система векторов, к каждому применяем оператор Адамара):

$$ H_n|x> = \frac {1}{2^{n/2}} \sum_{y=0}^{2^{n-1}} (-1)^{x*y} |y> $$ \(y\) - число;

\(|y>\) - вектор, где на позиции \(y\) стоит 1 (остальные нули);

\(x*y = x_0 y_0 \oplus x_1 y_1 \oplus ... \oplus x_{n-1} y_{n-1}\).

Алгоритм Дойча

Задача Дойча

Пусть есть функция:

\(f : {0,1} \rightarrow {0,1} \)

\(|f| = ?\)

\(f(x) = 0\) - константа

\(f(x) = 1\) - константа

\(f(x) = x\) - сбалансирована

\(f(x) = \bar x\) - сбалансирована

Вопрос: \(f(x)\) - константа или сбалансирована?

Чтобы увидеть пользу от квантового алгоритма, предполагаем, что один вызов \(f(x)\) занимает 24 года.

Сколько необходимо вызовов \(f(x)\), чтобы решить эту задачу?

\(f(0) = f(1)\) - константа

\(f(0) \neq f(1)\) - сбалансирована

2 вызова

Таким образом, на это у нас уйдёт всего 48 лет!

Оракул

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

Обозначается: \(U_f\)

Для вышеописанной функции Оракул будет иметь следующий вид:

\(U_f | x > | y > = | x > | y \oplus f(x) >\) - Оракул для \(f(x)\)

\(x\) используется для хранения предыдущего значения. \(y\) - производит вычисления функции \(f(x)\). Мы должны преобразовать это к обратимой форме (как принято в квантовом мире):


\(U_f | x > | y \oplus f(x)> = | x > | y + \oplus f(x) \oplus f(x) > = | x > | y >\)

\(U_f U_{f}^* = I\) \(U_{f}^{-1} = U_f\)

Проверим, как он воздействует на базисные векторы:

\(U_f |0 > | 0 > \rightarrow | 0 > | f(0) >\)

\(U_f |1 > | 0 > \rightarrow | 0 > | f(1) >\)

\(U_f |0 > | 1 > \rightarrow | 0 > | 1 \oplus f(0) >\)

\(U_f |1 > | 1 > \rightarrow | 1 > | 0 \oplus f(1) >\)

Пояснения:

\(0 \oplus f(x) = 0 \oplus 0 = 0 = f(x)\) - если \(f(x) = 0\)

\(0 \oplus f(x) = 0 \oplus 1 = 1 = f(x)\) - если \(f(x) = 1\)

\(0 \oplus f(x) = 0 \oplus x = x = f(x)\) - если \(f(x) = x\) - сбалансирована

\(0 \oplus f(x) = 0 \oplus \bar x = \bar x = f(x)\) - если \(f(x) = \bar x\) - сбалансирована

Таким образом, \(0 \oplus f(x) = f(x)\) всегда

В зависимости от того, является ли \(f\) константой или нет, мы можем заметить, что может произойти склеивание.

\(U_f | x > \frac {1}{\sqrt 2} (| 0 > - | 1 >) = \frac {1}{\sqrt 2} | x > (| 0 \oplus f(x) > - | 1 \oplus f(x) >) = \frac {1}{\sqrt 2} | x > | 0 \oplus f(x) > - \frac {1}{\sqrt 2} | x > | 1 \oplus f(x) > = \frac {1}{\sqrt 2} (-1)^{f(x)} | x > (| 0 > - | 1 >)\)

Заметим, что у нас не изменился вектор \(y\), вместо этого просто вектор \(x\) домножился на (-1) в зависимости от того, какое значение принимает функция \(f(x)\).

\(U_f\) при разных \(f(x):\)

если \(f(x) = 0\):

\(U_f | x > | y > = | x > | y \oplus 0 > = | x > | y >\)

Диаграмма 7.png





если \(f(x) = 1\):

\(U_f | x > | y > = | x > | y \oplus 1 > = | x > | y > = I \otimes X | x > | y > \)

Диаграмма 2.png






если \(f(x) = x\):

\(U_f | x > | y > = | x > | y \oplus x >\)


Диаграмма 3.png






если \(f(x) = \bar x\):

\(U_f | x > | y > = | x > | y \oplus \bar x >\)


Диаграмма 4.png






Алгоритм Дойче (Deuthland)

Можем написать наш алгоритм таким образом:

Диаграмма 8.png



\(M\) - измерение


Покажем, что нужно вычислить \(f(x)\) всего лишь один раз:

\(|01> \rightarrow^{H_2} \frac{1}{2}(| 0 > + | 1 >)(| 0 > - | 1 >) = \frac{1}{2} | 0 > (| 0 > - | 1 >) + \frac{1}{2} | 1 > (| 0 > - | 1 >) \rightarrow^{U_f} \frac{1}{2} (-1)^{f(0)}| 0 > (| 0 > - | 1 >) + \frac{1}{2} (-1)^{f(1)} | 1 > (| 0 > - | 1 >) = \frac{1}{2} ((-1)^{f(0)} | 0 > + (-1)^{f(1)} | 1 > )(| 0 > - | 1 >) = \frac{1}{\sqrt 2}((-1)^{f(0)} | 0 > + (-1)^{f(1)} | 1 > ) \frac{1}{\sqrt 2} (| 0 > - | 1 >) = | q_1 > | q_2 >\)

если \(f(x) = const\):

\(\pm \frac {1}{\sqrt 2} (| 0 > + | 1 >) = \pm | + > \rightarrow^{H} | 0 > \rightarrow^{M} 0\)

если \(f(x) \neq const\):

\(\pm \frac {1}{\sqrt 2} (| 0 > - | 1 >) = \pm | - > \rightarrow^{H} | 1 > \rightarrow 1\)

\(U_f\) - применяется ровно 1 раз, следовательно, один вызов \(f(x)\). Таким образом, мы получили ускорение в 2 раза на квантовом компьютере.

Полезные ссылки

https://docs.microsoft.com/en-us/quantum/

https://docs.microsoft.com/en-us/quantum/intro-to-katas