D-Wave и Volkswagen представили алгоритм квантового отжига для управления городским трафиком. Им удалось заметно ускорить обработку данных и проверить систему на реальной задаче с сотнями автомобилей. Все вычисления выполнял квантовый процессор Advantage2 в полностью автоматическом режиме. Результаты опубликованы в журнале Nature.
Шумные квантовые вычислители, которые уже сейчас используют в исследованиях, особенно эффективны для задач оптимизации. Они встречаются в самых разных сферах, включая борьбу с пробками. При этом управление транспортными потоками — это задача из разряда NP-трудных: число возможных решений растет настолько быстро с увеличением количества машин и дорожных участков, что найти оптимальный вариант в реальном времени крайне трудно.
В 2017 году Volkswagen и D-Wave показали, что трафик можно оптимизировать с помощью квантового отжига (Quantum Annealing). Они рассчитали маршруты для 418 автомобилей, используя 1254 кубита на квантовом процессоре D-Wave. Систему проверили в реальных условиях: во время конференции Web Summit в Лиссабоне она оптимизировала маршруты девяти курсирующих автобусов. Из-за ограничений оборудования пришлось использовать гибридный подход — часть вычислений выполнял классический компьютер. Это замедляло процесс и не позволило бы сделать его автоматическим для большого числа транспортных средств.
В работе команды ученых под руководством Ярослава Холодова (Yaroslav Kholodov) удалось решить задачу управления трафиком на карте реальной дорожной сети участка Алматы. В отличие от упрощенных моделей, карта имела сложную структуру, близкую к реальным городским условиям. Процесс удалось запустить уже без гибридных алгоритмов — только с помощью квантового отжига. Команда не тестировала свою систему на реальных дорогах, но разработала новый метод 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 с более чем пятью тысячами кубитов и улучшенной связностью.