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

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 самых распространенных исторических заблуждений

Распространенные исторические заблуждения

Maxim
«Огонь-батареи»: как изменились космические солнечные батареи за 67 лет «Огонь-батареи»: как изменились космические солнечные батареи за 67 лет

Какой путь прошли солнечные элементы космического типа с момента изобретения?

ТехИнсайдер
Как убрать синяк: 8 научно обоснованных способов Как убрать синяк: 8 научно обоснованных способов

Несколько способов, как предотвратить образование гематомы

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

Секс один-два раза в неделю может принести наибольшую психологическую пользу

Inc.
Anti-age: 7 правил Anti-age: 7 правил

Чтобы замедлить старение кожи, не обязательно прибегать к салонным процедурам

Добрые советы
На старт! Внимание! Гипс! Самые смешные и пугающие спортивные фото На старт! Внимание! Гипс! Самые смешные и пугающие спортивные фото

Спорт может быть скучным и серьезным

Maxim
Мир перевернулся: как выйти из психологического кризиса Мир перевернулся: как выйти из психологического кризиса

Отрывок из книги психолога Екатерины Сигитовой «Идеальный шторм»

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

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

Maxim
Почему спорить в интернете вредно и как с этим быть Почему спорить в интернете вредно и как с этим быть

Влияет ли на здоровье полемика в социальных сетях? Оказывается, да

РБК
Выжившие: как выглядели реальные герои фильмов про экстремальные путешествия Выжившие: как выглядели реальные герои фильмов про экстремальные путешествия

Прототипы героев фильмов о выживании и опасных путешествиях

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

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

Cosmopolitan
Побережье оторванных ног и другие самые загадочные преступления новейшего времени Побережье оторванных ног и другие самые загадочные преступления новейшего времени

Необъяснимые ужасы, вдохновившие самого Стивена Кинга на страшные истории

Maxim
Детокс на дому Детокс на дому

Что необходимо для хорошего самочувствия ранней весной?

Здоровье
«Мы суровый северный народ»: Юрий Колокольников — о Нолане, «Крюке» и образе плохих русских «Мы суровый северный народ»: Юрий Колокольников — о Нолане, «Крюке» и образе плохих русских

Актер Юрий Колокольников об изменениях в киноиндустрии в России и на Западе

Forbes
Малыш «Голиаф» — очень смешное и почти нестрашное супероружие вермахта Малыш «Голиаф» — очень смешное и почти нестрашное супероружие вермахта

Танкетка «Голиаф» — крохотное изобретение вермахта

Maxim
Самая большая свалка электроники и еще четыре места на Земле с самыми экстремальными условиями Самая большая свалка электроники и еще четыре места на Земле с самыми экстремальными условиями

В этих экстремальных местах живут люди

Maxim
Как обнаружить радиацию при помощи смартфона Как обнаружить радиацию при помощи смартфона

Насколько точны мобильные приложения, превращающие телефоны в дозиметры?

Популярная механика
5 физиологичных поз для сна: найдите свою 5 физиологичных поз для сна: найдите свою

Какие положения во время сна считаются физиологичными и кому они подходят

Psychologies
Помогает ли зеленый чай похудеть? Правда о популярном напитке Помогает ли зеленый чай похудеть? Правда о популярном напитке

Польза зеленого чая — это миф?

Playboy
Почему есть грибы полезно и для организма, и для планеты Почему есть грибы полезно и для организма, и для планеты

Рассказываем о всех особенностях грибов и развеиваем мифы о них

РБК
Древнейший духовой инструмент из раковины протрубил впервые за 18000 лет Древнейший духовой инструмент из раковины протрубил впервые за 18000 лет

Палеолитический аналог рога изготовили и раскрасили люди мадленской культуры

N+1
9 лучших игр для двоих: свежие идеи для домашнего свидания 9 лучших игр для двоих: свежие идеи для домашнего свидания

Хватит залипать в сериалы!

Playboy
Современные антипапы: игра святых престолов Современные антипапы: игра святых престолов

Идея папства как залога церковного единства

Weekend
Сила притяжения Сила притяжения

Дизайнер Ирина Крашенинникова наполнила квартиру отсылками к космической теме

AD
Иконоартист Иконоартист

Анна Толстова о том, как Билл Виола перестал быть современным

Weekend
Невероятная жизнь изобретателя велосипеда Невероятная жизнь изобретателя велосипеда

Немецкий барон Карл фон Дрез изобрел не только велосипед

Maxim
Не важно, закроется ли Clubhouse: почему у «социального аудио» есть будущее и какие сервисы нужны на этом рынке Не важно, закроется ли Clubhouse: почему у «социального аудио» есть будущее и какие сервисы нужны на этом рынке

Почему рынок «социального аудио» выглядит важным и кто на нем может заработать

VC.RU
Бенедикт Камбербэтч: «Дети – лучший якорь в нашем плаванье» Бенедикт Камбербэтч: «Дети – лучший якорь в нашем плаванье»

Трудно поверить, но Бенедикт Камбербэтч считает себя личностью вполне заурядной

Psychologies
Сменяемость власти: почему Кирилл Серебренников покидает «Гоголь-центр» Сменяемость власти: почему Кирилл Серебренников покидает «Гоголь-центр»

8,5 лет работы Кирилла Серебренникова в Гоголь-центре — фрагмент бесконечности

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