Запуск квантових схем

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

Огляд уроку

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

1. Чим насправді є квантові комп'ютери IBM®. Тобі потрібно знати основи апаратних особливостей, щоб оптимально проєктувати свої квантові схеми для запуску на них.

2. Що таке Qiskit, що таке примітиви, і як ми можемо використовувати їх для створення та виконання квантових схем.

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

Апаратне забезпечення — IBM-квантові процесори

Щоб зрозуміти, як ми можемо робити оптимальні вибори при проектуванні великомасштабних квантових схем, потрібно знати дещо про фактичне апаратне забезпечення, що буде запускати ці схеми. Тож коротко обговоримо фізичні кубіти та IBM-квантові процесори.

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

На чіпі виготовляються надвисокочастотні лінії передачі для подачі надвисокочастотних сигналів до кубітів. Коли ми застосовуємо точно відкалібровані НВЧ-імпульси — з конкретною частотою, амплітудою, формою та тривалістю — до ліній, ми можемо змусити кубіти виконувати конкретні дії. Це є основою наших квантових вентилів. Ми виготовляємо чіп так, щоб сусідні кубіти з'єднувалися у специфічній решітковій структурі, яка називається решіткою «важкого шестикутника». Ця зв'язність — так звана топологія — наших процесорів є важливим фактором при проектуванні схеми, як ми обговоримо пізніше в уроці.

Інструкції для НВЧ-імпульсу надходять від твого комп'ютера через хмару до кімнатно-температурної контрольної електроніки, яка інтерпретує ці інструкції та фізично генерує імпульси. Після того як кімнатно-температурні блоки управління створюють імпульси, вони проходять кабелями до рефрижератора розчинення і, зрештою, до квантового чіпа. Сигнал надходить у резонатори, через дротяне з'єднання і потім надходить по лінії передачі до наших кубітів.

IBM має десятки квантових комп'ютерів по всьому світу, і нещодавно оновив свій флот, щоб мати виключно процесори з більш ніж 100 кубітами. Деякі з них розташовані в IBM-квантовому дата-центрі на півночі штату Нью-Йорк та розгорнуті через хмару для використання всіма — і деякі з них є виділеними локальними системами, що підтримують партнерів у мережі IBM Quantum® Network. Ти можеш увійти на quantum.cloud.ibm.com, щоб переглянути, до яких процесорів ти маєш доступ.

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

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

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

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

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

EPLG (Errors Per Layered Gate, помилки на шаруватий вентиль). Міра середньої помилки, внесеної операціями заплутувальних вентилів, розташованих шарами. Нижчий EPLG зазвичай вказує на вищу якість вентилів та нижче накопичення помилок.

CLOPS (Circuit Layer Operations Per Second, операції шару схеми за секунду). Бенчмарк, який вимірює, як швидко квантова система може виконати стандартизоване навантаження, що включає як квантові операції, так і пов'язану класичну обробку.

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

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

Програмне забезпечення: Qiskit та IBM Quantum Compute Service

Щоб перетворити свою квантову задачу в інструкції для квантового комп'ютера, ти будеш використовувати Qiskit — відкритий набір інструментів розробки програмного забезпечення, розроблений для роботи на квантових комп'ютерах компанією IBM. Є також екосистема Qiskit — колекція програмних підручників та функцій, що будуються або розширюють основні функціональні можливості Qiskit, — та Quantum Compute — сервіс квантових обчислень та модель програмування, що дозволяють користувачам проектувати та оптимізувати їхні квантові навантаження та ефективно виконувати їх за допомогою примітивів IBM Quantum.

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

З нещодавнім випуском Qiskit v1.0 Qiskit став більш продуктивним та стабільним, ніж будь-коли раніше. Тож якщо ти тільки починаєш, ти прийшов саме вчасно! Тим із вас, хто вже знайомий з Qiskit, потрібно завантажити та перевстановити нову версію. Для повного посібника з встановлення відвідай посібник Встановлення Qiskit.

Квантові схеми

Тепер ми готові обговорити основу квантових програм: квантові схеми. Цей розділ служитиме лише нагадуванням — якщо ти не знайомий з квантовими схемами, рекомендуємо докладніше ознайомитись з ними, відвідавши урок Квантові схеми в курсі «Основи квантової інформації» перед продовженням.

Квантова схема — це мережа квантових вентилів та вимірювань, пов'язаних дротами, що представляють кубіти, як показано нижче. Квантові схеми можна читати як нотні записи — зліва направо, починаючи з часу 0 зліва. Віртуальні кубіти — ті, що ще не призначені фізичному кубіту на процесорі — перелічені в порядку зростання зверху вниз.

