Перегляд вихідного коду сторінки Алгоритми квантової оптимізації

У Вас нема дозволу на редагування цієї сторінки з такої причини:

Ваша IP-адреса знаходиться в діапазоні, який заблоковано у всіх вікі Фонду Вікімедіа.

Блокування зроблено ‪EPIC‬. Причиною вказано Open proxy/Webhost: See the help page if you are affected.

Початок блокування: 08:48, 2 липня 2024
Закінчення блокування: 08:48, 2 липня 2025

Ваша поточна IP-адреса: 206.189.44.186. Заблокований діапазон — 206.189.32.0/20.

Будь ласка, додайте всі вказані подробиці до будь-яких запитів, які Ви будете робити. Якщо ви вважаєте, що вас заблокували помилково, ви можете знайти додаткову інформацію та інструкції в глобальній політиці Без відкритих проксі.

В іншому випадку, щоб обговорити блокування, будь ласка, опублікуйте запит на розгляд на Мета-вікі. Ви також можете надіслати електронний лист до VRT-черги стюардів за адресою stewards@wikimedia.org, вказавши усю вищезазначену інформацію.

Ви можете переглянути та скопіювати вихідний текст цієї сторінки:

[[Оптимізація (математика)|Математична оптимізація]] стосується пошуку найкращого рішення проблеми (за деякими критеріями) із набору можливих рішень. Переважно, проблема оптимізації формулюється як проблема мінімізації, де намагаються мінімізувати помилку, яка залежить від рішення: оптимальне рішення має мінімальну помилку. У різних галузях, таких як [[механіка]], [[економіка]] та інженерія, застосовуються різні методи оптимізації, а в міру збільшення складності та обсягу даних необхідні більш ефективні способи вирішення проблем оптимізації. Потужність [[Квантовий комп'ютер|квантових обчислень]] може дозволити вирішувати задачі, які практично не можливо розв'язати на класичних комп'ютерах, або запропонувати значну швидкість щодо найбільш відомого класичного алгоритму. Серед інших квантових алгоритмів існують '''алгоритми квантової оптимізації''', які можуть запропонувати вдосконалення у вирішенні завдань оптимізації.<ref>{{Cite news|title=Quantum optimization using variational algorithms on near-term quantum devices|last3=Bishop|first9=Jay M|last8=Fuhrer|first8=Andreas|last7=Filipp|first7=Stefan|last6=Egger|first6=Daniel J|last5=Cross|first5=Andrew|last4=Chow|first4=Jerry M|first3=Lev S|url=http://dx.doi.org/10.1088/2058-9565/aab822|last2=Barkoutsos|first2=Panagiotis|last=Moll|first=Nikolaj|issue=3|volume=3|pages=030503|doi=10.1088/2058-9565/aab822|issn=2058-9565|accessdate=2019-12-23|date=2018-06-19|work=Quantum Science and Technology|last9=Gambetta}}</ref>

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

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

Алгоритм отримує на вхід <math>{\displaystyle N}</math> точок даних<math> {\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})} </math> і <math>{\displaystyle M}</math> неперервних функцій<math>{\displaystyle f_{1},f_{2},...,f_{M}}</math>. Алгоритм знаходить і дає на вихід неперервну функцію <math>{\displaystyle f_{\vec {\lambda }}}</math>, котра є лінійною комбінацією із <math>{\displaystyle f_{j}}</math>:

<math>{\displaystyle f_{\vec {\lambda }}(x)=\sum _{j=1}^{M}f_{j}(x)\lambda _{j}}</math>

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

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

<math>{\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}}</math>

де ми визначаємо <math>F</math> як наступну матрицю:

<math>{\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}}}</math>

Квантовий алгоритм апроксимації найменших квадратів<ref>{{Cite news|title=Quantum Algorithm for Data Fitting|url=http://dx.doi.org/10.1103/physrevlett.109.050505|work=Physical Review Letters|date=2012-08-02|accessdate=2019-12-23|issn=0031-9007|doi=10.1103/physrevlett.109.050505|volume=109|issue=5|first=Nathan|last=Wiebe|first2=Daniel|last2=Braun|first3=Seth|last3=Lloyd}}</ref> використовує версію квантового алгоритму Харроу, Хассідима та Ллойда для лінійних систем рівнянь (HHL) та виводить коефіцієнти <math>{\displaystyle \lambda _{j}}</math> і оцінку якості апроксимації <math>{\displaystyle E}</math>. Він складається з трьох підпрограм: алгоритму виконання псевдо зворотної операції, однієї підпрограми для оцінки якості придатності та алгоритму вивчення параметрів придатності.

Оскільки квантовий алгоритм в основному базується на алгоритмі HHL, він пропонує експоненціальне поліпшення<ref>{{Cite news|title=Quantum algorithms: an overview|url=http://dx.doi.org/10.1038/npjqi.2015.23|work=npj Quantum Information|date=2016-01-12|accessdate=2019-12-23|issn=2056-6387|doi=10.1038/npjqi.2015.23|volume=2|issue=1|first=Ashley|last=Montanaro}}</ref> у випадку, коли <math>{\displaystyle F}</math> є розрідженою матрицею і число умови (а саме співвідношення між найбільшим і найменшим власними значеннями) обох <math>{\displaystyle FF^{\dagger }}</math> і <math>{\displaystyle F^{\dagger }F}</math> невелике.

== Квантове напіввизначене програмування ==
Напіввизначене програмування - це підрозділ оптимізації, що займається оптимізацією лінійної цільової функції (визначена користувачем функція, яка повинна бути мінімізована або максимізована), через перетин конуса позитивних напіввизначених матриць із афінним простором. Цільова функція - це внутрішній добуток матриці <math>{\displaystyle C}</math> (заданий як вхід) зі змінною <math>{\displaystyle X}</math>. Позначимо <math>{\displaystyle \mathbb {S} ^{n}}</math> як простір усіх <math> {\displaystyle n\times n}</math> симетричних матриць. Змінна <math> {\displaystyle X}</math> повинна лежати у еконусі позитивних напіввизначених симетричних матриць <math>{\displaystyle \mathbb {S} _{+}^{n}}</math>. Внутрішній добуток двох матриць визначається як:

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

Проблема може мати додаткові обмеження (задані як вхідні дані), які також формулюються як внутрішні добутки. Кожне обмеження змушує внутрішній добуток матриць <math>{\displaystyle A_ {k}}</math> (задане як вхід) із змінною оптимізації <math>{\displaystyle X}</math> бути меншим, ніж задане значення <math>b_{k}</math> (задається як вхід). Нарешті, проблему можна записати так:

<math>{\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}}</math>

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

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

Квантовий алгоритм<ref>{{Cite news|title=Quantum Speed-Ups for Solving Semidefinite Programs|url=http://dx.doi.org/10.1109/focs.2017.45|publisher=IEEE|work=2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)|date=2017-10|accessdate=2019-12-23|isbn=978-1-5386-3464-6|doi=10.1109/focs.2017.45|first=Fernando G.S.L.|last=Brandao|first2=Krysta M.|last2=Svore}}</ref> складається з декількох ітерацій. У кожній ітерації він знаходить будь-яке рішення, що задовольняє наступним умовам (даючи поріг <math>{\displaystyle t}</math>):

<math>{\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}}}</math>

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

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

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

<math>{\displaystyle C(z)=\sum _{\alpha =1}^{m}C_{\alpha }(z)}</math>

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

=== Квантовий приблизний алгоритм оптимізації ===
Для комбінаторної оптимізації алгоритм квантової приблизної оптимізації (КПАО)<ref name=":0">{{Cite news|title=HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL|first=EDWARD|first4=DANIEL|last3=GUTMANN|first3=SAM|last2=GOLDSTONE|first2=JEFFREY|last=FARHI|issue=03|url=http://dx.doi.org/10.1142/s021974990800358x|volume=06|pages=503–516|doi=10.1142/s021974990800358x|issn=0219-7499|accessdate=2019-12-23|date=2008-06|work=International Journal of Quantum Information|last4=NAGAJ}}</ref> має кращий коефіцієнт наближення, ніж будь-який відомий класичний алгоритм поліноміального часу (для певної проблеми)<ref name=":0"/>, поки не було запропоновано більш ефективний класичний алгоритм<ref>{{Cite news|title=Rounding Semidefinite Programming Hierarchies via Global Correlation|url=http://dx.doi.org/10.1109/focs.2011.95|publisher=IEEE|work=2011 IEEE 52nd Annual Symposium on Foundations of Computer Science|date=2011-10|accessdate=2019-12-23|isbn=978-0-7695-4571-4|doi=10.1109/focs.2011.95|first=Boaz|last=Barak|first2=Prasad|last2=Raghavendra|first3=David|last3=Steurer}}</ref>. Відносна прискореність квантового алгоритму є відкритим дослідницьким питанням.

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

У квітні 2021 відбулась демонстрація застосування надпровідного кубітового квантового процесора [[Процесор Sycamore|Sycamore]] до комбінаторних задач оптимізації з алгоритмом квантової наближеної оптимізації (QAOA). Як і в минулих експериментах QAOA, вивчалась ефективність для проблем, визначених на площинному графіку; однак QAOA також застосовувалась до {{не перекладено |модель Шеррінгтона – Кіркпатріка |3=en| 4=Spin_glass#The_model_of_Sherrington_and_Kirkpatrick}}<!-- Проблема вікіфікації: Сторінка [[:en:Spin_glass#The_model_of_Sherrington_and_Kirkpatrick]] перекладена як [[Спінове скло]], хоча хотіли [[модель Шеррінгтона – Кіркпатріка]] (SashkoR0B0T)--> та {{не перекладено |MaxCut (максимальний розріз графа)|3=en|4=Maximum_cut}}, для реалізації яких потрібна велика компіляція<ref>{{Cite news|title=Quantum approximate optimization of non-planar graph problems on a planar superconducting processor|first3=Matthew|first9=Rami|last8=Bardin|first8=Joseph C.|last7=Atalaya|first7=Juan|last6=Arya|first6=Kunal|last5=Arute|first5=Frank|last4=Satzinger|first4=Kevin J.|last3=Neeley|last2=Sung|url=https://www.nature.com/articles/s41567-020-01105-y|first2=Kevin J.|last=Harrigan|first=Matthew P.|language=en|issue=3|volume=17|pages=332–336|doi=10.1038/s41567-020-01105-y|issn=1745-2481|accessdate=2021-05-01|date=2021-03|work=Nature Physics|last9=Barends|archive-date=22 червня 2021|archive-url=https://web.archive.org/web/20210622145632/https://www.nature.com/articles/s41567-020-01105-y}}</ref>.

== Див також ==
* [[Квантовий відпал]]
* [[Квантова перевага]]
* [[Квантове програмування]]
* [[Квантове розповсюдження ключа]]

== Посилання ==
<references />
[[Категорія:Алгоритми]]

Шаблони, використані на цій сторінці:

Шаблон:Cite news (переглянути вихідний код) (захищено)
Шаблон:Не перекладено (переглянути вихідний код) (захищено)
Модуль:Citation/CS1 (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/COinS (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Configuration (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Identifiers (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Utilities (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/Whitelist (переглянути вихідний код) (захищено)
Модуль:Citation/CS1/styles.css (переглянути вихідний код) (захищено)
Модуль:Не перекладено (переглянути вихідний код) (захищено)

Повернення до сторінки «Алгоритми ква��тової оптимізації».

Отримано з https://uk.wikipedia.org/wiki/Алгоритми_квантової_оптимізації