?

Log in

No account? Create an account

eslitak

Previous Entry Поделиться Next Entry
11:41 pm: Квантовый ликбез 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: ,

Comments

[User Picture]
From:ptushnik
Date:Август 22, 2014 04:50 pm
(Link)
Остались сомнения в правильном понимании следующего куска:
"Как уже говорилось, тут можно обойтись методами классической цифровой схемотехники. То есть, вычислительная схема квантового оракула аналогична (на чертеже!) классической схеме, "переворачивающей" флаговый бит только в том случае, если на входах данных установлена искомая, "правильная" комбинация нулей и единиц. Ну а если не на чертеже, а в деле, то квантовый оракул, в отличие от классического, должен быть реализован с помощью кубитов и квантовых операций. Ведь на классической логике никакого параллелизма мы не получим."

В классической цифровой схемотехнике вычисления выполняются последовательно. (Распараллеливание всего, чего можно, тоже присутствует, но предлагаю оставить его за скобками, чтобы не путать с квантовыми штучками.) Следующая операция использует результаты предыдущей и последовательность может быть довольно длинной. Поскольку квантовые вычисления носят вероятностный характер, не будут ли они "тормозить" на каждой элементарной операции?
[User Picture]
From:eslitak
Date:Август 24, 2014 08:45 pm
(Link)
На этом этапе никакого вероятностного характера нет, всё детерминировано. Вероятность "работает" только при измерении, то есть, считывании результата. А пока мы детерминированно работаем над тем, чтобы вероятность считывания правильного результата максимально увеличить.

Конечно, сама по себе проверка для одного значения осуществляется последовательной цепью операций. Но поскольку оракул имеет дело с суперпозицией всех N значений, то он параллельно ведёт N таких проверок. Так что тормозов не будет.
[User Picture]
From:urjuk
Date:Октябрь 5, 2015 02:57 pm
(Link)
тут я уже, честно скажу, скролил, потому как пошла специальная тема, имхо. но меня насторожило понятие "оракул". недавно разбираясь в Геделе (зачем мне это надо?:)) наткнулся в объяснениях на оракула также. это не одно и тоже лицо? :)
http://fregimus.livejournal.com/85513.html?view=7211529#t7211529
см. камент от falcao
(простите, если вопрос показался Вам глупым)
[User Picture]
From:eslitak
Date:Октябрь 5, 2015 05:41 pm
(Link)
Здесь (и вообще в теории квантовых и обычных вычислений) под оракулом понимается алгоритм, который определяет, принадлежит ли число на входе (оракула) к определённому множеству. Это чисто технический термин - "оракул". Простейшим примером такого технического оракула является банальный компаратор, сравнивающий два числа и выставляющий на выходе "1", если числа равны, или "0", если не равны.

ИМХО, кстати, "оракул" - не слишком удачное название. Сбивает с толку
некоторым мистическим душком.

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

Так что, это "не одно и то же лицо". Мой оракул - это младший брат по разуму того оракула, о котором говорит falcao. Сильно младший :)


Edited at 2015-10-05 17:41 (UTC)
[User Picture]
From:urjuk
Date:Октябрь 6, 2015 04:53 pm
(Link)
Спасибо за развернутый ответ.
Разработано LiveJournal.com