Алгоритми квантової оптимізації

Один з найпоширеніших типів апроксимації даних — це розв'язання задачі з найменшими квадратами, мінімізація суми квадратів відмінностей між точками даних та вбудованою функцією.

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

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

Іншими словами, алгоритм знаходить складний коефіцієнт ${\displaystyle {\displaystyle \lambda _{j}}}$ і, таким чином, знаходить вектор ${\displaystyle {\displaystyle {\vec {\lambda }}=(\lambda _{1},\lambda _{2},...,\lambda _{M})}.}$

Алгоритм спрямований на мінімізацію помилки, котра задається:

${\displaystyle {\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 {\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 {\displaystyle \lambda _{j}}}$ і оцінку якості апроксимації ${\displaystyle {\displaystyle E}}$. Він складається з трьох підпрограм: алгоритму виконання псевдо зворотної операції, однієї підпрограми для оцінки якості придатності та алгоритму вивчення параметрів придатності.

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

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

Квантовий алгоритм[4] складається з декількох ітерацій. У кожній ітерації він знаходить будь-яке рішення, що задовольняє наступним умовам (даючи поріг ${\displaystyle {\displaystyle t}}$):

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

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

Квантовий алгоритм забезпечує квадратичне вдосконалення над найкращим класичним алгоритмом у загальному випадку та експоненціальне вдосконалення, коли вхідні матриці низького рангу.

Для комбінаторної оптимізації алгоритм квантової приблизної оптимізації (КПАО)[5] має кращий коефіцієнт наближення, ніж будь-який відомий класичний алгоритм поліноміального часу (для певної проблеми)[5], поки не було запропоновано більш ефективний класичний алгоритм[6]. Відносна прискореність квантового алгоритму є відкритим дослідницьким питанням.

Серце КПАО покладається на використання унітарних операторів, залежних від кутів ${\displaystyle {\displaystyle 2p}}$, де ${\displaystyle {\displaystyle p>1}}$ є вхідним цілим числом. Ці оператори ітераційно застосовуються в стані, що є зрівноваженою квантовою суперпозицією всіх можливих станів в обчислювальній основі. У кожній ітерації стан вимірюється в обчислювальній основі і обчислюється ${\displaystyle {\displaystyle C(z)}}$. Після достатньої кількості повторень значення ${\displaystyle {\displaystyle C(z)}}$ є майже оптимальним, і стан, що вимірюється, також близький до оптимального.

У квітні 2021 відбулась демонстрація застосування надпровідного кубітового квантового процесора Sycamore до комбінаторних задач оптимізації з алгоритмом квантової наближеної оптимізації (QAOA). Як і в минулих експериментах QAOA, вивчалась ефективність для проблем, визначених на площинному графіку; однак QAOA також застосовувалась до модель Шеррінгтона – Кіркпатріка та MaxCut (максимальний розріз графа), для реалізації яких потрібна велика компіляція[7].