Квантовый ликбез 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 более подробно.
Продолжение
В этой подчасти мы посмотрим на квантовый алгоритм неупорядоченного поиска, он же – алгоритм Гровера – с высоты, так сказать, птичьего полёта.
Оттолкнёмся от классического алгоритма поиска. В самом общем виде этот алгоритм можно представить так:
Подразумевается, что в ячейке памяти «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, и вероятность «правильных» альтернатив становится ещё выше. После определённого количества таких циклов вероятность «правильной» альтернативы максимально приближается к единице.
Количество циклов, необходимое для достижения максимальной вероятности, составляет приблизительно
От повторений, значит, мы не избавляемся совсем, задача неупорядоченного поиска не решается за один проход даже на квантовом компьютере. Но количество циклов квантового поиска по сравнению с классическим сокращается очень и очень существенно.
После отработки необходимого количества циклов мы измеряем состояния кубитов «х1, x2, ... xk»: полученная комбинации нулей и единиц и будет правильным ответом с очень высокой вероятностью.
Обратите внимание: в квантовом алгоритме Гровера зацикливание осуществляется не по условию «найден правильный ответ», как это делается в классическом поиске, а строго по счётчику.
В продолжении мы рассмотрим работу блоков 1, 2, 3 более подробно.
Продолжение