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

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

Подгонка квантовых данных [ править ]

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

Квантовый метод наименьших квадратов [ править ]

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

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

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

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

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

${\displaystyle 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}}$

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

${\displaystyle {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}}}$

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

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

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

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

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

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

${\displaystyle {\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. ^[4]

Квантовый алгоритм [ править ]

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

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

В основе QAOA лежит использование унитарных операторов, зависящих от углов , где - входное целое число. Эти операторы итеративно применяются к состоянию, которое представляет собой равновзвешенную квантовую суперпозицию всех возможных состояний в вычислительном базисе. На каждой итерации состояние измеряется в вычислительной базе и вычисляется. После достаточного количества повторений значение почти оптимальное, и измеряемое состояние также близко к оптимальному.${\displaystyle 2p}$ ${\displaystyle p>1}$${\displaystyle C(z)}$${\displaystyle C(z)}$

В статье ^[9], опубликованной в Physical Review Letters 5 марта 2020 г. (предварительная печать ^[9], представленная 26 июня 2019 г. в arXiv ), авторы сообщают, что QAOA демонстрирует сильную зависимость от отношения ограничения проблемы к переменным (плотность проблемы), накладывающее ограничение на способность алгоритмов минимизировать соответствующую целевую функцию .

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

См. Также [ править ]

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

Ссылки [ править ]