Для яких задач квантові комп'ютери підходять найкраще?

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

Вступ

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

Класична та квантова складність

Перш ніж перейти до прикладів, давай обговоримо, як ми вивчаємо і класифікуємо складність різних задач. Деякі задачі легко розв'язуються на класичному комп'ютері, і квантовий комп'ютер для цього не потрібен. З іншого боку, є дуже складні задачі, для яких необхідні квантові комп'ютери. Один відомий приклад — знаходження простих дільників величезних цілих чисел. Безпека RSA-шифрування ґрунтується на складності цієї задачі, і алгоритм Шора розроблений саме для її розв'язання на квантовому комп'ютері. Ще один приклад — пошук розв'язку у невпорядкованому наборі даних, який теоретично можна розв'язати за допомогою квантового алгоритму Гровера. Однак більшість експертів погоджуються, що такі алгоритми вимагатимуть виправлення помилок, якого технологія поки ще не досягла.

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

Класи складності

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

• P: Задачі, які можна розв'язати за поліноміальний час при збільшенні розміру задачі. Вони легко розв'язуються.
• NP: Розшифровується як недетермінований поліном. Ці задачі не обов'язково розв'язуються за поліноміальний час, але їхні відповіді можна перевірити за поліноміальний час.
• NP-повні — найскладніші задачі в NP, для яких немає відомого поліноміального рішення. Тут живуть такі відомі задачі, як комівояжер і гра Судоку.
• BPP, або задачі з обмеженою похибкою та поліноміальним часом — ті, що розв'язуються з певним порогом похибки ймовірнісним класичним комп'ютером за поліноміальний час.

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

• BQP, або задачі з обмеженою похибкою та квантовим поліноміальним часом. Це квантовий еквівалент BPP: клас задач прийняття рішень, що розв'язуються квантовим комп'ютером за поліноміальний час з малою ймовірністю помилки.

Усі ці класи знаходяться у більшому класі PSPACE. Вище зображено діаграму передбачуваних співвідношень між деякими класами складності, але математично довести це дуже важко. Помітимо, що BQP не обов'язково перетинається з NP-повними. Проте ти міг зустрічати квантові підходи, що намагаються розв'язувати NP-повні задачі.

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

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

Труднощі з доведенням жорстких меж не означають, що ми не можемо просуватися вперед. Ми вводимо ідею евристичних рішень. Якщо ти експериментатор, то, мабуть, добре знаєш і любиш такі рішення. Евристика — це будь-який підхід до розв'язання задачі, що є прагматичним, але не обов'язково оптимальним, оскільки рішення не мусять бути оптимальними, щоб бути корисними. Наприклад, подумай про фінансові застосування. Ми ще не знайшли експоненційного прискорення для більшості фінансових алгоритмів із квантовим застосуванням, але нам не потрібне оптимальне рішення. У фінансах навіть рішення, що лише на 0,1% ефективніше, може означати мільярди доларів прибутку.

Сучасні квантові комп'ютери та їхні обмеження

Отже, як зрозуміти, які варіанти використання та задачі можуть підходити для квантових обчислень прямо зараз? Чи є вагомі підстави вважати, що квантову корисність або навіть перевагу можна знайти вже зараз або в найближчому майбутньому?

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

Всі ці обмеження враховані в дорожній карті IBM Quantum®, і ми очікуємо досягти виправлення помилок на початку 2030-х, але наразі потрібно шукати експерименти, що задіюють більшість кубітів на конкретному QPU. Ми також підкреслюємо важливість пом'якшення та придушення помилок. І нарешті, має бути очевидне розширення до майбутніх застосувань, важливих для суспільства, яке з часом могло б привести до квантової переваги.

Галузі застосування і конкретні випадки

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

1. Симуляція природи. Сучасні класичні методи атомного та молекулярного моделювання обмежені неефективними математичними описами атомної структури. Зберігання та маніпуляція квантовим станом потребує показниково великих ресурсів на класичному комп'ютері, але ефективно виконується на квантовому. Це може призвести до прогресу в секвеструванні вуглекислого газу, альтернативних акумуляторах або розробці нових ліків. Серед особливо актуальних алгоритмів у цій галузі: варіаційний власний вирішувач (VQE), що використовується для оцінки певних властивостей матеріалу, таких як рівноважний або мінімально-енергетичний стан; алгоритм симуляції часової динаміки (TDS), що оцінює функції відгуку або спектральні властивості матеріалів; і новачок — вибіркова квантова діагоналізація (SQD), про яку ми дедалі більше чутимемо в майбутньому.

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

