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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

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

Кусок нижней челюсти архаичного человека Penghu-1 принадлежал денисовцу

N+1
Кое-что о тактике российской оппозиции, или Слово в защиту повестки «малых дел» Кое-что о тактике российской оппозиции, или Слово в защиту повестки «малых дел»

Владислав Иноземцев: российское протестное движение пересекло рубеж развития

СНОБ
Какие ценности есть у ИИ? Ученые изучили Claude и рассказали интересные факты! Какие ценности есть у ИИ? Ученые изучили Claude и рассказали интересные факты!

Как ИИ выражает свои «принципы» в диалогах с людьми

ТехИнсайдер
Грандиозный пожар в гостинице «Россия» 25 февраля 1977 года Грандиозный пожар в гостинице «Россия» 25 февраля 1977 года

Символ советского туризма обернулся сотней пострадавших и погибших

Maxim
Как правильно ехать по серпантину: ПДД для водителей Как правильно ехать по серпантину: ПДД для водителей

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

РБК
Не хочу работать: 7 основных причин, почему не хочется трудиться, и способы борьбы с апатией Не хочу работать: 7 основных причин, почему не хочется трудиться, и способы борьбы с апатией

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

Playboy
Поэтесса на пути к президентству: кто такая Аманда Горман Поэтесса на пути к президентству: кто такая Аманда Горман

Как Аманда Горман вошла в список лидеров будущего Time100 Next?

РБК
Легко: бросить курить Легко: бросить курить

Все способы избавления от никотиновой зависимости

Maxim
«Выглядит вызывающим и является непристойным»: ФАС завела дело из-за клипа Моргенштерна и Альфа-банка «Выглядит вызывающим и является непристойным»: ФАС завела дело из-за клипа Моргенштерна и Альфа-банка

Антимонопольная служба завела дело из-за клипа Моргенштерна

Forbes
Ночницы не почувствовали сладкого несмотря на наличие нужных рецепторов Ночницы не почувствовали сладкого несмотря на наличие нужных рецепторов

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

N+1
Стилист назвала 5 главных ошибок с оверсайз-пиджаками — никогда так не делай! Стилист назвала 5 главных ошибок с оверсайз-пиджаками — никогда так не делай!

Вещи оверсайз сегодня на пике популярности

Cosmopolitan
Предельный Туле Предельный Туле

Край мира: где его искать

Вокруг света
Почему твой бывший совершенно точно «не торт» с точки зрения астрологии Почему твой бывший совершенно точно «не торт» с точки зрения астрологии

Заканчивать отношения всегда непросто, но это не значит, что ты должна страдать

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

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

Популярная механика
Гидрофобный катализатор помог поднять селективность реакции Фишера — Тропша Гидрофобный катализатор помог поднять селективность реакции Фишера — Тропша

Вода не задерживается на катализаторе и не вызывает побочные реакции

N+1
Что не так с фильмом «Малкольм и Мари» от создателей «Эйфории» Что не так с фильмом «Малкольм и Мари» от создателей «Эйфории»

Режиссер Сэм Левинсон слишком увлекся саморефлексией

GQ
Считал Airbnb достойным соперником и ставил на лояльность: как Арне Соренсон сделал Marriott крупнейшей сетью отелей Считал Airbnb достойным соперником и ставил на лояльность: как Арне Соренсон сделал Marriott крупнейшей сетью отелей

Как Арне Соренсон превратил Marriott в самую крупную сеть гостиниц в мире

VC.RU
Андрей Руденский: «Если бы думал, что я как все, не пошел бы в актеры» Андрей Руденский: «Если бы думал, что я как все, не пошел бы в актеры»

«Нет... Вас никогда не будут снимать. Ваше лицо — для рекламы одеколона»

Караван историй
10 дешевых иномарок, которые понравились бы россиянам. Фото 10 дешевых иномарок, которые понравились бы россиянам. Фото

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

РБК
Мария Власова и ее рукописный альбом Мария Власова и ее рукописный альбом

Домашний альбом Марии Власовой, сестры Зинаиды Волконской

Наука
«Полю все равно, какого я пола»: почему индийские женщины протестуют из-за аграрной реформы «Полю все равно, какого я пола»: почему индийские женщины протестуют из-за аграрной реформы

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

Forbes
Почему ругаться матом, нарушать социальные нормы и тупить полезно: объясняет психолог Почему ругаться матом, нарушать социальные нормы и тупить полезно: объясняет психолог

Иногда рамки нам очень сильно вредят

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

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

Psychologies
Так ли страшен глютен: мифы и правда Так ли страшен глютен: мифы и правда

Кому на самом деле нельзя употреблять глютен?

РБК
Как позволить себе стать собой и изменить жизнь Как позволить себе стать собой и изменить жизнь

Как найти свое место в потоке жизни, как узнать, куда плыть?

Psychologies
Поднимите мне веки Поднимите мне веки

Рассказываем, как скорректировать веки красиво и безопасно

Собака.ru
«Погребальный звон по карьере Вуди Аллена»: на HBO вышло расследование о семье режиссера «Погребальный звон по карьере Вуди Аллена»: на HBO вышло расследование о семье режиссера

В чем суть конфликта в семье Вуди Аллена и как мир воспринял новое расследование

Forbes
Профессора Стэнфордской школы бизнеса дали 5 советов, как шутить на работе, чтобы стать лучшим руководителем Профессора Стэнфордской школы бизнеса дали 5 советов, как шутить на работе, чтобы стать лучшим руководителем

Шутки в команде влияют на вовлечённость сотрудников и мотивацию

Inc.
Что такое Синдром упущенной выгоды и как его побороть Что такое Синдром упущенной выгоды и как его побороть

Возможно, ты счастливый обладатель Синдрома упущенной выгоды

Maxim
Собачники vs кошатники: ученые установили, чем отличаются их характеры (не очень приятные новости для владельцев кошек) Собачники vs кошатники: ученые установили, чем отличаются их характеры (не очень приятные новости для владельцев кошек)

У любителей кошек есть одна специфическая черта

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