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

Алгоритмы оптимизации с использованием квантовых вычислений

Алгоритмы квантовой оптимизации — это квантовые алгоритмы , которые используются для решения задач оптимизации. ^[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}$

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

Полуопределенное программирование (SDP) — это подполе оптимизации, занимающееся оптимизацией линейной целевой функции (задаваемой пользователем функции, подлежащей минимизации или максимизации) над пересечением конуса положительных полуопределенных матриц с аффинным пространством . Целевая функция — это внутренний продукт матрицы (заданной в качестве входных данных) с переменной . Обозначим через пространство всех симметричных матриц. Переменная должна лежать в (замкнутом выпуклом) конусе положительных полуопределенных симметричных матриц . Внутренний продукт двух матриц определяется как: ${\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 основано на использовании унитарных операторов , зависящих от углов , где — входное целое число. Эти операторы итеративно применяются к состоянию, которое представляет собой равновзвешенную квантовую суперпозицию всех возможных состояний в вычислительном базисе. На каждой итерации состояние измеряется в вычислительной базе и оценивается. Затем углы обновляются классическим способом для увеличения . После повторения этой процедуры достаточное количество раз значение становится практически оптимальным, а измеряемое состояние также близко к оптимальному. В принципе, оптимальное значение может быть достигнуто с любой точностью, это гарантируется адиабатической теоремой ^[9] или, альтернативно, универсальностью унитарной системы QAOA. ^[10] Однако вопрос о том, возможно ли это сделать, остается открытым. Например, было показано, что QAOA демонстрирует сильную зависимость от отношения ограничения задачи к переменным (плотности задачи), что накладывает предельное ограничение на способность алгоритма минимизировать соответствующую целевую функцию . ^[11] ${\displaystyle 2p}$ ${\displaystyle p>1}$ ${\displaystyle C(z)}$ ${\displaystyle C(z)}$ ${\displaystyle C(z)}$ ${\displaystyle C(z)}$

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

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

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

Смотрите также

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

Рекомендации

1. Молл, Николай; Баркуцос, Панайотис; епископ Лев С.; Чоу, Джерри М.; Кросс, Эндрю; Эггер, Дэниел Дж.; Филипп, Стефан; Фюрер Андреас; Гамбетта, Джей М.; Ганцхорн, Марк; Кандала, Абхинав; Меццакапо, Антонио; Мюллер, Питер; Рисс, Уолтер; Салис, Джиан; Смолин, Джон; Тавернелли, Ивано; Темме, Кристан (2018). «Квантовая оптимизация с использованием вариационных алгоритмов на квантовых устройствах ближайшего будущего». Квантовая наука и технология . 3 (3): 030503. arXiv : 1710.01022 . Бибкод : 2018QS&T....3c0503M. дои : 10.1088/2058-9565/aab822. S2CID  56376912.
2. Вибе, Натан; Браун, Дэниел; Ллойд, Сет (2 августа 2012 г.). «Квантовый алгоритм подбора данных». Письма о физических отзывах . 109 (5): 050505. arXiv : 1204.5242 . Бибкод : 2012PhRvL.109e0505W. doi :10.1103/PhysRevLett.109.050505. PMID  23006156. S2CID  118439810.
3. Монтанаро, Эшли (12 января 2016 г.). «Квантовые алгоритмы: обзор». npj Квантовая информация . 2 : 15023. arXiv : 1511.04206 . Бибкод : 2016npjQI...215023M. дои : 10.1038/npjqi.2015.23. S2CID  2992738.
4. Рамана, Мотакури В. (1997). «Точная теория двойственности полуопределенного программирования и ее последствия для сложности». Математическое программирование . 77 : 129–162. дои : 10.1007/BF02614433. S2CID  12886462.
5. Брандао, Фернандо GSL; Своре, Криста (2016). «Квантовое ускорение полуопределенного программирования». arXiv : 1609.05537 [квант-ph].
6. Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм (2014). «Квантовый приближенный алгоритм оптимизации». arXiv : 1411.4028 [квант-ph].
7. Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм (2014). «Алгоритм квантовой приближенной оптимизации, примененный к задаче с ограниченными ограничениями». arXiv : 1412,6062 [квант-ph].
8. Барак, Вооз; Мойтра, Анкур; О'Доннелл, Райан ; Рагхавендра, Прасад; Регев, Одед; Стойрер, Дэвид; Тревизан, Лука; Виджаярагаван, Аравиндан; Уитмер, Дэвид; Райт, Джон (2015). «Преодоление случайного назначения в задачах удовлетворения ограничений ограниченной степени». arXiv : 1505.03424 [cs.CC].
9. Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм (2014). «Квантовый приближенный алгоритм оптимизации». arXiv : 1411.4028 [квант-ph].
10. Моралес, Мэн; Биамонте, доктор медицинских наук; Зимборас, З. (20 сентября 2019 г.). «Об универсальности алгоритма квантовой приближенной оптимизации». Квантовая обработка информации . 19 : 291. arXiv : 1909.03123 . дои : 10.1007/s11128-020-02748-9.
11. Акшай, В.; Филатонг, Х.; Моралес, МЧС; Биамонте, JD (05 марта 2020 г.). «Дефицит достижимости в квантовой приближенной оптимизации». Письма о физических отзывах . 124 (9): 090504. arXiv : 1906.11259 . Бибкод : 2020PhRvL.124i0504A. doi : 10.1103/PhysRevLett.124.090504. PMID  32202873. S2CID  195699685.
12. Марш, С.; Ван, JB (08.06.2020). «Комбинаторная оптимизация с помощью высокоэффективных квантовых блужданий». Обзор физических исследований . 2 (2): 023302. arXiv : 1912.07353 . Бибкод : 2020PhRvR...2b3302M. doi : 10.1103/PhysRevResearch.2.023302. S2CID  216080740.
13. Далзелл, Александр М.; Харроу, Арам В.; Кох, Дакс Эншан; Ла Плака, Роландо Л. (11 мая 2020 г.). «Сколько кубитов необходимо для квантового вычислительного превосходства?». Квантовый . 4 : 264. arXiv : 1805.05224 . doi : 10.22331/кв-2020-05-11-264 . ISSN  2521-327Х.
14. Лыков, Данило; Вурц, Джонатан; Пул, Коди; Саффман, Марк; Ноэль, Том; Алексеев, Юрий (2022). «Пороговые значения частоты дискретизации для квантового преимущества алгоритма квантовой аппроксимированной оптимизации». arXiv : 2206.03579 [квант-ph].