?

Log in

No account? Create an account

eslitak

Previous Entry Поделиться Next Entry
12:14 am: Квантовый ликбез 25-2. Алгоритм Гровера - инициализация.
Предыдущие посты

Теперь разберём алгоритм Гровера подробнее. Будем вести две линии рассказа:

- теоретическую, в словесах и общих формулах;
- практическую, в числах, диаграммах и схемах.

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

Для практического описания нам потребуется конкретная задача. В качестве примера возьмём такую: найти число 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 есть?


Tags: ,

Comments

[User Picture]
From:photo_viewer
Date:Август 14, 2014 08:56 pm
(Link)
ух. ну очень своевременная книга.
[User Picture]
From:eslitak
Date:Август 15, 2014 06:44 am
(Link)
Радует, что это ещё кому-то нужно :)
[User Picture]
From:photo_viewer
Date:Август 15, 2014 02:40 pm
(Link)
Лет 20 шашек в руки не брал, а тут интерес возник. Начал копать, но внятное изложение - редкость. И тут как раз случайно на Ваш ликбез наткулся. Признателен очень.
[User Picture]
From:yoginka
Date:Август 15, 2014 09:16 pm
(Link)
//Специфична под задачу только схема блока 2. А именно, та её часть, которая проверяет соответствие входного значения заданному критерию. Понятно, что для серьёзных задач, типа поиска решения какого-нибудь многоэтажного уравнения, схема этой "проверялки" будет гораздо сложнее, чем в нашем простейшем примере. Но нам в эти дебри лезть не стоит, поскольку это уже не столько квантовая специфика, сколько особенности классической цифровой схемотехники, изучение которой не входит в наши планы.
//
- Мне (как программисту) блок 2 представляется потенциально проблемным с смысле ресурсов, в частности, времени. Если это делается классическим (не квантовым) способом, то не сведет ли это на нет весь выигрыш блоков 1 и 3?
[User Picture]
From:eslitak
Date:Август 17, 2014 08:31 pm
(Link)
Это делается квантовым способом, мы ведь работаем с кубитами и применяем квантовые вентили. Так что квантовый параллелизм обеспечивает необходимые "ресурсы", оракул обрабатывает все числа за один проход. Классическим тут является сам алгоритм. Нарисуйте классическую схему, устанавливающую флаг для нужной комбинации нулей и единиц на входе. Но реализуйте её на кубитах и квантовых гейтах - получите готовый оракул.

Подробности о блоке 2 в следующей серии.
[User Picture]
From:yoginka
Date:Август 17, 2014 09:03 pm
(Link)
Спасибо, теперь понятно.
[User Picture]
From:eslitak
Date:Август 17, 2014 08:52 pm
(Link)
Маленькое уточнение: при построении классического алгоритма оракула можно использовать только обратимые операции, например, нельзя использовать элемент "И". Иначе не получится реализовать алгоритм на квантовых гейтах.
Разработано LiveJournal.com