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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

Медиатор: кто это и чем занимается Медиатор: кто это и чем занимается

В каких ситуациях медиатор незаменим и чем он отличается от психолога?

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

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

CHIP
4 простых лайфхака, как вывести плесень с одежды 4 простых лайфхака, как вывести плесень с одежды

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

ТехИнсайдер
Терраформирование Марса уже не фантастика Терраформирование Марса уже не фантастика

Для терраформирования Марса необходимо увеличить его температуру на 10°C

ТехИнсайдер
Никто не может трогать эту древнюю лестницу в храме Гроба Господня! Узнайте почему Никто не может трогать эту древнюю лестницу в храме Гроба Господня! Узнайте почему

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

ТехИнсайдер
Посмотрите на «устрицу-монстра»! Эксперты: это не самая большая устрица, но она поражает Посмотрите на «устрицу-монстра»! Эксперты: это не самая большая устрица, но она поражает

Устрицы могут достигать колоссальных размеров

ТехИнсайдер
От модели до CEO: как Брук Шилдс основала собственный бьюти-бренд для зрелых женщин От модели до CEO: как Брук Шилдс основала собственный бьюти-бренд для зрелых женщин

Брук Шилдс о том, как она решилась начать новую карьеру — в бизнесе

Forbes
Супер фреш! Супер фреш!

Что выбрать, чтобы освежить, уплотнить или даже реконструировать кожу

Собака.ru
Набрать, сбросить, повторить: как актеры вынуждены менять свою внешность ради карьеры Набрать, сбросить, повторить: как актеры вынуждены менять свою внешность ради карьеры

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

Forbes
Она — легенда: как Сьюзен Войджицки стала ролевой моделью для многих женщин в бизнесе Она — легенда: как Сьюзен Войджицки стала ролевой моделью для многих женщин в бизнесе

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

Forbes
Доктор наук объяснила, почему истории про маньяков так затягивают нас Доктор наук объяснила, почему истории про маньяков так затягивают нас

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

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

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

N+1
Мир Шрёдингера Мир Шрёдингера

«Черный пес»: китайский неовестерн о сломе времен

Weekend
Последние роли Орловой, Гурченко, Мордюковой и других великих советских актрис Последние роли Орловой, Гурченко, Мордюковой и других великих советских актрис

Мы решили вспомнить фильмы, которые стали для артисток последними

VOICE
«Понадобилось 60 лет»: как Япония осмысливает военные преступления прошлого «Понадобилось 60 лет»: как Япония осмысливает военные преступления прошлого

Как Япония подходит к проблемному разговору о вине и ответственности за прошлое

Forbes
9 привычек бестактных свекровей, которые портят жизнь молодым 9 привычек бестактных свекровей, которые портят жизнь молодым

Что раздражает молодых супругов в поведение их родителей?

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

Почему взрослую женщину просят вернуть мужу, как расценивать такие призывы?

Forbes
Хайям Аминов: «Наша задача — изучить всю Енисейскую Сибирь» Хайям Аминов: «Наша задача — изучить всю Енисейскую Сибирь»

Хайям Аминов о карьере, бизнесе, сибирских продуктах и душе

Bones
Правда ли, что волосы на самом деле мертвые: 11 любопытных фактов о нашей шевелюре Правда ли, что волосы на самом деле мертвые: 11 любопытных фактов о нашей шевелюре

Мы стараемся тщательно ухаживать за волосами, но так мало о них знаем

ТехИнсайдер
В чем секрет успеха спортсменов на Олимпиаде? Психолог олимпийской сборной Британии раскрыла секреты! В чем секрет успеха спортсменов на Олимпиаде? Психолог олимпийской сборной Британии раскрыла секреты!

Как спортсменов готовят к олимпиаде?

ТехИнсайдер
Кого на самом деле всю жизнь любила Клавдия Шульженко Кого на самом деле всю жизнь любила Клавдия Шульженко

«Я это исполнять не буду. Что за платочки? Банально, приторно!»

Коллекция. Караван историй
Почему люди из Азии пахнут иначе? Вот как мутация одного гена повлияла на их тела! Почему люди из Азии пахнут иначе? Вот как мутация одного гена повлияла на их тела!

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

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

Сколько спонсорских контрактов заключают девушки профессиональных теннисистов

Forbes
Сможет ли ИИ написать «Войну и мир-2» Сможет ли ИИ написать «Войну и мир-2»

SSM-модель — что нового она привнесла для мира нейросетей?

ТехИнсайдер
Господин хороший: 10 главных ошибок мягкого руководителя Господин хороший: 10 главных ошибок мягкого руководителя

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

Forbes
Машины из параллельного импорта подорожали: когда и как можно сэкономить Машины из параллельного импорта подорожали: когда и как можно сэкономить

Что привело к падению объемов параллельного импорта автомобилей

РБК
9 последствий парентификации, которые неминуемо отражаются на женской психике 9 последствий парентификации, которые неминуемо отражаются на женской психике

Как меняется поведение дочерей, ставших жертвами парентификации?

Psychologies
Молнии над водой Молнии над водой

Как выглядят гонки Formula E1 на электрических лодках с подводным крылом?

ТехИнсайдер
Рычит, но не испепеляет: каким получился второй сезон «Дома Дракона»? Рычит, но не испепеляет: каким получился второй сезон «Дома Дракона»?

Второй сезон «Дома Дракона»: каким он получился и как обманул ожидания фанатов

Правила жизни
Замедление Гольфстрима может привести к похолоданию в северной Европе Замедление Гольфстрима может привести к похолоданию в северной Европе

Изменения Гольфстриме могут привести к серьезному снижению температуры в Европе

ТехИнсайдер
Открыть в приложении