?

Log in

No account? Create an account

eslitak

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

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


Оттолкнёмся от классического алгоритма поиска. В самом общем виде этот алгоритм можно представить так:



Подразумевается, что в ячейке памяти «x» хранится предполагаемое решение, значение, которое мы проверяем на предмет соответствия некоему заданному критерию.

«Стартовый» блок 1 устанавливает исходное значение «x». Например, если речь идёт о поиске решения в виде целого числа в диапазоне от «0» до «N», тогда в качестве исходного значения «x» выбирают обычно наименьшее – «0». Так же устанавливается в «0» служебная ячейка «f» (о ней чуть ниже).

Блок 2 осуществляет расчёт и/или проверку соответствия значения в ячейке «x» заданному критерию. Обычно этот блок организуется так, что результат проверки сохраняется в специально выделенной битовой ячейке памяти, у нас это ячейка «f» (программисты называют такой бит флагом). Если результат проверки положительный, флаговый бит инвертируется. Если мы условились, что в начале флаговый бит установлен в
«0» , то при положительном результате проверки он «переворачивается» в «1». При отрицательном результате проверки флаг сохраняет изначальное состояние. Например, если мы решаем задачу факторизации некоего числа «M», тогда блок 2 осуществляет деление «M» на «x». Если делится без остатка – делитель найден – в бит «f» записывается «1». Если делиться с остатком – текущее значение «x» делителем не является – в «f» остаётся значение «0».

Блок 3 организует дальнейшую работу алгоритма в зависимости от результата проверки текущего «x». Если флаг равен «1» – искомое найдено – алгоритм останавливается. Нам остаётся только прочитать результат поиска в ячейке «x». Если же флаг равен «0», поиск продолжается.

Блок 4 изменяет текущее значение «x». Как правило, «x» просто увеличивается на единицу. Дальше опять запускается блок 2, проверяя теперь уже новое значение.

Таким образом, алгоритм «крутится» в цикле «блок 3 – блок 4 – блок 2 – блок 3» до тех пор, пока не будет найдено решение задачи.

По хорошему, тут ещё должна быть «ветка», останавливающая алгоритм в том случае, если решение вообще не найдено в предполагаемой области поиска. Но мы эти тонкости проигнорируем.

Теперь такими же «крупными мазками» изобразим алгоритм квантового поиска:


Перед тем, как перейти к обсуждению этой картинки, напомню, что мы работаем с кубитовым регистром. Размер регистра – количество кубитов – выбирается таким образом, чтобы гарантированно перекрыть весь диапазон поиска. Плюс добавляется один «флаговый» кубит. Ту часть регистра, где храняться проверяемые данные, обозначим как «X» и назовём это «подрегистр данных». Отдельные кубиты подрегистра данных обозначим как «x1, х2 ... хk». Здесь k – это количество кубитов в регистре. А «флаговый» кубит обозначим как «f».


На практике понадобится ещё несколько служебных кубитов, но их назначение мы выясним позже. А пока вкратце пробежимся по отдельным блокам. Если сходу не всё будет понятно – не беда, дальше мы всё разберём подробно.

Блок 1 формирует в кубитах «x1, х2 ... хk» равновесную суперпозицию всех значений из области поиска. Флаговый кубит «f» устанавливается в состояние:




Зачем такое странное состояние - об этом чуть позже.

Блок 2 делает то же самое, что и в классическом случае: считает и проверяет соответствие входного значения заданному критерию. Но в квантовом случае обрабатывается не один экземпляр входных данных, а сразу все альтернативные экземпляры то есть, вся область поиска.

Процедура проверки строится так, что состояние кубитов данных «x1, х2 ... хk» не изменяется. Зато изменяется состояние флагового кубита. А именно: в тех альтернативах, где проверямое значение соответствует заданному критерию, флаговый кубит инвертируется.

Точнее говоря, он бы инвертировался, если бы изначально был установлен в базисное состояние
|0〉 или |1〉. Но флаг был инициализирован в суперпозицию базисных состояний (ф. 25.1.1). В этом случае срабатывает чисто квантовая цепь событий: инверсия  флага для "правильных" состояний приводит к такому изменению состояния квантового регистра в целом, что флаг возвращается в исходное состояние (ф. 25.1.1), но амплитуды вероятности "правильных" групп изменяют знак (с положительного на отрицательный).

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

Блок 3 тут самый «хитрый» - он увеличивает амплитуды вероятности тех альтернатив - групп вариантов, у которых амплитуды вероятности отрицательны. Стало быть, после одного прохода алгоритма, альтернативы, несущие правильный ответ, имеют большую вероятность реализоваться, чем все остальные.

