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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Грудное молоко помешало бактерии вызвать воспаление в кишечнике новорожденного Грудное молоко помешало бактерии вызвать воспаление в кишечнике новорожденного

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

N+1
Что такое нестбоксинг Что такое нестбоксинг

Люди помогают дуплогнездникам поселиться в крепком и надежном дуплоне

Наука
Оригами-робота научили прижимать ноги и ходить по-крабьи Оригами-робота научили прижимать ноги и ходить по-крабьи

Инженер из Германии разработал четвероногого оригами-робота Fold Walker

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

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

Forbes
Завтрак с Сократом Завтрак с Сократом

Философия повседневной жизни

kiozk originals
В центре французского города нашли римский особняк с мраморной мозаикой и системой отопления В центре французского города нашли римский особняк с мраморной мозаикой и системой отопления

Археологи обнаружили на юге Франции остатки двух римских городских усадеб

N+1
В израильском зоопарке обнаружили два одинаковых римских саркофага В израильском зоопарке обнаружили два одинаковых римских саркофага

Памятники античной эпохи оказались открыты заново

N+1
Элеонора Севенард: «В балете, как в жизни, – если упал, надо подниматься и продолжать» Элеонора Севенард: «В балете, как в жизни, – если упал, надо подниматься и продолжать»

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

Grazia
Ракетные металлы: как закалялась сталь Ракетные металлы: как закалялась сталь

Из каких материалов строят космические корабли, "бороздящие просторы Вселенной"

Популярная механика
Водка у таксистов, или Что роднило СССР и Великобританию Водка у таксистов, или Что роднило СССР и Великобританию

О британской кухне в 70-е годы советский человек мог сказать только одно

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

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

Forbes
“Я вышла замуж по расчету” “Я вышла замуж по расчету”

Юлия Эльдеева слушала не веление сердца, а голос рассудка

Psychologies
Насекомые — пища на все времена Насекомые — пища на все времена

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

Наука и жизнь
Президент «Рив Гош» Эдгар Шабанов — о будущем компании Президент «Рив Гош» Эдгар Шабанов — о будущем компании

В каком направлении будет развиваться парфюмерно-косметическая сеть «Рив Гош»

РБК
От шаровар к легинсам: в чем женщины занимались спортом раньше и в чем сейчас От шаровар к легинсам: в чем женщины занимались спортом раньше и в чем сейчас

Какой путь прошел женский спортивный костюм за историю своего существования?

Cosmopolitan
«Хорошо сохранилась»: что делает Дженнифер Энистон, чтобы круто выглядеть в 52 «Хорошо сохранилась»: что делает Дженнифер Энистон, чтобы круто выглядеть в 52

Любимые бьюти-приемы Дженнифер Энистон, помогающие ей выглядеть молодой

Cosmopolitan
Бьюти-эволюция Инстасамки: как изменилась популярная блогерша из Тобольска Бьюти-эволюция Инстасамки: как изменилась популярная блогерша из Тобольска

Хип-хоп-певица Instasamka не так давно обновила «тюнинг»

Cosmopolitan
Одна вокруг света: Робин Гуд Дикого Запада и кусочек родины в Вайоминге Одна вокруг света: Робин Гуд Дикого Запада и кусочек родины в Вайоминге

107-я серия о кругосветном путешествии Ирины Сидоренко и ее собаки Греты

Forbes
Новая этика или новый тоталитаризм? Куда делась свобода слова в интернете Новая этика или новый тоталитаризм? Куда делась свобода слова в интернете

Почему рано или поздно нам всем придется привыкнуть к новой цифровой реальности

Esquire
Уроки бизнеса в русской классике: как плохое ТЗ, русский комплекс неполноценности и скрепы привели к провалу Левши Уроки бизнеса в русской классике: как плохое ТЗ, русский комплекс неполноценности и скрепы привели к провалу Левши

Отрывок из книги «Бесполезная классика» Леонида Клейна

Inc.
Физики поставили рекорд в измерении размера альфа-частицы Физики поставили рекорд в измерении размера альфа-частицы

Для этого они провели измерение частоты 2S-2S перехода в мюонном ионе гелия

N+1
Заложница собственного отца и жертва поп-культуры? Что мы узнали из документального фильма The New York Times о Бритни Спирс Заложница собственного отца и жертва поп-культуры? Что мы узнали из документального фильма The New York Times о Бритни Спирс

Как развивалась карьера Бритни Спирс почему она 13 лет не принимает решения сама

Esquire
Как в реальности выглядели участники группы Дятлова, о которых сняли сериал? Как в реальности выглядели участники группы Дятлова, о которых сняли сериал?

Насколько сериал «Перевал Дятлова» соответствовал действительности?

Cosmopolitan
«Меня все видят — это важно!» «Меня все видят — это важно!»

Кирилл Кяро — о комфорте, габаритах и экстремальных ситуациях на дорогах

OK!
Марс окружен роботами: почему ОАЭ, Китай и США почти одновременно решили послать свои аппараты к Марсу и куда смотрит Россия? Марс окружен роботами: почему ОАЭ, Китай и США почти одновременно решили послать свои аппараты к Марсу и куда смотрит Россия?

Откуда такое внимание к Марсу? В чем уникальность миссий и куда смотрит Россия?

Esquire
...Бегом под парусом ...Бегом под парусом

Кубок «Америки» – 2021 и гонка бегущих яхт

Популярная механика
Хватит мной управлять! Хватит мной управлять!

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

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

У самки темноспинного альбатроса Уиздом вылупился новый птенец

N+1
Золотая середина Золотая середина

Низкой самооценке часто приписывают все наши беды

Лиза
Алиса Фрейндлих и другие звезды «Служебного романа» 40 лет спустя Алиса Фрейндлих и другие звезды «Служебного романа» 40 лет спустя

Как сейчас выглядят звезды «Служебного романа»

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