Квантовый алгоритм Дойча-Йожи на практике

Хотите начать работу с квантовым машинным обучением? Взгляните на статью Практическое квантовое машинное обучение с помощью Python.

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

Затем мы начинаем изучать это. Во-первых, мы узнаем, чем квантовые биты (кубиты) отличаются от классических битов. Они находятся в состоянии суперпозиции. Суперпозиция - это сложная (как в комплексных числах) линейная комбинация состояний 0 и 1. Многим нравится идея, что кубит не равен 0 или 1, но одновременно, это 0 и 1. Даже если это понятие неверно - или по крайней мере, неточно - это наглядно демонстрирует преимущество квантовых алгоритмов. В то время как классические компьютеры обрабатывают свои задачи последовательно, по одному, квантовые компьютеры выполняют все шаги одновременно.

В предыдущем посте мы рассмотрели алгоритм Дэвида Дойча. Этот квантовый алгоритм классифицирует, является ли функция постоянной (всегда возвращает один и тот же результат) или сбалансированной (возвращает разные результаты при разных входных данных), глядя на нее только один раз. В отличие от классического алгоритма нужно будет дважды посмотреть на функцию.

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

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

Прежде чем согласиться на игру, сначала нужно убедиться, что монета не подвергается манипуляциям. Допустим, есть два варианта. Либо монета справедливая и в половине случаев выпадает с каждой стороны. Или монета обманута и всегда падает с одной и той же стороны. Единственный надежный способ узнать, честная ли монета, - это подбросить ее и посмотреть, на какой стороне она приземляется.

Допустим, мы тестируем монету четыре раза. Честная монета приземлится с обеих сторон два раза. Итак, как часто вам нужно подбрасывать монету, чтобы узнать? Если вы подбросите его только один раз, он приземлится либо хедз-ап, либо решка. Это вообще ничего вам не говорит. Если вы подбросите его снова, и он приземлится с другой стороны, все готово. Тогда вы знаете, что это честная монета. Но что, если монета снова окажется на той же стороне? Честная монета может приземлиться на одну сторону два раза из четырех. Чтобы точно сказать, что монета обманута, вам нужно подбросить ее как минимум три раза (когда мы предполагаем, что это честно при размере выборки четыре).

Математически, когда монета справедлива при n подбрасываниях, нам нужно подбросить монету 2 ^ (n / 2–1) +1 раз. Для n = 4 это 2 ^ (4 / 2–1) + 1 = 3 броска. Для n = 8 это было 2 ^ (8 / 2–1) + 1 = 7 бросков, для n = 10 это было 2 ^ (10 / 2–1) + 1 = 15 бросков и так далее. Это число растет в геометрической прогрессии.

В худшем из возможных сценариев мы могли бы многократно получать один и тот же результат, не зная, будет ли монета по-прежнему честной. Для этого потребуется экспоненциальное количество запросов - по крайней мере, если мы будем делать это классическим образом.

С помощью квантовых вычислений мы можем решить эту проблему за один запуск. Вместо этого мы используем кубит для каждой возможной комбинации бросков. Для простоты предположим, что мы подбрасываем монету всего три раза. И, скажем, 1 представляет орел, а 0 - решку. Таким образом, есть восемь возможных входов: (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1 , 0,1), (1,1,0), (1,1,1).

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

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

Основная часть алгоритма - квантовый оракул. Если вы впервые слышите об оракуле в области квантовых вычислений, не волнуйтесь. Это не волшебный трюк и не требует сверхъестественной силы. Квантовый оракул - не что иное, как заполнитель для ворот трансформации. Оракул похож на управляющую структуру с переключателем, которую вы, возможно, знаете из классического программирования. У вас есть переменная, оракул. И вы указываете поведение для каждого возможного значения.

В нашем случае оракул представляет поведение монеты. Обмананная монета дает либо только 0, либо только 1.

Qiskit инициализирует кубит в состоянии | 0⟩. В этом состоянии мы всегда измеряем кубит как 0. Итак, когда мы ничего не делаем, у нас уже есть оракул, представляющий обманную монету, которая всегда выпадает решкой.

Мы все равно оборачиваем «ничего не делать» в функцию. Эта функция создает для нас настраиваемый вентиль трансформации. Чтобы прояснить, что мы делаем, мы применяем I-вентили ко всем кубитам, представляющим броски. I-вентиль является вентилем идентичности и оставляет кубит неизменным.

На следующем рисунке tails_oracle показано графически.

