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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Базальты с обратной стороны Луны возникли из истощенной мантии Базальты с обратной стороны Луны возникли из истощенной мантии

Источником базальтов, добытых станцией «Чанъэ-6», была мантия из слоев Луны

N+1
От чего на самом деле зависит либидо? От чего на самом деле зависит либидо?

Почему высокий уровень либидо – это важно?

Домашний Очаг
Работа с умом: каков потенциал генеративного ИИ для роста производительности в России Работа с умом: каков потенциал генеративного ИИ для роста производительности в России

Ученые проанализировали влияние генеративного ИИ на задачи и профессии

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

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

Weekend
5 сверхспособностей, которые станут доступны людям уже через 5 лет по версии футурологов 5 сверхспособностей, которые станут доступны людям уже через 5 лет по версии футурологов

Какие «суперспособности» станут реальностью уже к 2030 году — и какой ценой?

Maxim
Эффект Netflix: как сериалы делают модными шахматы и помогают продавать кроссовки Эффект Netflix: как сериалы делают модными шахматы и помогают продавать кроссовки

Современные сериалы могут поднять продажи чего угодно

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

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

N+1
Черепашка-ниндзя против Ferrari: суперкар который не смог Черепашка-ниндзя против Ferrari: суперкар который не смог

История «Гордон-Кибл» — автомобиля с лучшей в мире эмблемой

Maxim
Осторожно, окрашено! Осторожно, окрашено!

Визажистка Пэт Макграт превратила подиумный макияж в вид искусства

Vogue
«Мы забросили русское искусство!» Что Мягков думал о современном российском кино «Мы забросили русское искусство!» Что Мягков думал о современном российском кино

Андрей Мягков, его отношение к кино, железные принципы и большая любовь

Cosmopolitan
«Рана» Оксаны Васякиной — роман о любви и нелюбви. Публикуем его фрагмент «Рана» Оксаны Васякиной — роман о любви и нелюбви. Публикуем его фрагмент

Отрывок из умного и эмоционально насыщенного романа о любви от Оксаны Васякиной

Esquire
Касторовое масло: состав, применение, мнение врача Касторовое масло: состав, применение, мнение врача

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

РБК
«Истинный сын американского Юга»: Мэттью Макконахи вспоминает советы мамы и детство в Техасе «Истинный сын американского Юга»: Мэттью Макконахи вспоминает советы мамы и детство в Техасе

Отрывок из дневников актера Мэттью Макконахи

Forbes
«Между нами все кончено»: как удержаться от контактов с бывшим «Между нами все кончено»: как удержаться от контактов с бывшим

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

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

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

Популярная механика
Совсем не скучно: документальные фильмы про маньяков Совсем не скучно: документальные фильмы про маньяков

Документальные фильмы, рассказывающие о чудовищных преступлениях

Cosmopolitan
Бьюти-гаджеты Бьюти-гаджеты

Разбираемся в популярных девайсах для лица

Лиза
Платина и карбид молибдена помогли получить водород при 40 градусах Цельсия Платина и карбид молибдена помогли получить водород при 40 градусах Цельсия

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

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

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

N+1
«Хаббл» рассмотрел комету-трансформер «Хаббл» рассмотрел комету-трансформер

Астрономы изучили комету, которая изначально была троянским астероидом

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

Что упускает бизнес, с недоверием относящийся к сотрудникам с инвалидностью?

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

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

Cosmopolitan
Самые интересные факты о Майкле Бэе Самые интересные факты о Майкле Бэе

Майкл Бэй подарил нам больше огня и взрывов, чем все другие вместе взятые

Maxim
Сэкономь свои деньги! 5 бесполезных косметических процедур — мнение эксперта Сэкономь свои деньги! 5 бесполезных косметических процедур — мнение эксперта

Самые бесполезные косметические процедуры

Cosmopolitan
Как начать заниматься в тренажерном зале: 16 советов от мировых тренеров Как начать заниматься в тренажерном зале: 16 советов от мировых тренеров

Как правильно начать заниматься фитнесом, сохранить мотивацию и избежать травм

Playboy
Что в твоей стране норма, а для всего мира странно: люди делятся абсурдными традициями Что в твоей стране норма, а для всего мира странно: люди делятся абсурдными традициями

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

Playboy
«Аллен против Фэрроу» — документальный сериал об обвинениях в насилии в адрес режиссера. Можно ли ему верить — или пора «отменять» Вуди Аллена? «Аллен против Фэрроу» — документальный сериал об обвинениях в насилии в адрес режиссера. Можно ли ему верить — или пора «отменять» Вуди Аллена?

«Аллен против Фэрроу» — сериал о #metoo, абьюзе и исторической памяти

Esquire
Археологи нашли пурпурные ткани времен царя Соломона и воссоздали процесс добычи красителя Археологи нашли пурпурные ткани времен царя Соломона и воссоздали процесс добычи красителя

Исследование окрашенного текстиля времен царя Соломона

N+1
Паруса в виде колонн: эффект Магнуса Паруса в виде колонн: эффект Магнуса

Странные мачты-паруса на яхте

Популярная механика
Интервью с белорусским акционистом Алексеем Кузьмичом ‎о политическом искусстве и критике протестов Интервью с белорусским акционистом Алексеем Кузьмичом ‎о политическом искусстве и критике протестов

Белорусский акционист Алексей Кузьмич — о том, за что критикует оппозицию

СНОБ
Открыть в приложении