Який стосунок квантові алгоритми мають до S&P 500 індексу

Мене звати Володимир Сергєєв, я Scientific Software Engineer в Zapata Computing, Inc. Ентузіаст квантових обчислень, починав долучатися до ІТ ще в часи OS/2 Warp і FIDO.

У статті описую практичне застосування сімейства квантових алгоритмів QEO у домені фінтех для управління дохідністю і ризиком інвестицій. На лайтовому рівні даю означення квантових вентилів, гамільтоніана системи й генеративних алгоритмів. Буде цікаво прочитати ентузіастам квантових обчислень, криптоінвесторам, студентам Львівського політеху за напрямом «Квантові комп’ютери та квантове програмування» і всім тим, хто керує ризиками у фінансовій сфері.

Портфельна теорія Г. Марковіца

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

Частина моєї роботи пов’язана з алгоритмами сімейства Quantum Enhanced Optimizer (QEO). Ці квантові алгоритми належать до галузі комбінаторної оптимізації. Вони реалізують дві стратегії квантово покращеної оптимізації. Перша схема використовує підхід, схожий до машинного навчання з учителем — на вході використовують дані, отримані оптимізаційним пошуком із використанням довільного квантового чи класичного оптимізатора. Друга стратегія застосовує QEO як незалежного комбінаторного оптимізатора (stand-alone solver, на жаль, не знайшов в українській мові гарного аналога для цього терміна).

Тут є велика спокуса вгрузнути в болоті матаналізу та операціях з матрицями. Але ближче до тіла. Краще приклад. Який стосунок мають квантові алгоритми до інвестування і чи dream androids of electric sheep.

NP-hard клас задач оптимізації

У теорії обчислень NP-hard (non-deterministic polynomial hardness) або NP-складні задачі мають поліноміальну залежність часу пошуку рішення до кількості змінних у задачі:

Як видно з формули, час роботи найкращого алгоритму буде зростати доволі швидко (але повільніше, ніж експотенціально), відповідно до ступеня n. Є гіпотеза, що NP-складні задачі взагалі не мають алгоритмів рішення з поліноміальною швидкістю і їх точне рішення наближатиметься в часі до EXPTIME (Exponential Time) задач.

Задача підбору оптимального інвестиційного портфеля належать до NP-складних, і у класичних алгоритмах повний перебір варіантів займатиме астрономічний час. Для прикладу із портфелем акцій 50 компаній розмір поля пошуку буде 10 в 69 ступені.

10⁶⁹ = 1000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000

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

Генеративні алгоритми і MPS

У 2018 році група британських китайських вчених опублікувала працю Unsupervised Generative Modeling Using Matrix Product States. Ці дослідження стосуються GAN — генеративно-змагальних нейронних мереж (Generative adversarial network). GAN — це один з алгоритмів машинного навчання, навчання без учителя, класичний не квантовий алгоритм.

GAN-алгоритм поєднує генератор, який навчається виробляти цільовий результат, з дискримінатором. В процесі навчання мережі дискримінатор вчиться відрізняти правдиві дані від вихідних даних генератора. Для цього використовується training dataset. Генератор, своєю чергою, намагається «обдурити» дискримінатора, цикл за циклом покращуючи вихідні дані генеровані мережею, а дискримінатор намагається уникнути обману.

Дискримінаторна модель виконує класичну задачу класифікації. Це «cat», а це «dog». Задача генератора у генеративній моделі набагато складніша — створити з меншого більше. Наприклад, із текстових символів C A T отримати зображення. Перевірте себе: ці люди справді не існують і ці котики не муркають.

GAN-мережі здатні генерувати «кандидатні» дані, які не обмежаться генерацією тексту чи картинок. Генератор моделює, створює вихідні дані відповідно до «схеми». Схема може задати 2d чи 3d об’єкт, структуру із набором полів (наприклад, номер вашої картки з пін-кодом), або портфель інвестицій.

Quantum Enhanced Optimizer

У нашій задачі генеративна мережа генерує «кандидати» оптимальних інвестиційних портфелів із компаній в індексі S&P 500. Кандидатне рішення може мати субоптимальний рівень дохідності чи ризику. Для прикладу із портфелем акцій 50 компаній це може бути варіант із дохідністю 80–90% від оптимальної при ризику, наприклад, 5%.

Для алгоритму QEO-Booster вхідними даними GAN є «преоптимізовані» ймовірні рішення, отримані з використанням класичного чи квантового алгоритму — Simulated Annealing, Parallel Tempering, Generic абощо. Для алгоритму з незалежним оптимізатором QEO-Standalone на вхід GAN генерується рандомний набір даних із нормальним розподілом у полі пошуку.

Введемо лайтове визначення трьох ключових термінів:

1. Хвильова функція (Wavefunction) — математичний опис квантового стану.
2. Гамільтоніан (Hamiltonian) — квантовий енергетичний оператор, який описує загальну енергію квантової системи.
3. Квантові вентилі (Quantum gates) — операції, що виконуються над кубітами, маніпуляції квантовими станами. (Просто: аналогом квантових вентилів є базові операції в класичних алгоритмах — І, АБО, НІ тощо). Квантові схеми будуються із вентилів.

На основі вхідних даних будується «пробна хвильова функція» або початковий стан і кодується на квантовому комп’ютері із використанням квантових вентилів. Створюється квантовий стан на квантовому процесорі, який представляє конкретну версію хвильової функції, використовуючи комбінацію заплутаних вентилів, однокубітових вентилів та їх послідовності. Паралельно GAN нейронна мережа навчається цикл за циклом, відбувається семплінг «кандидатних» розміщень інвестицій і/або їх відбраковка за цільовою функцією.

Загальним для різних застосувань є необхідність представлення задачі у вигляді PUBO/QUBO (polynomial unconstrained binary optimization, QUBO — quantum unconstrained binary optimization при застосуванні квантових схем і квантових обчислювальних машин). Це представлення має вигляд оператора енергії системи, гамільтоніана, таким чином представляється функція втрат або цільова функція (Loss function). Цей крок зазвичай є складним. Однак із PUBO/QUBO представленням задача спрощується до пошуку мінімуму/максимуму енергії системи. Як приклад можна навести гібридний класично-квантовий алгоритм VQE, який ефективно працює на платформі IBM Quantum. В цьому алгоритмі класичний комп’ютер керує експериментальними параметрами, що контролюють підготовку квантового стану, потім квантовий комп’ютер реалізує цей стан із кубітами та обчислює його властивості.

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

Публікація на ArXiv є розгорнутим описом серії експериментів та ілюстрацією результатів порівняння QEO із рядом класичних алгоритмів комбінаторної оптимізації — баєсові оптимізатори, УВП (умовні випадкові поля, conditional random fields, CRFs), симуляції відпалу (simulated annealing, SA), гаусівської оптимізації процесів (GPyOpt). Заради жарту зазначу, що в репозиторії публікація має вигляд файлу юніт-тесту на Python :)

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті