Квантовый отжиг испытали на модели трафика в Алматы

Физики из Университета Иннополис представили алгоритм квантового отжига для управления городским трафиком. Им удалось заметно ускорить обработку данных и проверить систему на реальной задаче с сотнями автомобилей. Все вычисления выполнял квантовый процессор Advantage 1 в полностью автоматическом режиме. Результаты опубликованы в журнале Scientific Reports.

Шумные квантовые вычислители, которые уже сейчас используют в исследованиях, особенно эффективны для задач оптимизации. Они встречаются в самых разных сферах, включая борьбу с пробками. При этом управление транспортными потоками — это задача из разряда NP-трудных: число возможных решений растет настолько быстро с увеличением количества машин и дорожных участков, что найти оптимальный вариант в реальном времени крайне трудно.

В 2017 году Volkswagen и D-Wave показали, что трафик можно оптимизировать с помощью квантового отжига (Quantum Annealing). Они рассчитали маршруты для 418 автомобилей, используя 1254 кубита на квантовом процессоре D-Wave. Систему проверили в реальных условиях: во время конференции Web Summit в Лиссабоне она оптимизировала маршруты девяти курсирующих автобусов. Из-за ограничений оборудования пришлось использовать гибридный подход — часть вычислений выполнял классический компьютер. Это замедляло процесс и не позволило бы сделать его автоматическим для большого числа транспортных средств.

Команде ученых из Университета Иннополис под руководством Хади Саллума (Hadi Salloum) удалось решить задачу управления трафиком на карте реальной дорожной сети участка Алматы. В отличие от упрощенных моделей, карта имела сложную структуру, близкую к реальным городским условиям. Процесс удалось запустить уже без гибридных алгоритмов — только с помощью квантового отжига. Команда не тестировала свою систему на реальных дорогах, но разработала новый метод Mini-scale Traffic Flow Optimization (MTF): он разбивает большую задачу на несколько небольших, каждая из которых помещается в квантовый процессор целиком.

Чтобы подготовить задачу для квантового процессора, физики использовали QUBO-модель. В ней нужно минимизировать квадратичную функцию из нулей и единиц. Каждая переменная функции показывает, движется ли автомобиль по определенному участку дороги. Коэффициенты учитывают износ дороги, пропускную способность и последствия перегрузки сегмента. Алгоритм отслеживает сегменты с чрезмерным количеством машин и локально оптимизирует поток, в том числе на соседних участках, чтобы пробка не смещалась, а исчезала.

Эффективность метода проверили на реальной карте Алматы с 100, 200, 300, 400 и 500 автомобилями, у каждого из которых были разные начальные и конечные точки. Такой подход позволяет оценить как алгоритм масштабируется, то есть ведет себя при увеличении числа переменных.

В задаче авторам удалось снизить среднюю загруженность дорог на 25 процентов при 100 автомобилях и на 62 процента при 500. При этом алгоритм оказался в десятки раз быстрее прежнего подхода: если раньше расчет занимал около трех секунд, то MTF находил решение за 0,15–0,225 секунды даже при 500 автомобилях, а внутренние итерации выполнялись за миллисекунды.

Вычислителями D-Wave пользуется не только Volkswagen: с 2017 года компания продает 2000-кубитный D-Wave 2000Q всем желающим (первым его получила компания, специализирующаяся на кибербезопасности). В 2020 году D-Wave выпустила вычислитель Advantage на пяти тысячах кубитов. Сейчас доступна обновленная версия Advantage2 с более чем пятью тысячами кубитов и улучшенной связностью.