Алгоритмы квантовой оптимизации

Алгоритмы квантовой оптимизации — это квантовые алгоритмы , которые используются для решения задач оптимизации. Математическая оптимизация занимается поиском лучшего решения проблемы (по некоторым критериям) из множества возможных решений. В основном задача оптимизации формулируется как задача минимизации, где пытаются минимизировать ошибку, которая зависит от решения: оптимальное решение имеет минимальную ошибку. Различные методы оптимизации применяются в различных областях, таких как механика , экономика и инженерия , и по мере роста сложности и объема используемых данных необходимы более эффективные способы решения задач оптимизации. Квантовые вычисления могут позволить решить проблемы, которые практически невозможно решить на классических компьютерах, или предложить значительное ускорение по сравнению с самым известным классическим алгоритмом.

Подбор квантовых данных

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

Подбор квантовых наименьших квадратов

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

Алгоритм приведен $N$ точки входных данных $(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})$ и $M$ непрерывные функции $f_{1},f_{2},...,f_{M}$. Алгоритм находит и выдает на выходе непрерывную функцию $f_{\vec {\lambda }}$ это линейная комбинация $f_{j}$:

$f_{\vec {\lambda }}(x)=\sum _{j=1}^{M}f_{j}(x)\lambda _{j}$

Другими словами, алгоритм находит комплексные коэффициенты $\lambda _{j}$, и, следовательно, вектор ${\vec {\lambda }}=(\lambda _{1},\lambda _{2},...,\lambda _{M})$.

Алгоритм направлен на минимизацию ошибки, которая определяется выражением:

$E=\sum _{i=1}^{N}\left\vert f_{\vec {\lambda }}(x_{i})-y_{i}\right\vert ^{2}=\sum _{i=1}^{N}\left\vert \sum _{j=1}^{M}f_{j}(x_{i})\lambda _{j}-y_{i}\right\vert ^{2}=\left\vert F{\vec {\lambda }}-{\vec {y}}\right\vert ^{2}$

где $F$ определяется как следующая матрица:

${F}={\begin{pmatrix}f_{1}(x_{1})&\cdots &f_{M}(x_{1})\\f_{1}(x_{2})&\cdots &f_{M}(x_{2})\\\vdots &\ddots &\vdots \\f_{1}(x_{N})&\cdots &f_{M}(x_{N})\\\end{pmatrix}}$

Алгоритм квантовой аппроксимации методом наименьших квадратов использует версию квантового алгоритма Харроу, Хасидима и Ллойда для линейных систем уравнений (HHL) и выводит коэффициенты $\lambda _{j}$ и оценка качества подгонки $E$. Он состоит из трех подпрограмм: алгоритма выполнения псевдообратной операции , одной процедуры оценки качества подгонки и алгоритма обучения параметров подгонки.

Поскольку квантовый алгоритм в основном основан на алгоритме HHL, он предполагает экспоненциальное улучшение. в случае, когда $F$ является разреженным , и число обусловленности (а именно, отношение между наибольшим и наименьшим собственными значениями ) обоих $FF^{\dagger }$ и $F^{\dagger }F$ мал.

Квантовое полуопределенное программирование

Полуопределенное программирование (SDP) — это подполе оптимизации, занимающееся оптимизацией линейной целевой функции (задаваемой пользователем функции, подлежащей минимизации или максимизации) над пересечением конуса положительных полуопределенных матриц с аффинным пространством . Целевая функция является внутренним продуктом матрицы $C$ (данный как вход) с переменной $X$. Обозначим через $\mathbb {S} ^{n}$ пространство всего $n\times n$ симметричные матрицы. Переменная $X$ должен лежать в (замкнутом выпуклом) конусе положительных полуопределенных симметричных матриц $\mathbb {S} _{+}^{n}$. Внутренний продукт двух матриц определяется как:

$\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1}^{n}A_{ij}B_{ij}.$

Проблема может иметь дополнительные ограничения (заданные в качестве входных данных), которые также обычно формулируются как внутренние продукты. Каждое ограничение заставляет внутренний продукт матриц $A_{k}$ (данный в качестве входных данных) с переменной оптимизации $X$ быть меньше указанного значения $b_{k}$ (данный в качестве входных данных). Наконец, задачу SDP можно записать так:

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}$

Неизвестно, чтобы лучший классический алгоритм работал безоговорочно за полиномиальное время . Известно, что соответствующая задача осуществимости лежит либо вне объединения классов сложности NP и co-NP, либо в пересечении NP и co-NP.

Квантовый алгоритм

