Что такое вариационный квантово-классический алгоритм и зачем он нам нужен?
Этот пост является частью книги: Практическое квантовое машинное обучение с помощью Python.
Кирк: «Мистер. Спок, учли ли вы переменную массу китов и воды в своей программе возвращения в атмосферу во времени? »
Спок: «Мистер. Скотт не может дать мне точных цифр, адмирал, так что… я сделаю предположение ».
Кирк: «Предположение? Ты, Спок? Это невероятно ».
Спок: Маккою «Не думаю, что он понимает».
Маккой: «Нет, Спок. Он имеет в виду, что он чувствует себя увереннее в ваших догадках, чем в большинстве фактов других людей ".
Спок: «Значит, вы говорите… это комплимент?»
Маккой: Это так.
Спок: «А. Тогда я постараюсь сделать как можно больше предположений ».
Нет, вам не нужно гадать, что такое вариационный квантово-классический алгоритм. Но через минуту вы поймете, о чем это вступление.
Квантовые вычисления - это другая форма вычислений. Форма, которая может изменить сложность решения проблем, сделав их послушными. Возможно, вы слышали об алгоритме факторизации Шора. Этот алгоритм снижает сложность поиска (простых чисел) множителей данного числа с экспоненциальной сложности до субэкспоненциальной сложности.
Если это вас не ошеломляет, давайте перефразируем. Современная криптография основана на предположении, что факторизовать большое число невозможно. Для классического компьютера это невозможно, потому что сложность его поиска возрастает в геометрической прогрессии.
Шор доказал, что квантовый компьютер может разложить на множители большое число за разумное время. Квантовый компьютер, способный запускать алгоритм Шора, разрушил бы современную криптографию, как карточный домик.
Машинное обучение сталкивается с проблемами, сопоставимыми с проблемой факторизации. Мы ищем один набор параметров для наших моделей, чтобы предсказывать будущее. Но существует очень много возможных комбинаций параметров. Классически их просто рассчитывать слишком сложно.
Разницу между экспоненциальной и субэкспоненциальной сложностью нельзя недооценивать. Например, ваш смартфон может умножать числа на 800 цифр за несколько секунд. Это субэкспоненциальная проблема.
Напротив, факторизация таких чисел на суперкомпьютере занимает около 2000 лет. Потому что это экспоненциально растущая проблема.
Есть только одна проблема. Для этих алгоритмов требуются миллионы квантовых битов (кубитов). Флагманские квантовые компьютеры IBM и Google в настоящее время имеют около 50 кубитов. И эти кубиты даже не так хорошо работают.
Квантовые компьютеры должны быть очень точными. Им нужно поддерживать непрерывное квантовое состояние. Любое сколь угодно малое колебание может испортить вычисление. Но современные квантовые компьютеры настолько шумны, что максимальное время вычислений измеряется миллисекундами, а не секундами.
Квантовые процессоры, которые мы ожидаем в ближайшем будущем, останутся относительно небольшими и шумными. Мы живем в эпоху, описываемую термином «шумный квант промежуточного масштаба» - NISQ.
В эту эпоху мы не можем использовать миллионы кубитов. В нашу эпоху мы не можем запускать алгоритмы часами или даже днями.
Нынешняя эра устройств NISQ требует другого набора алгоритмов, инструментов и стратегий.
Например, вариационные квантово-классические алгоритмы стали популярным способом размышления о квантовых алгоритмах для квантовых устройств краткосрочного использования. В этих алгоритмах классические компьютеры выполняют общую задачу машинного обучения на основе информации, которую они получают в результате выполнения определенных трудно вычисляемых вычислений на квантовом компьютере.
Квантовый алгоритм производит информацию на основе набора параметров, предоставляемых классическим алгоритмом. Поэтому они называются параметризованными квантовыми схемами (ПКК).
Они относительно небольшие, недолговечные и поэтому подходят для NISQ-устройств.
Вариационный гибридный квантово-классический алгоритм состоит из трех частей:
- Мы предварительно обрабатываем данные на классическом компьютере для вычисления квантового состояния.
- Мы вычисляем наше решение в рамках квантовой схемы и измеряем кубит, который представляет результат.
- Мы обрабатываем измерение и преобразуем его в прогноз.
На следующем изображении представлена анатомия такого алгоритма.
Обычно PQC содержит модель или части модели. Но его параметры, такие как веса в нейронной сети или вероятности в байесовской сети, остаются снаружи. Они вводятся в модель каждый раз, когда мы запускаем модель.
Эта структура позволяет нам хранить параметры постоянно (или, по крайней мере, дольше, чем несколько секунд). В то же время мы можем использовать квантовую схему, которая может снизить сложность вычислений.
Давайте посмотрим на такой алгоритм в действии. Допустим, наша модель - квантовая байесовская сеть с двумя узлами.
У нас есть две двоичные переменные A и B. Мы знаем, что они не независимы. A - родительский узел. B - дочерний узел, условную вероятность которого мы пытаемся оценить.
У нас есть некоторые данные, но одна запись неполная. Мы упускаем ценность.
В байесовской сети мы все время работаем с вероятностями. Почему бы нам не заполнить недостающую точку данных распределением вероятностей вместо определенного значения?
Ждать! Как мы можем заполнить значение распределением вероятностей, если это распределение - это то, что мы стремимся вычислить в первую очередь? Давай сделаем что-нибудь экстраординарное. Спок!
Угадаем распределение. Мы используем его для вычисления логарифмической оценки правдоподобия и следующего распределения B при ¬A.
Мы выполняем итерацию между заполнением недостающих данных распределением и оценкой нового распределения вероятностей.
Вот реализация этого алгоритма.
Начнем с импорта библиотек из Qiskit, IBM SDK для квантовых вычислений (строки 1–4). Затем мы инициализируем наши данные (строки 6–8).
Мы используем две вспомогательные функции. Во-первых, prob_to_angle-функция (строки 11–12) принимает вероятность и преобразует ее в угол поворота, который мы можем использовать в вентиле преобразования кубита.
log-likelihood-функция вычисляет вероятность того, что модель приведет к наблюдаемым данным (строки 15–28). Мы адаптировали его к нашим конкретным обстоятельствам. Ожидается, что data будет списком кортежей по два элемента в каждом. Далее он принимает параметры нашей модели. Это вероятности A и B (prob_a_b), A, а не B (prob_a_nb), не A и B (prob_na_b), а не A и не B (prob_na_nb).
Мы вызываем функцию get_prob для каждого кортежа в списке и возвращаем сумму всех результатов. Эта функция get_prob принимает данные point (кортеж) и оценивает их комбинацию. Он просто возвращает логарифм соответствующей вероятности. Например, если оба значения A и B равны 1, он возвращает log(prob_a_b) - вероятность A и B.
Если мы не можем идентифицировать комбинацию, мы возвращаем логарифм суммы prob_na_b и prob_na_nb. Это тот случай, когда мы пропускаем значение B. У нас есть только один случай ((0, None)) в наших данных, а его значение A равно 0. Таким образом, мы знаем, что он не содержит A. Но мы не уверены в B.
Следующий листинг кода изображает квантовую байесовскую сеть.
Он начинается с объявления двух списков. Первый list_a (строка 4) содержит все элементы наших данных, где значение A равно 1, что означает, что A истинно. Второй list_na (строка 5) содержит все элементы, в которых значение A равно 0, не представляя A. Мы используем эти списки для вычисления вероятностей четырех комбинаций (A∧B, A∧¬B, ¬A∧B, ¬A ∧¬B).
Начнем с предельной вероятности A (строка 8). Это количество элементов в наших данных, где A истинно (1, длина list_a), деленное на общее количество элементов в наших данных (длина data). Мы позволяем кубиту в позиции 0 представлять эту вероятность (строки 10-12).
Затем мы разделяем случаи, когда A ложно, на те, где B истинно, и те, где B также ложно (строки 13-17). Сначала мы «активируем» состояние, в котором A ложно, применяя НЕ-вентиль к кубиту в позиции 0 (строка 13). Управляемый RY-вентиль устанавливает кубит в позиции 1 в состояние | 1⟩, когда B истинно (строка 14). Мы рассчитываем вероятность, разделив количество элементов, для которых A - ложь, а B - истинно, на количество элементов, для которых A - ложь (строка 15). Конечно, нам нужно вернуть кубит в состояние | 1⟩ в случаях, когда A истинно (строка 17).
Наконец, мы разделяем случаи, когда A истинно, на те, где B тоже истинно, и те, где B ложно. Применяем еще один управляемый RY-гейт. Угол поворота представляет собой вероятность того, что B истинно, если A также истинно (строка 21).
На следующем рисунке эта квантовая схема изображена графически.
Все эти вычисления вероятностей и углов поворота отображают этап предварительной обработки PQC. Мы подготавливаем данные на классическом компьютере для создания действительного квантового состояния.
Давайте запустим эту квантовую схему.
Вероятности измерения четырех различных состояний представляют собой вероятности возможных комбинаций A или ¬A и B или ¬B.
После того, как мы запустили схему, нам нужно ее обработать.
Давайте подадим результаты в нашу log_likelihood функцию, которую мы создали ранее. Для этого мы создаем еще одну удобную функцию.
Эта функция eval_qbn (строка 1) принимает в качестве модели qbn-функцию. Но мы можем подключить и любую другую модель, если она принимает набор данных заданного формата и возвращает результаты, полученные от Qiskit. Второй параметр prepare_data - это функция, которая заботится об отсутствующей точке данных. Мы просто вводим наши данные и ожидаем набора данных, который мы помещаем в нашу модель (строка 2).
Функция возвращает логарифмическую оценку правдоподобия данной модели (строка 3). Поэтому мы предоставляем вероятностные меры, которые мы получаем от квантовой схемы (строки 4–7). Обратите внимание, что состояния, которые мы получаем из квантовой схемы, читаются справа (кубит в позиции 0 представляет A) слева (кубит в позиции 1 представляет B).
А теперь давайте соберем это вместе.
Мы инициализируем наше распределение с P (B | ¬A) = 0,5 и запускаем PQC.
Похоже, это была довольно хорошая догадка. Оценка логарифма правдоподобия составляет -9,476.
Но мы не останавливаемся на достигнутом. Модель сообщает нам новое значение P (B | ¬A) = 0,3. Давайте запустим нашу модель с этим значением.
Наша модель улучшается. Мы получили оценку логарифма правдоподобия -9,452 и новое распределение для отсутствующей точки данных.
По-видимому, мы можем выполнять итерацию между заполнением недостающих данных распределением и оценкой нового распределения вероятностей.
Заключение
Этот итерационный процесс является примером общей процедуры, называемой алгоритмом максимизации ожидания (EM).
Если сначала вы не устанете, повторяйте, пока результат не сойдется. Однако может быть трудно сказать, когда ЭМ сошлась. Иногда модели надолго становятся чуть лучше. Как только вы думаете, что процесс завершен, оценка резко возрастает. Невозможно сказать.
Эта небольшая программа показывает, как можно эффективно реализовать вариационный квантово-классический алгоритм. На этапе предварительной обработки мы преобразуем классические данные в квантовое состояние. Затем мы запускаем параметризованную квантовую схему на квантовом компьютере (или симуляторе - если в вашем распоряжении нет квантового компьютера). Наконец, на этапе постобработки мы оцениваем результаты квантовой схемы, чтобы обновить нашу модель и начать заново.
Сохраняя модель вне квантовой схемы, мы можем хранить ее в течение более длительных периодов времени и ограничить квантовую схему до минимума. Это может позволить нам использовать его даже в эпоху NISQ, в которой мы живем.
Этот пост является частью книги: Практическое квантовое машинное обучение с помощью Python.
Первые три главы получите бесплатно здесь.