3. Квантове машинне навчання. Ця галузь викликала великий ентузіазм останніми роками, але, схоже, QML не стане корисним так скоро, як симуляція. Тим не менш, над деякими вражаючими алгоритмами активно працюють, щоб вирішити дуже важливі завдання. Серед можливих варіантів — обробка природної мови, аналіз мережевого трафіку і навіть виявлення шахрайства у фінансових транзакціях. Відповідні алгоритми в цій галузі: квантова машина опорних векторів (QSVM), квантові нейронні мережі (QNN) і квантові генеративно-змагальні мережі.

У рамках цих широких галузей застосування спільнота бачить цінність у роботі груп, зосереджених на більш конкретній темі. IBM® ініціювала проект «Робочі групи», щоб допомогти співавторам познайомитися одне з одним і створити продуктивну взаємодію у чотирьох конкретних областях: охорона здоров'я та науки про життя, матеріали та HPC, фізика високих енергій, і оптимізація. Нещодавно була створена й п'ята робоча група — зі сталого розвитку.

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

Варіант використання 1: Симуляція динаміки адронів

Спочатку розглянемо статтю групи Мартіна Саваджа з Університету Вашингтону під назвою Квантові симуляції динаміки адронів у моделі Швінгера з використанням 112 кубітів.

Навіть якщо ти не є фізиком-теоретиком, ти, можливо, знайомий з терміном «адрон» — наприклад, з Великого адронного колайдера (LHC), гігантського прискорювача частинок завдовжки 27 км, який дозволив нарешті спостерігати бозон Хіггса. Адрон — це субатомна складена частинка, що складається з дрібніших частинок, які звуться кварками. Серед прикладів адронів — нейтрони та протони.

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

Модель Швінгера — популярна проста модель для симуляції деяких із цих динамік. Вона описує поведінку електронів і позитронів, що взаємодіють через фотони у 1+1D (тобто час і один просторовий вимір). Модель має багато подібностей з квантовою хромодинамікою (КХД), що описує взаємодію кварків і адронів, але КХД надзвичайно важко симулювати. Тому модель Швінгера часто використовується як іграшкова модель для дослідження деяких явищ, спільних для обох.

Щоб зрозуміти, чому вони взялися за цю задачу, поставимо собі низку запитань.

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

По-друге, чому ця тема цікава? Фізика високих енергій загалом викликає великий інтерес. Люди були готові витратити мільярди доларів на будівництво LHC, і тисячі вчених і техніків по всьому світу присвятили цій галузі свої кар'єри. Хоча модель Швінгера спрощена і не охоплює три просторові виміри, вона все ж є корисним спрощенням повної теорії.

Нарешті, як була виконана ця робота, або як ми підійшли б до задачі, якби хотіли продовжити це дослідження? В експериментах типу симуляцій VQE є одним із найпоширеніших підходів, і перший крок майже завжди однаковий: підготувати основний стан. У цьому випадку це вакуумний стан. В експерименті використовувалася нова версія VQE під назвою SC-ADAPT-VQE (масштабовані схеми — адаптивний VQE з псевдо-Троттерівим анзацем, похідно-зібраним) для підготовки як основного стану, так і хвильового пакету адрона у цьому вакуумі. Наступний крок — дозволити адронам еволюціонувати в часі. Нарешті, потрібно визначити спостережувані та виміряти їх.

Якщо ці кроки здаються трохи знайомими — за вирахуванням частини про хвильовий пакет адрона — то тому, що вони дуже схожі на те, що ми розглядали в прикладі з QAOA на попередньому уроці. Ми починаємо зі знайомого стану (тут — вакуумного), потім даємо йому еволюціонувати в часі за допомогою серії експоненційованих гамільтоніанів. Багато варіаційних алгоритмів дотримуються цього загального підходу. Ключова відмінність тут полягає в тому, що ми створюємо хвильовий пакет адронів, розміщений у центрі схеми, перш ніж почати дозволяти йому еволюціонувати.

Як же ми створюємо хвильовий пакет? На вакуумі адрон можна збудити, створивши пари ферміон-антиферміон на сусідніх вузлах. Готуючи суперпозицію таких адронів у різних місцях, можна підготувати довільний хвильовий пакет. Автори розмістили свій хвильовий пакет у центрі схеми, щоб спостерігати еволюцію без досягнення границі.

