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

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

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

Представление gate в электротехнике

Задача

Для того, чтобы понять, зачем нам нужны квантовые компьютеры, посмотрим на ограничения обычных компьютеров. Рассмотрим достаточно простую задачу: пусть у нас есть некоторое число \(S\), которое представляется в форме:

\(S = p q\), где \(p,q\) - простые числа.

\(|S| = 10^{90}\)

Найти необходимо числа \(p,q\).

Проблема заключается в том, что у нас есть физическое ограничение: количество частиц в наблюдаемой части Вселенной, которое, к сожалению, нам не даст найти это число, поскольку в нашей Вселенной всего лишь \(3*10^{80}\) частиц. То есть если мы будем строить машину, которая нам будет искать факторизацию этого числа, то у нас не хватит материи для того, чтобы её построить. Для этого потребуется очень большое количество времени. Соответственно, нам необходимо искать другие вычислительные устройства, которые могут решать задачу.

Поговорим немного об обычных вычислителях. Компонентная база, которая есть в современных компьютерах, построена на транзисторах. В транзисторе есть переход, за счет чего можно строить какие-либо системы, которые выполняют различные логические операции.

Условное обозначение трафнзистора
Условное обозначение транзистора

NAND gate

NAND gate:

NaN.bmp


Эта схема на двух транзисторах позволяет нам делать операцию NAND. Обозначается на схемах следующим образом:

NAND на схеме.bmp


Таблица истинности
A B RES
0 0 1
0 1 1
1 0 1
1 1 0

Таким образом с помощью данного gate мы можем, к примеру, подсчитать сумму 2 бит (,биты A и B):

Сумма 2 бит.bmp


\(S\) - сумма 2 бит

\(C\) - переполнение (вышли за границу разряда)

С помощью данной схемы мы можем не только подсчитать сумму 2 бит, но и получить флаг переполнения.


Таким образом мы можем построить схему более большую, которая нам позволяет суммировать 4-х разрядные числа:

Сумма 4-х разрядных чисел.bmp


\(NAND = x | y\)

Таким образом, \(NAND\) является базисом в пространстве логических функций, то есть мы можем, используя \(NAND\), построить все другие логические gates: \( AND \ NOT \ OR \)

Аналог Машины Тьюринга (вычисление с памятью)

Чтобы мы перешли к универсальному вычислителю, который не просто вычисляет суммы, нам не хватает в данной системе памяти. На \(NAND\) также можно организовать память. Такая схема называется \(D\) - триггером:

D - триггер.bmp



В данной схеме у нас все элементы - \(NAND\) gates.




D Flip flop.png

Рассмотрим входы:


\(PRESET\) - позволяет нам задать какое-либо начальное значение;

\(Data \ Pin\) - данные, которые мы сейчас подаём;

\(Output\) - выход с прошлого момента времени;

\(Inverted \ Output\) - инвертированный выход с прошлого момента времени;

\(Clock\) - сигнал синхронизации (D - триггер изменит свое состояние только тогда, когда на данный вход поменяет уровень);

\(CLEAR\) - очистить D - триггер;



Таким образом триггер - простая схема, которая может хранить в себе состояния.

Ограничения с точки зрения физики

Появляется такое важное понятие как скорость работы. Мы не можем подавать сигнал с огромной скоростью (неограниченно быстро), потому что это приведёт к перегреву (чем быстрее мы подаём сигнал на \(Clock\), тем быстрее у нас происходит переключение транзисторов, выделяется тепло \(W\) и меняются характеристики транзисторов, поэтому у нас перегревается компьютер, схема перестаёт работать).

Стоит отметить тот факт, что у нас все процессы необратимые. Поэтому выделяется тепло во внешнее пространство.

Что мы можем извлечь из этого момента (с точки зрения физики):

1) Ограничение скорости

2) Ограничение ёмкости

Ограничения с точки зрения математики

Рассмотрим с точки зрения математики.

Сколько есть различных алгоритмов?

