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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

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

Нейроны обонятельных луковиц синхронизируют свои осцилляции с сердцебиением

N+1
Как Курт Кобейн за один день родился на глазах публики, умер и был воскрешен силой любви Как Курт Кобейн за один день родился на глазах публики, умер и был воскрешен силой любви

Отрывок из книги о Курте Кобейне «Тяжелее небес» Чарльза Р. Кросса

Forbes
«Двуликий ИИ»: как ИИ учится обманывать и скрывать ложь «Двуликий ИИ»: как ИИ учится обманывать и скрывать ложь

Как и люди, системы искусственного интеллекта (ИИ) могут намеренно лгать

ТехИнсайдер
Ботан стал мачо: как изменились звезды сериала Ботан стал мачо: как изменились звезды сериала

Как сейчас выглядят звезды «Простых истин» и чем они занимаются

Cosmopolitan
3 реальные причины, почему вы еще не достигли своих целей 3 реальные причины, почему вы еще не достигли своих целей

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

Psychologies
Польза масла черного тмина: научные данные Польза масла черного тмина: научные данные

Вместе с экспертом разбираемся в полезных свойствах тмина

РБК
Клуб первых жен: к истории фотосессии с Юлией Навальной Клуб первых жен: к истории фотосессии с Юлией Навальной

Жены оппозиционеров — это сила, с которой придется считаться

СНОБ
«Наш тариф выше, а наш океан гораздо более голубой» «Наш тариф выше, а наш океан гораздо более голубой»

Тимур Турлов — об истинной рентабельности брокерского бизнеса

Эксперт
На вторых ролях: почему ни один из топ-менеджеров Amazon не стал миллиардером На вторых ролях: почему ни один из топ-менеджеров Amazon не стал миллиардером

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

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

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

Cosmopolitan
Аграрный связной Аграрный связной

Как немец Штефан Дюрр использует 630 000 га российской земли

Forbes
Вышел сериал Вышел сериал

"Кларисса" — сериальное продолжение легендарного "Молчания ягнят"

Esquire
Осторожно! 10 популярных бьюти-процедур, которые могут обернуться кошмаром Осторожно! 10 популярных бьюти-процедур, которые могут обернуться кошмаром

Многие популярные процедуры все-таки лучше доверить профессионалам

Cosmopolitan
Большая голубая гасконская гончая Большая голубая гасконская гончая

Эта гончая — аристократ, обладатель белой кости и голубой крови

Weekend
Мал, да удал: мини-сериалы 2020-го года, от которых невозможно оторваться! Мал, да удал: мини-сериалы 2020-го года, от которых невозможно оторваться!

Лучшие мини-сериалы 2020-го года

Cosmopolitan
Полтора века безумия: как изучали шизофрению раньше и изучают сейчас Полтора века безумия: как изучали шизофрению раньше и изучают сейчас

О безумии людям известно с давних времен

Популярная механика
Фуху на островах южных морей Фуху на островах южных морей

Любой житель Британских островов скажет, что бокс придумали англичане

Вокруг света
Справляется без Джобса и не стесняется политики ради эффективности: история и главные решения Тима Кука во главе Apple Справляется без Джобса и не стесняется политики ради эффективности: история и главные решения Тима Кука во главе Apple

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

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

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

Популярная механика
На два фронта На два фронта

Что делать женщине, если ее муж – «двоеженец» и не собирается ничего менять?

Лиза
Австралийцы убили 350000 крыс и мышей на острове Лорд-Хау. Это пошло на пользу редким видам Австралийцы убили 350000 крыс и мышей на острове Лорд-Хау. Это пошло на пользу редким видам

Проект по истреблению крыс на острове Лорд-Хау дал плоды

N+1
«Смерти нет — и это, в общем-то, правда» «Смерти нет — и это, в общем-то, правда»

Александр Соболев — об альтернативной истории России и русской литературы

Полка
Субмаринные воды Крыма Субмаринные воды Крыма

Дебет подземных вод Горного Крыма оценивается примерно в 330 млн м3 в год

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

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

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

Определение глубокого сна и его значение для полноценного отдыха

Playboy
Лучшие книги и ресурсы для развития памяти Лучшие книги и ресурсы для развития памяти

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

Reminder
Тюркские юрты, саамский футбол, хоомей и тихий Дон: куда поехать, чтобы познакомиться с культурой народов России Тюркские юрты, саамский футбол, хоомей и тихий Дон: куда поехать, чтобы познакомиться с культурой народов России

Пять российских этнопарков, раскрывающих разные стороны России

Forbes
Криптомиллионеры начали платить тысячи долларов за право собственности на мемы. Wired рассказал, как устроен рынок NFT Криптомиллионеры начали платить тысячи долларов за право собственности на мемы. Wired рассказал, как устроен рынок NFT

Биткоин-элита тратит миллионы долларов на покупку цифрового искусства

Inc.
Важен каждый голос. Упражнения, которые помогут вам говорить свободнее Важен каждый голос. Упражнения, которые помогут вам говорить свободнее

Тяжело выступать публично? Голос кажется сдавленным и слишком высоким?

Reminder
Поэтесса на пути к президентству: кто такая Аманда Горман Поэтесса на пути к президентству: кто такая Аманда Горман

Как Аманда Горман вошла в список лидеров будущего Time100 Next?

РБК
Открыть в приложении