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

N+1Hi-Tech

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

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

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

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

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

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

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

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

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

Мезозойские млекопитающие и их родственники оказались обладателями однотонного темно-коричневого меха Мезозойские млекопитающие и их родственники оказались обладателями однотонного темно-коричневого меха

Палеонтологи реконструировали окраску шести маммалиаформов

N+1
Размер ноги, длина пальцев и женская простата. Мифы и поверья вокруг секса Размер ноги, длина пальцев и женская простата. Мифы и поверья вокруг секса

Разбираемся в стереотипах вокруг секса

СНОБ
Новая модель ChatGPT o1: шаг вперед или не до конца проработанная революция? Новая модель ChatGPT o1: шаг вперед или не до конца проработанная революция?

ChatGPT o1 обещает стать большим прорывом в мире искусственного интеллекта

ТехИнсайдер
Лучи поддержки Лучи поддержки

Зачем над растениями вешают фиолетовые лампы

N+1
Ирландская загадочность, стиль и бездонные голубые глаза: 7 лучших фильмов с Киллианом Мерфи Ирландская загадочность, стиль и бездонные голубые глаза: 7 лучших фильмов с Киллианом Мерфи

Самые знаковые работы харизматичного актера Киллиана Мерфи

Psychologies
Змеи в костюмах Змеи в костюмах

Как защититься от психопатов на работе

kiozk originals
«Невероятно настоящий». Коллеги Кирилла Серебренникова — о работе с ним «Невероятно настоящий». Коллеги Кирилла Серебренникова — о работе с ним

Коллеги и ученики Кирилла Серебренникова о том, чему они научились у него

РБК
Насекомые — пища на все времена Насекомые — пища на все времена

Поедание насекомых стимулировало трудовую деятельность наших предков

Наука и жизнь
Разговорится ли «русский Zoom»? Разговорится ли «русский Zoom»?

Российские IT-компании конкурируют с мировыми производителям систем видеосвязи

Эксперт
«Я не могу без тебя»: о чем говорит это послание? «Я не могу без тебя»: о чем говорит это послание?

Психиатр — о том, что такое расстройство сепараторной тревоги

Psychologies
Как порвались связи советской науки с мировой Как порвались связи советской науки с мировой

Советские ученые должны были служить только советской науке и никакой другой

Наука
Общение с сородичами повысило выживаемость самок жирафов Общение с сородичами повысило выживаемость самок жирафов

Жизнь в группе снижает уровень стресса у самок жирафов и помогает им искать пищу

N+1
Алкогений №75: Л. И. Брежнев Алкогений №75: Л. И. Брежнев

Леонид Ильич Брежнев не был алкоголиком ельцинского калибра

Maxim
Зоологи допустили существование сумчатых волков в наши дни Зоологи допустили существование сумчатых волков в наши дни

Скорее всего, этот вид вымер не в 1936 года, а на рубеже 1990-2000 годов

N+1
Эффект дома Эффект дома

После реновации дом в Подмосковье приобрёл своё собственное лицо

SALON-Interior
Принцип 80/20 Принцип 80/20

Как достичь большего с наименьшими усилиями

kiozk originals
Узнай, кем станет твой ребенок, по игрушкам, в которые он играет Узнай, кем станет твой ребенок, по игрушкам, в которые он играет

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

Maxim
7 типов плохих начальников, которые уверены, что они хорошие 7 типов плохих начальников, которые уверены, что они хорошие

Типы руководителей, которые мешают работе и карьере подчиненных

Psychologies
По кусочку По кусочку

Есть ли какое-то объяснение привычки кусочничества?

Худеем правильно
«Да» значит «да», но можно передумать»: юрист Анна Ривина — о концепции согласия в отношениях «Да» значит «да», но можно передумать»: юрист Анна Ривина — о концепции согласия в отношениях

Как зафиксировать сексуальное согласие?

Forbes
Сцепились языками Сцепились языками

Александр Добровинский объясняет, как в юности накопил большой словарный запас

Tatler
Илону Маску не хватило денег на российские ракеты — и он создал SpaceХ. Почему надо перестать повторять чужие ошибки и искать ключи под фонарем Илону Маску не хватило денег на российские ракеты — и он создал SpaceХ. Почему надо перестать повторять чужие ошибки и искать ключи под фонарем

Отрывок из книги «Думай как Илон Маск» бывшего ракетостроителя Озана Варола

Inc.
Менсплейнинг — зло: женщины поделились историями, когда мужчины с умным видом втирали им очевидное Менсплейнинг — зло: женщины поделились историями, когда мужчины с умным видом втирали им очевидное

Как мужчины поучают женщин, независимо от того, насколько они сами компетентны

Playboy
Пневматическая почта: как это работает Пневматическая почта: как это работает

Пневмопочта сможет спасти крупные города от пробок и смога

Популярная механика
Как Артемия Панарина попытались сделать жертвой «культуры отмены» Как Артемия Панарина попытались сделать жертвой «культуры отмены»

Рассказываем почему обвинения в адрес Артемия Панарина вызывают много вопросов

GQ
Золото в шкафу: как крошечный стартап помогает крупным компаниям наживаться на буме перепродаж Золото в шкафу: как крошечный стартап помогает крупным компаниям наживаться на буме перепродаж

Секонд-хенд становится тенденцией, от которой в восторге и покупатели, и бренды

Forbes
6 принципов воспитания от мам XXI века 6 принципов воспитания от мам XXI века

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

Psychologies
«Я смог бы сыграть всё» «Я смог бы сыграть всё»

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

OK!
Почему ты все время голодный? Почему ты все время голодный?

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

Maxim
У вызывающей болезнь Крона бактерии нашли слабое место У вызывающей болезнь Крона бактерии нашли слабое место

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

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