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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Палеоиндейцы изготовили иглы из костей пушных животных Палеоиндейцы изготовили иглы из костей пушных животных

Ученые выяснили, из костей каких животных изготавливали иглы палеоиндейцы

N+1
Геополитические конфликты из-за энергетической безопасности Геополитические конфликты из-за энергетической безопасности

Отрывок из книги Дэниела Ергина «Новая карта мира»

СНОБ
Искусственный снег, джакузи из обычной ванны и еще 7 необычных применений для домашнего мини-компрессора Искусственный снег, джакузи из обычной ванны и еще 7 необычных применений для домашнего мини-компрессора

Ищем забавные способы использовать домашний мини-компрессор

ТехИнсайдер
«Чай с любовью» «Чай с любовью»

Регина Тодоренко и Влад Топалов — о любви, браке и 30 книгах по психологии

OK!
Как уговорить близкого с зависимостью обратиться за помощью: 6 верных шагов Как уговорить близкого с зависимостью обратиться за помощью: 6 верных шагов

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

Psychologies
Инклюзивный наем: зачем компании берут на работу людей с физическими и ментальными особенностями Инклюзивный наем: зачем компании берут на работу людей с физическими и ментальными особенностями

Что упускает бизнес, с недоверием относящийся к сотрудникам с инвалидностью?

Forbes
Илону Маску не хватило денег на российские ракеты — и он создал SpaceХ. Почему надо перестать повторять чужие ошибки и искать ключи под фонарем Илону Маску не хватило денег на российские ракеты — и он создал SpaceХ. Почему надо перестать повторять чужие ошибки и искать ключи под фонарем

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

Inc.
Как восстановить режим сна Как восстановить режим сна

Превратись из ворчливого полуночника в раннюю пташку!

Maxim
Они этого не скрывают! Российские звезды, которые признались в пластике Они этого не скрывают! Российские звезды, которые признались в пластике

Знаменитости, которые не боятся говорить о произошедших с ними изменениях

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

Что означают твои сны?

Cosmopolitan
Диета молодости Диета молодости

Правильный рацион – ключевой элемент старения

Домашний Очаг
7 признаков того, что ваш собеседник — не слишком приятный человек 7 признаков того, что ваш собеседник — не слишком приятный человек

Быстро ли мы понимаем, что с нашим новым знакомым «что-то не так»?

Psychologies
«Полезные идиоты» для Путина. Почему Amnesty International забанила Навального «Полезные идиоты» для Путина. Почему Amnesty International забанила Навального

Кремлевская кампания очернения «шовиниста Навального» идет в сетях давно

СНОБ
Планктон по-русски. Законы выживания в суровом мужском коллективе Планктон по-русски. Законы выживания в суровом мужском коллективе

Как выжить в русском офисе, сохранить психику и не потерять авторитет

Maxim
Ученые реконструировали ДНК мамонта старше миллиона лет Ученые реконструировали ДНК мамонта старше миллиона лет

Это позволило больше узнать об эволюции шерстистых мамонтов и мамонтов Колумба

N+1
Чего ждут работодатели от «свитчеров» — людей, которые решили сменить работу и пошли на онлайн-курсы Чего ждут работодатели от «свитчеров» — людей, которые решили сменить работу и пошли на онлайн-курсы

Работодатели — об ожиданиях от людей, сменивших род деятельности

VC.RU
Одна вокруг света: встреча с бизонами и несанкционированная ночевка в Йеллоустоуне Одна вокруг света: встреча с бизонами и несанкционированная ночевка в Йеллоустоуне

106-я серия о кругосветном путешествии москвички и ее собаки Греты

Forbes
Ломает волосы, портит цвет и еще 3 причины отказаться от ламинирования Ломает волосы, портит цвет и еще 3 причины отказаться от ламинирования

Ламинирование – не единственный способ сделать волосы красивыми

Cosmopolitan
Модная база: выбрали актуальные черные кофты для твоих стильных образов Модная база: выбрали актуальные черные кофты для твоих стильных образов

Черная кофта – универсальная базовая вещь

Cosmopolitan
10 душераздирающих фильмов, которые заставят вас плакать 10 душераздирающих фильмов, которые заставят вас плакать

10 чудесных лент, во время просмотра которых мы можете заплакать!

Cosmopolitan
Отличные фильмы с Мягковым, которые ты мог пропустить Отличные фильмы с Мягковым, которые ты мог пропустить

Андрей Мягков играл не только в «Иронии судьбы» или «Служебном романе»

Maxim
Anti-age: 7 правил Anti-age: 7 правил

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

Добрые советы
Гликемический индекс продуктов: на что влияет и поможет ли похудеть Гликемический индекс продуктов: на что влияет и поможет ли похудеть

Гликемический индекс продуктов надо учитывать тем, кто контролирует свое питание

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

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

Cosmopolitan
Как правильно ругаться в соцсетях, чтобы не нарушить закон о мате Как правильно ругаться в соцсетях, чтобы не нарушить закон о мате

Распространённые примеры, которые позволят тебе ругаться как аристократу

Maxim
Не спать всю ночь и пережить день? Легко! Не спать всю ночь и пережить день? Легко!

Как оставаться бодрой после бессонной ночи?

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

Макс Левчин смог преобразовать концепцию «покупай сейчас, а плати потом»

Forbes
Корпорации узнали о менопаузе: как меняется аудитория фемтех-стартапов Корпорации узнали о менопаузе: как меняется аудитория фемтех-стартапов

Сфера фемтех-стартапов за последние два года существенно выросла

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

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

Maxim
8 способов развить креативное мышление 8 способов развить креативное мышление

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

РБК
Открыть в приложении