О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.
Оптимальность алгоритма Гровера. Часть 2
Loading...
Из курса от партнера Saint Petersburg State University
Квантовые вычисления (Quantum computing)
20 оценки
Из урока
Алгоритм Гровера и границы квантовых вычислений
Познакомьтесь с преподавателями
Сысоев Сергей Сергеевичкандидат физико-математических наук
Кафедра системного программирования
[МУЗЫКА]
[МУЗЫКА] Первую
часть неравенства мы доказали для любого единичного вектора φ, теперь мы
предъявим некоторый вектор φ, для которого выполняется вторая часть неравенства.
Для этого давайте сначала рассмотрим поподробнее наш оператор U(ω,t).
Это оператор, который вызывает оракул Uω t раз.
Давайте выделим в нем эти вызовы оператора Uω.
[БЕЗ СЛОВ]
[БЕЗ СЛОВ] Ну
и действуем мы на
начальный вектор системы ψ₀.
Здесь просто видны вызовы операторов Uω,
и между ними происходят какие-то другие действия, которые мы предполагаем,
что алгоритм U(ω,t) делает лучше, чем алгоритм Гровера.
Обозначим |Ψt > вектор,
который получается с действием
U(ω,t) на начальный вектор системы.
И новое обозначение |Φt >,
это воздействие оператора U(ω,t) без вызовов оракула.
То есть мы берем только вот эти промежуточные части между вызовами
оракула, которые мы делаем лучше, чем у Гровера, ставим их вместе,
а оракул не вызываем.
U₁, и тоже действуем на начальный вектор системы.
То есть вектор |Ψt > — это вектор
системы на шаге t для алгоритма, который лучше, чем алгоритм Гровера,
а вектор |Φt > — это действие на начальный вектор системы вот такого вот алгоритма.
Тот же самый U(ω,t), только без вызовов оракула.
Мы можем заметить, что вот этот оператор получается из оператора U(ω,t),
если мы операторы оракулов заменим на тождественные операторы.
Давайте рассмотрим такую величину.
E(ω,t) норма
Uω − I
* |Ψt >.
Как отличается норма вектора,
если мы действуем оператором Uω или если мы действуем тождественным оператором?
Вспомним, что вектор Uω
= I − 2
ω > <
ω мы вычитаем тождественный оператор,
и все это действует на вектор |Ψt >.
Тождественные операторы взаимоуничтожаются.
Получается [БЕЗ СЛОВ]
скалярное произведение ω на |Ψt >,
норма вектора ω — 1,
и получается, что у нас просто два модуля
скалярного произведения ω на |Ψt >.
Теперь рассмотрим следующую величину.
f(t) — это норма разности
векторов |Ψt > и |Φt >.
[БЕЗ СЛОВ] Вектор |Ψt > давайте мы выразим через вектор |Ψt − 1 >.
Это оператор UtUω
к вектору |Ψt − 1 >.
А вектор |Φt > — это просто вектор |Ut >.
Оператор Ut к вектору |Φt − 1 >.
Теперь я хочу сюда вот в эту норму прибавить
и вычесть такое вот значение.
[БЕЗ СЛОВ] Что
мы получим после того, как я сделаю это?
Вычту я из первого члена, получим Ut (Ut
можно будет вынести за скобку),
Uω − I на
|Ψt − 1 >.
И вот сюда мне надо прибавить
(Ut опять я выношу за скобку)
|Ψt − 1 >
− |Φt − 1 >.
Теперь я могу разбить эту норму по неравенству треугольника,
оценить ее сверху.
Вот на этом плюсе мы
разбиваем Ut(Uω
− I) |Ψt − 1
> + вторая часть.
Ut |Ψt
− 1 > − |Φt − 1 >.
Теперь обратите внимание: оператор Ut из-под знака нормы можно просто выкинуть,
поскольку это унитарный оператор, и он не меняет длину вектора.
И тогда здесь мы получаем значение,
которое мы оценивали на предыдущем шаге: E(ωt − 1),
а здесь мы получаем определенную нами ранее функцию f(t − 1).
Таким образом, мы можем сказать, что функция f от полного
количества итераций (t) будет меньше,
либо равна двух сумм ω
на Ψt
по всем t.
Ну или от 1 до t, не важно.
Мы с вами доказали только что вот такое неравенство.
При этом заметим, что вектор |Ψt > — это вектор системы после t вызовов оракула,
и, соответственно, это вектор |Ψω >.
Результат работы алгоритма.
А вектор |Φt >, как вы, наверное, уже догадываетесь, это и будет наш
искомый вектор, для которого будет выполняться вторая часть неравенства.
Поэтому мы должны теперь посмотреть, что будет из себя представлять
вот эта вот норма в квадрате, поскольку у нас тут сумма по нормам в квадрате.
Итак, это норма (я не
буду ее переписывать) ||...||² ≤ соответственно,
4 (∑ по t от 1 до t модулей скалярных
произведений ω |Ψt − 1 >)².
И я не зря не стер лемму,
доказанную нами в предыдущей лекции.
Это меньше, либо равно по лемме
4T ∑ по t от
1 до T модулей скалярных
произведений в квадрате.
Квадрат нормы мы оценили, теперь надо взять сумму по всем ω.
Давайте это сделаем.
∑ по ω (вот эта вот норма в квадрате) ≤...
и, соответственно, ∑ по ω надо взять вот для этой части.
Я могу сразу переставить сумму местами, я возьму сначала ∑ по t.
Потом ∑ по всем ω,
и этот
модуль в
квадрате.
Вы можете заметить, что вот эта вот сумма — это просто
квадрат нормы вектора |Ψt − 1 >.
Поскольку это сумма по всем базисным векторам пространства.
Соответственно, она равна 1.
У нас получается сумма из t единиц, это равно 4T *
сумму из T единиц, и это равно 4T².
Получается, что сумма норм в квадрате отсюда меньше,
либо равна, чем 4T² и вторая часть неравенства доказана.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