Входные данные алгоритма: $A_{1}...A_{m},C,b_{1}...b_{m}$ решения и параметры, касающиеся трассы , точности и оптимального значения (значения целевой функции в оптимальной точке).

Квантовый алгоритм состоит из нескольких итераций. На каждой итерации он решает задачу осуществимости , а именно находит любое решение, удовлетворяющее следующим условиям (давая порог $t$):

${\begin{array}{lr}\langle C,X\rangle _{\mathbb {S} ^{n}}\leq t\\\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\X\succeq 0\end{array}}$

На каждой итерации разный порог $t$ выбирается, и алгоритм выводит либо решение $X$ такой, что $\langle C,X\rangle _{\mathbb {S} ^{n}}\leq t$ (и другие ограничения тоже выполняются) или указание на то, что такого решения не существует. Алгоритм выполняет двоичный поиск , чтобы найти минимальный порог. $t$ для чего решение $X$ все еще существует: это дает минимальное решение проблемы SDP.

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

Квантовая комбинаторная оптимизация

Задача комбинаторной оптимизации направлена ​​на поиск оптимального объекта из конечного множества объектов. Проблему можно сформулировать как максимизацию целевой функции , которая представляет собой сумму логических функций . Каждая булева функция $\,C_{\alpha }\colon \lbrace {0,1\rbrace }^{n}\rightarrow \lbrace {0,1}\rbrace$ получает в качестве входных данных $n$-битовая строка $z=z_{1}z_{2}\ldots z_{n}$ и выдает на выходе один бит (0 или 1). Задача комбинаторной оптимизации $n$ биты и $m$ пунктов – это нахождение $n$-битовая строка $z$ которая максимизирует функцию

$C(z)=\sum _{\alpha =1}^{m}C_{\alpha }(z)$

Приближенная оптимизация — это способ найти приближенное решение задачи оптимизации, которая часто является NP-трудной . Приближенным решением задачи комбинаторной оптимизации является строка $z$ это близко к максимизации $C(z)$.

Алгоритм квантовой приближенной оптимизации

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

QAOA состоит из следующих этапов:

1. Определение гамильтониана стоимости $H_{C}$ так, что его основное состояние кодирует решение задачи оптимизации.
2. Определение гамильтониана смесителя $H_{M}$.
3. Определение оракулов $U_{C}(\gamma )=\exp(-\imath \gamma H_{C})$ и $U_{M}(\alpha )=\exp(-\imath \alpha H_{M})$, с параметрами $\gamma$ и а.
4. Повторное применение оракула $U_{C}$ и $U_{M}$, в порядке: $U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})=\coprod _{i=1}^{N}(U_{C}(\gamma _{i})U_{M}(\alpha _{i}))$
5. Подготавливаем начальное состояние, то есть суперпозицию всех возможных состояний, и применяем $U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})$ государству.
6. Использование классических методов оптимизации параметров ${\boldsymbol {\gamma }},{\boldsymbol {\alpha }}$ и измерить выходное состояние оптимизированной схемы, чтобы получить приближенное оптимальное решение стоимостного гамильтониана. Оптимальным решением будет то, которое максимизирует математическое ожидание гамильтониана стоимости. $H_{C}$.

Пример анзаца QAOA для трехкубитной схемы

Структура алгоритма, а именно использование гамильтонианов стоимости и смесителя, основана на квантовой адиабатической теореме , которая гласит, что начиная с основного состояния гамильтониана, зависящего от времени, если гамильтониан развивается достаточно медленно, конечное состояние будет основное состояние конечного гамильтониана. Более того, адиабатическая теорема может быть обобщена на любое другое собственное состояние, если на протяжении эволюции нет перекрытия (вырождения) между различными собственными состояниями. Отождествление исходного гамильтониана с $H_{M}$ и окончательный гамильтониан с $H_{C}$, основное состояние которого кодирует решение интересующей задачи оптимизации, можно аппроксимировать задачу оптимизации как адиабатическое развитие гамильтониана от начального к конечному, основное (собственное) состояние которого дает оптимальное решение. В общем, QAOA опирается на использование унитарных операторов, зависящих от $2p$ углы (параметры), где $p>1$ — входное целое число, по которому можно определить количество слоев оракула $U({\boldsymbol {\gamma }},{\boldsymbol {\alpha }})$. Эти операторы итеративно применяются к состоянию, которое представляет собой равновзвешенную квантовую суперпозицию всех возможных состояний в вычислительном базисе. На каждой итерации состояние измеряется в вычислительном базисе и логической функции $C(z)$ оценивается. Затем углы обновляются классическим способом для увеличения $C(z)$. После повторения этой процедуры достаточное количество раз значение $C(z)$ почти оптимально, и измеряемое состояние также близко к оптимальному. Пример схемы, реализующей QAOA на квантовом компьютере, приведен на рисунке. Эта процедура поясняется на следующем примере поиска минимального вершинного покрытия графа.