Количество алгоритмов счётное множество, поскольку алгоритм можно представить как последовательность 0 и 1, а последовательность 0 и 1 - число натуральное.

Сколько у нас есть функций, которые отображают натуральное число в натуральное?

\(f : N \rightarrow N\)

Для этого достаточно просто их построить.

У нас есть некоторое число \(a\)

\(a=0.a_1 a_2 a_3 ... a_k\), \(a_k \in [0, 1]\), мощность множества континуальная, соответственно, можем определить функцию:

\(f_a (n) = a_n\)

Поскольку чисел \(a\) \(2^N\), то всевозможные функции - всевозможные алгоритмы. То есть у нас у нас есть ограничение, которое говорит о том, что классические процессы не всегда позволяют много чего вычислить. Чаще всего они требуют больше времени, чем хотелось бы (пример - факторизация чисел, описано выше).

Квантовая физика

Опыт Юнга

Возьмём классический опыт Юнга:

Опыт Юнга(1).png



У нас есть некоторая пластина с двумя щелями, также есть электронная пушка, которая стоит по центру и стреляет электронами. Логично предположить то, что так как электрон - частица, то получаются 2 горки по краям (2 жирные точки на схеме).






Однако, если этот опыт проводить в реальности, то мы будем наблюдать несколько иную картину. То есть электрон будет проявлять свои волновые свойства.

Опыт Юнга(2).png



В данном случае пушка - источник волн. Точки будут порождать вторичные волны. Таким образом, у нас получится интерференционная картина.





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

Копенгагенская и многомировая интерпретации

Существует 2 интерпретации того, что происходит в квантовом мире:

1) Копенгагенская - говорит о том, что мы не можем в процессе измерения достаточно сильно отделить измеритель от измеряемого объекта. То есть когда мы наблюдаем за электроном, измеритель начинает на него так влиять, что он начинает двигаться как частица.

2) Многомировая - говорит нам о том, что, когда мы начинаем наблюдать за электроном, мы детерминируем свое положение относительно мультиверса.

Многомировая интерпретация(1).bmp



У нас есть Вселенная в момент времени \(t_0\), 2 отверстия, 2 Вселенные в момент времени \(t_1\): в одной электрон пролетает через верхнее отверстие, в другой - через нижнее. Когда мы измеряем, мы оказываемся в одной из вселенных. Таким образом, мы определяем своё положение относительно вселенной, в которой случилось определённое событие.






Кот Шрёдингера

Обратимся к классическому опыту с котом Шрёдингера:


У нас есть электронная пушка, 2 отверстия, чёрный ящик, в котором сидит кот Рядом с котом находится устройство, которое убьёт кота, если электрон пролетит через верхнее отверстие, ничего не случится, ничего не случится, если пролетит через нижнее. Рядом с установкой стоят наблюдатели \(Н_1\) и \(Н_2\).

Кот Шрёдингера(4 !).bmp


В момент времени \(t_0\) испускается электрон, есть одна Вселенная. При этом наблюдатели не знают, в какой Вселенной они находятся. В момент времени \(t_1\) образовалось 2 Вселенные, в одной из которых кот мёртв, в другой - жив. Далее наблюдатель \(Н_1\) может открыть ящик и узнать правду. При этом он сам окажется в 2 Вселенных: в одной кот мёртв, в другой - жив. С точки зрения наблюдателя \(Н_2\), пока мы не посмотрим на наблюдателя \(Н_1\), мы не сможем точно сказать, в какой из Вселенных он находится.


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

Евклидово и Гильбертово пространства

Евклидово пространство

Евклидово пространство - некоторое пространство над множеством вещественных чисел конечной размерности, в котором соблюдаются некоторые правила.

\(\overrightarrow{x},\overrightarrow{y} \in R^n\), \(\overrightarrow{x},\overrightarrow{y}\) - векторы

Правила

Правила \(\forall \overrightarrow{x},\overrightarrow{y}\)

Мы можем суммировать покоординатно векторы:

\(\overrightarrow{x} +\overrightarrow{y} = (\overrightarrow{x_0} + \overrightarrow{y_0}, \overrightarrow{x_1} + \overrightarrow{y_1}, ... , \overrightarrow{x_n} + \overrightarrow{y_n})\)

Домножать векторы на число:

\( \lambda \overrightarrow{x} = (\lambda \overrightarrow{x_0}, \lambda \overrightarrow{x_1}, ... , \lambda \overrightarrow{x_n})\)

Также существует понятие скалярного произведения векторов:

\((\overrightarrow{x}, \overrightarrow{y}) = (\overrightarrow{y}, \overrightarrow{x})\)

\((\overrightarrow{x}, \overrightarrow{y} + \overrightarrow{z}) = (\overrightarrow{x}, \overrightarrow{y}) + (\overrightarrow{x}, \overrightarrow{z})\)

\((\lambda \overrightarrow{x}, \overrightarrow{y}) = \lambda (\overrightarrow{x}, \overrightarrow{y})\)

\((\overrightarrow{x},\overrightarrow{x})>0\), если \(\overrightarrow{x} \neq \overrightarrow{0}\), \(\overrightarrow{0}: (\overrightarrow{0},\overrightarrow{0}) = 0\)

Гильбертово пространство

Гильбертово пространство может быть определено над множеством комплексных чисел и может иметь бесконечную размерность.

Вышеописанные свойства (Евклидова пространства) выполняются

Примеры:

1) Евклидово пространство: оно является подмножеством Гилбертова пространства

2) Пространство \(l^2 : x = \{ x_n \}_{n = 1}^{\infty} : \sum_{n=1}^{\infty} |x_n|^2\) - сходится

Дополнительные правила

Скалярное произведение на этом пространстве:

\((x, y) = \sum_{n=1}^{\infty} x_n y_n\)

Тензорное произведение

Пусть у нас есть 2 матрицы:

\(A\) с размерностью \( |A| = m \times n\);

\(B\) с размерностью \(|B| = p \times q\);

$$A \otimes B = \left[ \begin{array} aa_{11}B & ... & a_{1n}B \\ ... & ... & ... \\ a_{m1}B & ... & a_{mn}B \end{array} \right] $$

\( |A \otimes B| = mp \times nq\)

Пример:

$$ \begin{pmatrix} 1 & 2 \\ 3 & 4 \\ \end{pmatrix} \otimes \begin{pmatrix} 1 & 1 \\ 1 & -1 \\ \end{pmatrix} = \begin{pmatrix} 1*B & 2*B \\ 3*B & 4*B \\ \end{pmatrix} = \begin{pmatrix} 1 & 1 & \ & 2 & 2 \\ 1 & -1 & \ & 2 & -2 \\ \ & \ & \ & \ & \ \\ 3 & 3 & \ & 4 & 4 \\ 3 & -3 & \ & 4 & -4 \\ \end{pmatrix} $$

Квантовые вычисления

Обозначения Дирака

Кет - скобки $$ | x > = \begin{pmatrix} x_1 \\ ... \\ x_n \\ \end{pmatrix} $$

$$ | y > = \begin{pmatrix} y_1 \\ ... \\ y_n \\ \end{pmatrix} $$

$$ x_i, y_i \in C $$

Пространство

Скалярное произведение обозначается следующим образом: \( < x | y > = \sum_{i=1}^{n} x_i y_{i}^* \), где \(y_{i}^* сопряжённое\)

Норма: \(||x|| = | <x,x> |\) \(|| ||: C^n \rightarrow R\) \(|a| = \alpha_i + \beta_i = \sqrt { \alpha^2 + \beta^2 } \)

Между векторами есть косинус угла: \(cos \theta = \frac{|<x|y>|}{||x||*||y||} = \frac{|x_1 * y_1 + x_2 * y_2|}{\sqrt {x_{1}^2 + y_{1}^2} * \sqrt {x_{2}^2 + y_{2}^2}}\)

\(\theta = arccos \frac{|<x|y>|}{||x||*||y||} \)

\(\theta \in [0, \frac{\pi}{2}]\)

