QAOA у масштабі корисності

Перегляньте відео про QAOA у масштабі корисності від Олівії Лейнс або відкрийте відео в окремому вікні на YouTube.

Огляд уроку

До цього моменту в курсі ми сподіваємося надали тобі міцну основу фреймворку та інструментів для вирішення задач у масштабі корисності на квантовому комп'ютері. Тепер настав час побачити ці інструменти в дії.

У цьому уроці ми «забруднимо руки» із масштабним прикладом задачі Max-Cut — знаменитої задачі теорії графів про оптимальне розбиття графа на дві частини. Почнемо з простого графа з п'ятьма вузлами, щоб сформувати інтуїцію щодо того, як квантовий комп'ютер може допомогти вирішити задачу, а потім перейдемо до масштабної версії.

Цей урок дає широкий огляд підходу. Це не покрокове пояснення коду. Проте разом із уроком є туторіал із реальним кодом, який ти можеш запустити, щоб розв'язати Max-Cut на квантовому комп'ютері.

Задача

Нагадаємо: не всі обчислювальні задачі підходять для квантових обчислень. «Легкі задачі» не отримають жодних переваг від цієї технології, оскільки класичні комп'ютери і так їх чудово розв'язують.

Три сфери застосування, щодо яких ми найбільш оптимістичні:

1. симуляція природи
2. обробка даних зі складною структурою
3. оптимізація

Сьогодні ми зосередимося на третій — оптимізації. В задачі оптимізації, як правило, шукають найбільше або найменше значення певної функції. Складність знаходження цих екстремумів класичними методами може зростати експоненційно зі зростанням розміру задачі.

Задача оптимізації, що нас цікавить, — Max-Cut, яку ми будемо розв'язувати за допомогою алгоритму Quantum Approximate Optimization Algorithm (QAOA).

Що таке Max-Cut?

Маємо граф — множину вершин (вузлів), деякі з яких з'єднані ребрами. У задачі потрібно розбити вузли на дві підмножини, «розрізаючи» ребра між ними. Мета — знайти розбиття, що максимізує кількість розрізаних ребер — звідси назва «Max-Cut».

Наприклад, на малюнку вище показано граф з п'ятьма вузлами та рішенням Max-Cut праворуч. Розрізано п'ять ребер — максимально можливе для цього графа.

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

Хотілося б вирішувати Max-Cut для більших, складніших графів, адже задача має багато практичних застосувань: виявлення шахрайства у фінансах, кластеризація графів, проектування мереж, аналіз соціальних медіа. Max-Cut часто зустрічається як підзадача в більших задачах, тому є значно поширенішою, ніж може здатися.

Рішення

Розглянемо підхід до розв'язання Max-Cut на квантовому комп'ютері. Робитимемо це на простому графі з п'ятьма вузлами. Можна слідкувати за ходом у туторіалі з кодом Python. Після простого прикладу туторіал проведе тебе через масштабну версію задачі.

Перший крок — створити граф, задавши кількість вузлів та ребра. Це можна зробити, імпортувавши пакет rustworkx, як показано в туторіалі. Результат буде виглядати так:

Для пошуку рішень Max-Cut ми використаємо фреймворк Qiskit patterns.

Відображення

Потрібно відобразити задачу на квантовий комп'ютер. Для цього зауважимо, що максимізацію кількості розрізів у графі можна математично записати як:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

де $i$ і $j$ — вузли графа, $x_i$ і $x_j$ — 0 або 1 залежно від того, на якому боці розбиття знаходиться вузол. Коли $x_i$ і $x_j$ на одному боці, вираз у сумі рівний нулю. Коли на різних — рівний одиниці. Тому максимізація кількості розрізів максимізує суму.

Можна також перевернути задачу і шукати мінімум, помноживши значення на мінус один:

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

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

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

QUBO

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

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

