[МУЗЫКА]

[МУЗЫКА] Постановка задачи.

У нас есть некоторая функция f, реализованная в виде черного ящика,

которая принимает на вход n-битные строки и возвращает,

например, тоже n-битные строки.

И существует единственное такое значение ω,

единственная такая n-битная строка, для которой f вот этой ω равно

некоторому заданному значению a, которое нам известно.

Задача заключается в том, чтобы найти это значение ω.

Как видите, это обобщенная постановка любой задачи из NP.

Получив ответ, мы можем легко его проверить,

вызвав оракулы, посмотрев, возвращает ли он значение a.

Если же ответ неизвестен,

то его требуется искать и в случае черного ящика искать перебором.

Имея такой черный ящик, мы можем определить функцию fω,

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

Определим ее следующим образом:

fω(x) = 1,

если x = ω,

и 0 во

всех остальных случаях.

Функция fω — это у нас классический оракул.

Для квантовых вычислений нам нужно определить квантовый оракул Ufω.

И давайте вспомним, как он действует на состояние вида, когда в последнем

бите у нас вот такая суперпозиция.

[ШУМ]

[ШУМ] Если мы

рассмотрим проекцию этого оператора на

подпространство аргумента, то мы получим оператор,

который мы назовем Uω, который действует на

аргумент следующим образом.

То есть он сохраняет

все вектора, кроме вектора ω, а вектор ω домножает на 1.

Этот оператор Uω мы можем записать несколько иначе.

[ШУМ]

[ШУМ] Действует он следующим образом.

[ШУМ] Здесь

у нас просто скалярное произведение ω на x.

Как видите, если x ≠ ω — это скалярное произведение равно 0,

и мы получаем просто вектор x.

Если x = ω, то это скалярное произведение = 1,

и у нас получается ω − 2ω, то есть −ω.

Таким образом, это тот же самый оператор.

Для запуска алгоритма Гровера нам потребуется во входном регистре

подготовить следующее начальное состояние, назовем его вектором s.

Это просто оператор Адамара от n ноликов,

что, как мы помним, = 1 / 2 в степени n

/ 2 сумма всех векторов пространства,

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

Итак, вектор

s — это у нас равновзвешенная сумма всех базисных векторов пространства.

И мы еще определим оператор Us,

[ШУМ]

[ШУМ] который действует следующим образом, аналогично оператору Uω.

В материалах курса вы можете найти ссылку на симулятор квантового компьютера,

разработанного моим дипломником Юрием Коноплевым,

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

оператор Us через квантовые гейты, который мы с вами уже проходили.

Алгоритм Гровера итеративен.

Каждая его итерация выглядит следующим образом.

Оператор итерации Гровера равен последовательному

применению Uω и Us,

наших операторов, которые мы с вами определили.

Давайте посмотрим, как итерация Гровера действует на вот

этот начальный вектор системы.

Нарисуем картинку.

[ШУМ] На

этой картинке по вертикальной оси у нас отложен искомый вектор ω,

а по горизонтальной оси все остальные базисные вектора, то есть горизонтальная

ось — у нас гиперпространство размерности 2 в степени n − 1.

И вектор s нависает над этим гиперпространством,

имея с ним какой-то угол, назовем его θ.

Оператор Uω, который в итерации применяется первым,

отражает наш вектор s, вообще вектор состояния системы,

относительно гиперплоскости ортогональная ω вот сюда.

Это Uω|s>,

поскольку все вектора, не равные ω, он сохраняет, а вектор ω заменяет на −ω.

Дальше оператор Us отражает вектор системы относительно вектора s.

Вот сюда.

[ШУМ] И,

поскольку здесь у нас между вектором s и вот этим вектором угол уже 2θ,

то и здесь угол получается 2 θ.

Таким образом, мы повернули за одну итерацию наш вектор системы,

пододвинули его чуть ближе к искомому вектору ω.

Что будет, если мы повторим итерацию еще раз?

Мы опять отражаем вектор системы относительно гиперплоскости

ортогональная ω, получается здесь угол −3θ,

угол с вектором s получается 4θ,

и после отражения угол с вектором s опять же остается 4θ, но в эту сторону.

И получается еще сдвиг на 2θ.

Таким образом, каждая итерация Гровера поворачивает наш вектор системы

чуть-чуть ближе к вектору ω каждый раз на угол 2θ.

После t итераций угол между нашим вектором системы и горизонтальной

гиперплоскостью будет равен θ + 2θ × T,

где T — количество итераций.

И этот угол должен быть равен π / 2,

чтобы мы пришли вектор ω и получили

его в результате измерения с вероятностью 1 или близкой к 1.

Соответственно, нам надо вычислить неизвестный нам здесь параметр T,

потому что sinθ = скалярному произведению,

модулю скалярного произведения ω × s.

