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

N+1Наука

Задачу коммивояжера решили одним кубитом

Пока только для шести городов

Егор Конюхов

f2e8bae82b8dd7ab7bd111d2ba6f1867.jpg
N + 1; Peter Schmelcher et al. / arXiv, 2024

Ученые оптимизировали маршрут между городами с помощью одного кубита. Для этого они отобразили условные города на сферу Блоха и воспользовались принципом суперпозиции. Предложенный способ обладает большей точностью по сравнению с классическими и квантовыми алгоритмами, но пока только для шести городов. Препринт исследования доступен на arXiv.org.

Задача коммивояжера — известная NP-трудная проблема. Ее суть состоит в том, чтобы построить кратчайший маршрут, который проходит через каждый город один раз. Классические компьютеры для этого либо требуют огромных затрат по времени вычислений, либо позволяют найти решение, но оно не всегда оказывается оптимальным (так называемые эвристические алгоритмы). То есть маршрут будет одним из самых коротких, но только с некоторой вероятностью оптимальным. Часто оптимальность решения исследователям трудно проверить именно из-за NP-сложности задачи.

Для решения задачи коммивояжера также используют квантовые вычислители. В этом случае на помощь приходит квантовая запутанность. Тем не менее нынешние квантовые алгоритмы позволяют ученым найти ответ для четырех городов лишь с 90-процентной вероятностью успеха, при этом для вычислений требуются сотни и тысячи физических кубитов.

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

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

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

У пиренейского кроманьонца выявили инвагинацию зуба У пиренейского кроманьонца выявили инвагинацию зуба

Ученые исследовали 17 зубов, которые археологи нашли в слоях верхнего палеолита

N+1
«Завышенная цена стала рыночной»: почему дорожает аренда элитной недвижимости «Завышенная цена стала рыночной»: почему дорожает аренда элитной недвижимости

С чем связан рост арендных ставок на элитное жилье в Москве

СНОБ
Урал, любовь моя Урал, любовь моя

5 абсолютно разных граней Большой уральской тропы

2Xplore
Почему люди из Азии пахнут иначе? Вот как мутация одного гена повлияла на их тела! Почему люди из Азии пахнут иначе? Вот как мутация одного гена повлияла на их тела!

Ген ABCC11 сильно влияет на запах тела у представителей разных этнических групп

ТехИнсайдер
Аллергия на дождь! Узнайте факты о необычной болезни: аквагенная крапивница Аллергия на дождь! Узнайте факты о необычной болезни: аквагенная крапивница

Аквагенная крапивница: что это за заболевание и как она влияет на жизнь человека

ТехИнсайдер
Что делать, если твоя подруга влюбилась в абьюзера: как ей помочь — рассказывает психолог Что делать, если твоя подруга влюбилась в абьюзера: как ей помочь — рассказывает психолог

Что делать, если подруга влюбилась в абьюзера и не хочет слышать разумные доводы

VOICE
Ксения Лучанинова: «На Дальнем Востоке частная медицина конкурирует с государственной за кадры» Ксения Лучанинова: «На Дальнем Востоке частная медицина конкурирует с государственной за кадры»

Дальний Восток — регион, в который устремлены все планы государства

ФедералПресс
Секс — мощное оружие маркетинга: жесткая диктатура длинных ног и коротких половых связей Секс — мощное оружие маркетинга: жесткая диктатура длинных ног и коротких половых связей

Почему быть сексуальным и иметь половую жизнь — это показатель престижа?

Psychologies
Как работает автопилот и чем он отличается от круиз-контроля Как работает автопилот и чем он отличается от круиз-контроля

Насколько различаются возможности автопилота и круиз-контроля в автомобиле

Maxim
«Кукушка»: боди-хоррор о репродуктивном насилии на альпийском курорте «Кукушка»: боди-хоррор о репродуктивном насилии на альпийском курорте

Как действительно жуткий фильм осмысляет проблему репродуктивного насилия

Forbes
Кто ты, мой новый герой? Кто ты, мой новый герой?

Слава Копейкин и Денис Косиков зажигают звезды

Men Today
Глава минпромторга Красноярского края: «Инвестиции растут на 25% в год» Глава минпромторга Красноярского края: «Инвестиции растут на 25% в год»

Красноярский край реализует инвестпроекты на триллионы рублей

ФедералПресс
Внимание, найден внутренний ребенок Внимание, найден внутренний ребенок

Что такое эго-состояния, можно ли «включать» их в нужный момент?

Grazia
Холодец: некoтoрые любят похолоднее Холодец: некoтoрые любят похолоднее

Откуда произошел холодец и как его правильно приготовить?

КАНТРИ Русская азбука
Мамина диета Мамина диета

Ответы на самые популярные вопросы по питанию, которые волнуют будущих мамочек

Лиза
Рескиллинг как новая норма Рескиллинг как новая норма

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

РБК
Андрей Миронов. «Он нравился. Он влюблял в себя. В нем была магия...» Андрей Миронов. «Он нравился. Он влюблял в себя. В нем была магия...»

«Быть артистом — это абсолютно его предназначение. Сцена у него затмевала все»

Коллекция. Караван историй
Почему лениться полезно Почему лениться полезно

5 неожиданных фактов о лени от врача

Лиза
«Если ко мне не будут приставать, как я пойму, чего стою?»: почему женщины зависимы от (любого) мужского внимания «Если ко мне не будут приставать, как я пойму, чего стою?»: почему женщины зависимы от (любого) мужского внимания

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

Psychologies
Вперед и вверх: как начать заниматься скалолазанием и куда пойти Вперед и вверх: как начать заниматься скалолазанием и куда пойти

Быстрый гид по скалолазанию для начинающих

Правила жизни
Сергей Безруков: «Как выдерживаю? Привычка, самодисциплина и терпение» Сергей Безруков: «Как выдерживаю? Привычка, самодисциплина и терпение»

Любознательность — то, что в себе нужно культивировать, развивать

Караван историй
«Я пытаюсь делать все максимально искренне» «Я пытаюсь делать все максимально искренне»

Дельфин – о прелести студийной аппаратуры 1970-х и оперной музыки

Правила жизни
Как табачные компании приучили женщин курить через идеи феминизма Как табачные компании приучили женщин курить через идеи феминизма

Как капитализм благими намерениями приучил женщин курить

Maxim
Люди из будущего Люди из будущего

Время не имеет над тайцами силы, ведь каждый продолжается в вечности

Вокруг света
5 причин посмотреть новый фильм «Ворон» 2024 года 5 причин посмотреть новый фильм «Ворон» 2024 года

«Ворон»: получилась ли новая экранизация комикса удачной?

Maxim
Как включить счетчик ФПС в КС 2 Как включить счетчик ФПС в КС 2

Как поставить счетчик ФПС в КС 2 — только быстрые и рабочие способы

CHIP
Биохакинг на экспорт: как запустить медицинский бизнес на постсоветском пространстве Биохакинг на экспорт: как запустить медицинский бизнес на постсоветском пространстве

Как сеть клиник биохакинга Biorise запустила франшизу в Казахстане и Армении

Forbes
Юла: кручу-верчу Юла: кручу-верчу

Яркая и шумная юла уже много веков веселит малышню в российских домах

КАНТРИ Русская азбука
Стесняюсь спросить: как отличить отек от жира? Стесняюсь спросить: как отличить отек от жира?

Как понять, жир у вас или отек, и как избавиться от того, и от другого

Правила жизни
Сезонные работы Сезонные работы

Каким должен быть уход за кожей после лета?

Лиза
Открыть в приложении