eslitak (eslitak) wrote,
eslitak
eslitak

Category:

Квантовый ликбез 25-3. Алгоритм Гровера - оракул.

Предыдущие посты

2. Блок 2 - "оракул".

Блок 2 проверяет соответствие входного значения заданному критерию. На входе блока 2 присутствуют суперпозиция всех N проверяемых значений. На выход - суперпозиция всех N результатов проверки. В силу такого квантового параллелизма оракул проверяет все значения за один цикл работы.
.
В работе блока 2 задействованы кубиты данных «xk... x1» и флаговый кубит «f». Все эти кубиты образуют систему из k+1 кубитов. Кубит «f», напомню, после инициализации находится в следующей суперпозиции базисных состояний:



Но сходу объяснять, как оракул работает при таком состоянии флагового кубита, будет довольно трудно. Поэтому давайте сначала разберём, что происходит, если флаговый кубит находится в одном из базисных состояний.

Пусть, например, флаговый кубит находится в состоянии:

|f〉 = |0〉

В этом случае квантовое состояние системы кубитов |x,f〉 "на входе" блока 2 несёт в себе N базисных состояний - альтернатив следующего вида:

|xk, xk-1, ... x1, 0f

Процедура проверки строится таким образом, что состояние кубита «f» в "правильных" альтернативах меняется на противоположное. В нашем случае |0〉 меняется на |1〉. В прочих "неправильных" альтернативах, флаговый кубит сохраняет состояние |0〉.

Если же изначально флаговый кубит находится в состоянии |1〉, тогда в "правильных" альтернативах его состояние в результате работы оракула меняется на |0〉.

Простейшим примером оракула является известный нам гейт «CNOT».  Если рассматривать кубит на контролирующем входе как кубит данных, а «рабочий» кубит - как флаговый, тогда можно считать, что гейт «CNOT» проверяет кубит данных на предмет его равенства единице. У единственного кубита данных всего две альтернативы. Так вот, для той альтернативы, где кубит данных находится в состоянии |1〉, состояние флагового кубита меняется. Покажем это на рисунке для случая когда флаг инициализирован в |0〉:



"Правильная" альтернатива на этом рисунке и дальше выделена зелёным цветом. Дополнительно красным выделено всё то, что относится к кубиту «f».

Заметим по ходу дела, что сепарабельное квантовое состояние (его формула на рисунке слева) в результате работы оракула меняется на запутанное состояние (формула справа). Математически, напомню, сепарабельное состояние квантовой системы характеризуется тем, что его формула в виде "голой" суммы может быть корректно преобразована в произведение двух состояний отдельных подсистем. В частности, для формулы слева:



Формулу справа аналогичным образом преобразовать не получится, это несепарабельное состояние.

Физически же сепарабельное состояние отличается тем, что в нём результат измерения одной подсистемы никак не коррелирует с результатом измерения второй подсистемы. В частности, если мы измерим кубит «f» до работы оракула, то на состояние кубита «x1» это никак не повлияет. Если же измерить «f» после оракула, то состояние кубита «x1» будет коррелировать с результатом измерения.

Аналогично «маленьким оракулом» можно считать трёхкубитный гейт «CCNOT». Он «переворачивает» флаг только для одной из четырёх альтернатив. А именно, для той, где оба контролирующих кубита равны единице (рисунок 23.3.2).



Алгоритм оракула зависит, конечно, от особенностей конкретной задачи. Но разработчик, проектирующий этот алгоритм, вправе не забивать себе голову квантовыми премудростями. Как уже говорилось, тут можно обойтись методами классической цифровой схемотехники. То есть, вычислительная схема квантового оракула аналогична (на чертеже!) классической схеме, "переворачивающей" флаговый  бит только в том случае, если на входах данных установлена искомая, "правильная" комбинация нулей и единиц. Ну а если не на чертеже, а в деле, то квантовый оракул, в отличие от классического, должен быть реализован с помощью кубитов и квантовых операций. Ведь на классической логике никакого параллелизма мы не получим.

