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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Искусственный белок поменял конформацию в ответ на повышение концентрации ионов кальция Искусственный белок поменял конформацию в ответ на повышение концентрации ионов кальция

Как искусственный белок реагирует на повышение концентрации ионов кальция

N+1
Электричество и свет помогли химикам разорвать углерод-водородную связь дважды Электричество и свет помогли химикам разорвать углерод-водородную связь дважды

Химики смогли дважды заменить водород на азот в производных этилбензола

N+1
Дружелюбный инсайдер: как ИИ становится новым каналом утечек Дружелюбный инсайдер: как ИИ становится новым каналом утечек

ИИ против безопасности: почему компании теряют данные через ChatGPT

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

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

Популярная механика
Как путешествия меняют нас: 5 не заметных глазу трансформаций Как путешествия меняют нас: 5 не заметных глазу трансформаций

Как путешествия влияют на наше ментальное и физическое здоровье?

ТехИнсайдер
Что делать, если оштрафовали за разметку под снегом. Инструкция Что делать, если оштрафовали за разметку под снегом. Инструкция

Как обжаловать «письмо счастья»?

РБК
Как повысить иммунитет и избежать авитаминоза? Как повысить иммунитет и избежать авитаминоза?

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

GQ
Парни поделились главными вещами, которым их научили отцы Парни поделились главными вещами, которым их научили отцы

Эти отцовские уроки запоминаются на всю жизнь

Playboy
Неизменные перчатки, отсылки к Голливуду и регулярные разборы шкафа: каким был гардероб Любви Орловой Неизменные перчатки, отсылки к Голливуду и регулярные разборы шкафа: каким был гардероб Любви Орловой

Гардероб актрисы Любови Орловой, одной из главных советских икон стиля

Esquire
10 способов укрепить ногти в домашних условиях 10 способов укрепить ногти в домашних условиях

Устрой своим ногтям SPA-курорт, не выходя из дома

Cosmopolitan
3D-печать удешевит создание ионных двигателей для кубсатов 3D-печать удешевит создание ионных двигателей для кубсатов

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

N+1
Тысячи болезненных укусов: как ведут себя интернет-тролли и что чувствуют их жертвы Тысячи болезненных укусов: как ведут себя интернет-тролли и что чувствуют их жертвы

Отрывок из книги «Я так не хотела» адвоката Кэрри Голдберг об интернет-троллях

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

К процессу бритья надо подходить с умом

Playboy
У Лукоморья труп зеленый. О чем на самом деле рассказывается в добрых детских сказках У Лукоморья труп зеленый. О чем на самом деле рассказывается в добрых детских сказках

Ты даже не представляешь, какие детские сказки читали наши прапрапрадеды

Maxim
Снизившуюся популярность коллекционирования бабочек назвали угрозой их изучения Снизившуюся популярность коллекционирования бабочек назвали угрозой их изучения

Сегодня люди стараются фотографировать бабочек, а не ловить их

N+1
Прощайте, роботы: за что мы любим Daft Punk Прощайте, роботы: за что мы любим Daft Punk

Чем запомнится дуэт Daft Punk

Esquire
Зайки и лужайки: что делать, если родственники уговаривают родить ребенка? Зайки и лужайки: что делать, если родственники уговаривают родить ребенка?

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

Cosmopolitan
5 лучших хорроров, чтобы не скучать в пандемию: часть 2 5 лучших хорроров, чтобы не скучать в пандемию: часть 2

Хорроры, которые помогут скоротать вечера и немного пощекотать нервы

Популярная механика
«Ваша цель — сделать так, чтобы вы шестимесячной давности выглядели идиотом в глазах себя сегодняшнего» «Ваша цель — сделать так, чтобы вы шестимесячной давности выглядели идиотом в глазах себя сегодняшнего»

Советы и бизнес-истории для начинающих предпринимателей от Остина Рифа

VC.RU
10 важных принципов, которые должна знать умная женщина 10 важных принципов, которые должна знать умная женщина

Жизнь непредсказуема, но несколько важных женских принципов в ней выделить можно

Cosmopolitan
В США впервые клонировали вымирающего американского хорька В США впервые клонировали вымирающего американского хорька

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

N+1
Цифровой Левиафан: как политика влияет на развитие технологий Цифровой Левиафан: как политика влияет на развитие технологий

Почему проваливается российская цифровизация?

Forbes
Карта: средний рост мужчин в разных странах мира. Как думаешь, Россия — страна карликов или великанов? Карта: средний рост мужчин в разных странах мира. Как думаешь, Россия — страна карликов или великанов?

Найди страну, на жителей которой ты можешь смотреть свысока!

Maxim
10 провальных бьюти-запусков звезд: от Кардашьян до Пэрис Хилтон 10 провальных бьюти-запусков звезд: от Кардашьян до Пэрис Хилтон

Чуть ли каждая вторая знаменитость создает свой бренд косметики и ухода

Cosmopolitan
Как пить соджу: секреты употребления популярной корейской водки Как пить соджу: секреты употребления популярной корейской водки

Рассказ о традиционном корейском алкогольном напитке

Playboy
Икра со вкусом виски или как наука воплощает самые смелые фантазии человека Икра со вкусом виски или как наука воплощает самые смелые фантазии человека

Какой будет еда будущего

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

Газ на Венере никак не связан с деятельностью живых микробов

Популярная механика
Шепотом и криком Шепотом и криком

Игорь Гулин о Геннадии Горе

Weekend
Чему нас учит измена и как она может изменить нашу жизнь к лучшему Чему нас учит измена и как она может изменить нашу жизнь к лучшему

Что произошло между двумя людьми, раз союз затрещал по швам

Psychologies
«Чахотка: другая история немецкого общества» «Чахотка: другая история немецкого общества»

Отрывок из книги Ульрике Мозер «Чахотка: другая история немецкого общества»

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