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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Пары жуков сизифов эффективнее одиночек перенесли навозные шарики через препятствия Пары жуков сизифов эффективнее одиночек перенесли навозные шарики через препятствия

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

N+1
На два фронта На два фронта

Что делать женщине, если ее муж – «двоеженец» и не собирается ничего менять?

Лиза
Петля затягивается: чем опасна новая уязвимость для проведения DDoS-атак Петля затягивается: чем опасна новая уязвимость для проведения DDoS-атак

Эксперты обнаружили новый вид атаки типа «отказ в обслуживании» (DDoS)

Forbes
Самый быстрорастущий дейтинг в мире: как Bumble пришел к IPO и почему непопулярен в России Самый быстрорастущий дейтинг в мире: как Bumble пришел к IPO и почему непопулярен в России

Сервис знакомств Bumble провел успешное IPO в Нью-Йорке

Forbes
Стеклоочистители, Wi-Fi и посудомоечные машины: 10 изобретений, которые придумали женщины Стеклоочистители, Wi-Fi и посудомоечные машины: 10 изобретений, которые придумали женщины

«Большинство изобретений — заслуга мужчин», — распространенное заблуждение

ТехИнсайдер
Эффект Кулиджа: почему секс заканчивается, и при чем здесь американский президент? Эффект Кулиджа: почему секс заканчивается, и при чем здесь американский президент?

У вас не кризис, а эволюционное стратегическое спаривание перестало работать

GQ
Реальная любовь Реальная любовь

Мы встретились с известным футболистом Кириллом Комбаровым и его супругой

OK!
7 отвратительных фильмов, снятых по мотивам видеоигр 7 отвратительных фильмов, снятых по мотивам видеоигр

Подборка настолько плохого кино, что от него мог бы сесть кинескоп

Maxim
Техника безопасности Техника безопасности

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

Glamour
Львы, слоны и зазеркалье: самые красивые книги на фестивале нидерландской литературы Львы, слоны и зазеркалье: самые красивые книги на фестивале нидерландской литературы

Самые красочные и необычные детские книги от нидерландских писателей

Seasons of life
Nikon разработала двухслойную фотоматрицу со встроенным HDR Nikon разработала двухслойную фотоматрицу со встроенным HDR

Группы пикселей в ней снимают с разной экспозицией

N+1
«Убийство Уильяма Норвичского. Происхождение кровавого навета в средневековой Европе» «Убийство Уильяма Норвичского. Происхождение кровавого навета в средневековой Европе»

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

N+1
Наркотики и аборты без анестезии: как обращались с детьми-актерами в Голливуде Наркотики и аборты без анестезии: как обращались с детьми-актерами в Голливуде

Голливуд — фабрика грез с двойным дном

Cosmopolitan
Проклятое платье Монро, которое не могли продать, и еще 5 ее скандальных нарядов Проклятое платье Монро, которое не могли продать, и еще 5 ее скандальных нарядов

Самые известные, громкие и скандальные наряды Мэрилин

Cosmopolitan
Как расслабить шею: 5 способов справиться с напряжением Как расслабить шею: 5 способов справиться с напряжением

Как расслабить шею в домашних условиях

Cosmopolitan
Как прошла женская акция солидарности и протеста в Москве Как прошла женская акция солидарности и протеста в Москве

Репортаж с акции «Цепь солидарности и любви» в поддержку женщин-политзаключенных

СНОБ
Александр Колесов Александр Колесов

В феврале 2021 года у главного синоптика Петербурга важная годовщина

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

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

Cosmopolitan
Почему безналичные чаевые в России — миллиардный рынок, которому мешают стереотипы Почему безналичные чаевые в России — миллиардный рынок, которому мешают стереотипы

Что интересного в сервисах для безналичных чаевых

VC.RU
Свет заставил полимерные диски левитировать в условиях мезосферы Свет заставил полимерные диски левитировать в условиях мезосферы

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

N+1
6 самых жутких врачей в истории 6 самых жутких врачей в истории

После этой статьи ты начнешь обходить районную поликлинику стороной!

Maxim
Игры с кошками помогли на треть снизить количество жертв охоты Игры с кошками помогли на треть снизить количество жертв охоты

Игровая активность и мясное питание снижают желание домашних котов охотиться

N+1
Мировой уровень Мировой уровень

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

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

Как освободиться от сахара?

Cosmopolitan
Как менялось отношение к делу Вуди Аллена и Миа Фэрроу Как менялось отношение к делу Вуди Аллена и Миа Фэрроу

История отношения общества и прессы к Вуди Аллену и его семье с Миа Фэрроу

Weekend
8 звезд, у которых неидеальные стопы. Но они вообще не комплексуют! 8 звезд, у которых неидеальные стопы. Но они вообще не комплексуют!

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

Cosmopolitan
Почему у тебя могут сохнуть глаза ночью (да, так бывает) Почему у тебя могут сохнуть глаза ночью (да, так бывает)

Крайне неприятное ощущение

Playboy
«Чтобы стать предпринимателем, нужно разозлиться». Основатель Social Capital Чамат Палихапития — о быстром успехе, ошибках и смысле денег «Чтобы стать предпринимателем, нужно разозлиться». Основатель Social Capital Чамат Палихапития — о быстром успехе, ошибках и смысле денег

Чамат Палихапития — один из самых влиятельных людей в Кремниевой долине

Inc.
Простор для творчества Простор для творчества

Кажется, что выполнить рекомендуемую «норму» по овощам — невозможно

Худеем правильно
Суп из мальчика, беременная Рапунцель: шокирующие детали сказок братьев Гримм Суп из мальчика, беременная Рапунцель: шокирующие детали сказок братьев Гримм

Почитайте сказки братьев Гримм без цензуры!

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