Вентилі представлені різними символами на дротах залучених кубітів. Однокубітні вентилі — як вентиль Адамара, зображений нижче (прямокутник із H) — впливають лише на кубіт, на дроті якого вони розміщені. Багатокубітні вентилі — як вентиль CNOT, також показаний нижче (знак плюс у колі з лінією, що з'єднується з q0) — впливають на два або більше кубітів. На зображеному CNOT стан q1 змінюється відповідно до стану q0. Після виконання всіх вентилів ми можемо вимірювати кубіти, на що вказують чорні вентилі з символом вимірювання. Результати вимірювань записуються на класичні реєстри, подвійно-лінійну шину «meas» внизу.

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

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

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

Проектування квантової схеми: патерни Qiskit

Отже, як нам підійти до проектування та запуску квантової схеми? Найпростіший спосіб зрозуміти типовий робочий процес квантових обчислень — через патерни Qiskit. Патерни Qiskit — це концептуальний фреймворк, що дозволяє користувачам запускати квантові навантаження, реалізуючи певні кроки з модульними інструментами. Це дозволяє виконувати задачі квантових обчислень на потужній гетерогенній (CPU/GPU/QPU) обчислювальній інфраструктурі. Кроки можуть виконуватися як послуга та можуть включати управління ресурсами, що дозволяє безперешкодну компонованість нових можливостей у міру їх розробки.

Ось основні кроки, які досвідчені користувачі Qiskit, мабуть, впізнають.

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

2. Оптимізація. На цьому кроці ми використовуємо транспілятор Qiskit, щоб маршрутизувати та розташувати схему на реальному, фізичному кубітному апаратному забезпеченні. Це включає переклад окремих квантових вентилів у послідовності операцій, що виконуються на апаратному забезпеченні, а також оптимізацію розташування вентилів.

3. Виконання. Примітиви IBM Quantum надають інтерфейс до апаратного забезпечення IBM Quantum, що дозволяє запускати транспільовані схеми. Цей крок також включає використання методів придушення та пом'якшення помилок, які значною мірою можуть бути абстраговані від користувача.

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

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

Крок відображення по суті ставить питання: «Як мені перекласти свою задачу у квантову схему, яка може розумно запускатися на квантовому апаратному забезпеченні?» Без сумніву, відображення — важка задача та активна галузь досліджень. Немає надійного методу, що гарантує успіх, але є рекомендовані вказівки та приклади задач, які ми вже знаємо, як відображати.

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

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

Також май на увазі, що апаратне забезпечення, яке ти будеш використовувати, має специфічну топологію, як ми обговорювали в розділі про апаратне забезпечення. Деякі кубіти з'єднані, а деякі ні — тобі потрібно відобразити задачу на схему, що поважає топологію «важкого шестикутника» IBM-квантових процесорів.

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

Оптимізація

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

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

1. Не всі кубіти з'єднані. Деякі з них розташовані дуже далеко один від одного на чіпі, і нам потрібно зменшити або усунути взаємодії на великій відстані, де це можливо. Можна застосувати послідовність SWAP-вентилів між сусідніми кубітами, щоб перемістити інформацію кубітів, але SWAP-вентилі дорогі та схильні до помилок, тому можуть існувати кращі способи зробити це. Намагайся уникати занадто великої кількості дорогих SWAP-вентилів.

2. Розміщення (layout) та маршрутизація (routing) — це ітеративні процеси. Це можна робити вручну, але також є інструмент Qiskit під назвою mapomatic, який може давати рекомендації щодо фізичного розміщення кубітів на основі приблизних показників помилок. Транспілятор (який ми незабаром обговоримо) також може дати обґрунтовану пропозицію.

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

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

Транспілятор Qiskit

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

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

1. Ініціалізація. На цьому етапі виконуються будь-які початкові проходи, необхідні перед тим, як почати вбудовувати схему в бекенд. Зазвичай це передбачає розгортання користувацьких інструкцій та перетворення схеми лише на одно- та двокубітні гейти.

2. Розміщення (Layout). На цьому етапі віртуальні кубіти в схемі відображаються на фізичні кубіти бекенду. Детальніше див. Layout Stage.

3. Маршрутизація (Routing). Цей етап виконується після застосування розміщення і додає гейти (наприклад, swap-гейти) в початкову схему, щоб зробити її сумісною зі зв'язністю бекенду. Детальніше див. Routing Stage.

4. Трансляція (Translation). На цьому етапі гейти в схемі перетворюються на базовий набір цільового бекенду. Детальніше див. Translation Stage.

5. Оптимізація. На цьому етапі повторно виконується основний цикл оптимізації, поки не буде досягнута умова (наприклад, досягнення певної цільової глибини). У нас є чотири різні рівні оптимізації на вибір, описані нижче.

6. Планування (Scheduling). Цей етап призначений для будь-яких проходів планування, що враховують апаратне забезпечення. На високому рівні планування можна уявити як вставку затримок у схему, щоб врахувати час простою кубітів між виконанням інструкцій.

Є чотири рівні оптимізації від 0 до 3, де вищі рівні оптимізації займають більше часу та обчислювальних зусиль, але можуть дати кращу схему. Рівень оптимізації 0 призначений для характеристичних експериментів пристрою та, як такий, лише відображає вхідну схему на обмеження цільового бекенду без виконання будь-яких оптимізацій. Рівень оптимізації 3 докладає найбільше зусиль для оптимізації схеми. Однак, оскільки багато технік оптимізації в транспіляторі базуються на евристиках, більші обчислювальні зусилля не завжди призводять до покращення якості вихідної схеми. Якщо це тебе цікавить більше, дивись документацію транспілятора у документації Qiskit.

Придушення помилок

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

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

1. Динамічне розв'язування (dynamical decoupling) використовується для ефективного скасування частини шуму навколишнього середовища, що виникає, коли кубіт простоює. Застосовуючи серію вентилів у певні моменти часу, можна зробити так, щоб шум, накопичений в одній частині періоду простою, приблизно компенсував шум в іншій частині.

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

Виконання

Тепер ми готові виконати квантову програму. Примітиви IBM Quantum надають інтерфейс до IBM Quantum-апаратного забезпечення, а також абстрагують придушення та пом'якшення помилок від користувача. Є два примітиви на вибір: Sampler та Estimator.

IBM Quantum Sampler запускає схему багато разів на квантовому пристрої, виконуючи вимірювання при кожному запуску, та відновлює розподіл ймовірностей із відновлених бітових рядків. Що більше запусків (або знімків) він виконує, то точнішими будуть результати, але це потребує більше часу та квантових ресурсів. Зокрема, він обчислює ймовірність отримання кожного можливого стандартного базисного стану шляхом вимірювання стану, підготовленого схемою.

IBM Quantum Estimator використовує складний алгебраїчний процес для оцінки математичного сподівання на реальному квантовому пристрої, розкладаючи спостережуване на комбінацію інших спостережуваних із відомими власними базисами.

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

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

На рівні стійкості 0 транспілятор нічого не робить зі схемою.

На рівні 1 він запроваджує метод під назвою Twirled Readout Error eXtinction (T-REX). T-REX використовує скручування Паулі, як обговорювалось у розділі про придушення помилок. Як згадувалось, вставка випадкових вентилів у схему може зробити навіть дуже складний, важко моделюємий шум стохастичним і значно легшим для врахування або віднімання в постобробці.

На рівні стійкості 2 додається Zero Noise Extrapolation (ZNE). Це популярна техніка, з якою ми мали багато нещодавніх успіхів. Ідея за ZNE може бути трохи несподіваною — ми фактично додаємо шум поверх того, що вже є! Але це дозволяє нам екстраполювати у зворотному напрямку, щоб передбачити, як виглядатимуть результати при меншому і меншому шумі.

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

Одним конкретним типом ZNE є Probabilistic Error Amplification (PEA). Після того як ми дізнаємося модель шуму для вентиля, PEA працює шляхом вибірки помилок з цієї моделі шуму та навмисного їх введення в схему. Це ще недоступно в Qiskit, але буде пізніше цього року.

Остання форма пом'якшення помилок, яку ми розглянемо, — Probabilistic Error Cancellation (PEC). Замість того щоб знаходитись на 3-му рівні стійкості, PEC — це спеціальна можливість, яку потрібно вмикати вручну в Qiskit, оскільки необхідні обчислювальні ресурси не масштабуються добре порівняно з іншими техніками пом'якшення помилок. Починаєш з вивчення шуму, що впливає на твою схему — запускаєш навчальні або характеризаційні схеми шуму для кожного унікального шару двокубітних вентилів у твоїй схемі. Ці результати дозволяють описати шум у термінах операторів Паулі. Як тільки ти знаєш ці шумові члени, можна модифікувати свої схеми так, щоб вони ефективно мали протилежні вентилі Паулі, вбудовані для скасування цих шумових каналів. У певному сенсі процес схожий на те, як працюють навушники з шумопоглинанням. Однак цей спосіб скасування шуму дуже дорогий, із часом запуску, що швидко та показниково зростає з кількістю вентилів, тому він може бути не найкращим вибором для дуже великої схеми.

Постобробка

Етап постобробки — це де ми візуалізуємо та аналізуємо вихід нашої квантової схеми. Для цього є ряд інструментів Qiskit, таких як модулі візуалізації та квантової інформації. Ми не будемо розглядати їх тут, але побачимо ці модулі в дії, коли заглибимось у деякі прикладні застосування в майбутніх уроках.

Висновок

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

Наступного разу ми розглянемо конкретний приклад того, як використовувати робочий процес патернів Qiskit для проектування та запуску квантової схеми, яка вирішує класичну задачу з теорії графів — MaxCut.