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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Выдр уличили в охоте на пингвинов Выдр уличили в охоте на пингвинов

Ученые зафиксировали нападения выдр на пингвинов в ЮАР

N+1
Космические нейтрино рождаются квазарами Космические нейтрино рождаются квазарами

Нейтрино рождаются вблизи черных дыр в далеких активных галактиках

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

Ошибки, которые ухудшают качество звука и срок службы наушников

ТехИнсайдер
Петров, Хабенский, Аксенова и другие: актеры из простых семей и их родители Петров, Хабенский, Аксенова и другие: актеры из простых семей и их родители

Талант — не всегда генетика, что доказывают российские артисты из простых семей

Cosmopolitan
Недосып и тревожность: как сон влияет на психику и почему возникают панические атаки Недосып и тревожность: как сон влияет на психику и почему возникают панические атаки

Почему недосып — это не просто усталость

Правила жизни
Львы, слоны и зазеркалье: самые красивые книги на фестивале нидерландской литературы Львы, слоны и зазеркалье: самые красивые книги на фестивале нидерландской литературы

Самые красочные и необычные детские книги от нидерландских писателей

Seasons of life
«Мы должны сделать комфорт максимально изысканным» «Мы должны сделать комфорт максимально изысканным»

Дизайн-директор Brioni Норберт Штумпфль о законах бренда и новой коллекции

Weekend
Думай, как Илон Маск: почему мышление ракетостроителя приводит к успеху Думай, как Илон Маск: почему мышление ракетостроителя приводит к успеху

Отрывок из книги Озана Варола «Думай как Илон Маск»

Forbes
Опасные гидраты и где они обитают Опасные гидраты и где они обитают

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

Наука и жизнь
Одиноким предоставляется Одиноким предоставляется

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

Cosmopolitan
Цвет настроения синий: как улучшить качество сна с помощью цвета и света Цвет настроения синий: как улучшить качество сна с помощью цвета и света

Процесс засыпания можно ускорить с помощью света

РБК
Равенство поколений: действительно ли молодым сейчас жить труднее, чем раньше? Равенство поколений: действительно ли молодым сейчас жить труднее, чем раньше?

Отрывок из книги Эндрю Скотта и Линды Граттон «Новое долголетие»

СНОБ
Мигрень: что нужно знать? Мигрень: что нужно знать?

Всё самое новое о профилактике и лечении мигрени

Домашний Очаг
В прокате «Родные» — удивительная народная комедия с Буруновым и Монеточкой. Рассказываем, почему ее стоит посмотреть В прокате «Родные» — удивительная народная комедия с Буруновым и Монеточкой. Рассказываем, почему ее стоит посмотреть

«Родные» — лихое и веселое роуд-муви, которое превращается в драму

Esquire
Говорить ли с детьми о политике? Говорить ли с детьми о политике?

Как разговаривать с детьми о политике сегодня?

Psychologies
Александр Рогов — о Бали, мини-юбках не для всех и трендах весны Александр Рогов — о Бали, мини-юбках не для всех и трендах весны

Стилист Александр Рогов — об отдыхе на Бали и отношениях с мамой

Cosmopolitan
Снова как девочки! 8 причесок, которые молодят звезд после 35 Снова как девочки! 8 причесок, которые молодят звезд после 35

Мы собрали самые удачные прически голливудских знаменитостей

Cosmopolitan
Итоги «войны» Reddit и Уолл-стрит для её героев: кинотеатры AMC спасли себя, а GameStop не воспользовалась шумом Итоги «войны» Reddit и Уолл-стрит для её героев: кинотеатры AMC спасли себя, а GameStop не воспользовалась шумом

На GameStop заработали частные инвесторы и фонды, но не сам магазин

VC.RU
Какой получилась игра The Medium — первый в истории хоррор с двумя реальностями в одном экране Какой получилась игра The Medium — первый в истории хоррор с двумя реальностями в одном экране

The Medium — самый дорогой проект студии Bloober Team, и это их лучшая игра

Esquire
Лучи поддержки Лучи поддержки

Зачем над растениями вешают фиолетовые лампы

N+1
Цианобактерии выжили на марсианских ресурсах Цианобактерии выжили на марсианских ресурсах

Цианобактерии наработали биомассу в условиях низкого давления

N+1
Не очевидно Не очевидно

Как выявлять тренды раньше других

kiozk originals
Луна, женщины, СССР: зачем смотреть сериал «Ради всего человечества» Луна, женщины, СССР: зачем смотреть сериал «Ради всего человечества»

Сериал «Ради всего человечества» — проект-фантазия о космических достижениях США

РБК
Справляется без Джобса и не стесняется политики ради эффективности: история и главные решения Тима Кука во главе Apple Справляется без Джобса и не стесняется политики ради эффективности: история и главные решения Тима Кука во главе Apple

Как Тим Кук отточил производство до мелочей и избежал последствий торговой войны

VC.RU
Почему у собаки холодный нос и другие ответы на самые частые собачьи «почему» Почему у собаки холодный нос и другие ответы на самые частые собачьи «почему»

Ответы на самые часто задаваемые Гуглу вопросы о собаках

Maxim
Пробки навсегда? О транспортных сетях в Москве и России Пробки навсегда? О транспортных сетях в Москве и России

Что не так с российскими путями сообщения и что можно с этим сделать

N+1
Можно ли сделать иммунную систему сильнее или это миф Можно ли сделать иммунную систему сильнее или это миф

Йогурт или аскорбинка вряд ли помогут вам «усилить» иммунитет

Популярная механика
«Хаббл» рассмотрел комету-трансформер «Хаббл» рассмотрел комету-трансформер

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

N+1
Девушка на Кубе Девушка на Кубе

Катя Бобкова позирует в горячей, солнечной и морской фотосессии

Maxim
5 лучших хорроров, чтобы не скучать в пандемию: часть 2 5 лучших хорроров, чтобы не скучать в пандемию: часть 2

Хорроры, которые помогут скоротать вечера и немного пощекотать нервы

Популярная механика
Открыть в приложении