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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Медоуказчики привели людей к змеям по ошибке Медоуказчики привели людей к змеям по ошибке

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

N+1
«Мы разведемся»: Кирилл Кяро чуть не потерял жену из-за карантина «Мы разведемся»: Кирилл Кяро чуть не потерял жену из-за карантина

Кирилл Кяро признался, что самоизоляция едва не разрушила его отношения

Cosmopolitan
Столкновение умов: как не проиграть конкуренцию в борьбе за лидерство в области ИИ Столкновение умов: как не проиграть конкуренцию в борьбе за лидерство в области ИИ

Как на самом деле развивается ИИ в России?

Forbes
Почему в корпорации исчезает атмосфера стартапа: опыт главы Waze, который боролся за свободу внутри Google и сдался Почему в корпорации исчезает атмосфера стартапа: опыт главы Waze, который боролся за свободу внутри Google и сдался

Ноам Бардин — что произошло с его независимым стартапом после продажи ИТ-гиганту

VC.RU
Утерянный 5000 лет назад: ученые воскресили древнейший в мире синтетический краситель. Зачем он нужен? Утерянный 5000 лет назад: ученые воскресили древнейший в мире синтетический краситель. Зачем он нужен?

Откуда взялся яркий, насыщенный синий цвет в Древнем Египте

Inc.
Конец операции «Гриф»: как немцы в американскую униформу переодевались и что из этого вышло Конец операции «Гриф»: как немцы в американскую униформу переодевались и что из этого вышло

Как немцы пытались проникнуть в тыл врага и устроить хаос на плечах врага

Maxim
Пикап по-самурайски. Как знакомиться с девушками в японских ресторанах Пикап по-самурайски. Как знакомиться с девушками в японских ресторанах

Почему нужно знакомиться с девушкой в японском ресторане?

Maxim
Тысячи болезненных укусов: как ведут себя интернет-тролли и что чувствуют их жертвы Тысячи болезненных укусов: как ведут себя интернет-тролли и что чувствуют их жертвы

Отрывок из книги «Я так не хотела» адвоката Кэрри Голдберг об интернет-троллях

Forbes
Застойный период Застойный период

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

Лиза
По кусочку По кусочку

Есть ли какое-то объяснение привычки кусочничества?

Худеем правильно
Звезда «Топей» и будущий «Майор Гром»: интервью с Тихоном Жизневским Звезда «Топей» и будущий «Майор Гром»: интервью с Тихоном Жизневским

Тихон Жизневский — о том, почему важно вовремя уйти и вовремя вернуться

Cosmopolitan
Обмани меня Обмани меня

Амурные аферисты: самые распространенные способы брачного мошенничества

Лиза
Honda уходит из России. Прощаемся в компании с обновленной CR-V Honda уходит из России. Прощаемся в компании с обновленной CR-V

Прощаемся с маркой Honda в ходе знакомства с рестайлинговым кроссовером CR-V

РБК
«Вам просили передать: маловато безумия» «Вам просили передать: маловато безумия»

Рената Литвинова о своем «Северном ветре» и полном матриархате

Weekend
Физики измерили асимметрию антикварков внутри протона Физики измерили асимметрию антикварков внутри протона

Асимметрия в распределении верхних и нижних антикварков внутри протона

N+1
Почему Пентагон недоволен самолетом F-35 Почему Пентагон недоволен самолетом F-35

Истребители-бомбардировщики F-35 оказались почти непригодны к эксплуатации

Популярная механика
Государственный крой Государственный крой

Как идеи перестройки и вкусы одной женщины повлияли на стиль президента СССР

GQ
Футбольный провидец: как Лионель Месси разгадал парадокс времени Футбольный провидец: как Лионель Месси разгадал парадокс времени

Глава из книги Мэтью Сайеда «От лучшего к величайшему», посвященная Месси

Forbes
Что делать, если на машину упал снег с крыши. Инструкция Что делать, если на машину упал снег с крыши. Инструкция

Куда обращаться и что делать, если автомобиль раздавило снежным комом

РБК
На канарском острове Ла-Пальма нашли признаки активизации вулканизма На канарском острове Ла-Пальма нашли признаки активизации вулканизма

Слабые вертикальные смещения поверхности сообщают о движении магмы на глубине

N+1
«В чем сила, брат?» 7 фильмов Алексея Балабанова, которые нужно пересмотреть «В чем сила, брат?» 7 фильмов Алексея Балабанова, которые нужно пересмотреть

Алексей Балабанов - самый противоречивый российский режиссер

Cosmopolitan
Клатч у груди и вибратор в сумочке: что скрывала леди Диана — 6 тайн принцессы Клатч у груди и вибратор в сумочке: что скрывала леди Диана — 6 тайн принцессы

Вспоминаем самые странные привычки принцессы Дианы и раскрываем их тайный смысл

Cosmopolitan
Поймай, если сможешь: как списывающие студенты помогают заработать компании стоимостью $13 млрд Поймай, если сможешь: как списывающие студенты помогают заработать компании стоимостью $13 млрд

Кто стоит за компанией, акции которой за год подорожали почти на 300%?

Forbes
Иностранцы о русских. Часть 2: Отношения русского народа и власти Иностранцы о русских. Часть 2: Отношения русского народа и власти

Высказывания иностранцев об отношениях русского народа и власти

Maxim
Покемоны, Марио и Pac-Man: 13 самых продаваемых игр в истории Покемоны, Марио и Pac-Man: 13 самых продаваемых игр в истории

Самые продаваемые видеоигры

CHIP
«До конца времен: Сознание, материя и поиск смысла в меняющейся Вселенной» «До конца времен: Сознание, материя и поиск смысла в меняющейся Вселенной»

Вселенная обречена: звезды погаснут, исчезнут галактики

N+1
Не только букеты в вазе: почему флористический декор стал интерьерным трендом и как украсить свой дом цветами Не только букеты в вазе: почему флористический декор стал интерьерным трендом и как украсить свой дом цветами

Как можно использовать цветы в украшении интерьера

Esquire
В США снесли одно из первых казино Трампа: каким было обанкротившееся предприятие экс-президента. Фоторепортаж В США снесли одно из первых казино Трампа: каким было обанкротившееся предприятие экс-президента. Фоторепортаж

История одного из первых казино Дональда Трампа — в фоторепортаже

Forbes
Проще простого: 8 лайфхаков для уборки Проще простого: 8 лайфхаков для уборки

Полезные советы для тех, кто хочет тратить время на бесконечную работу по дому

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

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

Cosmopolitan
Открыть в приложении