Вчені досліджували новий спосіб вирішення проблеми малого числа кубітів квантових обчислювачів для вирішення реальних оптимізаційних завдань. Вони пішли не шляхом збільшення потужності комп'ютерів, а вирішили підлаштовувати формулювання вирішуваних ними завдань у потрібному напрямку. Дослідники показали, як квантовий комп'ютер може впоратися з різними варіаціями завдання маршрутизації транспорту. Роботу опубліковано в журналі.
Одними з найскладніших з точки зору класичних обчислювачів і найбільш перспективними з точки зору квантових можна назвати завдання, що належать класу квадратичної необмеженої бінарної оптимізації (QUBO, quadratic unbounded binary optimization). Але найважливіше те, що ці оптимізаційні завдання зустрічаються в реальному житті - від економіки і фінансів до машинного навчання. Тому їх дослідження і розвиток можливостей квантових обчислень для рішення може принести видиму користь.
Змінні в таких завданнях можуть приймати значення 0 або 1 (бінарні), а мета завдання - оптимізація якоїсь заданої функції. Зазвичай, потрібно щось мінімізувати (наприклад, час, витрати, відстань) або максимізувати (прибуток, заповнення рюкзака) і при цьому дотримуватися необхідних умов. Один з найстаріших прикладів оптимізаційного завдання - завдання комівояжера. Комівояжер виїжджає зі свого міста, прямує у справах до різних міст і хоче знати оптимальний маршрут для того, щоб потрапити до кожного міста і повернутися найвигідніше. Критеріями вигідності можуть бути час, відстань, вартість поїздки або все разом.
Якщо перевести завдання на математичну мову, то вийде граф, вершини якого - міста, ребра - дороги між ними, а їх ваги можуть бути відстанню між містами, вартістю квитка або прибутком, який можна отримати в місті. Чим більше міст, тим більше варіантів шляхів є у комівояжера. Для 4 міст крім міста старту число варіантів обходу складе 4! = 24, а для 10 вже 10! = 3628800. Але це ще не найстрашніше, тому що через наявність умов на подорож комівояжера, ймовірність того, що знайдеться хоч якесь рішення, виявляється дуже маленькою. Для вирішення завдання потрібно не просто якесь, але оптимальне рішення, тому перебір варіантів на класичному комп'ютері виявляється довгим і неефективним.
Цікавим залишається питання про те, як в це все вписати квантові комп'ютери. Справа в тому, що навіть для вирішення оптимізаційного завдання в класичному світі потрібно сформулювати його математично - перевести всі умови у формули і сформулювати цільову функцію, яку необхідно мінімізувати (або максимізувати). Квантові обчислювачі вміють працювати з гамільтоніанами, тому перед їх запуском потрібно перевести умову завдання з класичної мови на квантову.
Розширеним і прикладним варіантом завдання комівояжера можна вважати завдання маршрутизації транспорту. Саме для неї дослідники з ExxonMobil і IBM Quantum під керівництвом Донні Грінбера (Donny Greenberg) сформулювали різні варіанти постановки завдання, перевели їх на квантову мову і показали, як квантовий обчислювач зможе їх вирішити.
Для початку потрібно розібратися, чим відрізняються різні підвиди завдання маршрутизації і для чого вони потрібні. Автори розглядають загальне завдання як граф з N вершинами, залежно від завдання є вершина d (депо) - вона може бути початковою і кінцевою точкою маршруту, якщо фізично, це, наприклад, склад. Кожна вершина позначає місце доставки або навантаження, вага i-тієї вершини qi може бути більше нуля (навантаження) або менше (доставка). Додатково для кожної вершини визначено проміжок часу [ai, bi], в який має бути здійснено навантаження/вивантаження. У граней-доріг теж є свої параметри - це витрати на її подолання cij, які зазвичай відповідають довжині ребра, і час tij на її подолання. Крім усіх описаних параметрів, є умови, що забезпечують приїзд транспорту вчасно (він може приїхати раніше потрібного часу, але не запізнитися), обслуговування кожного вузла одним автомобілем (не можна розбивати замовлення на частини і доставляти окремо), а весь транспорт передбачається однаковим у плані вантажопідйомності Q. Крім виконання всіх умов для вирішення завдання необхідно мінімізувати сумарну вартість всього процесу. Тому серед безлічі варіантів маршруту вибрати оптимальний виявляється нелегко.
Для кожного конкретного випадку можуть виявлятися важливими різні умови або з'являтися додаткові. Від цього залежить математична формула завдання. Наприклад, для морського транспорту час переміщень між вузлами виявляється набагато більше часу перебування в них, існує кілька депо і при навантаженні, наприклад, природного газу потрібно повністю завантажити судно і після проходження одного ребра повністю його розвантажити. Крім специфічних завдань, можуть відрізнятися підходи у формулюванні спільного завдання: можна відштовхуватися від набору різних маршрутів і вибирати тільки відповідні, фіксувати дискретним набором час на кожен автомобіль або число його зупинок.
Виявилося, що різні формулювання не тільки зміщують фокус завдання, але і змінюють складність її вирішення при збільшенні часу. Про це сигналізує різний характер збільшення кількості змінних.
Для чисельного моделювання вчені використовували квантовий обчислювач IBM Quantum, на якому реалізовували варіаційні гібридні квантові алгоритми. Сенс таких алгоритмів полягає в тому, що завдання ділиться між квантовою і класичною частиною (тому гібридні) і квантова відповідає за приготування потрібного стану, який буде відповіддю в завданні, а класична допомагає побудувати цей стан. Тобто в квантовому обчислювачі є варіювані параметри (звідси назва алгоритмів - варіаційні), значення яких вибирає класичний оптимізатор. Автори розглядали два типи квантових алгоритмів і два типи класичних оптимізаторів, для того, щоб знайти найефективнішу комбінацію. Їм вдалося це зробити для 16 кубітів, що дозволило перевірити аналітично точність знайдених рішень.
Дослідники говорять про те, що через обмежену кількість кубітів у найближчому майбутньому необхідно шукати формулювання завдання, які дозволять «ущільнювати» число змінних і підлаштовувати їх під нинішні можливості квантових обчислювачів. Вони показали, як параметри завдання впливають на їх складність і продемонстрували, що сучасний квантовий обчислювач може впоратися з різними типами завдань. Найкомпактнішим виявилося формулювання, яке базується на виборі певного маршруту (route-based).
Якщо говорити про експериментальні реалізації квантових обчислювачів, то вони вже охопили різні платформи - надпровідникові для завдання генерації випадкової послідовності, оптичні для завдання бозонного семплінгу і перевірки вирішення завдання з класу NP-повних.