Это у нас равно 1 / √N,

где N, N — это

2 в степени n.

И, поскольку N у нас достаточно большое при больших значениях n,

это примерно сам угол θ, потому что

sin примерно равен своему аргументу при маленьких значениях аргумента.

Ну что?

Решаем.

Получается, что у нас 1 /

√N (1 + 2T) = π / 2.

И отсюда нам надо выразить T.

Так, −√N.

[ШУМ] [НЕРАЗБОРЧИВО]

/ 4 − 1/2 √N,

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

И получается, что количество итераций у нас должно быть равно π/4 * √N.

В сравнении с классическим случаем, где нам нужно n-итераций,

здесь мы получаем корень из n-итераций, что разумеется, намного лучше,

хотя это и не экспоненциальное ускорение, как в алгоритме Шора.

Давайте еще раз посмотрим на схему нашего алгоритма — алгоритма Гровера.

Почему мы таким образом выбрали начальное состояние системы — вектор | s >?

Дело в том, что каждая итерация алгоритма приближает наше состояние

системы к вектору | ω >, к искомому вектору, на угол 2θ.

И количество итераций зависит от значения угла θ.

Соответственно, для того чтобы рассчитать количество итераций,

нам нужно знать угол θ.

И единственный вектор, если мы совершенно ничего не знаем про вектор | ω >,

единственный вектор, угол которого с ω мы знаем, — это угол,

который находится на одинаковом расстоянии,

имеет одинаковый угол со всеми векторами нашего пространства.

Далее, мы предположили, что искомый вектор, точка | ω > только одна.

То есть существует единственная ω, такая,

что f ω (ω) = 1.

От всех других значений fω = 0.

Если таких точек несколько,

то здесь по вертикальной оси у нас возникает сразу несколько векторов.

То есть получается, по вертикальной оси гиперпространство всех этих векторов,

на которых f(ω) дает 1, и это приводит к изменению угла θ.

Sinθ становится равен (если таких

векторов, скажем, K), то √K / √N.

Поскольку меняется угол θ, то меняется количество итераций,

и получается, что нам нужно знать точное количество таких векторов — векторов ω,

точное количество особых точек нашей функции — вот это число K.

Потому что если мы неправильно рассчитаем количество итераций и добавим чуть больше

итераций или существенно больше итераций, чем нам нужно,

мы можем проскочить вектор | ω > и оказаться где-то здесь.

Добавление итерации в алгоритме Гровера ухудшает вероятность измерения того,

что нам нужно, — векторов | ω >, и соответственно то количество итераций,

которое мы рассчитали, надо выполнять в точности, не больше и не меньше.

Ну и наконец, почему мы так определили оператор Us?

Как отражение относительно вектора s?

Дело в том, что нам в пространстве нужна какая-то точка,

относительно которой мы будем отражаться в направлении вектора | ω >.

Чем ближе эта точка будет на этой окружности к вектору | ω >,

тем меньше нам потребуется отражений.

Если бы эта точка была ровно на середине пути,

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

Всего за одну итерацию мы попали бы в вектор | ω >.

Но где же взять эту точку?

Поскольку мы ничего не знаем о векторе | ω >, то, опять же, наилучшей такой

точкой для нас является равновзвешенная сумма всех векторов пространства.

Давайте немножко пофантазируем.

Когда мы только начинаем итерацию Гровера, мы ничего не знаем о состоянии | ω >.

Давайте представим, что мы выполнили ровно половину итераций, как на слайде

на картинке справа, и находимся на половине пути состояния | ω >.

Вектор | s6 > знает об | ω > значительно больше, чем знаем мы.

И если бы мы могли отразиться от него,

мы бы за одну итерацию попали бы в искомое состояние.

Проблема в том, что нам нечего отразить относительно вектора | ω >,

поскольку он сам является вектором системы.

Вот если бы мы могли использовать его как оператор над другой системой,

где итерации Гровера еще не начались,

вот тогда бы мы в этой системе за одну итерацию попали бы в состояние | ω >.

Более того, сам вектор | s6 > мог бы быть точно таким же образом

получен из вектора | s3 > таким же отражением.

И получается, что вместо √ из n-итераций мы получаем

логарифм от n-итераций при использовании таких вот двух систем.

Для подобного усовершенствования нам придется научиться использовать

состояния — квантовые данные, как операторы — квантовые гейты.

В классических вычислениях это называется архитектурой фон Неймана.

К сожалению, для квантовых вычислений реализация такой

архитектуры находится до сих пор под большим вопросом.

Подобные операции не входят в математическую модель,

разобранную нами на второй неделе нашего курса.

Поэтому прекращаем фантазировать и переходим к доказательству

оптимальности алгоритма Гровера в той модели, которая

у нас с вами есть.

Алгоритм Гровера

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

Meet the Instructors