Але пам'ятай: головне правило при роботі з галасливими QPU — зберегти глибину схеми керованою. Для цього протокол SC-ADAPT-VQE використовує симетрії та ієрархії масштабів довжини для визначення квантових схем малої глибини для підготовки станів. Це створить анзац з меншою кількістю параметрів і, відповідно, меншою глибиною.

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

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

Ми бачимо два різні часові кроки в еволюції хвильового пакету. При $t=1$ хіральний конденсат вузький і локалізований, і він добре збігається з класичною симуляцією. При $t=14$ він значно більш розширений. Відповідність симулятору не настільки ідеальна, але все одно очевидно дуже хороге узгодження між теорією і даними, що надихає.

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

Варіант використання 2: Оптимізація спінового стекла Ізинга

Наш наступний приклад присвячений оптимізації і є глибоким зануренням у статтю Bias-Field Digitized Counterdiabatic Quantum Optimization, виконану членами команди Kipu Quantum та Університету Країни Басків в Іспанії.

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

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

Тепер інший жаргонний вислів із назви: поле зміщення. Інші ітеративні алгоритми, наприклад VQE, беруть класичні параметри у стани і використовують класичні оптимізатори для пошуку в багатовимірному просторі параметрів набору, що дає мінімальне математичне сподівання для фіксованого гамільтоніана. Тут натомість вони змінюють гамільтоніан щоразу, переходячи адіабатично від відомого випадку до цікавого. Щоб змінити гамільтоніан, вони просто безпосередньо застосовують математичне сподівання Паулі-Z однієї ітерації як поле зміщення в гамільтоніані наступної. Таким чином вони спрямовують динаміку до фактичного розв'язку без потреби в класичних оптимізаторах.

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

І чому ми думали, що це спрацює? Запропонований алгоритм прискорює еволюцію для зменшення глибини схеми, одночасно придушуючи неадіабатичні переходи. Крім того, він не покладається на жодні класичні підпрограми оптимізації, які можуть бути джерелом проблем з «безплідними плато» і застряганням у локальних мінімумах. Нарешті, автори також подбали про узгодження взаємодій у гамільтоніані задачі з апаратною зв'язністю реальних QPU, що завжди дуже важливо.

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

Отже, коли проводився експеримент, автори вирішили запустити алгоритм на 127-кубітному IBM Quantum-комп'ютері Brisbane. Нижче наведено рисунок, що показує 8-му ітерацію алгоритму оптимізації для зразка спінового стекла з найближчими сусідами на 100 кубітах. Вони порівнюють ідеалізовані результати класичної симуляції для DCQO і BF-DCQO, а також експериментальний результат на квантовому комп'ютері. Також наведено результат класичного розв'язувача Gurobi як орієнтир. Вже за 10 ітерацій BF-DCQO забезпечує разючі поліпшення порівняно з DCQO. Хоча експериментальний результат трохи відрізняється від ідеального через шум, продуктивність все одно краща за ідеальний DCQO. Це свідчить про те, що у сфері квантової оптимізації продовжується відмінний прогрес і на 100+ кубітах вперше повідомляються хороші результати.

Варіант використання 3: Передбачення вторинної структури мРНК

Нарешті, розглянемо статтю від Moderna Pharmaceuticals під назвою mRNA Secondary Structure Prediction Using Utility-Scale Quantum Computers.

Спочатку коротко нагадаємо про мРНК. Матрична РНК — це тип РНК, що бере участь у синтезі білків. Фактично вона зчитує інструкції від ДНК. Вторинна структура мРНК — це спосіб, яким ланцюг складається, як показано на діаграмі нижче. А задача передбачення вторинної структури РНК полягає в тому, щоб знайти найстабільніше складання послідовності основ або нуклеотидів, з яких складається РНК: аденіну (A), цитозину (C), урацилу (U) та гуаніну (G). Зображення нижче показує деякі загальні структури складання мРНК, кожен колір відповідає різному типу вторинної структури. Що робить одну структуру сприятливішою за іншу — не дуже зрозуміло; все, що ми можемо зробити, — це обчислити, яка структура дає найнижчу вільну енергію порівняно з нескладеним станом. І ось тут з'являються квантові комп'ютери.

Чому вторинні структури мРНК важливі? Їх точне передбачення є вирішальним не лише для розуміння ДНК і наших генів, але й для розробки РНК-терапевтиків, таких як вакцина від COVID-19.

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

Цей експеримент проводився за допомогою так званого варіаційного власного вирішувача з умовним ризиком (CVaR-VQE) — модифікації традиційного алгоритму VQE, що, як очікується, забезпечує кращу збіжність.

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

Висновок

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

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

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