Когда мы запускаем схему, состоящую только из этого оракула, она выводит состояние 000, представляющее трижды «хвост вверх».

НЕ-вентиль переводит кубит из состояния | 0⟩ в состояние | 1⟩. Следовательно, мы можем создать оракул, представляющий обманную монету, которая всегда выпадает хедз-ап, применяя НЕ-вентили ко всем кубитам.

На следующем рисунке изображен этот оракул.

Этот оракул всегда производит состояние 111 - состояние, представляющее трижды хедз-ап.

Оракул, представляющий честную монету, немного сложнее. Впрочем, это тоже не так уж сложно. Имея три кубита, мы можем сказать, что он приземляется хотя бы один раз в хедз-апе и один раз в хвосте. Функция balanced_oracle принимает дополнительный параметр config. Это должна быть битовая строка, представляющая результат подбрасывания монеты. Мы применяем НЕ-вентили к кубитам, которые представляют собой бросок один на один.

Кроме того, мы добавляем элементы управляемого НЕ с каждым броском в качестве управляющего кубита и вспомогательного в качестве целевого кубита.

На следующем рисунке изображен сбалансированный оракул для конфигурации 110, обозначающей орел-орел-решка.

Этот оракул приводит к состоянию, которое мы указываем в config битовой строке. В нашем примере это 110. Он работает и со всеми другими входами. Обратите внимание, что кубиты читаются справа налево.

Судя по всему, три CNOT-гейта не повлияли. Это кажется правдоподобным, поскольку вентиль CNOT действует как вентиль НЕ, применяемый к целевому кубиту, только если управляющий кубит находится в состоянии | 1⟩. И все наши кубиты находятся в состоянии | 0⟩. См. Этот пост для более детального просмотра CNOT-ворот.

Возникает вопрос: «Если CNOT-gate не имеет значения, зачем мы вообще их добавляем?»

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

Итак, давайте реализуем наш алгоритм, который определяет, является ли монета постоянной (обманутой) или сбалансированной (справедливой).

Начнем с серии вентилей Адамара, чтобы перевести кубиты в состояние | +⟩, а вспомогательный кубит - в состояние |-. В этих состояниях кубит имеет вероятность быть измеренным как 0 или как 1 по 50% каждое. Разница между состоянием | +⟩ и состоянием | -⟩ - это фаза кубита (см. Этот пост, чтобы узнать больше о фазе кубита).

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

На следующем изображении показана схема, включая оракул.

Так. давайте посмотрим на эту схему в действии. Начнем с оракула постоянной решки вверх.

Он попадает в состояние 000.

Затем мы запускаем алгоритм с heads_oracle.

Он также попадает в состояние 000.

Наконец, мы запускаем схему со сбалансированным оракулом (вы можете запускать его с любой строкой битов).

С оракулом для симметричного входа схема оказывается в состоянии 111. Неважно, какую битовую строку вы вводите.

«Но как это работает?»

Когда оракул постоянен, мы либо применяем ворота I, либо ворота НЕ. Но поскольку наш алгоритм переводит кубиты в состояние | +⟩, мы ничего не меняем. Когда мы применяем НЕ-вентиль к кубиту в состоянии | +⟩, он остается в этом состоянии. Когда мы применяем вентили Адамара в конце нашей схемы, они переводят кубиты из состояния | +⟩ обратно в состояние | 0⟩. У нас есть простые HIH-последовательности.

Но когда мы применяем balanced_oracle, мы дополнительно применяем CNOT-вентили. Хотя это не имеет значения, если кубиты находятся в базовом состоянии (таком как | 0⟩), они имеют значение, если кубит находится в суперпозиции. Затем CNOT-вентиль применяет фазу целевого кубита к контрольному кубиту. Мы используем вспомогательный кубит в качестве целевого кубита в нашей схеме и переводим его в состояние |-. Итак, когда мы применяем CNOT-вентили, мы «копируем» эту фазу на другие кубиты.

В результате эти кубиты тоже переходят в состояние | -⟩. Последние вентили Адамара превращают кубиты из состояния | -⟩ в состояние | 1⟩. Мы называем этот эффект фазовой отдачей.

Заключение

разработал этот алгоритм. Это обобщение алгоритма Дойча, работающего только с двумя кубитами.

Этот алгоритм является одним из первых примеров квантового алгоритма, который экспоненциально быстрее классического алгоритма.

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

Хотите начать работу с квантовым машинным обучением? Взгляните на статью Практическое квантовое машинное обучение с помощью Python.

Первые три главы получите бесплатно здесь.