Квантовый ликбез 25-4. Алгоритм Гровера - "усилитель"
Предыдущие посты
Напомню "входное" состояние, с которым мы работаем. После оракула амплитуды вероятности альтернатив, содержащих правильное значение, отрицательны. Амплитуды вероятности "неправильных" альтернатив положительны. Усиление "правильных" альтернатив в алгоритме Гровера осуществляется методом, который называется "инверсия относительно среднего". В некоторых описаниях эту операцию называют ещё "диффузией". Несложная математическая суть метода заключается в следующем.
1. Вычисляется Am - среднее значение амплитуд вероятноcти по всем альтернативам. Самым обычным образом: амплитуды всех альтернатив суммируются, и полученная сумма делится на количество альтернатив:
2. Амплитуда каждой группы преобразуется по следующему правилу:
Вот и вся хиторость! После этой операции положительные амплитуды по модулю уменьшаются, а отрицательные - по модулю увеличиваются. Таким образом мы усиливаем "правильные" альтернативы.
Посмотрим, как эта матемаматика работает в нашем примере.
На первом проходе алгоритма на выходе оракула мы имеем суперпозицию из 16-ти равновесных альтернатив. Равновесных, потому что модули амплитуд вероятности всех альтернатив равны между собой и равны 0,25. Но вот знаки амплитуд вероятности альтернатив различаются.
У пятнадцати "неправильных" альтернатив, "несущих" числа от 0 до 8 и от 10 до 15, амплитуды вероятности равны +0,25.
У одной "правильной" альтернативы (число 9) амплитуда вероятности равна -0,25.
Значит, среднее по всем амплитудам вероятности равно:
Проиллюстрруем эту ситуацию следующим графиком:
После инверсии относительно среднего амплитуда вероятности всех "неправильных" групп преобразуется следующим образом:
А амплитуда вероятности "правильной" группы "9" преобразуется так:
Что нам и требовалось. Модули амплитуд "неправильных" групп уменьшились, модуль амплитуды "правильной" группы увеличился. смотрим на график после преобразования:
Обратите, кстати, внимание, что знак "правильной" амплитуды сменился с отрицательного на положительный.
Теперь нам надо выяснить, как реализовать эту математику с помощью унитарных воздействий на кубиты. Матрица [D] воздействия, осуществляющего требуемое преобразование квантового состояния k-кубитного подрегистра данных, выглядит следующим образом:
Сама матрица [D] показана в чёрном цвете. Всё зелёное - это поясняющая информация.
Первая строка матрицы определяет, в какой пропорции воздействие расщепляет базисное состояние, несущее число "0". Вторая - расщепление базисного состояния, соответсвующее единице, ну и так далее до числа "N-1". Чтобы вам легче было ориентироваться, справа от каждой строки показано "расщепляемое" базисное состояние.
Давайте посмотрим, как это преобразование работает для простейшего двухкубитного регистра данных. В этом случае N = 4, стало быть, матрица "инверсии относительно среднего" должна иметь следующий вид:
Пусть на входе у нас такое состояние подрегистра "x":
На следующей диаграмме визуализирован процесс "усиления" альтернативы с отрицательной амплитудой вероятности, а именно альтернативы |11〉 - число "3".
Как видим, в результате воздействия каждая из четырёх групп виртуальных вариантов "распадается" на четыре "осколка". Всего получается шестнадцать "осколков". И они тут же эти вновь группируются, но уже в другой пропорции. Образовавшиеся "кусочки" групп |00〉, |01〉, |10〉, изначально имеющих положительную амплитуду вероятности, имеют разный знак и взаимно "уничтожаются", то есть, становятся нереализуемыми. Зато |11〉 группа, "отрицательная" до операции, наоборот, "усиливается" за счёт суммирования однознаковых "кусков".
Кстати, в двухкубитном случае мы наблюдаем "идеальное усиление" - за один такт работы "усилителя" мы гарантированно получаем готовый ответ в виде единственной "правильной" альтернативы. Все прочие группы, всилу осуществившейся взаимной деструкции "осколков", имеют нулевую вероятность реализоваться. Кодга мы имеем дело с подрегистром данных большего размера - это не так. Пример с четырьмя кубитами мы уже рассмотрели чуть выше.
Ну что же, теперь нам надо выяснить, как реализовать матрицу инверсии относительно среднего с помощью элементарных гейтов. Как уже говорилось, вычислительная схема блока 3 является универсальной для любой задачи поиска. Эта универсальная схема показана на следующем рисунке:
Здесь, как раньше, k - это количество кубитов в подрегистре данных "x".
В схеме задействован однокубитный гейт [iI], который нам прежде не встречался. Этот гейт "расщепляет" базисные состояния кубита следующим образом:
[iI] |0〉 = i |0〉
[iI] |1〉 = i |1〉
Здесь "i" - это мнимая единица. Ранее неоднократно подчёркивалось, что апмлитуды вероятности выражаются в общем случае комплексными числами, но в частных примерах мы до этого места мы обходились без мнимых значений. Ну пусть уже будут!
Как видим, схема "усилителя" построена, в основном, из однокубитных гейтов. Имеется единственная k-кубитная операция "C...СNOT", в которой всего один кубит является "рабочим" (на схеме - самый нижний), а все остальные биты - управляющие. В этой операции "рабочий" кубит изменяет своё состояние только в тех альтернативах, где все управляющие кубиты находятся в состоянии |1〉.
Теперь нарисуем вычислительную схему для нашего примера.
В схеме опять задействованы вспомогательные кубиты "v1" и "v2". Они здесь использованы для того, чтобы упростить реализацию четырёхкубитного гейта "CCCNOT". Ещё раз напомню, что коэффициенты в формулах - амплитуды вероятности - актуальны только для первого прохода алгоритма Гровера.
Здесь, пожалуй, нет смысла рисовать разноцветные диаграммы и разбирать подробно, как меняется состояние подрегистра данных на разных срезах схемы - это скорее запутает, чем прояснит дело. Тут такой случай, когда целую идею невозможно разобрать на отдельные "кирпичики". Поэтому "рядовых" читателей призваю просто поверить на слово: эта схема действительно реализует инверсию относительно среднего - усиление альтернатив с отрицательной амплитуой вероятности.
Ну а для недоверчивых (в хорошем научном смысле) читателей, тех, кто не боится формул и кропотливых вычислений, чуть погодя сделаю специальное дополнение к этой части. Там будут доказательства того, что схема работает. Заодно посмотрим на практическом примере, какая в квантовой механике польза от матриц. Это пригодится, если вы планируете и дальше разбираться в квантовых тонкостях.
Вот, основные сложности позади, все блоки алгоритма Гровера мы разобрали. Осталось сделать несколько завершающих штрихов.
Продолжение
Напомню "входное" состояние, с которым мы работаем. После оракула амплитуды вероятности альтернатив, содержащих правильное значение, отрицательны. Амплитуды вероятности "неправильных" альтернатив положительны. Усиление "правильных" альтернатив в алгоритме Гровера осуществляется методом, который называется "инверсия относительно среднего". В некоторых описаниях эту операцию называют ещё "диффузией". Несложная математическая суть метода заключается в следующем.
1. Вычисляется Am - среднее значение амплитуд вероятноcти по всем альтернативам. Самым обычным образом: амплитуды всех альтернатив суммируются, и полученная сумма делится на количество альтернатив:
2. Амплитуда каждой группы преобразуется по следующему правилу:
Вот и вся хиторость! После этой операции положительные амплитуды по модулю уменьшаются, а отрицательные - по модулю увеличиваются. Таким образом мы усиливаем "правильные" альтернативы.
Посмотрим, как эта матемаматика работает в нашем примере.
На первом проходе алгоритма на выходе оракула мы имеем суперпозицию из 16-ти равновесных альтернатив. Равновесных, потому что модули амплитуд вероятности всех альтернатив равны между собой и равны 0,25. Но вот знаки амплитуд вероятности альтернатив различаются.
У пятнадцати "неправильных" альтернатив, "несущих" числа от 0 до 8 и от 10 до 15, амплитуды вероятности равны +0,25.
У одной "правильной" альтернативы (число 9) амплитуда вероятности равна -0,25.
Значит, среднее по всем амплитудам вероятности равно:
Проиллюстрруем эту ситуацию следующим графиком:
После инверсии относительно среднего амплитуда вероятности всех "неправильных" групп преобразуется следующим образом:
А амплитуда вероятности "правильной" группы "9" преобразуется так:
Что нам и требовалось. Модули амплитуд "неправильных" групп уменьшились, модуль амплитуды "правильной" группы увеличился. смотрим на график после преобразования:
Обратите, кстати, внимание, что знак "правильной" амплитуды сменился с отрицательного на положительный.
Теперь нам надо выяснить, как реализовать эту математику с помощью унитарных воздействий на кубиты. Матрица [D] воздействия, осуществляющего требуемое преобразование квантового состояния k-кубитного подрегистра данных, выглядит следующим образом:
Сама матрица [D] показана в чёрном цвете. Всё зелёное - это поясняющая информация.
Первая строка матрицы определяет, в какой пропорции воздействие расщепляет базисное состояние, несущее число "0". Вторая - расщепление базисного состояния, соответсвующее единице, ну и так далее до числа "N-1". Чтобы вам легче было ориентироваться, справа от каждой строки показано "расщепляемое" базисное состояние.
Давайте посмотрим, как это преобразование работает для простейшего двухкубитного регистра данных. В этом случае N = 4, стало быть, матрица "инверсии относительно среднего" должна иметь следующий вид:
Пусть на входе у нас такое состояние подрегистра "x":
На следующей диаграмме визуализирован процесс "усиления" альтернативы с отрицательной амплитудой вероятности, а именно альтернативы |11〉 - число "3".
Как видим, в результате воздействия каждая из четырёх групп виртуальных вариантов "распадается" на четыре "осколка". Всего получается шестнадцать "осколков". И они тут же эти вновь группируются, но уже в другой пропорции. Образовавшиеся "кусочки" групп |00〉, |01〉, |10〉, изначально имеющих положительную амплитуду вероятности, имеют разный знак и взаимно "уничтожаются", то есть, становятся нереализуемыми. Зато |11〉 группа, "отрицательная" до операции, наоборот, "усиливается" за счёт суммирования однознаковых "кусков".
Кстати, в двухкубитном случае мы наблюдаем "идеальное усиление" - за один такт работы "усилителя" мы гарантированно получаем готовый ответ в виде единственной "правильной" альтернативы. Все прочие группы, всилу осуществившейся взаимной деструкции "осколков", имеют нулевую вероятность реализоваться. Кодга мы имеем дело с подрегистром данных большего размера - это не так. Пример с четырьмя кубитами мы уже рассмотрели чуть выше.
Ну что же, теперь нам надо выяснить, как реализовать матрицу инверсии относительно среднего с помощью элементарных гейтов. Как уже говорилось, вычислительная схема блока 3 является универсальной для любой задачи поиска. Эта универсальная схема показана на следующем рисунке:
Здесь, как раньше, k - это количество кубитов в подрегистре данных "x".
В схеме задействован однокубитный гейт [iI], который нам прежде не встречался. Этот гейт "расщепляет" базисные состояния кубита следующим образом:
[iI] |0〉 = i |0〉
[iI] |1〉 = i |1〉
Здесь "i" - это мнимая единица. Ранее неоднократно подчёркивалось, что апмлитуды вероятности выражаются в общем случае комплексными числами, но в частных примерах мы до этого места мы обходились без мнимых значений. Ну пусть уже будут!
Как видим, схема "усилителя" построена, в основном, из однокубитных гейтов. Имеется единственная k-кубитная операция "C...СNOT", в которой всего один кубит является "рабочим" (на схеме - самый нижний), а все остальные биты - управляющие. В этой операции "рабочий" кубит изменяет своё состояние только в тех альтернативах, где все управляющие кубиты находятся в состоянии |1〉.
Теперь нарисуем вычислительную схему для нашего примера.
В схеме опять задействованы вспомогательные кубиты "v1" и "v2". Они здесь использованы для того, чтобы упростить реализацию четырёхкубитного гейта "CCCNOT". Ещё раз напомню, что коэффициенты в формулах - амплитуды вероятности - актуальны только для первого прохода алгоритма Гровера.
Здесь, пожалуй, нет смысла рисовать разноцветные диаграммы и разбирать подробно, как меняется состояние подрегистра данных на разных срезах схемы - это скорее запутает, чем прояснит дело. Тут такой случай, когда целую идею невозможно разобрать на отдельные "кирпичики". Поэтому "рядовых" читателей призваю просто поверить на слово: эта схема действительно реализует инверсию относительно среднего - усиление альтернатив с отрицательной амплитуой вероятности.
Ну а для недоверчивых (в хорошем научном смысле) читателей, тех, кто не боится формул и кропотливых вычислений, чуть погодя сделаю специальное дополнение к этой части. Там будут доказательства того, что схема работает. Заодно посмотрим на практическом примере, какая в квантовой механике польза от матриц. Это пригодится, если вы планируете и дальше разбираться в квантовых тонкостях.
Вот, основные сложности позади, все блоки алгоритма Гровера мы разобрали. Осталось сделать несколько завершающих штрихов.
Продолжение