Теперь посмотрим, что произойдёт, если флаговый кубит инициализирован в состояние (ф 25.3.1), это уже будут сугубо квантовые дела. Разберём их на примере гейта-оракула «CCNOT», показанного на рисунке 23.3.2.

Сепарабельное состояние на входе оракула можно записать следующим образом:



Внимательно следим за знаками и флаговым кубитом!

Теперь воздействуем на это состояние оракулом. В результате флаговый кубит в "правильных" альтернативах "переворачивается":



Но, о квантовое чудо, это же опять сепарабельное состояние! Оно легко раскладывается на две скобки (продолжаем формулу):



Что мы видим? Кубит «f» в каком состоянии был на входе оракула, в таком же и остался на выходе. А вот в состоянии пары |x2, x1амплитуда вероятности "правильной" альтенативы (оба кубита - "единица") поменяла знак с положительного на отрицательный, что нам и требуется для последующих операций.

Что же, давайте спроектируем оракул для нашего примера. Он может выглядеть, например, так (рисунок 23.3.3):



Прошу иметь в виду, что формулы входного и выходного состояний подрегистра данных |x и системы |x,f, объединяющей подрегистр данных и флаговый кубит, показанные на рисунке, актуальны только для первого прохода алгоритма. На следующем проходе они похожи, но амплитуды вероятности альтернатив будут уже другими.

Кстати, формулы эти "распутывать" вам не обязательно, они по смыслу аналогичны тем, что мы разбирали чуть выше для оракула "CCNOT", только более громоздкие. Ведь в примере мы имеем дело не с двухкубитным, а с четырёхкубитным регистром данных.

Сверху номера со стрелочками - это чтобы удобнее было пояснять, что происходит на разных "срезах" схемы.

Срез 1 - тут у нас пока начальное состояние. Состояние
|xподрегистра данных несёт в себе 16 чисел - альтернатив.

Если рассмотреть совокупное состояние , то мы видим, что каждое число представлено двумя альтернативами. Положительной, вида |x4,x3,x2,x1,0, и отрицательной вида |x4,x3,x2,x1,1〉.

Срез 2 - благодаря гейтам [X], применяемым к кубитам «x2», «x3», альтернатива |1001, та самая, которую мы ищем, превращается в альтернативу |1111〉. Прочие альтернативы после такого преобразования хоть один "ноль" в кубитах данных да имеют.

Срез 3 - с помощью трёх гейтов «CCNOT» реализуется логическая операция «И» для кубитов данных. Кубиты «v1», «v2» играют тут вспомогательную роль, упрощая организацию логического «И».

Только если все четыре кубита данных находятся в состоянии |1〉 , то есть, для альтернативы |1111, кубит «f» "переворачивается". Но тут же, благодаря особому начальному состоянию кубита «f»:

- а
льтернатива |1111меняет знак;

- состояние кубита
«f» восстанавливается в первоначальное.

Срез 4 - теперь вспомогательные кубиты «v1», «v2» следует вернуть в состояние |0〉. Это и обеспечивают два гейта «CCNOT».

Срез 5 - опять применяем гейт [X] к кубитам «x2», «x3», возвращая их "на место". В результате все альтернативы вновь модифицируются. В частности, альтернатива "минус |1111
〉" превращается в альтернативу "минус |1001〉",  Все остальные альтернативы имеют положительную амплитуду вероятности Требуемый от оракула результат достигнут!

Вот, частный пример оракула рассмотрели, теперь подпустим немного формалистики. Обобщённо, для любой задачи, оракул можно представить в виде вот такого "чёрного ящика":



В формулах на рисунке приняты следующие обозначения:

- суммирование по всем i, принадлежащим к множеству "неправильных" значений;
- суммирование по всем i, принадлежащим к множеству "правильных" значений.

a - амплитуды вероятности "неправильных" альтернатив;
b - амплитуды вероятности "правильных" альтернатив.

С каждым проходом алгоритма амплитуды "a" будут уменьшаться, а амплитуды "b" - увеличиваться. Почему - про это мы узнаем в следующем посте.


Продолжение
Tags: квантовый ликбез, физика
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 14 comments