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

Математична оптимізація стосується пошуку найкращого рішення проблеми (за деякими критеріями) із набору можливих рішень. Переважно, проблема оптимізації формулюється як проблема мінімізації, де намагаються мінімізувати помилку, яка залежить від рішення: оптимальне рішення має мінімальну помилку. У різних галузях, таких як механіка, економіка та інженерія, застосовуються різні методи оптимізації, а в міру збільшення складності та обсягу даних необхідні більш ефективні способи вирішення проблем оптимізації. Потужність квантових обчислень може дозволити вирішувати задачі, які практично не можливо розв'язати на класичних комп'ютерах, або запропонувати значну швидкість щодо найбільш відомого класичного алгоритму. Серед інших квантових алгоритмів існують алгоритми квантової оптимізації, які можуть запропонувати вдосконалення у вирішенні завдань оптимізації.

Квантова апроксимація даних

Апроксимація даних — це процес побудови математичної функції, яка найкраще відповідає набору точок даних. Якість придатності вимірюється деякими критеріями, як правило, відстані між функцією та точками даних.

Квантова апроксимація методом найменших квадратів

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

Алгоритм отримує на вхід ${\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}}}}$

Квантовий алгоритм апроксимації найменших квадратів використовує версію квантового алгоритму Харроу, Хассідима та Ллойда для лінійних систем рівнянь (HHL) та виводить коефіцієнти ${\displaystyle {\displaystyle \lambda _{j}}}$ і оцінку якості апроксимації ${\displaystyle {\displaystyle E}}$. Він складається з трьох підпрограм: алгоритму виконання псевдо зворотної операції, однієї підпрограми для оцінки якості придатності та алгоритму вивчення параметрів придатності.

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

Квантове напіввизначене програмування

Напіввизначене програмування - це підрозділ оптимізації, що займається оптимізацією лінійної цільової функції (визначена користувачем функція, яка повинна бути мінімізована або максимізована), через перетин конуса позитивних напіввизначених матриць із афінним простором. Цільова функція - це внутрішній добуток матриці ${\displaystyle {\displaystyle C}}$ (заданий як вхід) зі змінною ${\displaystyle {\displaystyle X}}$. Позначимо ${\displaystyle {\displaystyle \mathbb {S} ^{n}}}$ як простір усіх ${\displaystyle {\displaystyle n\times n}}$ симетричних матриць. Змінна ${\displaystyle {\displaystyle X}}$ повинна лежати у еконусі позитивних напіввизначених симетричних матриць ${\displaystyle {\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}.}$

Проблема може мати додаткові обмеження (задані як вхідні дані), які також формулюються як внутрішні добутки. Кожне обмеження змушує внутрішній добуток матриць ${\displaystyle {\displaystyle A_{k}}}$ (задане як вхід) із змінною оптимізації ${\displaystyle {\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}}}$

Найкращий відомий класичний алгоритм працює у найгіршому випадку за поліноміальний час.

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

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

Квантовий алгоритм складається з декількох ітерацій. У кожній ітерації він знаходить будь-яке рішення, що задовольняє наступним умовам (даючи поріг ${\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}}$: це дає мінімальну відповідь для задачі.

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

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

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

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

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

Квантовий приблизний алгоритм оптимізації

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

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

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

Див також

• Квантова перевага
• Квантове програмування
• Квантове розповсюдження ключа

Посилання

1. Moll, Nikolaj; Barkoutsos, Panagiotis; Bishop, Lev S; Chow, Jerry M; Cross, Andrew; Egger, Daniel J; Filipp, Stefan; Fuhrer, Andreas; Gambetta, Jay M (19 червня 2018). Quantum optimization using variational algorithms on near-term quantum devices. Quantum Science and Technology. Т. 3, № 3. с. 030503. doi:10.1088/2058-9565/aab822. ISSN 2058-9565. Процитовано 23 грудня 2019.
2. Wiebe, Nathan; Braun, Daniel; Lloyd, Seth (2 серпня 2012). Quantum Algorithm for Data Fitting. Physical Review Letters. Т. 109, № 5. doi:10.1103/physrevlett.109.050505. ISSN 0031-9007. Процитовано 23 грудня 2019.
3. Montanaro, Ashley (12 січня 2016). Quantum algorithms: an overview. npj Quantum Information. Т. 2, № 1. doi:10.1038/npjqi.2015.23. ISSN 2056-6387. Процитовано 23 грудня 2019.
4. Brandao, Fernando G.S.L.; Svore, Krysta M. (2017-10). Quantum Speed-Ups for Solving Semidefinite Programs. 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. doi:10.1109/focs.2017.45. ISBN . Процитовано 23 грудня 2019.
5. FARHI, EDWARD; GOLDSTONE, JEFFREY; GUTMANN, SAM; NAGAJ, DANIEL (2008-06). HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL. International Journal of Quantum Information. Т. 06, № 03. с. 503—516. doi:10.1142/s021974990800358x. ISSN 0219-7499. Процитовано 23 грудня 2019.
6. Barak, Boaz; Raghavendra, Prasad; Steurer, David (2011-10). Rounding Semidefinite Programming Hierarchies via Global Correlation. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE. doi:10.1109/focs.2011.95. ISBN . Процитовано 23 грудня 2019.
7. Harrigan, Matthew P.; Sung, Kevin J.; Neeley, Matthew; Satzinger, Kevin J.; Arute, Frank; Arya, Kunal; Atalaya, Juan; Bardin, Joseph C.; Barends, Rami (2021-03). . Nature Physics (англ.). Т. 17, № 3. с. 332—336. doi:10.1038/s41567-020-01105-y. ISSN 1745-2481. Архів оригіналу за 22 червня 2021. Процитовано 1 травня 2021.