Теперь разберём алгоритм Гровера подробнее. Будем вести две линии рассказа:
- теоретическую, в словесах и общих формулах;
- практическую, в числах, диаграммах и схемах.
Надеюсь, что эти две линии дополнят друг друга и облегчат вам понимание алгоритма. Но, чтобы различать, где говорится о теории, а где – о практике, выделим текст цветом. Всё, что будет касаться общей теории алгоритма Гровера, останется черным. А практическую часть покрасим в синий.
Для практического описания нам потребуется конкретная задача. В качестве примера возьмём такую: найти число 9 среди целых чисел от 0 до 15. Не смотря на кажущуюся "игрушечность" задачи, её будет вполне достаточно для демонстрации основных идей алгоритма Гровера. Нам ведь главное понять следующие вещи:
а) Как создать суперпозицию всех значений, среди которых мы будем искать нужное (блок 1). В нашем примере мы создадим суперпозицию 16-ти значений – от 0 до 15.
б) Как отыскать и "отмаркировать" нужную группу в суперпозиции (блок 2). Наш простейший оракул просто сравнит значение в каждой альтернативе с числом 9 – это и будет проверка на соответствие входного значения заданному критерию. И для искомой группы, а именно |1001〉, которая соответствует числу 9 в двоичном исчислении, оракул инвертирует флаговый кубит. Что, в свою очередь, вызовет изменение знака амплитуды вероятности группы |1001〉.
в) Как усилить виртуальную группу с отрицательной амплитудой верояности (блок 3). В нашем примере мы, значит, проследим, как в результате работы блока 3 увеличивается амплитуда группы |1001〉.
Здесь и дальше нумерация блоков как на рисунке 25.1.2.
Тут надо сказать, что вычислительные схемы блоков 1 и 3 универсальны для любой решаемой задачи, если не учитывать разницу в количестве кубитов данных. Специфична под задачу только схема блока 2. А именно, та её часть, которая проверяет соответствие входного значения заданному критерию. Понятно, что для серьёзных задач, типа поиска решения какого-нибудь многоэтажного уравнения, схема этой "проверялки" будет гораздо сложнее, чем в нашем простейшем примере. Но нам в эти дебри лезть не стоит, поскольку это уже не столько квантовая специфика, сколько особенности классической цифровой схемотехники, изучение которой не входит в наши планы.
Итак, надеюсь, я убедил вас в том, что выбранная учебная задача годится для разбора алгоритма Гровера.
____________________________________
____________________________________
Перед тем, как приступить к подробностям, хочу ещё вкратце напомнить и дополнить некоторые тонкости квантовой математики, которые мы уже проходили. При желании можете пропустить этот вспомогательный текст до следующей зелёной отбивки. Если же что-то дальше будет непонятно, вернитесь и прочитайте.
а) Если квантовая система "A" находится в чистом состоянии, то это состояние математически может рассматриваться как вектор |A〉, представляющий собой сумму векторов базисных состояний с некоторыми коэффициентами - амплитудами вероятности. В частности, для квантовой системы типа "кубит" это выглядит так:
б) Если квантовые системы "A" и "B" находятся в чистом состоянии каждая, то совокупное состояние |AB〉 может рассматриваться как вектор, представляющий собой произведение векторов |A〉 и |B〉. Скажем, если у нас есть два кубита в чистых состояниях:
тогда двухкубитное состояние можно записать так:
Речь, строго говоря, идёт о тензорном произведении, но это уже сильно высшая математика, мы туда не полезем. Для нашего ликбеза достаточно владеть элементарной техникой раскрытия скобок. Раскрываем и продолжаем формулу:
В каждом члене этой суммы присутствует произведение двух однокубитных базисных векторов вида:
Индексы временно добавлены, чтобы вы сориентировались, где тут какой кубит. Это произведение базисных состояний отдельных кубитов можно понимать, в свою очередь, как базисное состояние двухкубитной системы, или двухкубиный базисный вектор:
Собственно, это математическое свойство как раз и является проявлением вышеупомянутой "тензорности" произведения. Учитывая это, можем переложить (ф. 25.2.1-2) в следующий вид:
Индексы в базисных состояниях опять опущены, мы ведь уже запомнили, где тут какой кубит. Слева - "a", справа - "b". Мы таким приёмом и дальше будем пользоваться: сначала с индексами, чтобу показать, где чьё место в формуле, а потом без индексов, чтобы не загромождать.
Переведём запись (ф. 25.2.1-3) с "математического" на "физический". Формула показывает амплитуды вероятности четырёх реализуемых групп виртуальных вариантов. Под виртуальным вариантом в данном случае подразумевается та или иная комбинация результатов будущих измерений кубитов "A" и "B".
____________________________________
____________________________________
Теперь договоримся про обозначения. Пусть в теоретической линии подрегистр данных обозначается буквой «x», а его отдельные кубиты: x1, x2 … xk. Подразумеваем, что xk – это старший разряд числа, x1 – младший. Квантовое состояние подрегистра данных будем записывать вот в таком формате:
|xk, … x1〉
Так, как принято для чисел: старший разряд слева, младший - справа. Или будем писать сокращённо:
|x〉
Количество k кубитов в подрегистре данных определяется размером области поиска – количеством проверяемых решений.
В нашей конкретной задаче… Нет, давайте, дальше, чтобы не тащить с собой эту словесную конструкцию: «наша конкретная задача», будем говорить коротко – «пример». В примере мы ищем решение в виде целого числа в диапазоне от 0 до 15, значит, наш подрегистр данных должен «вмещать» 16 базисных состояний. Для этого достаточно 4-х кубитов: x1, x2, x3, x4. Четырёхкубитное квантовое состояние подрегистра данных запишем, стало быть, вот в таком формате:
|x4, x3, x2, x1〉
Также нам понадобится служебный флаговый кубит, обозначим его «f». Подрегистр данных и флаговый кубит в совокупности несут в себе k+1 кубитное квантовое состояние:
|x, f〉
В примере это будет пятикубитное состояние:
|x4, x3, x2, x1, f〉
Перечисленные нами кубиты являются обязательными для алгоритма Гровера в независимости от того, какую задачу поиска мы решаем. Для конкретных задач могут понадобиться ещё дополнительные кубиты. В примере мы используем два дополнительных кубита, обозначим их v1, v2.
Итак, договорились, в примере алгоритм Гровера использует регистр из семи кубитов.
Теперь пошли по блокам.
1. Блок 1 - подготовка исходных данных, или, как говорят программисты, инициализация.
1.1. Первым делом приводим кубитовый регистр в исходное состояние.
Все кубиты подрегистра «x» приводим в состояние |0〉.
Технически операция «обнуления» осуществляется путём измерения кубита. Предполагается, что до начала работы все кубиты находятся в произвольном, как правило, неизвестном нам состоянии. Значит, в результате измерения мы можем получить как 〈0〉, так и 〈1〉. Если получен результат 〈0〉, прекрасно, значит, кубит гарантированно находится в состоянии |0〉, .оставляем его в покое до следующего шага. Если 〈1〉 – применяем к такому кубиту унитарную операцию [X], она же - квантовый гейт «NOT».
Каждый кубит подрегистра x находится теперь в чистом состоянии |0〉. Значит, системное состояние подрегистра x мы можем записать как произведение состояний отдельных кубитов или как k-кубитное квантовое состояние:
В примере:
В правой части, где поясняющие индексы удалены, сразу видно, что подрегистр данных хранит пока что единственную группу виртуальных вариантов, представляющую двоичное число "0".
Для примера можем изобразить диаграмму состояния подрегистра данных:
Но это ещё не всё, надо инициализировать также служебные кубиты.
Кубит «f» приводим в состояние:
Это тоже не сложно. Сначала переводим кубит «f» в состояние |1〉, затем применяем к нему однокубитную операцию Адамара [H], «расщепляющую» базисное состояние |1〉 в пропорции (ф. 25.2.4).
Кубиты "v1", "v2", которые являются специфическими для примера, приведем в состояние |0〉.
1.2. Создаём в подрегистре данных x равновесную суперпозицию всех проверяемых значений.
Для этого достаточно применить к каждому из кубитов подрегистра данных гейт Адамара [H]. Пусть сначала мы применяем гейт адамара к кубиту x1. Тут на самом деле не важно, с какого кубита начать. А можно вообще работать со всеми кубитами параллельно, как и будет показано ниже на схеме. Но в целях постепенности рассказа будем считать, что мы начали с x1. Кубит изменяет своё состояние следующим образом:
Значит, общее состояние подрегистра данных теперь таково (сразу пишем для для нашего четырёхкубитного примера):
Пожалуйста, образовалось две равновесных реализуемых альтенативы. Одна из них представляет число «0», другая - число «1». Проиллюстрируем это действие диаграммой:
Применив операцию [H] ко всем четырём кубитам данных, получим равновесную суперпозицию целых чисел от "0" до "15", что и требовалось от блока 1. Всё это показано на следующей диаграмме:
Сверху - формулы состояний подрегистра "x" на разных этапах инициализации. Чтобы сделать длинные формулы компактнее, применёна запись с символом суммирования, давайте её расшифруем. В общем виде, для k-кубитного регистра данных, после инициализации состояние будет выглядеть так:
Здесь N - это общее количество базисных состояний (представляемых чисел) в суперпозиции, определяемое как 2 в степени k.
Для нашего примера, где k = 4, можем записать более конкретно:
Под |pi〉 в формулах (ф. 25.2.7) и (ф. 25.2.8) подразумевается базисное k-кубитное состояние, соответсвующее двоичному представлению числа "i". Например:
_
|p0〉 = |0000〉
|p1〉 = |0001〉
И так далее, до 15-ти.
И запомните, пожалуйста, чтобы не путаться в обозначениях:
"Икс" с нижним индексом x1, x2 … xk обозначает отдельный кубит подрегистра данных - одну двоичную цифру.
"Пэ" с нижним индексом p1, p2 … pN обозначает одно из базисных состояний подрегистра данных - одно двоичное число.
Для полной ясности один раз распишем формулу с символом суммирования (F_25.2.8) целиком:
Зелёным цветом выделена группа, кодирующая число "9". Именно эту группу мы дальше будем "вылавливать" и "усиливать".
И нарисуем вычислительную схему блока 1, точнее, подблока 1.2, для нашего примера.
Подблок 1.1. рисовать не будем. Подразумеваем, что он уже отработал и привёл кубиты в требуемые начальные состояния, которые показаны на схеме слева.
Справа также показаны состояния кубитов подрегистра данных на выходе блока 1. Пока кубиты не запутаны, мы вправе это делать, в смысле, рассматривать каждый кубит отдельно.
Вопросы по блоку 1 есть?