Преобразование Адамара

Loading...

Из курса от партнера Saint Petersburg State University

Квантовые вычисления (Quantum computing)

20 оценки

Saint Petersburg State University

Квантовые вычисления (Quantum computing)

20 оценки

О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.

Из урока

Математическая модель квантовых вычислений

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

Эволюция квантовой системы. Часть 18:22

Эволюция квантовой системы. Часть 28:47

Преобразование Адамара11:48

Познакомьтесь с преподавателями

Сысоев Сергей Сергеевич
кандидат физико-математических наук
Кафедра системного программирования

[МУЗЫКА]

[МУЗЫКА] Ну

и напоследок давайте докажем одно полезное выражение для

оператора Адамара, действующего на систему из n кубит.

То есть если у нас есть n кубит

и на каждый из них надо подействовать оператором Адамара,

то можно, конечно, тензорно перемножать все эти матрицы 2 x 2 каждый раз,

а можно один раз доказать такое выражение.

Оператор Адамара для системы из n кубит на вектор

состояния системы x действует следующим образом.

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА] Где операция жирная точка x,

жирная точка y расписывается следующим образом: это

покомпонентное перемножение

битов в x и в y и

последующее сложение их по модулю 2.

[БЕЗ_ЗВУКА] Таким образом,

результат этой операции — всегда один бит.

И −1 у нас всегда будет в степени либо 1, либо 0.

Обратите, пожалуйста, внимание.

Здесь, например, y встречается в двух ипостасях: он встречается в скобках,

и тогда это вектор, и он встречается без скобок, и тогда это число.

Давайте на примере.

Вот это у нас вектор в восьмимерном пространстве.

Если мы стираем скобки, получаем такую вот битовую строку,

и это у нас в двоичном представлении число 5 — номер этого вектора в базисе.

Таким образом, здесь у нас мы перебираем все

возможные номера наших векторов базиса.

И складываем, получается,

в этой сумме присутствуют все вектора базиса нашего пространства,

у каждого из которых будет коэффициент −1 в степени либо 0, либо 1.

Например, если вектор x полностью кодируется строкой нулей,

то есть вектор x равен такому вектору,

то оператор Адамара от вектора x будет

равен 1 / 2 в степени n/2,

сумма по всем возможным n-битным

строкам векторов, кодируемых этими строками.

То есть равновзвешенная сумма всех векторов нашего пространства.

Доказываем по индукции.

База n = 1.

Оператор Адамара вот

какого-то кубита x, одного кубита,

равен 1 / √2, как мы помним, нолик всегда у нас с плюсиком,

а вот коэффициент при 1 зависит от x.

Если у нас x = 0,

то здесь будет 0 + 1, если x = 1, то будет 0 − 1,

что и соответствует обычному нашему оператору Адамара.

Ну и соответственно это можно представить как 1 / 2 в

степени 1/2, n = 1,

Σ по y = 0 до

2 в степени 1 − 1, то есть до 1.

(−1) в степени x жирная точка y.

В данном случае это просто x * y,

поскольку у нас они все по одному биту.

y.

То есть вот эта сумма просто представлена здесь со знаком суммы.

Индукционный переход.

Hn давайте от | x > распишем как

покубитное применение

оператора H каждому из кубитов.

Это коэффициенты при каждом из операторов мы можем вместе

перемножить и получить 1 / 2 в степени n/2.

И у нас получается тензорное произведение таких скобок.

(| 0 > + (−1) в степени xn

− 1 * | 1 > )

(| 0 > + (−1)

в степени xn − 2, то есть n в −2-й бит икса,

* | 1 >) и так далее до (| 0 >

+ (−1) в степени x0 * | 1 >).

В этом выражении мы можем раскрыть

первую скобку.

И получится, что оставшихся

скобок у нас будет n − 1,

и мы можем применить индукционное предположение, предположение индукции,

и вот эти скобки свернуть по этой формуле.

Сейчас мы это сделаем.

Итак, мы раскрываем первую скобку, у нас получается первый нолик | 0 >,

дальше умножить на это всё, а это всё — это оператор

Адамара n − 1 от подстроки |

x > до n − 2 бита + 1

√2 (− 1) в

степени xn − 1 | 1 > *

на опять оператор Адамара

для n −

1 кубита, | x >,

состоящий из n − 1 бита.

Итак, здесь Hn в −1-й — это произведение n − 1 такой скобки, и xn − 1 я,

может быть, не очень удачно обозначил, это подстрока икса без последнего бита.

Теперь мы можем воспользоваться индукционным предположением,

и вот эти операторы H n − 1 заменить на эту формулу.

Давайте это сделаем.

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА] Здесь

у нас вместо n n − 1.

[БЕЗ_ЗВУКА] Теперь

со вторым слагаемым.

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА]

[БЕЗ_ЗВУКА] Итак,

давайте этот нолик внесем под сумму, сюда.

Перемножим здесь коэффициенты, получается 1

/ 2 в степени n/2.

Нолик мы договорились внести под сумму.

Здесь будет −1 в степени...

Давайте распишем эту жирную точку сейчас.

Это x0 y0 к [НЕРАЗБОРЧИВО] и так далее, она у нас была до n − 2.

xn − 2 * yn − 2.

И теперь я могу добавить

такую вот строчку.

x...

То есть не строчку, а бит.

xn − 1, правда, помноженный на ноль.

Все, что мы умножаем на ноль, дает ноль, сложением с

нулем ничего не меняет, поэтому вот такой вот член в сумму я добавить могу.

И у меня здесь внесенный наш вот этот нолик и y.

Обратите внимание, здесь у нас у y появился n − 1...

Как правильно сказать?

Бит с номером n − 1.

И здесь у нас в этой сумме уже n бит.

То есть n-й бит появился у y, который равен нулю.

И ту же самую операцию мы можем проделать с этой суммой.

Тоже перемножить коэффициенты,

тоже для (−1) расписать

x0 y0 и так далее.

И здесь у нас мы добавляем тоже n-й бит,

но домножаем его уже на 1, поскольку у нас здесь мы можем

внести также вот эту (−1) под сумму.

И здесь у нас получается | 1 >

тензорно на y.

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

Ну так давайте их сложим и получим.

Ну, мне не хочется приседать.

Получим мы вот это.

Доказательство завершено.

Спасибо!

Ознакомьтесь с нашим каталогом

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

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play