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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Квантование электрического заряда измерили линейкой Квантование электрического заряда измерили линейкой

Физики заставили каплю масла левитировать в оптической ловушке малой жесткости

N+1
10 самых ядовитых растений 10 самых ядовитых растений

Большинство растений кажутся безобидными, но их не стоит недооценивать

Популярная механика
Клетки Фарадея: как бизнес использует технологию защиты от электромагнитных излучений Клетки Фарадея: как бизнес использует технологию защиты от электромагнитных излучений

Самые распространенные виды применения клетки Фарадея

Популярная механика
«Иуда и черный мессия» – кривоватый, затянутый и поверхностный фильм «Иуда и черный мессия» – кривоватый, затянутый и поверхностный фильм

«Иуда и черный мессия» — фильм о людях, которым больше всех было надо

GQ
6 вредных привычек, от которых нужно избавиться, чтобы стать успешным 6 вредных привычек, от которых нужно избавиться, чтобы стать успешным

Привычки, которые вреднее курения

Playboy
Как поступить в сложной ситуации? Подскажут метафорические карты Как поступить в сложной ситуации? Подскажут метафорические карты

Метафорические карты помогут определить свою позицию накануне важного события

Psychologies
Мария Власова и ее рукописный альбом Мария Власова и ее рукописный альбом

Домашний альбом Марии Власовой, сестры Зинаиды Волконской

Наука
Эти чувства — вода Эти чувства — вода

Сергей Лазарев провел новогодние каникулы с друзьями на Бали

OK!
4 самых распространенных пикантных сна и их значение 4 самых распространенных пикантных сна и их значение

Нормально ли видеть эротические сны?

Playboy
Паруса в виде колонн: эффект Магнуса Паруса в виде колонн: эффект Магнуса

Странные мачты-паруса на яхте

Популярная механика
Считал Airbnb достойным соперником и ставил на лояльность: как Арне Соренсон сделал Marriott крупнейшей сетью отелей Считал Airbnb достойным соперником и ставил на лояльность: как Арне Соренсон сделал Marriott крупнейшей сетью отелей

Как Арне Соренсон превратил Marriott в самую крупную сеть гостиниц в мире

VC.RU
Как стать актером: ключевые этапы на пути к великой карьере, славе и деньгам Как стать актером: ключевые этапы на пути к великой карьере, славе и деньгам

От большого желания к конкретным действиям

Playboy
Новые Sonata, Haval, Granta, Sentra: на что жалуются владельцы на форумах Новые Sonata, Haval, Granta, Sentra: на что жалуются владельцы на форумах

Проблемы на свежих моделях авторынка и как их решают производители

РБК
Испанские страсти Испанские страсти

Певица Розалия готовит новый альбом, а в перерыве — выбирает наряды и пластинки

Vogue
Борщевик Сосновского: растение-терминатор или культура будущего Борщевик Сосновского: растение-терминатор или культура будущего

Борщевик — сорняк, с которым невозможно справиться

Наука
Не как у всех: зачем нужна персонализация для женского здоровья? Не как у всех: зачем нужна персонализация для женского здоровья?

Персонализированный подход в медицине — новый способ заботиться о здоровье

Cosmopolitan
Самые безумные и странные традиции средних веков Самые безумные и странные традиции средних веков

Средневековые традиции, которые выходили за все рамки адекватности

Популярная механика
История одной песни: Элтон Джон, «Candle in the Wind» История одной песни: Элтон Джон, «Candle in the Wind»

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

Maxim
Хомяки против кукловодов Хомяки против кукловодов

Инвесторы думали, что устроили революцию, но помогли заработать своим врагам

Эксперт
Чувствует ли улитка боль: почему наше восприятие других живых существ так ограничено Чувствует ли улитка боль: почему наше восприятие других живых существ так ограничено

Глава из книги Николая Кукушкина «Хлопок одной ладонью» о мышлении и мозге

Forbes
Размер ноги, длина пальцев и женская простата. Мифы и поверья вокруг секса Размер ноги, длина пальцев и женская простата. Мифы и поверья вокруг секса

Разбираемся в стереотипах вокруг секса

СНОБ
Миллиардер Рубен Варданян инвестировал в сервис знакомств на основе ИИ iris Dating Миллиардер Рубен Варданян инвестировал в сервис знакомств на основе ИИ iris Dating

Бизнесмен Рубен Варданян стал акционером сервиса для знакомств iris Dating

Forbes
15 массовых заблуждений, с которыми пора наконец покончить раз и навсегда 15 массовых заблуждений, с которыми пора наконец покончить раз и навсегда

Мы устали краснеть за тебя, краснеющего из-за своих дремучих заблуждений

Maxim
7 очень странных исторических фактов о сексе 7 очень странных исторических фактов о сексе

Блесни эрудицией во время секса!

Maxim
Ареал дальневосточного леопарда расширился в три раза Ареал дальневосточного леопарда расширился в три раза

Дальневосточные леопарды – самые редкие на планете крупные кошки

National Geographic
Как Томас Харрис позаимствовал у ФБР формулу «мыслить как преступник», а ФБР помогло Джонатану Демми снять «Молчание ягнят» Как Томас Харрис позаимствовал у ФБР формулу «мыслить как преступник», а ФБР помогло Джонатану Демми снять «Молчание ягнят»

История отношений Ганнибала Лектера и его преследователей

Weekend
Сооснователь «Моторики»: «Если сравнивать рынок запчастей для киборгов с рынком смартфонов, то сейчас мы в 1990-х» Сооснователь «Моторики»: «Если сравнивать рынок запчастей для киборгов с рынком смартфонов, то сейчас мы в 1990-х»

Василий Хлебников — о протезах рук, аналитике по их использованию и медтехе

VC.RU
Алкогений: Эрик Клэптон Алкогений: Эрик Клэптон

Гитарист и певец Эрик Клэптон шел навстречу бутылке извилистыми путями

Maxim
Новый вид гусей определили по росписи в древнеегипетской гробнице Новый вид гусей определили по росписи в древнеегипетской гробнице

Ученые обратили внимание на рисунок, возраст которого составляет около 4600 лет

National Geographic
25 спортивных подвигов 25 спортивных подвигов

MAXIM вспоминает героические моменты спорта

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