QAOA для поиска минимального вершинного покрытия графа

Цель здесь — найти минимальное вершинное покрытие графа: набор вершин, в котором каждое ребро графа содержит хотя бы одну вершину покрытия. Следовательно, эти вершины «закрывают» все ребра. Мы хотим найти вершинное покрытие с наименьшим возможным числом вершин. Покрытия вершин могут быть представлены битовой строкой, где каждый бит обозначает, присутствует ли соответствующая вершина в покрытии. Например, битовая строка 0101 представляет покрытие, состоящее из второй и четвертой вершины в графе с четырьмя вершинами.

Пример графика, иллюстрирующего задачу минимального покрытия вершин.

Рассмотрим график, представленный на рисунке. Он имеет четыре вершины, и для этого графа существует два минимальных покрытия вершин: вершины 0 и 2, а также вершины 1 и 2. Они могут быть соответственно представлены битовыми строками 1010 и 0110. Целью алгоритма является выборка этих битов. строки с высокой вероятностью. В этом случае гамильтониан стоимости имеет два основных состояния |1010⟩ и |0110⟩, совпадающих с решениями задачи. Гамильтониан смесителя представляет собой простую некоммутирующую сумму операций Паули-X на каждом узле графа, определяемую следующим образом:

$H_{C}=-0.25Z_{3}+0.5Z_{0}+0.5Z_{1}+1.25Z_{2}+0.75(Z_{0}Z_{1}+Z_{0}Z_{2}+Z_{2}Z_{3}+Z_{1}Z_{2})$

$H_{M}=X_{0}+X_{1}+X_{2}+X_{3}$

Результат реализации QAOA в Qiskit для задачи минимального вершинного покрытия. Обратите внимание, что битовая строка |1010> инвертируется как |0101>, поскольку Qiskit использует обратный порядок битов.

Реализация QAOA в Qiskit для задачи минимального вершинного покрытия.

Реализация алгоритма QAOA для этой четырехкубитной схемы с двумя слоями анзаца в киските (см. рисунок) и оптимизация приводят к распределению вероятностей для состояний, представленных на рисунке. Это показывает, что состояния |0110⟩ и |1010⟩ имеют наибольшую вероятность измерения, как и ожидалось.

Обобщение QAOA для комбинаторной оптимизации с ограничениями

В принципе оптимальное значение $C(z)$ может быть достигнута с любой точностью, это гарантирует адиабатическая теорема или, альтернативно, универсальностью унитариев QAOA. Однако вопрос о том, возможно ли это сделать реальным способом, остается открытым. задачи Например, было показано, что QAOA демонстрирует сильную зависимость от отношения ограничения к переменным (плотности задачи), что накладывает предельное ограничение на способность алгоритма минимизировать соответствующую целевую функцию .

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

В статье « Сколько кубитов необходимо для квантового вычислительного превосходства», представленной arXiv, авторы приходят к выводу, что для моделирования схемы QAOA с 420 кубитами и 500 ограничениями потребуется не менее столетия с использованием классического алгоритма моделирования, работающего на современных суперкомпьютерах, так что этого будет достаточно для превосходства в квантовых вычислениях .

Строгое сравнение QAOA с классическими алгоритмами может дать оценки глубины $p$ и количество кубитов, необходимых для квантового преимущества. Исследование алгоритма QAOA и MaxCut показывает, что $p>11$ требуется для масштабируемого преимущества.

Варианты QAOA

Было предложено несколько вариантов базовой структуры QAOA: которые включают вариации анзаца основного алгоритма. Выбор анзаца обычно зависит от типа задачи, например, комбинаторных задач, представленных в виде графиков, или задач, на которые сильно влияет конструкция аппаратного обеспечения. Однако анзац-дизайн должен балансировать между специфичностью и общностью, чтобы избежать переобучения и сохранить применимость к широкому кругу проблем. По этой причине разработка оптимального анзаца для QAOA является тщательно изучаемой и широко исследуемой темой. Некоторые из предложенных вариантов:

1. Многоугольное QAOA
2. КАОА+
3. Оцифрованное противоадиабатическое QAOA
4. Подход квантового знакопеременного оператора , что позволяет наложить ограничения на задачу оптимизации и т. д.

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

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

См. также

• Адиабатические квантовые вычисления
• Квантовый отжиг

Внешние ссылки

• Реализация алгоритма QAOA для задачи о рюкзаке с помощью Classiq