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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

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

Комета A117uUD встретилась с Сатурном и теперь улетает из Солнечной системы

ТехИнсайдер
Не до шуток: почему умирает жанр ситкомов и какой будет комедия положений будущего Не до шуток: почему умирает жанр ситкомов и какой будет комедия положений будущего

Почему зрители больше не хотят смотреть ситуационные комедии?

Forbes
Жилища обтекаемой формы: зачем в СССР строили дома в виде бочек Жилища обтекаемой формы: зачем в СССР строили дома в виде бочек

Дома-бочки в СССР: для кого строили эти дома и почему они были такой формы?

ТехИнсайдер
Второе дыхание: как преодолеть «плато» в похудении? Второе дыхание: как преодолеть «плато» в похудении?

О природе «плато» и о том, как все-таки сдвинуть вес с мертвой точки

Правила жизни
Катастрофа на озере Ниос: как токсичная вода за ночь унесла жизни 1746 африканцев Катастрофа на озере Ниос: как токсичная вода за ночь унесла жизни 1746 африканцев

Трагедия на озере Ниос: что произошло с обычным водоемом в тот жуткий день?

ТехИнсайдер
Про тех, кто вечно в шоке Про тех, кто вечно в шоке

Что такое аффектация простыми словами, рассказывает психолог Надежда Бримаер

Лиза
Китай строит поезд-снаряд, летящий в вакууме со скоростью 1000 км/ч Китай строит поезд-снаряд, летящий в вакууме со скоростью 1000 км/ч

Поезд на магнитной подушке, который способен развить скорость 1000 км/ч

ТехИнсайдер
Солнце мое: как правильно пользоваться санскрином на море и в городе? Солнце мое: как правильно пользоваться санскрином на море и в городе?

Какие важные факты об SPF важно держать в голове?

Правила жизни
Искусственный интеллект за кадром: как цифровые сотрудники меняют правила игры Искусственный интеллект за кадром: как цифровые сотрудники меняют правила игры

Кто такие цифровые сотрудники, как они влияют на бизнес?

Forbes
Ивановичи Ивановичи

Обоим сыновьям Ивана Калиты совсем не повезло с местом в истории

Дилетант
Эколог Крейндлин: эти животные будут осенью бросаться под колеса Эколог Крейндлин: эти животные будут осенью бросаться под колеса

Каких животных стоит остерегаться российским водителям осенью?

ТехИнсайдер
Куркума и зеленый чай — одни из самых полезных пищевых добавок, из-за которых люди попадают в больницы Куркума и зеленый чай — одни из самых полезных пищевых добавок, из-за которых люди попадают в больницы

Насколько вреден прием популярных растительных добавок, помогающих похудеть?

ТехИнсайдер
Со своим вкусом Со своим вкусом

Как придать уксусу или соли необычный вкус без особых усилий

Bones
Айсен Николаев о векторе развития республики Саха: «Экономический рост должен улучшать жизнь людей» Айсен Николаев о векторе развития республики Саха: «Экономический рост должен улучшать жизнь людей»

Якутия поражает темпами социального и экономического развития

ФедералПресс
Что нужно знать о бензопилах: 16 самых популярных вопросов Что нужно знать о бензопилах: 16 самых популярных вопросов

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

CHIP
Что такое цифровой суверенитет и как его достичь: цели до 2030 года Что такое цифровой суверенитет и как его достичь: цели до 2030 года

Каких показателей цифрового суверенитета хотят добиться к 2030 году

ФедералПресс
Что не продать — переработать Что не продать — переработать

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

Агроинвестор
Лесото обладает самым высоким уровнем самоубийств в мире! Вот где расположена эта страна Лесото обладает самым высоким уровнем самоубийств в мире! Вот где расположена эта страна

В Лесото наблюдается один из самых высоких уровней самоубийств в мире

ТехИнсайдер
О пользе лени: 5 причин разрешить себе бездельничать О пользе лени: 5 причин разрешить себе бездельничать

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

РБК
Два «кукурузника»: у нашего родного биплана По-2 нашелся американский брат-близнец Два «кукурузника»: у нашего родного биплана По-2 нашелся американский брат-близнец

Зачем Boeing разрабатывала «кукурузники»?

ТехИнсайдер
Худеем по науке Худеем по науке

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

Лиза
Исследование: женщины должны начинать ежегодную маммографию в возрасте 40 лет Исследование: женщины должны начинать ежегодную маммографию в возрасте 40 лет

Когда женщинам следует начинать делать маммографию? Ответ есть!

ТехИнсайдер
Король ток-шоу: кто такой Фил Донахью? Король ток-шоу: кто такой Фил Донахью?

Чем Фил Донахью заслужил уважение и доверие телезрителей?

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

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

Psychologies
Галопом по Востоку Галопом по Востоку

Помимо острова Беринга, в восточной части России есть масса удивительных мест

2Xplore
Пропало либидо: план действий от психолога и сексолога Пропало либидо: план действий от психолога и сексолога

Что делать, если ты вдруг поняла: интима совсем не хочется и либидо на нуле?

VOICE
Фабрика-кухня: филиал Третьяковки в Самаре Фабрика-кухня: филиал Третьяковки в Самаре

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

Psychologies
Смерть в Тегеране: как гибель лидера ХАМАС изменит ситуацию на Ближнем Востоке Смерть в Тегеране: как гибель лидера ХАМАС изменит ситуацию на Ближнем Востоке

Ликвидация лидера движения ХАМАС едва ли изменит ситуацию в секторе Газа

Forbes
Финслерова геометрия как теория четырехмерности мира Финслерова геометрия как теория четырехмерности мира

О геометрии Вселенной, сверхсветовых скоростях и египетских пирамидах

Зеркало Мира
Меренга-бой Меренга-бой

Немного времени и хороший миксер — залог успеха меренги

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