Что такое кубит?

Кубит - наименьший элемент для хранения информации в квантовом компьютере. Определяем кубит как вектор в Гильбертовом пространстве, его норма равна 1. Встаёт вопрос: какая размерность этого Гильбертова пространства? Она равна 2. Кубит задаётся как некоторая линейная комбинация в ортонормированном базисе в этом Гильбертовом пространстве:

\( | \phi > \in H, ||\phi|| = 1, dim \ H = 2\)

\( | \phi > = \alpha | 0 > + \beta| 1 > \)

\( | 0 >, | 1 > \) - ортонормированный базис

\(|| \ | 0 > \ || = || \ | 1 > \ || = 1\)

\( | 0 > \bot | 1 > \)

\((1 , 0) - \overrightarrow{x} \)

\((0 , 1) - \overrightarrow{y} \)

\(\overrightarrow{z} = \alpha \overrightarrow{x} + \beta \overrightarrow{y} \)

Что вообще означают \(\alpha \ и \ \beta\) ?

У них есть физический смысл. Вернёмся к обычным компьютерам и посмотрим на такую вещь, как микрофон:

Микрофон.png

У нас есть человек, он что - то говорит. Также у нас есть микрофон. В микрофоне магнит и мембрана, мы получаем волны. Что происходит дальше со звуковыми волнами, когда мы их переносим в компьютер? Необходимо оцифровать на аналого-цифровом преобразователе: взять некоторое количество значений, которые нам позволят восстановить эту волну. Далее, когда мы захотим воспроизвести эту информацию на некотором динамике, который состоит из магнита с мембраной, то мы должны будем подать на него колебания, после этого получим более кривую волну. Поэтому оцифровка "уничтожает" истинное звучание.

С квантовыми компьютерами получается интересная ситуация. Когда мы измеряем некоторое значение кубита, получаем одно значение с разными вероятностями\(P(| 0 > \phi) = \alpha^2\) \\ вероятность того,что мы получим значение 0 при измерении кубита \(\phi\)

\(P(| 1 > \phi) = \beta^2\) \\ вероятность того,что мы получим значение 1 при измерении кубита \(\phi\)

Аналогии с котом Шрёдингера

В кубите \(\phi\) находятся и 0 и 1 одновременно также, как и кот Шрёдингера мёртв и жив одновременно. Таким образом кот - тот же самый кубит. Кубит кота состоит из вероятности того, что он жив и некоторой вероятностью того, что он мёртв.

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

Пример

Предположим, что у нас есть вектор:

\( | \phi > = \frac{1}{\sqrt 2} | 0 > + \frac{1}{2} | 1 > \)

Кубит пример.bmp

Попробуем его измерить.

\(P(| 0 > | \phi) = \alpha^2 = \frac{1}{2}\)

\(P(| 1 > | \phi) = \beta^2 = \frac{1}{2}\)

\(P( A | B ) = \frac{P(AB)}{P(B)}\) - формула условной вероятности.

\(P(| 0 >| \phi ) = \frac{P(| 0 > \cap | \phi >)}{P(\phi)} = \frac{}{1}\)

\(P(| 0 >| \phi ) + P(| 1 >| \phi ) = 1\)

Посмотри на другой вектор \(\psi\)

\( | \psi > = \frac{1}{\sqrt 2} | 1 > - \frac{1}{\sqrt 2} | 0 > \)

\(P(| 0 > | \psi) = \alpha^2 = \frac{1}{2}\)

\(P(| 1 > | \psi) = \beta^2 = \frac{1}{2}\)

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

Базис Адамара

Возьмём другой базис - базис Адамара (Hadamard):

\( | + > = \frac{1}{\sqrt 2} | 0 > + \frac{1}{\sqrt 2} | 1 > \)
\( | - > = \frac{1}{\sqrt 2} | 0 > - \frac{1}{\sqrt 2} | 1 > \)
Что будет, если мы попробуем в базисе Адамара вычислить значение вероятностей вектора \(\phi\):

\(P(| + > | \phi) = 1\)

