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

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 мистических находок археолога: куда пропала Клеопатра и что такое «воздушные змеи» пустыни

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

Популярная механика
Февральская революция: как искусственный интеллект может повысить производительность труда Февральская революция: как искусственный интеллект может повысить производительность труда

Русские ученые устроили шестую промышленную революцию!

ТехИнсайдер
Наше, родное: российские сериалы 2020-го, которые ничем не уступают «Нетфликсу» Наше, родное: российские сериалы 2020-го, которые ничем не уступают «Нетфликсу»

Российские сериалы, в которых прекрасно все — история, герои, режиссура

Cosmopolitan
Как кофеин влияет на мозг и тело: неожиданные факты Как кофеин влияет на мозг и тело: неожиданные факты

Исследования выявили ряд интересных фактов, связанных с кофеином

Psychologies
Я перестала делать из хорошего мужа «идеального отца» Я перестала делать из хорошего мужа «идеального отца»

Почему не нужно решать за мужа, каким он должен быть отцом

Psychologies
Внедорожник быстрее Ferrari: тест-драйв GMC Typhoon Внедорожник быстрее Ferrari: тест-драйв GMC Typhoon

Этот автомобиль можно считать дедушкой всех современных суперкроссоверов

РБК
Самые странные обычаи и приметы разных профессий Самые странные обычаи и приметы разных профессий

Пожелание спокойной смены, «Таня», «беременный стул» и прочие суеверия

Maxim
«Меняйтесь не ради цифр на весах, а ради внутренней гармонии и здоровья» «Меняйтесь не ради цифр на весах, а ради внутренней гармонии и здоровья»

История похудения со 115 кг до 65 кг

Худеем правильно
Чему нас может научить общение с нарциссами Чему нас может научить общение с нарциссами

Общение с нарциссами истощает и выматывает

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

Это не первый случай усыновления у вампиров

N+1
Русская соборность 1921 года: несостоявшееся и состоявшееся Русская соборность 1921 года: несостоявшееся и состоявшееся

Церковный собор весной 1921 года и кровавые репрессии

Наука
10 самых редких наборов LEGO, производившихся серийно 10 самых редких наборов LEGO, производившихся серийно

Бывают нумизматы, бывают филателисты, а бывают – коллекционеры LEGO

Популярная механика
Новый контракт: как снизить уровень бедности в России Новый контракт: как снизить уровень бедности в России

В России социальные выплаты не всегда доходят до тех, кто в них нуждается

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

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

Maxim
Какой мужчина! Сериалы с самыми привлекательными актерами Какой мужчина! Сериалы с самыми привлекательными актерами

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

Cosmopolitan
«Титаники» наших дней: чем опасны круизы сегодня «Титаники» наших дней: чем опасны круизы сегодня

Часть романтики морских путешествий состоит в ощущении опасности

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

Необъяснимые ужасы, вдохновившие самого Стивена Кинга на страшные истории

Maxim
«Не хотим продавать бизнес»: братья из Вологды рассказали Тинькову о цели создать крупнейшую игровую компанию «Не хотим продавать бизнес»: братья из Вологды рассказали Тинькову о цели создать крупнейшую игровую компанию

Основатели Playrix решили сделать его самой дорогой игровой компанией в мире

Forbes
Венсан Кассель: «Когда заканчиваются съемки фильма, я сбриваю волосы и чувствую себя свободным» Венсан Кассель: «Когда заканчиваются съемки фильма, я сбриваю волосы и чувствую себя свободным»

Венсан Кассель — один из самых знаменитых актеров во Франции

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

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

Playboy
Антикризисный бизнес: сколько в России ИП и много ли они зарабатывают Антикризисный бизнес: сколько в России ИП и много ли они зарабатывают

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

Forbes
Либеральный диктатор Навальный. Можно ли прорубить новое окно в Европу без сильной руки Либеральный диктатор Навальный. Можно ли прорубить новое окно в Европу без сильной руки

Противники Навального любят вспоминать о его националистическом прошлом

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

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

РБК
Материнский капитал Материнский капитал

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

Robb Report
Правила жизни Айн Рэнд Правила жизни Айн Рэнд

Писатель, скончалась в 1982 году в Нью-Йорке

Esquire
Египтологи восстановили историю египетской мумии в глиняном панцире Египтологи восстановили историю египетской мумии в глиняном панцире

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

N+1
5 шагов к эффективному управлению командой на удаленке 5 шагов к эффективному управлению командой на удаленке

Как сделать дистанционную работу максимально эффективной

СНОБ
«И смех, и грех»: идет ли юмор на пользу сексу? «И смех, и грех»: идет ли юмор на пользу сексу?

Психолог: Как понять, уместен ли смех в интимных отношениях

Psychologies
Биоинженерный суставной хрящ синтезировал для себя лекарство в ответ на нагрузку Биоинженерный суставной хрящ синтезировал для себя лекарство в ответ на нагрузку

Cоздан биоинженерный суставной хрящ на основе свиных клеток

N+1
Открыть в приложении