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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Плюшеголовые сойки не сумели воспользоваться инструментом Плюшеголовые сойки не сумели воспользоваться инструментом

Плюшеголовые разноцветные сойки не могут решить задачу с инструментами

N+1
Клуб первых жен: к истории фотосессии с Юлией Навальной Клуб первых жен: к истории фотосессии с Юлией Навальной

Жены оппозиционеров — это сила, с которой придется считаться

СНОБ
Информационная безопасность: десять основных видов хакерских атак Информационная безопасность: десять основных видов хакерских атак

Отрывок из книги Антона Евгеньева «Ценность ваших решений»

Forbes
Все о звездах сериала Все о звездах сериала

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

Cosmopolitan
История человеческого тела История человеческого тела

Эволюция, здоровье и болезни

kiozk originals
Только белый: как научиться носить самый нежный цвет и приручить total white Только белый: как научиться носить самый нежный цвет и приручить total white

Несколько практических советов по адаптации моды на белый цвет к реальной жизни

Cosmopolitan
7 диких развлечений наших предков 7 диких развлечений наших предков

В XIX веке люди умели повеселиться: у тебя нынешнего волосы встанут дыбом

Maxim
Правила жизни Пэрис Хилтон Правила жизни Пэрис Хилтон

Правила жизни светской львицы Пэрис Хилтон

Esquire
Можно ли вылечить насморк быстро? 7 советов оториноларинголога Можно ли вылечить насморк быстро? 7 советов оториноларинголога

Как избавиться от насморка и при этом не навредить себе

РБК
Квантовый вычислитель оказался сильнее классического в прикладной задаче Квантовый вычислитель оказался сильнее классического в прикладной задаче

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

N+1
Иконоартист Иконоартист

Анна Толстова о том, как Билл Виола перестал быть современным

Weekend
Как не поссориться с девушкой в День Святого Валентина Как не поссориться с девушкой в День Святого Валентина

5 советов для тех, кто планирует порадовать свою девушку 14 февраля

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

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

РБК
Размер ноги, длина пальцев и женская простата. Мифы и поверья вокруг секса Размер ноги, длина пальцев и женская простата. Мифы и поверья вокруг секса

Разбираемся в стереотипах вокруг секса

СНОБ
Обновлённый Hyundai Santa Fe выходит на российский рынок Обновлённый Hyundai Santa Fe выходит на российский рынок

Характеристики Hyundai Santa Fe, а также комплектации и стоимость кроссовера

Популярная механика
Опасные гидраты и где они обитают Опасные гидраты и где они обитают

Потепление климата связывают с ростом в атмосфере количества парниковых газов

Наука и жизнь
10 самых ядовитых растений 10 самых ядовитых растений

Большинство растений кажутся безобидными, но их не стоит недооценивать

Популярная механика
Что посмотреть и попробовать в Туве. Гид «РБК Стиль» Что посмотреть и попробовать в Туве. Гид «РБК Стиль»

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

РБК
Каждый наш клиент — история успеха Каждый наш клиент — история успеха

Дмитрий Брейтенбихер о том, как зарабатывать в эпоху интеллектуальной экономики

Esquire
Эффект дома Эффект дома

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

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

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

VC.RU
Сколько стоят за границей те же машины, что у нас. Сравнительная таблица Сколько стоят за границей те же машины, что у нас. Сравнительная таблица

Сравниваем российские ценники с европейскими, украинскими и азиатскими

РБК
Кто в доме хозяин Кто в доме хозяин

Муж, который готов потакать своей жене, со стороны кажется идеальным партнером

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

10 признаков, что твоя симпатичная коллега на работе не против

Maxim
Заложница собственного отца и жертва поп-культуры? Что мы узнали из документального фильма The New York Times о Бритни Спирс Заложница собственного отца и жертва поп-культуры? Что мы узнали из документального фильма The New York Times о Бритни Спирс

Как развивалась карьера Бритни Спирс почему она 13 лет не принимает решения сама

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

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

Cosmopolitan
Почти как BMW Х5, только дешевле: Nissan представил новый внедорожник Почти как BMW Х5, только дешевле: Nissan представил новый внедорожник

Такого крутого «Пасфайндера» еще не было!

Maxim
Операция «медиация»: как сохранить лицо во время конфликта без суда и следствия Операция «медиация»: как сохранить лицо во время конфликта без суда и следствия

Адвокат — о том, как решить конфликтные вопросы без суда

Forbes
Алло, гараж! Алло, гараж!

Смартфон и кнопочный телефон: как выбрать мобильник для своей мамы или бабушки?

Лиза
Вышел сериал Вышел сериал

"Кларисса" — сериальное продолжение легендарного "Молчания ягнят"

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