Задачи маршрутизации адаптировали к квантовым вычислениям

Ученые исследовали новый способ решения проблемы малого числа кубитов квантовых вычислителей для решения реальных оптимизационных задач. Они пошли не по пути увеличения мощности компьютеров, а решили подстраивать формулировки решаемых ими задачи в нужном направлении. Исследователи показали, как квантовый компьютер может справиться с разными вариациями задачи маршрутизации транспорта. Работа опубликована в журнале IEEE Transactions on Quantum Engineering.

Одними из самых сложных с точки зрения классических вычислителей и наиболее перспективными с точки зрения квантовых можно назвать задачи, принадлежащие классу квадратичной неограниченной бинарной оптимизации (QUBO, quadratic unbounded binary optimization). Но важнее всего то, что эти оптимизационные задачи встречаются в реальной жизни — от экономики и финансов до машинного обучения. Поэтому их исследование и развитие возможностей квантовых вычислений для решения может принести видимую пользу.

Переменные в таких задачах могут принимать значения 0 или 1 (бинарные), а цель задачи — оптимизация какой-нибудь заданной функции. Обычно, нужно что-то минимизировать (например, время, расходы, расстояние) или максимизировать (прибыль, заполнение рюкзака) и при этом соблюдать необходимые условия. Один из старейших примеров оптимизационной задачи — задача коммивояжера. Коммивояжер выезжает из своего города, направляется по делам в разные города и хочет знать оптимальный маршрут для того, чтобы попасть в каждый город и вернуться обратно выгоднее всего. Критериями выгодности могут быть время, расстояние, стоимость поездки или все вместе.

Если перевести задачу на математический язык, то получится граф, вершины которого — города, ребра — дороги между ними, а их веса могут быть расстоянием между городами, стоимостью билета или прибылью, которую можно получить в городе. Чем больше городов, тем больше вариантов путей есть у коммивояжера. Для 4 городов помимо города старта число вариантов обхода составит 4! = 24, а для 10 уже 10! = 3628800. Но это еще не самое страшное, потому что из-за наличия условий на путешествие коммивояжера, вероятность того, что найдется хоть какое-то решение, оказывается очень маленькой. Для решения задачи нужно не просто какое-то, но оптимальное решение, поэтому перебор вариантов на классическом компьютере оказывается долгим и неэффективным.

Интересным остается вопрос о том, как в это все вписать квантовые компьютеры. Дело в том, что даже для решения оптимизационной задачи в классическом мире нужно сформулировать ее математически — перевести все условия в формулы и сформулировать целевую функцию, которую необходимо минимизировать (или максимизировать). Квантовые вычислители умеют работать с гамильтонианами, поэтому перед их запуском нужно перевести условие задачи с классического языка на квантовый.

Расширенным и прикладным вариантом задачи коммивояжера можно считать задачу маршрутизации транспорта. Именно для нее исследователи из ExxonMobil и IBM Quantum под руководством Донни Гринбера (Donny Greenberg) сформулировали разные варианты постановки задачи, перевели их на квантовый язык и показали, как квантовый вычислитель сможет их решить.

Для начала нужно разобраться, чем отличаются разные подвиды задачи маршрутизации и для чего они нужны. Авторы рассматривают общую задачу как граф с N вершинами, в зависимости от задачи есть вершина d (депо) — она может быть начальной и конечной точкой маршрута, если физически, это, например, склад. Каждая вершина обозначает место доставки или погрузки, вес i-той вершины q_i может быть больше нуля (погрузка) или меньше (доставка). Дополнительно для каждой вершины определен промежуток времени [a_i, b_i], в который должна быть совершена погрузка/выгрузка. У граней-дорог тоже еcть свои параметры — это затраты на ее преодоление c_ij, которые обычно соответствуют длине ребра, и время t_ij на ее преодоление. Кроме всех описанных параметров, есть условия, обеспечивающие приезд транспорта вовремя (он может приехать раньше нужного времени, но не опоздать), обслуживание каждого узла одним автомобилем (нельзя разбивать заказ на части и доставлять отдельно), а весь транспорт предполагается одинаковым в плане грузоподъемности Q. Помимо выполнения всех условий для решения задачи необходимо минимизировать суммарную стоимость всего процесса. Поэтому среди множества вариантов маршрута выбрать оптимальный оказывается нелегко.

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

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

Для численного моделирования ученые использовали квантовый вычислитель IBM Quantum, на котором реализовывали вариационные гибридные квантовые алгоритмы. Смысл таких алгоритмов заключается в том, что задача делится между квантовой и классической частью (поэтому гибридные) и квантовая отвечает за приготовление нужного состояния, которое будет ответом в задаче, а классическая помогает построить это состояние. То есть в квантовом вычислителе есть варьируемые параметры (отсюда название алгоритмов — вариационные), значения которых выбирает классический оптимизатор. Авторы рассматривали два типа квантовых алгоритмов и два типа классических оптимизаторов, для того, чтобы найти самую эффективную комбинацию. Им удалось это сделать для 16 кубитов, что позволило проверить аналитически точность найденных решений.

Исследователи говорят о том, что из-за ограниченного числа кубитов в ближайшем будущем необходимо искать формулировки задачи, которые позволят «уплотнять» число переменных и подстраивать их под нынешние возможности квантовых вычислителей. Они показали, как параметры задачи влияют на их сложность и продемонстрировали, что современный квантовый вычислитель может справиться с разными типами задач. Самой компактной оказалась формулировка, которая базируется на выборе определенного маршрута (route-based).

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

Оксана Борзенкова