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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

У бонобо нашли вокальные диалекты У бонобо нашли вокальные диалекты

Ученые сравнили вокализации бонобо из трех разных зоопарков

N+1
Как флешмоб обычных ребят на Reddit обанкротил миллионеров с Уолл-стрит Как флешмоб обычных ребят на Reddit обанкротил миллионеров с Уолл-стрит

Текущий кризис на американской бирже и банкротство крупнейших хеджевых фондов

Maxim
Трое в лодке: на ком лежит ответственность за кибербезопасность Трое в лодке: на ком лежит ответственность за кибербезопасность

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

Forbes
Физики провели химическую реакцию с одним атомом резерфордия Физики провели химическую реакцию с одним атомом резерфордия

Физики экспериментально доказали плохую растворимость гидроксида резерфордия

N+1
Что такое биполярное аффективное расстройство и как живут люди с таким диагнозом Что такое биполярное аффективное расстройство и как живут люди с таким диагнозом

Что такое БАР, действительно ли он распространен или стал искусственным трендом?

Forbes
Будь нежной и женственной! Самые романтичные принты на весну и как их сочетать Будь нежной и женственной! Самые романтичные принты на весну и как их сочетать

Одежда с каким принтом должна быть в твоем гардеробе весной

Cosmopolitan
Палеонтолог вместо топ-модели: кто из детей fashion-красавиц не пошел на подиум Палеонтолог вместо топ-модели: кто из детей fashion-красавиц не пошел на подиум

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

Cosmopolitan
Молниеносный Молниеносный

Французский десерт – это особый раздел гастрономии

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

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

РБК
Кто такой статский советник? Кто такой статский советник?

Статский советник — это один из гражданских чинов в дореволюционной России

Культура.РФ
Бизнесмен Тихон Смыков вспоминает, как в России появились Nokia, Apple, Nike и LEGO Бизнесмен Тихон Смыков вспоминает, как в России появились Nokia, Apple, Nike и LEGO

Тихон Смыков о том, как отечественный рынок ретейла поднимался с колен

GQ
Метод: “Сознание – всадник, бессознательное – лошадь” Метод: “Сознание – всадник, бессознательное – лошадь”

Метод, который заслужил неоднозначную славу

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

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

Forbes
10 изречений Энцо Феррари о жизни, любви и смерти в день его рождения 10 изречений Энцо Феррари о жизни, любви и смерти в день его рождения

Лучшие цитаты Энцо Феррари о любви, успехе, автомобилях, победе и жизни

Maxim
Храм будущей войны Храм будущей войны

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

Наука
Что представляет собой флот Монголии, не имеющей выхода к морю Что представляет собой флот Монголии, не имеющей выхода к морю

К 1990 году монгольский флот состоял из единственного судна

Maxim
Если сотрудник вечно жалуется вам на жизнь: что можно сделать Если сотрудник вечно жалуется вам на жизнь: что можно сделать

Что делать, если ваш коллега решил «поплакаться в жилетку»

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

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

Maxim
Прерванная жизнь Прерванная жизнь

Первое интервью Вики Коротковой после ДТП со смертельным исходом

Tatler
Мурены с карибских рифов выиграли от истребления акул Мурены с карибских рифов выиграли от истребления акул

Мурены остаются многочисленными на рифах поблизости с поселениями

N+1
Создано универсальное водородное топливо в виде пасты: дешево и удобно Создано универсальное водородное топливо в виде пасты: дешево и удобно

«Powerpaste» - паста на основе магния, которая накапливает водородную энергию

Популярная механика
Зачем Августин, Остап Бендер и HAL 9000 играли в шахматы Зачем Августин, Остап Бендер и HAL 9000 играли в шахматы

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

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

Альбатросы Южного полушария регулярно глотают пластиковый мусор

N+1
Помогает ли зеленый чай похудеть? Правда о популярном напитке Помогает ли зеленый чай похудеть? Правда о популярном напитке

Польза зеленого чая — это миф?

Playboy
Для карьеры и не только: как научиться красиво говорить Для карьеры и не только: как научиться красиво говорить

Как научиться говорить красиво и правильно

Cosmopolitan
«Моего оптимизма хватит на двоих»: история мамы, чья дочь победила рак «Моего оптимизма хватит на двоих»: история мамы, чья дочь победила рак

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

Psychologies
Так и ослепнуть можно! Ошибки в макияже, которые вредят глазам, — мнение врача Так и ослепнуть можно! Ошибки в макияже, которые вредят глазам, — мнение врача

Макияж — неотъемлемая часть жизни современной женщины

Cosmopolitan
«Черт с ним, с закрытым рестораном, мне было жалко людей»: ресторатор Евгений Ничипурук о лубочной русской кухне и выживании в кризис «Черт с ним, с закрытым рестораном, мне было жалко людей»: ресторатор Евгений Ничипурук о лубочной русской кухне и выживании в кризис

Интервью с ресторатором Евгением Ничипуруком о том, как бизнес пережил кризис

Forbes
«А вы думали, Земфира — не человек?»: почему новый альбом певицы «Борделайн» не звучит как открытие «А вы думали, Земфира — не человек?»: почему новый альбом певицы «Борделайн» не звучит как открытие

Почему Земфира не оправдала ожидания многих

Forbes
У Москвы–реки У Москвы–реки

Современный, респектабельный интерьер московской квартиры

SALON-Interior
Открыть в приложении