Від логістики Uber до ліків проти Альцгеймера: вчені створили метод для пошуку ідеальних рішень

Не варто недооцінювати силу простих відповідей «так» чи «ні».

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

Джерело: techxplore.com

Уявіть ситуацію: розпал Чемпіонату світу з футболу. Сотні уболівальників одночасно викликають таксі через додаток, щоб встигнути на матч. У той самий час інші їдуть в аеропорт, спортзал чи супермаркет. Містом пересуваються близько 10 000 водіїв, і лише половина з них вільні. Додайте сюди затори й пасажирів, які запізнюються або взагалі скасовують замовлення. Як розподілити виклики так, щоб водії заробили більше, а пасажири дісталися місця без переплат?

Це класичний приклад проблеми під назвою QUBO (квадратична безперешкодна бінарна оптимізація). Це математичне рівняння, мета якого — знайти найкращу комбінацію відповідей «так/ні», щоб мінімізувати витрати грошей чи енергії.

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

Де це застосовують

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

Цей метод діє як на макрорівні (трафік), так і на мікрорівні. Наприклад, для вивчення форми білків: кожен вигин амінокислотного ланцюга розглядається як вибір «так/ні». Це допомагає прогнозувати 3D-структуру білків. Оскільки багатьом хворобам (наприклад, Альцгеймера) передує саме деформація білків, розуміння їхньої правильної форми наближає вчених до лікування.

У чому була проблема

За словами екперта з квантової фізики Алехандро Монтанеса, кількість можливих комбінацій у ситуаціях із 10 і більше виборами зростає настільки стрімко, що на їхній розрахунок традиційним шляхом пішли б роки.

Для розв'язання таких задач використовують так звані Ізінгові машини (Ising machines). Вони перекладають мову задач QUBO на мову фізики — а саме на те, як поводяться електрони в металі (наприклад, у залізі). Властивості електронів («спін») діють як вимикачі «увімкнено/вимкнено».

Але тут фізики зіштовхнулися з пасткою «локального мінімуму».

Аналогія з туристом:

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

В алгоритмах це означає, що комп'ютер знаходить непогане рішення, але далеко не найкраще.

Рішення: метод Floquet

Щоб вирішити цю проблему, професор Касселла та його команда розробили аналоговий розв'язувач Analog Floquet Solver.

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

Це дає віртуальному туристові необхідний «імпульс». Завдяки зовнішній енергії система не «застрягає» в першій дрібній улоговині, а перестрибує її й продовжує рух далі — аж поки не знайде справжнісіньке дно найглибшої долини (ідеальне рішення).

Результати випробувань:

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