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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Гуннов вновь назвали носителями енисейских языков Гуннов вновь назвали носителями енисейских языков

Хунну и гунны, возможно, говорили на одном из енисейских языков

N+1
10 современныx фильмов про отношения детей и родителей 10 современныx фильмов про отношения детей и родителей

Фильмы на тему родительства, всех его граней и оттенков

Seasons of life
Вход в провал: какие гаджеты опередили свое время и потерпели неудачу Вход в провал: какие гаджеты опередили свое время и потерпели неудачу

Гаджеты, которые обещали перевернуть нашу жизнь, но в итоге потерпели крах

Forbes
Все раздражает? Возможно, самое время проверить щитовидку Все раздражает? Возможно, самое время проверить щитовидку

Слабость, сильная усталость и раздражительность — ело в щитовидной железе?

Psychologies
Ученые объяснили, как езда на велосипеде способствует снижению риска развития деменции Ученые объяснили, как езда на велосипеде способствует снижению риска развития деменции

Езда на велосипеде полезнее, чем вы думали

ТехИнсайдер
Форменное благочестие Форменное благочестие

Простое печенье маамуль издавна объединяет неспокойный мир Ближнего Востока

Вокруг света
Каменные гости:  как топ-менеджер «Адаманта» стал коллекционером минералов Каменные гости:  как топ-менеджер «Адаманта» стал коллекционером минералов

Как Владимир Голубев увлекся камнями и что ему удалось собрать

Forbes
У вызывающей болезнь Крона бактерии нашли слабое место У вызывающей болезнь Крона бактерии нашли слабое место

Ученые надеются, что открыли ключ к созданию терапии болезни Крона

N+1
Испанские страсти Испанские страсти

Певица Розалия готовит новый альбом, а в перерыве — выбирает наряды и пластинки

Vogue
Экспресс-диета на мочегонных чаях - почему лучше не рисковать? Экспресс-диета на мочегонных чаях - почему лучше не рисковать?

Так ли идеальны и безопасны для твоего здоровья чаи-диуретики?

Cosmopolitan
Как увеличить глубокий сон: подробный рассказ о важной стадии ночного отдыха Как увеличить глубокий сон: подробный рассказ о важной стадии ночного отдыха

Определение глубокого сна и его значение для полноценного отдыха

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

Лучшие книги для того, чтобы пощекотать себе нервы

Популярная механика
Существовала ли легендарная библиотека Ивана Грозного? Существовала ли легендарная библиотека Ивана Грозного?

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

Культура.РФ
«Мы забросили русское искусство!» Что Мягков думал о современном российском кино «Мы забросили русское искусство!» Что Мягков думал о современном российском кино

Андрей Мягков, его отношение к кино, железные принципы и большая любовь

Cosmopolitan
Логика войны: почему приговор Навальному станет долгосрочным фактором нестабильности Логика войны: почему приговор Навальному станет долгосрочным фактором нестабильности

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

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

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

Здоровье
«Кожа просто лопнула под фрезой»: мне пришлось удалять ноготь после маникюра «Кожа просто лопнула под фрезой»: мне пришлось удалять ноготь после маникюра

Как предупредить чужие ошибки и сохранить свое здоровье в маникюрном кабинете?

Cosmopolitan
Люк Бессон Люк Бессон

Правила жизни Люка Бессона

Esquire
Новые Sonata, Haval, Granta, Sentra: на что жалуются владельцы на форумах Новые Sonata, Haval, Granta, Sentra: на что жалуются владельцы на форумах

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

РБК
Пэрис Хилтон 40 лет. Как последний столп гламура держится на плаву Пэрис Хилтон 40 лет. Как последний столп гламура держится на плаву

Флагману селебрити-культуры Пэрис Хилтон удалось не исчезнуть с радаров

РБК
Как выглядят Как выглядят

Результаты исследования новейшего кратера газового выброса на Ямале

Популярная механика
Дельфина де Виган: Преданность Дельфина де Виган: Преданность

У каждого из четырех героев романа «Преданность» свои секреты и тайны

СНОБ
Насиловали за даму сердца, сморкались в скатерть: какими были настоящие рыцари Насиловали за даму сердца, сморкались в скатерть: какими были настоящие рыцари

Кого мы представляем себе, услышав слово «рыцарь»?

Cosmopolitan
«Мы разведемся»: Кирилл Кяро чуть не потерял жену из-за карантина «Мы разведемся»: Кирилл Кяро чуть не потерял жену из-за карантина

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

Cosmopolitan
Кирилл Серебренников. Перемена участи Кирилл Серебренников. Перемена участи

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

СНОБ
«Я не смогла сопротивляться страсти»: Мария Максакова увела Вороненкова из семьи «Я не смогла сопротивляться страсти»: Мария Максакова увела Вороненкова из семьи

Мария Максакова рассказала о своем скандальном браке с Денисом Вороненковым

Cosmopolitan
Екатерина Донцова-Солягина: Растет ли качество онлайн-образования Екатерина Донцова-Солягина: Растет ли качество онлайн-образования

Как меняется онлайн-образование?

СНОБ
Правильное питание: инструкция для начинающих Правильное питание: инструкция для начинающих

Что и как есть с пользой и без строгих запретов

РБК
Интимная гимнастика: удовольствие для самой себя Интимная гимнастика: удовольствие для самой себя

Как состояние интимных мышц влияет на здоровье и личную жизнь женщины?

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

Олег Шибанов предостерегает российских инвесторов от риска

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