Затем снова работает блок 2, после блок 3, и вероятность «правильных» альтернатив становится ещё выше. После определённого количества таких циклов вероятность «правильной» альтернативы максимально приближается к единице.

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

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

После отработки необходимого количества циклов мы измеряем состояния кубитов «х1, x2, ...
xk»: полученная комбинации нулей и единиц и будет правильным ответом с очень высокой вероятностью.

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

В продолжении мы рассмотрим работу блоков 1, 2, 3 более подробно.


Продолжение


Tags: ,

Comments

[User Picture]
From:ptushnik
Date:Июль 15, 2014 03:50 am
(Link)
На первой картинке справа от проверки должно быть: "f=1".
И несколько удивляет, что шаблон бесконечного арифметического цикла назван классическим (!) алгоритмом поиска. :)
[User Picture]
From:eslitak
Date:Июль 15, 2014 04:14 pm
(Link)
Спасибо, багу починил.
Так ведь поиск по-сути своей цикличен, не? И не бесконечный он тут, вроде, решение нашел - стоп.
[User Picture]
From:ptushnik
Date:Июль 15, 2014 06:43 pm
(Link)
Большинство известных алгоритмов скорее рекурсивны, чем цикличны. В принципе, вещи похожие, но...
К тому же здесь ведь именно арифметический цикл, что очень сужает круг задач, к тому же без ограничения сверху, что неправильно методологически (невозможно определить: то ли решения просто нет, то ли мы до него еще не добрались, то ли наврали в программе и она зациклилась).

Лучше уж тогда было взять конкретную задачу поиска делителя, тем более, все равно потом она всплыла.
Правда, при поиске делителя надо начинать не с нуля, а с двойки, потом переходить строго на нечет и заканчивать на корне из N. Что даст примерно то же количество циклов, что и в квантовой альтернативе. Но это жизнь... :)
[User Picture]
From:eslitak
Date:Июль 15, 2014 07:38 pm
(Link)
Рекурсия применима, когда поиск хоть как-то упорядочен. Здесь же речь идёт о полностью случайном "тыке". Например, как применить рекурсию для поиска владельца телефона 555-55-55 в справочнике, отсортированном по фамилиям абонентов? В классическом варианте это только перебор, ничего больше.

И не только арифметические задачи. Число X - это может быть номер записи по порядку в том же справочнике. В этом случае "оракул" настраивается так, что он устанавливает флаг в "1", если на входе установлен номер записи, содержащей искомый телефон 555-55-55. И, в конце концов, все мыслимые задачи, которые имеет смысл поручать компьютеру, сводятся к арифметике, это Гедель с Тьюрингом давно доказали. Так что с "широтой круга" всё в порядке :)

Что касается факторизации. В квантовом поиске делителя нам тоже никто не запрещает выкинуть из поиска все чётные числа и ограничить область поиска квадратным корнем из N. Что даст количество циклов примерно в корень четвёртой степени из N. Миллион циклов и тысяча циклов - "это две большие разницы". Вот это жизнь! :)



Edited at 2014-07-15 19:39 (UTC)
[User Picture]
From:ptushnik
Date:Июль 15, 2014 08:10 pm
(Link)
Конечно же, рекурсия применима не только для упорядоченного поиска. На множествах, где порядка нет, она тоже работает. Впрочем автору виднее, какими примерами иллюстрировать свои рассуждения. Мое дело - дать комментарий, а там - трава не расти. :)
Что касается Геделя с Тьюрингом, то и они вроде арифметику к бесконечному циклу не сводили.
[User Picture]
From:eslitak
Date:Июль 16, 2014 05:00 am
(Link)
Автору может и виднее, но коменты нужны, так что велкам :)

Арифметика же тут не в цикле закладывается, а внутри блока 2.


[User Picture]
From:ptushnik
Date:Июль 16, 2014 04:04 am
(Link)
Подумал, что я, возможно, плохо объяснил суть своих замечаний. Дело в том, что для переборной задачи (именно этот классический алгоритм излагает автор), характерен конечный набор проверяемых элементов, а цикл в примере предлагается бесконечный. Наличие проверки внутри цикла, как я уже писал, проблему не снимает, ибо не гарантирует завершения.
То, что цикл начинается с нуля, намекает на знакомство автора с Си-подобными языками программирования, но несколько противоречит академичности изложения.
Естественный алгоритм предполагает логический цикл по типу:
Пока нужный элемент не найден и есть непроверенные элементы ...
Если хочется зафиксировать арифметический перебор, то имеет смысл определить множество элементов {x1, ... xN} и писать арифметический цикл от 1 до N. Это хорошо бы сочеталось с последующими рассуждениями про кубиты.
[User Picture]
From:eslitak
Date:Июль 16, 2014 05:03 am
(Link)
ОК, учту это в следующей редакции.
Разработано LiveJournal.com