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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

Касторовое масло топит жир или нет: популярный тренд в TikTok Касторовое масло топит жир или нет: популярный тренд в TikTok

Следуя трендам: поможет ли касторовое масло избавиться от жира на животе?

ТехИнсайдер
Основной инстинкт Основной инстинкт

Быть желанной хочет каждая. Но что такое «соблазнительность» на самом деле?

Лиза
Союз спасения: как «Дэдпул и Росомаха» вернули киновселенную Marvel к жизни (или нет) Союз спасения: как «Дэдпул и Росомаха» вернули киновселенную Marvel к жизни (или нет)

«Дэдпул и Росомаха»: фестиваль фансервиса в мультивселенной безумия

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

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

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

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

ТехИнсайдер
Высокие амбиции Высокие амбиции

Современный интерьер с элементами шинуазри и азиатской тематики

SALON-Interior
Итальянский бродяга и французская гордость: герои Парижа, которых обсуждал весь мир Итальянский бродяга и французская гордость: герои Парижа, которых обсуждал весь мир

В Париже-2024 есть спортсмены, которых награждают совсем не медалями

Forbes
Сухбат Афлатуни: «Катехон». Фрагмент из романа-головоломки Сухбат Афлатуни: «Катехон». Фрагмент из романа-головоломки

Глава из «Катехона» — истории любви и хроники жизни от Сухбата Афлатуни

СНОБ
15 модных словечек и фраз, которые стоит позаимствовать из словаря зумеров 15 модных словечек и фраз, которые стоит позаимствовать из словаря зумеров

Разбираем зумерский сленг, чтобы найти с ними общий язык

Psychologies
Выгорела, но не могу остановиться: почему мы продолжаем пахать, даже если сил больше нет Выгорела, но не могу остановиться: почему мы продолжаем пахать, даже если сил больше нет

Почему наш внутренний супергерой продолжает спасать мир наизнос?

Psychologies
20 советов 20 советов

Советы тренеров со всего мира о том, как привести себя в форму

Men Today
От пара и лошади – к электричеству. Начала электротяги От пара и лошади – к электричеству. Начала электротяги

Сто лет на железных дорогах России работает электротяга. Но как все начиналось?

Наука и техника
Куда приводят мечты (и стоит ли за ними следовать) Куда приводят мечты (и стоит ли за ними следовать)

Что будет, если позволить себе воплотить в жизнь давние желания?

Psychologies
«Лучшее решение — блокировка сайтов с незарегистрированными БАДами» «Лучшее решение — блокировка сайтов с незарегистрированными БАДами»

Хакан Эртюрк о трендах и регулировании российского рынка БАДов

РБК
Золото короны: как члены королевских семей выступали и побеждали на Олимпиадах Золото короны: как члены королевских семей выступали и побеждали на Олимпиадах

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

Forbes
«Смерч 2»: блокбастер о девушке-метеорологе, которая бросила вызов торнадо «Смерч 2»: блокбастер о девушке-метеорологе, которая бросила вызов торнадо

«Смерч 2»: больше, чем захватывающий фильм-катастрофа

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

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

VOICE
Все суета Все суета

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

Вокруг света
Разумный рацион Разумный рацион

9 способов экономить на еде, продолжая питаться нормально

Лиза
8 способов увеличить автономность смартфона на Android 8 способов увеличить автономность смартфона на Android

Cпособы увеличения времени автономной работы смартфона Android

CHIP
Графомания или смерть Графомания или смерть

Что вынуждает ученых публиковать так много статей

N+1
Лайфстайл в локальном исполнении Лайфстайл в локальном исполнении

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

Монокль
«Криминальный гардероб: особенности девиантного костюма» «Криминальный гардероб: особенности девиантного костюма»

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

N+1
В поиске новых смыслов: почему на фоне мирового кризиса философия становится «модной» В поиске новых смыслов: почему на фоне мирового кризиса философия становится «модной»

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

Forbes
Просто добавь воды Просто добавь воды

Как восполнить недостаток влаги в коже

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

Почему растет живот у мужчин и как от него быстро избавиться?

РБК
Крафтсмены Крафтсмены

Рыцари невидимого фронта, которые помогают делать рестораны особенными

Bones
Игрушка: Петрушка Уксусов Игрушка: Петрушка Уксусов

Символ русского театра кукол — Петрушка

КАНТРИ Русская азбука
Стационарная вселенная и холодный ядерный синтез: известные научные теории, которые в результате оказались ошибочными Стационарная вселенная и холодный ядерный синтез: известные научные теории, которые в результате оказались ошибочными

Иногда научные теории могут основываться на достаточно сомнительных фактах

ТехИнсайдер
«Болячки прикладывали прямо к экрану»: псевдоцелители и «натуропаты» в новейшей истории России «Болячки прикладывали прямо к экрану»: псевдоцелители и «натуропаты» в новейшей истории России

«Целители», которые обещали людям из СССР лекарство от всех болезней

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