О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.
Преобразование Адамара
Loading...
Рецензии
4.8 (оценок: 29)
- 5 stars23 ratings
- 4 stars6 ratings
Из урока
Математическая модель квантовых вычислений
В этом модуле вы познакомитесь с математической моделью квантовой информации и квантовых вычислений и поймете, что такое алгоритм для квантового компьютера.
Преподаватели
Сысоев Сергей Сергеевич
кандидат физико-математических наук
[МУЗЫКА]
[МУЗЫКА] Ну
и напоследок давайте докажем одно полезное выражение для
оператора Адамара, действующего на систему из 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., 2019 Все права защищены.
