Правильная формулировка задачи может уменьшить число кубитов

N+1Hi-Tech

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

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

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

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

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

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

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

В старой коллекции находок из Костёнок нашли три кроманьонских зуба В старой коллекции находок из Костёнок нашли три кроманьонских зуба

Ученые обнаружили три кроманьонских человеческих зуба в Костёнки-1

N+1
В Египте нашли самую древнюю промышленную пивоварню В Египте нашли самую древнюю промышленную пивоварню

Предприятие возрастом около 5100 лет могло производить более 22000 литров пива

N+1
Корректировать размер скидки и определить брак: в чем ИИ поможет даже малому бизнесу Корректировать размер скидки и определить брак: в чем ИИ поможет даже малому бизнесу

Что именно искусственный интеллект делает для бизнеса уже сегодня?

Inc.
Хватит мной управлять! Хватит мной управлять!

Как развить эмоциональный интеллект?

Лиза
От Аттилия до Спартака: 5 знаменитых гладиаторов Древнего Рима От Аттилия до Спартака: 5 знаменитых гладиаторов Древнего Рима

История первых гладиаторских боев корнями уходит еще в III век до нашей эры...

ТехИнсайдер
Застойный период Застойный период

Как распознать причину частых отеков

Лиза
Принцип 80/20 Принцип 80/20

Как достичь большего с наименьшими усилиями

kiozk originals
Мощные ледниковые щиты за последние 150 тысяч лет дважды опреснили Северный Ледовитый океан Мощные ледниковые щиты за последние 150 тысяч лет дважды опреснили Северный Ледовитый океан

Арктика превращается в изолированный пресноводный резервуар

N+1
Кто такая и как прославилась Инстасамка: биография скандальной блогерши Кто такая и как прославилась Инстасамка: биография скандальной блогерши

Через что прошла Дарья Зотеева на пути к славе?

Cosmopolitan
Только белый: как научиться носить самый нежный цвет и приручить total white Только белый: как научиться носить самый нежный цвет и приручить total white

Несколько практических советов по адаптации моды на белый цвет к реальной жизни

Cosmopolitan
«Есть основания заблокировать любую соцсеть»: как власти России и Индии ограничивают работу крупнейших площадок «Есть основания заблокировать любую соцсеть»: как власти России и Индии ограничивают работу крупнейших площадок

Социальные сети сталкиваются с давлением властей разных стран на фоне протестов

Forbes
Австралийцы убили 350000 крыс и мышей на острове Лорд-Хау. Это пошло на пользу редким видам Австралийцы убили 350000 крыс и мышей на острове Лорд-Хау. Это пошло на пользу редким видам

Проект по истреблению крыс на острове Лорд-Хау дал плоды

N+1
Предельный Туле Предельный Туле

Край мира: где его искать

Вокруг света
Святой Валентин, что ты делаешь, прекрати! Святой Валентин, что ты делаешь, прекрати!

Самые запутанные любовные истории звезд, от которых голова идет кругом

Лиза
Истина где-то рядом: загадочная смерть Элизы Лэм Истина где-то рядом: загадочная смерть Элизы Лэм

История гибели канадской студентки Элизы Лэм четыре года назад потрясла США

Cosmopolitan
Полет ненормальный: как в фильме «Воздушный бой» соединяются хоррор, феминизм и война Полет ненормальный: как в фильме «Воздушный бой» соединяются хоррор, феминизм и война

Как фильм «Воздушный бой» с Хлоей Грейс Морец совмещает несовместимое

Forbes
Новый Дикий Запад: как пользователи Clubhouse научились зарабатывать в соцсети Новый Дикий Запад: как пользователи Clubhouse научились зарабатывать в соцсети

Как в Clubhouse зарождается рекламный рынок и сколько зарабатывают прямо сейчас

Forbes
Изобрести велосипед на последней миле: как стартап из Краснодара вырос в 21 раз за счет ИИ и «ВкусВилла» Изобрести велосипед на последней миле: как стартап из Краснодара вырос в 21 раз за счет ИИ и «ВкусВилла»

Как стартап «Чекбокс» способен составить конкуренцию лидерам индустрии доставки

Forbes
Как помогают животным Райан Гослинг, Шарлиз Терон и другие звезды Как помогают животным Райан Гослинг, Шарлиз Терон и другие звезды

Эти актеры известны не только своим талантом, но и большой любовью к животным

РБК
Ботан стал мачо: как изменились звезды сериала Ботан стал мачо: как изменились звезды сериала

Как сейчас выглядят звезды «Простых истин» и чем они занимаются

Cosmopolitan
Что посмотреть и попробовать в Туве. Гид «РБК Стиль» Что посмотреть и попробовать в Туве. Гид «РБК Стиль»

Гид по самой загадочной республике России, где есть ларьки и нет супермаркетов

РБК
Не только баскетбол и кроссовки: посмотрите, как Майкл Джордан играл в гольф и превосходно одевался для этого Не только баскетбол и кроссовки: посмотрите, как Майкл Джордан играл в гольф и превосходно одевался для этого

Как хобби может идти рука об руку с безупречным стилем

Esquire
Тут Русью пахнет Тут Русью пахнет

Отечественные дизайнеры все чаще находят источник вдохновения на родной почве

Vogue
Грандиозный пожар в гостинице «Россия» 25 февраля 1977 года Грандиозный пожар в гостинице «Россия» 25 февраля 1977 года

Символ советского туризма обернулся сотней пострадавших и погибших

Maxim
Галадриэль или королева Елизавета I: 10 лучших ролей Кейт Бланшетт Галадриэль или королева Елизавета I: 10 лучших ролей Кейт Бланшетт

Список обязательных к просмотру фильмов с участием Кейт Бланшетт

Cosmopolitan
Великий матриархат: как Рената Литвинова сняла фэнтези о феминизме и России Великий матриархат: как Рената Литвинова сняла фэнтези о феминизме и России

Рената Литвинова сняла фильм, который совмещает фэнтези и феминистский подтекст

Forbes
Как кино очищало общество от того, с чем не справилось государство Как кино очищало общество от того, с чем не справилось государство

Краткая история самосуда в кино

Weekend
Меч: тест Toyota Land Cruiser 200 Excalibur Меч: тест Toyota Land Cruiser 200 Excalibur

В своём классе Toyota Land Cruiser 200 по-прежнему сохраняет уверенное лидерство

Популярная механика
Синдром отличника Синдром отличника

Актер «Гоголь-центра» Михаил Тройник — о выборе, искусстве и точных науках

OK!
Алло, гараж! Алло, гараж!

Смартфон и кнопочный телефон: как выбрать мобильник для своей мамы или бабушки?

Лиза
Открыть в приложении