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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Длительное ожирение вызвало экспрессию биомаркеров старения в молодом возрасте Длительное ожирение вызвало экспрессию биомаркеров старения в молодом возрасте

Как ожирение снижает ожидаемую продолжительность жизни

N+1
Я не такая: каким женщинам не нужен феминизм Я не такая: каким женщинам не нужен феминизм

Почему мы все еще не достигли равноправия полов?

Psychologies
Сколько лет самому старому ныне летающему самолету ВВС США: даже знатокам будет трудно угадать! Сколько лет самому старому ныне летающему самолету ВВС США: даже знатокам будет трудно угадать!

Какой самый старый ныне летающий самолет в военной авиации США

ТехИнсайдер
«Я не смогла сопротивляться страсти»: Мария Максакова увела Вороненкова из семьи «Я не смогла сопротивляться страсти»: Мария Максакова увела Вороненкова из семьи

Мария Максакова рассказала о своем скандальном браке с Денисом Вороненковым

Cosmopolitan
Любите чай с молоком? Что это о вас говорит Любите чай с молоком? Что это о вас говорит

Способ заваривать и пить чай многое может рассказать о вашем характере

ТехИнсайдер
Еще 5 самых глупых вещей, которые навсегда изменили наш с тобой мир Еще 5 самых глупых вещей, которые навсегда изменили наш с тобой мир

История человечества была бы совершенно иной, будь нос Клеопатры чуточку длиннее

Maxim
Нейросеть озвучила беззвучную игру на фортепиано Нейросеть озвучила беззвучную игру на фортепиано

Алгоритм, который синтезирует восстановленный звук

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

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

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

Птицы поселились на планируемом месте его строительства, и тревожить их нельзя

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

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

N+1
От Skype к робокурьерам, от Oculus — к военным дронам: стартапы предпринимателей после крупных проектов От Skype к робокурьерам, от Oculus — к военным дронам: стартапы предпринимателей после крупных проектов

Янус Фриис, Макс Левчин, Палмер Лаки и другие строят новых «единорогов»

VC.RU
«Я смог бы сыграть всё» «Я смог бы сыграть всё»

Почему Антон Шагин не снимается в рекламе и не повторяется в ролях

OK!
Как прошла женская акция солидарности и протеста в Москве Как прошла женская акция солидарности и протеста в Москве

Репортаж с акции «Цепь солидарности и любви» в поддержку женщин-политзаключенных

СНОБ
Физики закрутили луч света в три концентрических спирали Физики закрутили луч света в три концентрических спирали

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

N+1
Невероятная жизнь скрипача Оле Булла, которого называли «Элвисом XIX века» Невероятная жизнь скрипача Оле Булла, которого называли «Элвисом XIX века»

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

Maxim
«Ложечку за маму» и другие опасные послания про еду из нашего детства «Ложечку за маму» и другие опасные послания про еду из нашего детства

Как родители прививают детям вредные установки про еду

Psychologies
«Кожа просто лопнула под фрезой»: мне пришлось удалять ноготь после маникюра «Кожа просто лопнула под фрезой»: мне пришлось удалять ноготь после маникюра

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

Cosmopolitan
«Еда для депрессии»: 5 продуктов, которые погрузят тебя в пучину отчаяния «Еда для депрессии»: 5 продуктов, которые погрузят тебя в пучину отчаяния

Если ты грустить собрался, съешь-ка жареной картошки — и открой ворота в ад!

Maxim
Гидрофобный катализатор помог поднять селективность реакции Фишера — Тропша Гидрофобный катализатор помог поднять селективность реакции Фишера — Тропша

Вода не задерживается на катализаторе и не вызывает побочные реакции

N+1
6 сигналов того, что ваш партнер ведет себя незрело 6 сигналов того, что ваш партнер ведет себя незрело

Определить эмоциональную незрелость другого человека не так-то просто

Psychologies
Как разговаривать с подростками о политике Как разговаривать с подростками о политике

Расскажи сыну про митинги, либерализм и демократию

Maxim
Правила жизни Бенисио Дель Торо Правила жизни Бенисио Дель Торо

Правила жизни актера Бенисио Дель Торо

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

Сколько же на самом деле происходит землетрясений и извержений в мире и России

Наука
4 фразы, с помощью которых мы оправдываем прокрастинацию 4 фразы, с помощью которых мы оправдываем прокрастинацию

Эти слова подкрепляют нежелательное поведение и помогают откладывать дела

Psychologies
Ма, ну сколько можно! Ма, ну сколько можно!

Мамочка, хватит уже критиковать подростка – дай ему возможность ошибаться

Лиза
Личная жизнь Джо Ди Маджо — одного из величайших игроков в истории бейсбола и мужа Мэрилин Монро (отрывок из книги) Личная жизнь Джо Ди Маджо — одного из величайших игроков в истории бейсбола и мужа Мэрилин Монро (отрывок из книги)

Фрагмент главы из книги Рока и Джона Позитано «Ужин с Ди Маджо»

Esquire
Святой Валентин, что ты делаешь, прекрати! Святой Валентин, что ты делаешь, прекрати!

Самые запутанные любовные истории звезд, от которых голова идет кругом

Лиза
Как помогают животным Райан Гослинг, Шарлиз Терон и другие звезды Как помогают животным Райан Гослинг, Шарлиз Терон и другие звезды

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

РБК
Диета молодости Диета молодости

Правильный рацион – ключевой элемент старения

Домашний Очаг
Новая эстетика. Кто и сколько зарабатывает на российской косметике новой волны Новая эстетика. Кто и сколько зарабатывает на российской косметике новой волны

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

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