Интуиция алгоритма Гровера
Этот пост является частью книги: Практическое квантовое машинное обучение с помощью Python.
Во многих ситуациях нам нужно найти один конкретный элемент в наборе из многих элементов. Неудивительно, что поисковые алгоритмы являются одними из самых известных и полезных алгоритмов в компьютерных науках.
Представим, что вам нужно позвонить знаменитому пионеру квантовых вычислений г-ну Гроверу. Вы ищете его номер в телефонной книге, потому что его еще нет. Вы открываете книгу посередине и видите имена с начальной буквой L. Поскольку G находится перед L, вы берете первую половину книги и снова открываете ее посередине. Там вы видите имена с буквой E. Поскольку G стоит после E, вы открываете книгу посередине между E и L. Там вы видите номер мистера Гровера.
Мы знаем этот алгоритм поиска как бинарный поиск. Этот алгоритм многократно делит интервал поиска пополам. Если искомый элемент ниже, чем элемент в середине интервала, он сужает интервал до нижней половины. В противном случае сужает его до верхней половины. Это повторяется до тех пор, пока значение не будет найдено или интервал не станет пустым. Алгоритм двоичного поиска довольно быстро сужает пространство поиска и сходится к решению. Единственная проблема заключается в том, что алгоритм полагается на сортировку данных, которые вы ищете. Алгоритм не работает, если данные не отсортированы.
Это большая проблема, потому что не только двоичный поиск полагается на отсортированные данные, но и почти все алгоритмы поиска.
Если данные не отсортированы и не структурированы каким-либо другим образом, единственным допустимым алгоритмом поиска является линейный поиск. В линейном поиске мы должны оценивать каждый элемент, чтобы проверить, является ли он искомым или нет. Хотя этот подход работает для небольших данных, он становится неприемлемым для больших наборов данных.
Здесь в игру вступает алгоритм Гровера. В этом посте мы познакомились с алгоритмом Дойча, который мог оценивать функцию для двух входных параметров, выполняя ее только один раз. Алгоритм Гровера учит нас, как искать элемент в несортированном списке, не просматривая каждый элемент по отдельности, а просматривая их все сразу. Это достигается двумя способами. Во-первых, он использует квантовый оракул для отметки состояния поиска. Во-вторых, он использует диффузор, который усиливает амплитуду отмеченного состояния, чтобы увеличить вероятность его измерения.
Мы можем описывать квантовые системы в терминах их состояний, амплитуд и вероятностей измерений. Но это внутренние описания, которые мы не можем наблюдать напрямую. Всякий раз, когда мы измеряем квантовую систему, мы получаем одно значение - одно состояние, в котором находится эта конкретная система.
Если мы измеряем две похожие системы, мы можем измерить разные значения. Тогда мы знаем, что эта конкретная система может находиться в разных состояниях. Если у нас много похожих систем, мы могли бы измерять систему в одних состояниях чаще, чем в других. Как часто мы измеряем квантовую систему в определенном состоянии, зависит от вероятности. Каждое состояние квантовой системы имеет определенную вероятность измерения. Чем он выше, тем больше вероятность, что мы проведем измерения системы в этом состоянии.
Вероятность измерения состояния зависит от амплитуды этого конкретного состояния. Математически вероятность измерения - это абсолютный квадрат амплитуды. Мы увидим, что это значит, через секунду.
Алгоритм поиска Гровера начинается с набора кубитов в равной суперпозиции. Это означает, что все состояния имеют равные амплитуды. Следовательно, все они имеют одинаковую вероятность измерения. Если измерить эту систему только один раз, мы найдем ее в любом состоянии. Какой из них - на волю случая. Если бы мы измеряли эту систему бесчисленное количество раз, мы бы увидели ее в каждом из состояний одинаково часто.
Состояние, которое мы ищем, входит в число этих состояний. Цель состоит в том, чтобы изменить систему таким образом, чтобы при измерении мы находили систему в этом единственном состоянии. Всегда.
Задача квантового оракула - идентифицировать искомое состояние. Квантовый оракул - это не волшебный ингредиент, а управляющая структура. Это квантовый оператор. Этот оператор отрицает амплитуду искомого состояния.
Конечно, важный вопрос: «Как оракул определяет состояние поиска?»
Оракул использует любую характеристику искомого квантового состояния. Если мы начнем с набора равных состояний, то по определению состояния различаются только в отношении их перечисления. Они различаются в зависимости от того, измеряем ли мы (если измеряем) определенный кубит как 0 или 1. Если мы используем, например, четыре кубита, то имеется 2 ^ 4 = 16 различных состояний. Начиная с | 0000⟩, до | 0001⟩, заканчивая | 1111⟩.
Каждый кубит может иметь определенное значение. Мы могли интерпретировать это как письмо. Буква, у которой нет 26 различных вариантов, а только два, | 0⟩ и | 1⟩. Имея достаточное количество кубитов, мы могли бы представлять всех живых людей. С 33 кубитами мы можем представить около 8,5 миллиардов различных состояний. Телефонная книга человечества. И мы не разобрали.
Теперь предположим, что четырех кубитов достаточно, а мистер Гровер известен как | 0010⟩. Оракул использует конкретную характеристику этого состояния для его идентификации. То есть состояние имеет | 1⟩ на третьей позиции и | 0⟩ в противном случае.
Поскольку квантовый оракул принимает на вход все кубиты, он может легко применить преобразование этого точного состояния. Не имеет значения, используем ли мы четыре кубита или 33. Оракул идентифицирует мистера Гровера за один ход.
Преобразование, которое оракул применяет к искомому состоянию, - это инверсия амплитуды.
В этом представлении амплитуд мы можем ясно видеть разницу между искомым состоянием и всеми другими состояниями. Мы можем преждевременно объявить об окончании обыска.
Единственная разница в знаке амплитуды. Поскольку вероятность измерения определяется абсолютным квадратом амплитуды, знак вообще не имеет значения.
Амплитуда происходит из концепции, согласно которой каждую квантовую сущность можно описать не только как частицу, но и как волну. Основная характеристика волны заключается в том, что она движется вверх и вниз. Амплитуда - это расстояние между центром и гребнем волны.
Если мы инвертируем амплитуду волны во всех положениях, в результате получится одна и та же волна, сдвинутая на половину своей длины волны.
Эти две волны различаются только своим взаимным положением. Это фаза волны. Для внешнего мира фаза волны не наблюдается. При индивидуальном наблюдении две волны кажутся идентичными. Итак, проблема в том, что мы не можем отличить эти две волны.
Как следствие, внешне система ничем не отличается. Несмотря на то, что оракул отметил искомое состояние и, следовательно, он отличается от других состояний, все состояния по-прежнему имеют одинаковую вероятность измерения.
Нам нужно превратить разницу в нечто измеримое. Нам нужно увеличить вероятность измерения отмеченного состояния. Это задача диффузора. Диффузор применяет инверсию средней амплитуды.
Посмотрим на среднюю амплитуду.
С четырьмя кубитами у нас есть 16 различных состояний. Каждое состояние имеет амплитуду 1 / sqrt (16) = 1/4. Фактически, каждое состояние, кроме одного - искомое состояние имеет эту амплитуду. Искомое состояние имеет амплитуду -1/4. Таким образом, среднее значение равно (15 ∗ 1 / 4−1 / 4) /16=0,21875.
Среднее значение немного меньше амплитуды всех не отмеченных нами состояний. Если мы инвертируем эти амплитуды с помощью этого среднего значения, они окажутся немного ниже среднего значения на 0,1875.
Поскольку амплитуда отмеченного состояния отрицательная, она довольно далеко от средней. Инверсия среднего имеет больший эффект. Он меняет амплитуду с -0,25 на 2 * (0,25 + 0,21875) до 0,6875.
Инверсия среднего значения хорошо работает, если мы ищем одну или несколько отрицательных амплитуд среди множества положительных амплитуд. Затем эта операция увеличивает отрицательные амплитуды, которые, как мы знаем, являются правильными. И эта операция уменьшает положительные амплитуды, мы знаем, что ошиблись.
Эта операция увеличивает отрицательную амплитуду на большую величину, уменьшая положительную амплитуду на небольшую величину.
Но чем больше у нас состояний, тем меньше будет общий эффект. В нашем примере мы вычислили новую амплитуду искомого состояния как 0,6875. Соответствующая вероятность измерения составляет 0,6875 ^ 2 = 0,47265625. Соответственно, мы измеряем эту систему только примерно каждый раз в искомом состоянии. В противном случае измеряем его в любом другом случае.
Конечно, теперь мы могли измерять систему много раз и видеть состояние нашего поиска как наиболее вероятное. Но запуск алгоритма столько раз лишит нас любого преимущества, которое мы получили, если не перебирали все состояния.
Вместо этого мы повторяем алгоритм. Мы используем тот же оракул, чтобы отрицать амплитуду искомого состояния. Затем мы снова инвертируем все амплитуды вокруг среднего.
Однако мы не должны повторять этот процесс слишком много раз. Этот процесс можно повторить оптимальное количество раз, чтобы получить наибольший шанс измерить правильный ответ. Вероятность получения правильного результата растет, пока мы не достигнем примерно π / 4 * sqrt (N), где N - количество состояний квантовой системы. При превышении этого числа вероятность измерения правильного результата снова снижается.
В нашем примере с четырьмя кубитами и N = 16 состояниями оптимальное количество итераций - 3.
Вывод
Алгоритм Гровера ищет несортированные данные. Это следует простой процедуре. Квантовый оракул инвертирует амплитуду искомого состояния. Затем диффузор инвертирует все состояния относительно средней амплитуды, таким образом, увеличивая исследуемое состояние. Алгоритм повторяет эти шаги до тех пор, пока решение не будет иметь вероятность измерения, близкую к 100%.
Количество повторов зависит от количества состояний, которые необходимо учитывать. Поскольку количество повторений увеличивается только примерно на квадратный корень из числа состояний, этот алгоритм обеспечивает квадратичное ускорение по сравнению с классическим линейным поиском - это единственный классический подход, который может искать несортированные данные.
Однако, как и все алгоритмы квантового компьютера, алгоритм Гровера является вероятностным. Он возвращает правильный ответ с высокой, но не абсолютной вероятностью. Следовательно, нам может потребоваться повторить алгоритм, чтобы минимизировать вероятность сбоя.
Этот пост является частью книги: Практическое квантовое машинное обучение с помощью Python.
Первые три главы получите бесплатно здесь.