\(P(| - > | \phi) = 0\)

\(P(| + > | \psi) = 0\)

\(P(| - > | \psi) = 1\)

В данном базисе мы смогли различить ветра состояний.

После измерения мы узнали вероятность вектора \(\phi\) и он больше не в суперпозиции:

$$ \begin{matrix} t_0 & t_1 \\ P(|0>|\phi)=\frac{1}{2} & P(|0>|\phi)=0 \\ P(|1>|\phi)=\frac{1}{2} & P(|1>|\phi)=1 \\ \end{matrix} $$

Опять, же после второго вскрытия ящика кот не оживёт и не умрёт. Таким образом, после измерения квантовой системы, мы оказываемся только в одной из Вселенных, где значение вектора соответствует одному из определённых значений кубита: либо 0, либо 1.

Как мы можем обойти ограничение?

Так как мы не можем снова вернуться к моменту времени \(t_0\) (по теореме о запрете клонирования мы не можем копировать состояния квантовых систем), то нам придется завести нового кота и поместить его в новую коробку!

Пусть у нас векторы кубиты \(a\) и \(b\). Пара кубитов будет выглядеть следующим образом:

$$ \begin{matrix} a & b & \\ |0> & \alpha|0> + \beta|1> & \alpha|00> + \beta|01> \\ \end{matrix} $$

\(P(|00>) = \alpha^2\) \(P(|01>) = \beta^2\)

Пусть у нас есть векторы:

$$ \begin{matrix} a & b & \\ \alpha|0> + \beta|1> & p|0> + q|1> & \alpha p|00> + \alpha q|01> + \beta p|10> + \beta q|11> \\ \end{matrix} $$

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

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

$$ | 00 > = \begin{pmatrix} 1 \\ 0 \\ \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \\ \end{pmatrix} $$

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

Представление кубита

Каждый кубит мы можем представить фактически одним атомом. Например, есть атом водорода, у него есть 2 орбитали, электрон может находиться в пространстве между 2 орбиталями, то есть электрон может находиться в суперпозиции и, фактически, реализует кубит.

Пример

Если у нас 5 атомов, то состояний может быть \(2^5 = 32\). 5 атомами мы представляем 32 значения. Если у нас 3000 атомов, то состояний может быть \(2^3000 = 10^90\). Таким образом, на 3000 атомах мы можем построить квантовый компьютер, с помощью которого можно факторизовать числа порядка \(10^90\). То есть квантовый компьютер позволяет нам резко уменьшить объём материй, который нам нужен для вычислений.

Пусть у нас есть некоторая пара кубитов: \(\alpha | 00 > + \beta | 11 >\). Эти кубиты связаны. Измерив только один кубит, мы сразу узнаем, что второй. Например, если первый кубит равен 1, то и второй равен 1.

Квантовые алгоритмы

Квантовый алгоритм - алгоритм, который задает последовательность унитарных операций с указанием, над какими именно кубитами их надо совершать. Результат работы носит вероятностный характер.

Квантовые алгоритмы описываются преобразованиями над кубитами. Эти преобразования осуществляются с помощью унитарных операторов. Унитарный оператор - некоторая матрица, которая умножается на вектор. Для того, чтобы оператор был унитарен, требуется, чтобы сопряженный ему оператор был его обратным оператором и был равен оператору эквивалентному: \(U^* U = UU^* = I\) Также \(\forall \phi \in H \ ||U|\phi>|| = |||\phi>||\) (должен сохранять норму) \(\forall \phi, \psi \in H \ |<U|\phi> | <U|\psi>| = |<\phi | \psi>|\) (должен сохранять угол между векторами) Пример Унитарный оператор - оператор Адамара Также оператор \(X - \) унитарный $$ 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^* = XX = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} = I $$

\(X \sim NOT\)

Так как оператор переводит 1 в 0, а 0 в 1, значит, он базисные векторы просто меняет местами и, соответственно, у нас сохраняются все углы и все длины.

Пример

Квантовый алгоритм(пример).png

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