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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Чернохвостые оленихи унаследовали миграционные маршруты матерей Чернохвостые оленихи унаследовали миграционные маршруты матерей

Как самки оленей учатся мигрировать у собственных матерей

N+1
Свет заставил полимерные диски левитировать в условиях мезосферы Свет заставил полимерные диски левитировать в условиях мезосферы

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

N+1
Как работает автофокус в фотоаппарате? От сенсора до мотора в объективе Как работает автофокус в фотоаппарате? От сенсора до мотора в объективе

Как работает автофокус: подробно и со схемами

ТехИнсайдер
Советы эксперта: все о визите к гинекологу Советы эксперта: все о визите к гинекологу

Что происходит в кабинете у гинеколога и зачем все это нужно?

Cosmopolitan
Не боги горшки обжигают: за что мы благодарны Михаилу Горшеневу из «Короля и Шута» Не боги горшки обжигают: за что мы благодарны Михаилу Горшеневу из «Короля и Шута»

Семь вещей, за которые стоит поблагодарить Михаила Горшенева

Правила жизни
«Зеленый» разворот: опасна ли политика Байдена для нефтегазового бизнеса «Зеленый» разворот: опасна ли политика Байдена для нефтегазового бизнеса

Новый президент Америки провозгласил курс на «зеленую» энергетику

Forbes
В 3500-летнем папирусе нашли древнейшее описание процесса мумификации В 3500-летнем папирусе нашли древнейшее описание процесса мумификации

Египтологи обнаружили старейшее из известных руководств по мумификации

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

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

Forbes
Настоящий доктор Лектер: кто был прототипом самого жуткого киноманьяка Настоящий доктор Лектер: кто был прототипом самого жуткого киноманьяка

Имя Ганнибала Лектера известно всем, но кто был его прообразом?

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

В традиционном народном творчестве заключена целительная сила

Psychologies
Ретабло – древнейшее из искусств Ретабло – древнейшее из искусств

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

Вокруг света
Личная жизнь Джо Ди Маджо — одного из величайших игроков в истории бейсбола и мужа Мэрилин Монро (отрывок из книги) Личная жизнь Джо Ди Маджо — одного из величайших игроков в истории бейсбола и мужа Мэрилин Монро (отрывок из книги)

Фрагмент главы из книги Рока и Джона Позитано «Ужин с Ди Маджо»

Esquire
Эра человечности: как пандемия и удаленка меняют отношения между сотрудниками Эра человечности: как пандемия и удаленка меняют отношения между сотрудниками

Жизнь на удаленке оказалась довольно удобной и выгодной для многих

Forbes
Стилист по почте: как стать миллиардером, запустив сервис подбора одежды для занятых женщин Стилист по почте: как стать миллиардером, запустив сервис подбора одежды для занятых женщин

Бизнес с одеждой по подписке

Forbes
Война с ценами: как российские власти пытаются сломать рынок Война с ценами: как российские власти пытаются сломать рынок

Регулирование цен может нарушить инвестиционные циклы в отрасли

Forbes
7 нон-фикшн книг, которые увлекут подростка 7 нон-фикшн книг, которые увлекут подростка

Подборка нон-фикшн произведений для подростков

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

Анджелина Джоли впервые пустила в свой дом журналистов!

Grazia
Складчатогубы поднялись до 1600 метров на восходящих потоках воздуха Складчатогубы поднялись до 1600 метров на восходящих потоках воздуха

Считалось, что рукокрылые не могут передвигаться на восходящих потоках воздуха

N+1
Метод: “Сознание – всадник, бессознательное – лошадь” Метод: “Сознание – всадник, бессознательное – лошадь”

Метод, который заслужил неоднозначную славу

Psychologies
Черепашка-ниндзя против Ferrari: суперкар который не смог Черепашка-ниндзя против Ferrari: суперкар который не смог

История «Гордон-Кибл» — автомобиля с лучшей в мире эмблемой

Maxim
Это надолго Это надолго

Как меняется секс в отношениях, куда девается и когда уже начинать волноваться?

Cosmopolitan
Пространство новых материалов Пространство новых материалов

Как один ученый придумал альтернативу таблице Менделеева

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

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

AD
Новый нос – за 3 дня и без реабилитации. Вся правда от пластического хирурга Новый нос – за 3 дня и без реабилитации. Вся правда от пластического хирурга

Сенсационный метод "сохраняющей" ринопластики по меньшей мере обнадеживает!

Cosmopolitan
Как менялось отношение к делу Вуди Аллена и Миа Фэрроу Как менялось отношение к делу Вуди Аллена и Миа Фэрроу

История отношения общества и прессы к Вуди Аллену и его семье с Миа Фэрроу

Weekend
Как пить соджу: секреты употребления популярной корейской водки Как пить соджу: секреты употребления популярной корейской водки

Рассказ о традиционном корейском алкогольном напитке

Playboy
Как сходить в кафе с собакой, чтобы в твоем счете не было разбитой посуды и покусанных посетителей Как сходить в кафе с собакой, чтобы в твоем счете не было разбитой посуды и покусанных посетителей

7 советов от кинологов для удачного вывода твоего четвероногого друга в свет

Maxim
«Без KPI можно построить «ВкусВилл»: основатель «Агамы» Юрий Алашеев о менеджменте, борьбе с бедностью и предпринимательстве «Без KPI можно построить «ВкусВилл»: основатель «Агамы» Юрий Алашеев о менеджменте, борьбе с бедностью и предпринимательстве

Интервью с Юрием Алашеевым о бизнесе и борьбе с бедностью

Forbes
7 обычных продуктов, которые смертельно опасны, если их съесть слишком много 7 обычных продуктов, которые смертельно опасны, если их съесть слишком много

Ты наверняка и не подозревал, что в твоем кухонном шкафу есть яды!

Maxim
Пройдя под парусом проливом Дрейка… Пройдя под парусом проливом Дрейка…

Зрелище надвигающегося штормового заряда из пролива Дрейка завораживает

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