МАТЕМАТИЧЕСКАЯ МОДЕЛЬ АЛГОРИТМА ГРОВЕРА

MATHEMATICAL MODEL OF THE GROWER ALGORITHM

Barnoniso Niyazova

Master, Department of Applied Mathematics and Programming Russian State University named after A.N. Kosygina,

Russia, Moscow

АННОТАЦИЯ

В данной статье проанализирована и описана математическая модель квантового алгоритма поиска данных, а именно квантовый алгоритм Гровера. Алгоритм Гровера считается одним из самых известных алгоритмов квантовых вычислений. Этот несложный подход к описанию математической модели познакомит с преимуществами систем квантовых вычислений.

ABSTRACT

This article analyzes and describes a mathematical model of a quantum data retrieval algorithm, namely the quantum Grover algorithm. Grover's algorithm is considered one of the most famous algorithms for quantum computing. This simple approach to describing a mathematical model will introduce you to the benefits of quantum computing systems.

Ключевые слова: квантовый компьютер, алгоритм, квантовый алгоритм, винтель, квантовый оракул, оракул, алгоритм Гровера.

Keywords: models of open systems model open systems environment, information security.

В наше время можно наблюдать связь между информатикой и физикой. Оказалось, что эффективность решения задач напрямую зависит от законов физики.

Алгоритм Гро вера решает з адачу нестру ктурирован ного поиск а. Если ест ь неупорядоче нный набор д анных и требуетс я найти в нё м какой-то о дин элемент, у довлетворя ющий специф ическому требо ванию. Этот а лгоритм ис пользует с войство кв антовой интерфере нции для то го, чтобы н айти значе ния некоторо го параметр а, на которо м заданная фу нкция выдаёт о пределённы й результат [1].

Алгоритм Гровера состоит из следующих шагов [2]:

Инициализация начального состояния. Необходимо подготовить равновероятностную суперпозицию состояний всех входных кубитов. Это делается при помощи применения соответствующего гейта Адамара, который равен тензорному произведению n унарных гейтов Адамара друг на друга [1].

Применение итерации Гровера. Данная итерация состоит из последовательного применения двух гейтов — оракула и так называемого гейта диффузии Гровера (будут детально рассмотрены ниже). Эта итерация осуществляется раз  раз [1].

Измерение. После применения итерации Гровера достаточное количество раз необходимо измерить входной регистр кубитов. С очень высокой вероятностью измеренное значение даст указание на искомый параметр. Если необходимо увеличить достоверность ответа, то алгоритм прогоняется несколько раз и вычисляется совокупная вероятность правильного ответа.

Задача поиска состоит в следующем: имеется неупорядоченная база данных, состоящая из N-элементов, из которых лишь один удовлетворяет данным условиям — именно этот элемент нужно найти. Если элемент можно осмотреть, то определение того, удовлетворяет он требуемым условиям или нет, осуществляется за один шаг.

Для более четкого описания математической модели алгоритма Гровера была сформулирована задача, в которой нужно найти число 9 среди целых чисел от 0 до 15. На рисунке 1 Блок схема работы квантового алгоритма гровера в виде задачи приведена блок схема работы квантового алгоритма Гровера в виде задачи, по этой блок схеме будет реализована задача.

Рисунок 1. Блок схема работы квантового алгоритма Гровера

1. Блок 1 – инициализация

1.1 Первым делом приводим кубитовый регистр в исходное состояние.

Все кубиты подрегистра «x» приводим в состояние |0〉.Технически операция «обнуления» осуществляется путём измерения кубита. Предполагается, что до начала работы все кубиты находятся в произвольном, как правило, неизвестном нам состоянии.

Каждый кубит подрегистра x находится теперь в чистом состоянии |0〉. Значит, системное состояние подрегистра x мы можем записать как произведение состояний отдельных кубитов или как k-кубитное квантовое состояние:

,

Но это ещё не всё, надо инициализировать также служебные кубиты.

Кубит «f» приводим в состояние:

Это тоже не сложно. Сначала переводим кубит «f» в состояние |1〉, затем применяем к нему однокубитную операцию Адамара [H], «расщепляющую» базисное состояние |1〉 в пропорции.

Кубиты  , которые являются специфическими для примера, приведем в состояние |0〉.

1. 2 Создаём в подрегистре данных x равновесную суперпозицию всех проверяемых значений.

Для этого достаточно применить к каждому из кубитов подрегистра данных гейт Адамара [H] [3]. . Пусть сначала мы применяем гейт адамара к кубиту x1. Но в целях постепенности рассказа будем считать, что мы начали с x1. Кубит изменяет своё состояние следующим образом:

Применяем операцию [H] ко всем четырём кубитам данных, получим равновесную суперпозицию целых чисел от "0" до "15", что и требовалось от 1 блока. В общем виде, для k-кубитного регистра данных, после инициализации формула будет выглядеть так:

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

Под в формулах подразумевается базисное k-кубитное состояние, соответствующее двоичному представлению числа "i". Например:

,

И так далее, до 15-ти. Для полной ясности один раз распишем формулу с символом суммирования целиком:

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

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

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

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

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

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

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

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

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

На формуле __ приведен оракул для четырехкубитного регистра:

3. Блок 3 – усилитель

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

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

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

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

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

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

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

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

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

Рисунок 2. График амплитуд вероятностей от 0 до 15

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

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

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

Рисунок 3. Амплитуда вероятности правильной группы 9

4. Блок 4 – повторение и измерение

На завершающем этапе мы немного уточним и дополним то, что уже говорилось в общем обзоре алгоритма Гровера. А также поговорим о том, почему квантовые компьютеры до сих пор не окружают нас со всех сторон.

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

В примере после первого прохода у нас следующий расклад:

• амплитуды вероятности "неправильных" альтернатив: +0,1875
• амплитуда вероятности "правильной" альтернативы: +0,6875

После второго прохода:

• амплитуды вероятности "неправильных" альтернатив: +0,078*
• амплитуда вероятности "правильной" альтернативы: +0,953

* Здесь и ниже округлено до трёх знаков после запятой.

После третьего прохода:

• амплитуды вероятности "неправильных" альтернатив: -0,051
• амплитуда вероятности "правильной" альтернативы: -0,980

Всё, для нашей задачи мы достигли возможного максимума усиления. Убедитесь сами, что если мы сделаем ещё один проход блоков 2 и 3, то получим:

• амплитуды вероятности "неправильных" альтернатив: -0,167
• амплитуда вероятности "правильной" альтернативы: +0,763

То есть, "правильная" амплитуда вероятности после четвёртого прохода уменьшится. В примере мы с вероятностью примерно 0,961 получим при измерении правильный ответ: двоичное число 〈1〉 〈0〉 〈0〉 〈1〉.

Список литературы:

1. Grover L.K. A fast quantum mechanical algorithm for database search // Proceedings, 28th Annual ACM Symposium on the Theory of Computing. -1996. - P. 212-232.
2. Душкин Р.В. Квантовые вычисления и функциональное программирование. / Р.В. Душкин — 2014. — 318 с., Ил.
3. Сапаев Д., Булычков Д. Квантовые вычисления против классических: зачем нам столько цифр. URL: https://habr.com/company/sberbank/blog/343308/ (Дата обращения 15.01.2019).
4. Риффель Э., Полак В. Основы квантовых вычислений // Квантовые компьютеры и квантовые вычисления: перевод с англ.: Романюк А.Ю., Федичкин Л.Е. – 2000. – №1.