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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Экологи усомнились в существовании «эскалатора вымирания» Экологи усомнились в существовании «эскалатора вымирания»

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

N+1
Хотите воплотить свою мечту? Начинайте действовать прямо сейчас Хотите воплотить свою мечту? Начинайте действовать прямо сейчас

Как перестать откладывать свои мечты на потом?

Psychologies
Здоров ли сайт: как провести аудит самостоятельно и когда привлекать специалистов Здоров ли сайт: как провести аудит самостоятельно и когда привлекать специалистов

Как самостоятельно выявить слабые места сайта?

Inc.
Распределенные вычисления на компьютерах добровольцев помогли найти новый пульсар-«черную вдову» Распределенные вычисления на компьютерах добровольцев помогли найти новый пульсар-«черную вдову»

Он разрушает своего маломассивного компаньона

N+1
Как заснуть буквально за минуту: способ, который все мы бессознательно используем Как заснуть буквально за минуту: способ, который все мы бессознательно используем

Как помочь своему организму заснуть?

Maxim
Вы считаете себя талантливым человеком? Вопрос дня Вы считаете себя талантливым человеком? Вопрос дня

Участники проекта «Сноб» рассказывают, считают ли они себя талантливыми

СНОБ
Как бороться с бессонницей: 18 эффективных средств для полноценного ночного отдыха Как бороться с бессонницей: 18 эффективных средств для полноценного ночного отдыха

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

Playboy
Эффектный конский хвост: 10 крутых идей для самой удобной прически Эффектный конский хвост: 10 крутых идей для самой удобной прически

Если обычный конский хвост — это слишком скучно, то попробуй наши варианты

Cosmopolitan
Как говорить, чтобы тебя все слушали Как говорить, чтобы тебя все слушали

Как сделать так, чтобы тебя слушали в любой компании из 2, 17 и 639 человек

Maxim
13 шагов, чтобы наладить грудное вскармливание, если мало молока 13 шагов, чтобы наладить грудное вскармливание, если мало молока

Врач-педиатр рассказывает, как наладить лактицию

9 месяцев
Солнечный свет помог в создании прозрачной древесины Солнечный свет помог в создании прозрачной древесины

Ученые сделали производство прозрачной древесины экологичнее, эффективнее, проще

N+1
На вторых ролях: почему ни один из топ-менеджеров Amazon не стал миллиардером На вторых ролях: почему ни один из топ-менеджеров Amazon не стал миллиардером

Что известно о Энди Ясси и почему он так и не стал миллиардером?

Forbes
Женская сила Женская сила

За художницей Артемизией Джентилески закрепилась слава первой феминистки

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

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

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

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

СНОБ
Литий-ионные аккумуляторы стали надежнее и эффективнее благодаря кремнию Литий-ионные аккумуляторы стали надежнее и эффективнее благодаря кремнию

Ученые смогли увеличить емкость литий-ионных батареек

Популярная механика
Управляя гневом Управляя гневом

Чему Кэри Маллиган научилась у своей новой героини?

OK!
Алексей Слаповский: Недо Алексей Слаповский: Недо

Отрывок из романа-столковения Алексея Слаповского «Недо»

СНОБ
Что приготовить из консервированного тунца, найденного в холодильнике: 8 крутых рецептов Что приготовить из консервированного тунца, найденного в холодильнике: 8 крутых рецептов

Что приготовить из тунца, консервированного в масле?

Playboy
Американские орнитологи опровергли эффект стола для пикников в Патагонии Американские орнитологи опровергли эффект стола для пикников в Патагонии

Редкие залетные птицы — не показатель присутствия новых видов

N+1
10 мини-сериалов, на которые не жалко потратить хоть все выходные 10 мини-сериалов, на которые не жалко потратить хоть все выходные

Мини-сериал - идеальное блюдо выходного дня

Cosmopolitan
Актер + актриса: почему распадаются красивые звездные пары Актер + актриса: почему распадаются красивые звездные пары

Психологи: знаменитостям не чужды кризисы, через которые проходят пары

Cosmopolitan
В США снесли одно из первых казино Трампа: каким было обанкротившееся предприятие экс-президента. Фоторепортаж В США снесли одно из первых казино Трампа: каким было обанкротившееся предприятие экс-президента. Фоторепортаж

История одного из первых казино Дональда Трампа — в фоторепортаже

Forbes
Личная жизнь Джо Ди Маджо — одного из величайших игроков в истории бейсбола и мужа Мэрилин Монро (отрывок из книги) Личная жизнь Джо Ди Маджо — одного из величайших игроков в истории бейсбола и мужа Мэрилин Монро (отрывок из книги)

Фрагмент главы из книги Рока и Джона Позитано «Ужин с Ди Маджо»

Esquire
Сестра таланта Сестра таланта

В весенне-летних коллекциях о себе решили напомнить почти забытые нами мини-юбки

Vogue
10 самых распространенных исторических заблуждений 10 самых распространенных исторических заблуждений

Распространенные исторические заблуждения

Maxim
Биолог — об исчезающих видах, экоциде и предсказании эпидемий Биолог — об исчезающих видах, экоциде и предсказании эпидемий

Сколько существует видов жизни на Земле

РБК
Как найти хорошую работу: 10 советов для построения успешной карьеры Как найти хорошую работу: 10 советов для построения успешной карьеры

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

Playboy
В поисках смысла В поисках смысла

Сегодня в кино Юра Борисов нарасхват

OK!
Посттравматический абсурд Посттравматический абсурд

«Рыцари справедливости» — депрессивная комедия о смысле жизни

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