eslitak (eslitak) wrote,
eslitak
eslitak

Category:

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

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

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

1. Вычисляется Am - среднее значение амплитуд вероятноcти по всем альтернативам. Самым обычным образом: амплитуды всех альтернатив суммируются, и полученная сумма делится на количество альтернатив:



2. Амплитуда каждой группы преобразуется по следующему правилу:



Вот и вся хиторость! После этой операции положительные амплитуды по модулю уменьшаются, а отрицательные - по модулю увеличиваются. Таким образом мы усиливаем "правильные" альтернативы.

Посмотрим, как эта матемаматика работает в нашем примере.

На первом проходе алгоритма на выходе оракула мы имеем суперпозицию из 16-ти равновесных альтернатив. Равновесных, потому что модули амплитуд вероятности всех альтернатив равны между собой и равны 0,25. Но вот знаки амплитуд вероятности альтернатив различаются.

У пятнадцати "неправильных" альтернатив, "несущих" числа от 0 до 8 и от 10 до 15, амплитуды вероятности равны +0,25.

У одной "правильной" альтернативы (число 9) амплитуда вероятности равна -0,25.

Значит, среднее по всем амплитудам вероятности равно:




Проиллюстрруем эту ситуацию следующим графиком:



После инверсии относительно среднего амплитуда вероятности всех "неправильных" групп преобразуется следующим образом:



А амплитуда вероятности "правильной" группы "9" преобразуется так:



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



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

Теперь нам надо выяснить, как реализовать эту математику с помощью унитарных воздействий на кубиты. Матрица [D] воздействия, осуществляющего требуемое преобразование квантового состояния k-кубитного подрегистра данных, выглядит следующим образом:



Сама матрица [D] показана в чёрном цвете. Всё зелёное - это поясняющая информация.

Первая строка матрицы определяет, в какой пропорции воздействие расщепляет базисное состояние, несущее число "0". Вторая - расщепление базисного состояния, соответсвующее единице,  ну и так далее до числа "N-1". Чтобы вам легче было ориентироваться, справа от каждой строки показано "расщепляемое" базисное состояние.

Давайте посмотрим, как это преобразование работает для простейшего двухкубитного регистра данных. В этом случае N = 4, стало быть, матрица "инверсии относительно среднего" должна иметь следующий вид:



Пусть на входе у нас такое состояние подрегистра "x":



На следующей диаграмме визуализирован процесс "усиления" альтернативы с отрицательной амплитудой вероятности, а именно альтернативы |11〉 - число "3".


Как видим, в результате воздействия каждая из четырёх групп виртуальных вариантов "распадается" на четыре "осколка". Всего получается шестнадцать "осколков". И они тут же эти вновь группируются, но уже в другой пропорции. Образовавшиеся "кусочки" групп |00〉, |01〉, |10〉, изначально имеющих положительную амплитуду вероятности, имеют разный знак и взаимно "уничтожаются", то есть, становятся нереализуемыми. Зато |11〉 группа, "отрицательная" до операции, наоборот, "усиливается" за счёт суммирования однознаковых "кусков".

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

Ну что же, теперь нам надо выяснить, как реализовать матрицу инверсии относительно среднего с помощью элементарных гейтов. Как уже говорилось, вычислительная схема блока 3 является универсальной для любой задачи поиска. Эта универсальная схема показана на следующем рисунке:



Здесь, как раньше, k - это количество кубитов в подрегистре данных "x".

В схеме задействован однокубитный гейт [iI], который нам прежде не встречался. Этот гейт "расщепляет" базисные состояния кубита следующим образом:

[iI] |0〉  = i |0〉
[iI] |1〉  = i |1〉

Здесь "i" - это мнимая единица. Ранее неоднократно подчёркивалось, что апмлитуды вероятности выражаются в общем случае комплексными числами, но в частных примерах мы до этого места мы обходились без мнимых значений. Ну пусть уже будут!

Как видим, схема "усилителя" построена, в основном, из однокубитных гейтов. Имеется единственная k-кубитная операция "C...СNOT", в которой всего один кубит является "рабочим" (на схеме - самый нижний), а все остальные биты - управляющие. В этой операции "рабочий" кубит изменяет своё состояние только в тех альтернативах, где все управляющие кубиты находятся в состоянии |1〉.

Теперь нарисуем вычислительную схему для нашего примера.



В схеме опять задействованы вспомогательные кубиты "v1" и "v2". Они здесь использованы для того, чтобы упростить реализацию четырёхкубитного гейта "CCCNOT". Ещё раз напомню, что коэффициенты в формулах - амплитуды вероятности - актуальны только для первого прохода алгоритма Гровера.

Здесь, пожалуй, нет смысла рисовать разноцветные диаграммы и разбирать подробно, как меняется состояние подрегистра данных на разных срезах схемы - это скорее запутает, чем прояснит дело. Тут такой случай, когда целую идею невозможно разобрать на отдельные "кирпичики". Поэтому "рядовых" читателей призваю просто поверить на слово: эта схема действительно реализует инверсию относительно среднего - усиление альтернатив с отрицательной амплитуой вероятности.

Ну а для недоверчивых (в хорошем научном смысле) читателей, тех, кто не боится формул и кропотливых вычислений, чуть погодя сделаю специальное дополнение к этой части. Там будут доказательства того, что схема работает. Заодно посмотрим на практическом примере, какая в квантовой механике польза от матриц. Это пригодится, если вы планируете и дальше разбираться в квантовых тонкостях.

Вот, основные сложности позади, все блоки алгоритма Гровера мы разобрали. Осталось сделать несколько завершающих штрихов.

Продолжение
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.
  • 0 comments