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

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
Я, мы, робот: как андроиды проникли в наши дома и головы Я, мы, робот: как андроиды проникли в наши дома и головы

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

Forbes
Как убрать синяк: 8 научно обоснованных способов Как убрать синяк: 8 научно обоснованных способов

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

РБК
11 способов становиться немного умнее каждый день 11 способов становиться немного умнее каждый день

Интеллект, как и тело, требует правильного питания и регулярных тренировок

Psychologies
Девочки тоже могут: выдающиеся обладательницы премии Дарвина Девочки тоже могут: выдающиеся обладательницы премии Дарвина

Самые выдающиеся победительницы премии Дарвина

Cosmopolitan
Насиловали за даму сердца, сморкались в скатерть: какими были настоящие рыцари Насиловали за даму сердца, сморкались в скатерть: какими были настоящие рыцари

Кого мы представляем себе, услышав слово «рыцарь»?

Cosmopolitan
Ресторатор Евгений Ничипурук — о русской пивной и проекте братьев Рока Ресторатор Евгений Ничипурук — о русской пивной и проекте братьев Рока

Ресторатор Евгений Ничипурук — это человек-мотор, который все успевает

РБК
Сложно поверить: самые удивительные и странные фотографии мира науки и природы Сложно поверить: самые удивительные и странные фотографии мира науки и природы

Порой кадры природных явлений слишком невероятны!

Популярная механика
У вызывающей болезнь Крона бактерии нашли слабое место У вызывающей болезнь Крона бактерии нашли слабое место

Ученые надеются, что открыли ключ к созданию терапии болезни Крона

N+1
От судьбы не уйти: 10 фильмов о неожиданной любви От судьбы не уйти: 10 фильмов о неожиданной любви

Фильмы о том, что любовь может случиться внезапно

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

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

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

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

N+1
Империя Безоса: как богатейший человек на планете создал Amazon и зачем рвется в космос Империя Безоса: как богатейший человек на планете создал Amazon и зачем рвется в космос

История успеха Джеффа Безоса — самого состоятельного человека в мире

Forbes
Пространство новых материалов Пространство новых материалов

Как один ученый придумал альтернативу таблице Менделеева

Популярная механика
Композитор Игорь Яковенко — о музыкальных шифрах, притворстве и джазе Композитор Игорь Яковенко — о музыкальных шифрах, притворстве и джазе

Композитор Игорь Яковенко — о Бенджамине Бриттене и звуках, которые не замечаешь

РБК
Сестра таланта Сестра таланта

В весенне-летних коллекциях о себе решили напомнить почти забытые нами мини-юбки

Vogue
Иконоартист Иконоартист

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

Weekend
Бенедикт Камбербэтч: «Дети – лучший якорь в нашем плаванье» Бенедикт Камбербэтч: «Дети – лучший якорь в нашем плаванье»

Трудно поверить, но Бенедикт Камбербэтч считает себя личностью вполне заурядной

Psychologies
«Новости со всех концов света»: Том Хэнкс соединяет штаты Америки и ведет ее в будущее словом «Новости со всех концов света»: Том Хэнкс соединяет штаты Америки и ведет ее в будущее словом

«Новости со всех концов света» — полюбившийся всем вестерн от Пола Гринграсса

Esquire
Невидимые угрозы: TORCH-инфекции Невидимые угрозы: TORCH-инфекции

Что такое TORCH-инфекции и чем они опасны для ребенка?

Здоровье
Настоящий доктор Лектер: кто был прототипом самого жуткого киноманьяка Настоящий доктор Лектер: кто был прототипом самого жуткого киноманьяка

Имя Ганнибала Лектера известно всем, но кто был его прообразом?

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

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

Seasons of life
Что такое нестбоксинг Что такое нестбоксинг

Люди помогают дуплогнездникам поселиться в крепком и надежном дуплоне

Наука
Что не так с манифестом Богомолова и теми, кто его порицает Что не так с манифестом Богомолова и теми, кто его порицает

Почему Путин может спать спокойно при такой оппозиции

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

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

Psychologies
Почему наша целеустремленность обусловлена эволюцией? Отрывок из книги «Что такое жизнь?» нобелевского лауреата Пола Нерса Почему наша целеустремленность обусловлена эволюцией? Отрывок из книги «Что такое жизнь?» нобелевского лауреата Пола Нерса

Фрагмент главы из книги «Что такое жизнь? Понять биологию за пять простых шагов»

Esquire
Призрак успеха: как фильм «Ганнибал» ввел весь Голливуд в заблуждение Призрак успеха: как фильм «Ганнибал» ввел весь Голливуд в заблуждение

Почему «Ганнибал» — коммерчески спорная идея

Forbes
Тест: Что сообщают ваши сновидения? Тест: Что сообщают ваши сновидения?

Все сновидения могут по-новому осветить нашу жизнь, страхи и желания

Psychologies
Армия розовощеких капиталистов: как стартап Roblox помогает зарабатывать подросткам Армия розовощеких капиталистов: как стартап Roblox помогает зарабатывать подросткам

Дэвид Базуки создал платформу, которая добилась стремительного внутреннего роста

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