де $Q$ — матриця розміром $n\times n$ з речовими числами, $n$ — кількість вузлів графа (тут п'ять).

Для застосування QAOA потрібно сформулювати задачу як Гамільтоніан — функцію або матрицю, що представляє повну енергію системи. Нам потрібен Гамільтоніан функції витрат, основний стан якого відповідає мінімуму функції. Тому для вирішення задачі оптимізації ми намагатимемося підготувати основний стан $H$ на квантовому комп'ютері. Вибірка з цього стану з високою ймовірністю дасть рішення $\min f(x)$.

Відображення на Гамільтоніан функції витрат

Виявляється, задача QUBO тісно пов'язана (і фактично обчислювально еквівалентна) одному з найвідоміших і найпоширеніших Гамільтоніанів фізики: Гамільтоніану Ізінга.

Щоб записати задачу QUBO як Гамільтоніан Ізінга, достатньо простої зміни змінних:

$$x_i = \frac{1-z_i}{2}.$$

Усі кроки описані в прикладеному блокноті. Підсумок: мінімізація QUBO еквівалентна мінімізації:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

Переписавши ще раз, отримуємо Гамільтоніан функції витрат, де мінімум відповідає основному стану, Z — оператор Паулі Z, $b$ — речовий скалярний коефіцієнт:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

Маючи Гамільтоніан, переписуємо його через двокальні оператори Паулі ZZ, що легко перетворюються на двокубітні гейти. Отримаємо шість об'єктів — рядків Паулі, — кожен відповідає одному з шести ребер графа. Кожен із п'яти елементів рядка представляє операцію на вузлі: тотожність, якщо вузол не зв'язаний із цим ребром, і Паулі Z, якщо зв'язаний. У Qiskit рядки кубітів індексуються у зворотному порядку. Наприклад, ребро між вузлами 0 і 1 кодується як IIIZZ, а між 2 і 4 — як ZIZII.

Побудова квантової схеми

Маючи Гамільтоніан у термінах операторів Паулі, будуємо квантову схему для вибірки гарних рішень:

Алгоритм QAOA натхненний Адіабатичною теоремою: якщо система починає в основному стані залежного від часу Гамільтоніана і Гамільтоніан еволюціонує достатньо повільно, кінцевий стан — основний стан фінального Гамільтоніана. QAOA — це дискретна, трояндована версія квантового адіабатичного алгоритму (QAA), де кожен крок Трота — шар QAOA. Замість плавної еволюції ми чергуємо Гамільтоніани функції витрат і «змішувальний» Гамільтоніан.

Перевага QAOA: він швидший за QAA, але дає наближені, а не оптимальні рішення. У граничному випадку нескінченного числа шарів QAOA збігається до QAA, але це обчислювально дуже дорого.

Для побудови схеми чергуємо оператори, параметризовані $\gamma$ і $\beta$, що представляють дискретизацію часової еволюції.

Три основні частини схеми QAOA:

1. Початковий пробний стан (сірий) — основний стан змішувача, утворений застосуванням воріт Адамара до кожного кубіта.
2. Еволюція за Гамільтоніаном функції витрат (темно-фіолетовий).
3. Еволюція за змішувальним Гамільтоніаном (світло-фіолетовий).

Вихідний Гамільтоніан — змішувальний, бо його основний стан є суперпозицією всіх можливих двійкових рядків, тобто сумішшю всіх можливих рішень.

Змішувальний Гамільтоніан — проста сума операторів Паулі-X на кожному вузлі. Qiskit дозволяє використовувати власний змішувальний оператор, але ми застосовуємо стандартний. Єдина робота, яку нам довелося виконати, — знайти функцію витрат.

Кожна ітерація цих операторів — шар. Шари можна розглядати як дискретизацію часової еволюції системи. Чим більше шарів — тим ближче до неперервної еволюції, як у QAA. Але для початку ми почнемо з одного шару. Пам'ятай: і Гамільтоніан функції витрат, і змішувальний параметризовані — ще потрібно знайти оптимальні $\gamma$ і $\beta$.

Оптимізація

Хоча схема виглядає просто, квантовий чіп не «розуміє» гейт QAOA. Потрібно перетворити його на серію однокубітних і двокубітних «рідних» гейтів, виконуваних безпосередньо на апараті. Рідні гейти — ті, що можна виконати безпосередньо на кубітах. Такі схеми написані в архітектурі набору інструкцій (ISA) пристрою.

Бібліотека Qiskit пропонує серію проходів транспіляції для широкого спектра перетворень схем. Потрібно оптимізувати схему для нашої мети.

Нагадаємо з попереднього уроку: транспіляція включає кілька кроків:

• Початкове відображення кубітів схеми на фізичні кубіти пристрою.
• Розгортання інструкцій квантової схеми в рідні інструкції апарата.
• Маршрутизація взаємодіючих кубітів схеми на сусідні фізичні кубіти.

Детальніше — у документації.

Перед транспіляцією потрібно вибрати бекенд, бо транспілятор оптимізує по-різному для різних процесорів. Це ще одна причина використовувати автоматичний транспілятор — не хочеться вручну оптимізувати схему і потім зрозуміти, що треба запускати її на іншому процесорі з іншими властивостями.

Передай вибраний бекенд через функцію транспілятора і вкажи рівень оптимізації. У туторіалі обирається рівень 3 — найвищий і найретельніший.

Тепер маємо транспіловану схему, готову до виконання на апараті!

Виконання

До цього моменту ми транспілювали схему, залишивши параметри gamma і beta вільними — але запустити схему без конкретних значень не можна. У робочому процесі QAOA оптимальні параметри знаходяться в ітераційному циклі оптимізації: ми запускаємо серію обчислень схеми і класичним оптимізатором знаходимо оптимальні $\beta$ і $\gamma$. Але потрібна відправна точка, тому робимо початкові здогадки: $\gamma=\pi/2$ і $\beta=\pi$.

Режими виконання

Перш ніж запустити схему, важливо знати: завдання можна надсилати по-різному — так звані режими виконання.

• Режим завдань (Job): одиничний запит до примітива Estimator або Sampler без контекстного менеджера. Схеми та вхідні дані пакуються як PUB і надсилаються як завдання на квантовий комп'ютер.

• Пакетний режим (Batch): менеджер для ефективного запуску експерименту з пакетом незалежних завдань. Дозволяє одночасно надсилати кілька примітивних завдань.

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

Для експерименту QAOA хорошим вибором є сесія (якщо є доступ), оскільки потрібно вибирати схему багато разів із різними значеннями параметрів.

Повернімося до задачі оптимізації. Потрібно знайти кращі значення gamma і beta, ніж наші початкові здогадки. Для цього підставимо функцію витрат і початкові здогадки в оптимізатор scipy COBYLA.

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

Тепер, знайшовши кращі значення параметрів, запустимо схему з новими значеннями gamma і beta. Наведені конкретні значення, але пам'ятай: коли ти спробуєш самостійно або просто перезапустиш туторіал, значення можуть трохи відрізнятися. Тепер запустимо оптимізовану схему і знайдемо рішення-кандидат нашої задачі Max-Cut.

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

Постобробка

Побудуємо гістограму даних для аналізу кінцевого рішення:

Бітові рядки представляють, як вузли розподілені між двома групами (мітки «0» і «1»). Має бути чотири рішення, що дають максимальну кількість розрізів — вони показані фіолетовим. Видно, що чотири рішення значно ймовірніші за всі інші. Найімовірніший бітовий рядок — 0,1,0,1,1 (пам'ятай: порядок кубітів у бітових рядках на графіку зворотний!).

З цього графіка беремо найімовірніший бітовий рядок і представляємо його як розбитий граф із розрізом через п'ять ребер:

Це справді рішення Max-Cut. Але не єдине! Через симетрію графа існує кілька правильних рішень. Замість вузлів 0 і 3 всередині розрізу могли б бути вузли 2 і 4. Просто повернемо розріз, щоб включити ці нові точки. Кількість розрізаних ребер залишається п'ятьма. Загалом є чотири рішення Max-Cut: кожне з двох рішень має «дзеркальний» варіант, де фіолетові й сірі вузли міняються місцями.

Подивимося на гістограму ще раз. Ідеально кожне з чотирьох найімовірніших рішень було б одним із чотирьох справжніх рішень Max-Cut. Але алгоритм не ідентифікував четверте і останнє рішення як одне з чотирьох найімовірніших — воно посіло п'яте місце. Четверте рішення, ідентифіковане алгоритмом, є хибним: якщо намалювати його, виявляється лише чотири розрізи.

Але пам'ятай: це апроксимаційний алгоритм. Він не бездоганний і не завжди правильний. Потрібно застосовувати власні знання для перевірки здоровим глуздом.

Ця помилка може виникати з кількох причин:

1. Наближена природа самого алгоритму і мала кількість шарів.
2. Кінцева похибка вибірки — зменшується зі збільшенням кількості пострілів.
3. Похибка зчитування — четверте справжнє рішення відрізняється лише одним бітом.

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

Проте не варто забувати: було 32 можливих бітових рядки, і чотири справжні рішення увійшли в п'ять найкращих кандидатів. І ми використали лише два шари. Загалом, щоб підвищити шанси знаходити найкращий Max-Cut щоразу, можна збільшити глибину шарів. Але тут є деякі нюанси — про це в наступних уроках.

У масштабі корисності

Тепер, коли ти спробував вирішити невелику задачу Max-Cut на квантовому комп'ютері, пропоную зробити це в масштабі. Слідуй за туторіалом і подивись, скільки розрізів вдасться отримати на графі зі 125 вузлами.