[МУЗЫКА] [МУЗЫКА] Первую часть неравенства мы доказали для любого единичного вектора φ, теперь мы предъявим некоторый вектор φ, для которого выполняется вторая часть неравенства. Для этого давайте сначала рассмотрим поподробнее наш оператор 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² и вторая часть неравенства доказана.
