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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

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

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

Psychologies
Россия по-итальянски Россия по-итальянски

Все подробности жизни и «невероятных приключений итальянца в России»

2Xplore
История альянса: факты, которые вы могли не знать о НАТО История альянса: факты, которые вы могли не знать о НАТО

Договор, военная поддержка и армия: необычные факты о НАТО

ТехИнсайдер
Крафтсмены Крафтсмены

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

Bones
Не морем единым Не морем единым

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

Лиза
Над поверхностью Земли Над поверхностью Земли

Существует целое сообщество людей, которым открыто все небо

2Xplore
На средневековых предметах и росписях из Китая нашли желтые краски из растений На средневековых предметах и росписях из Китая нашли желтые краски из растений

В средневековом Китае использовали краски из гарцинии и китайского бархата

N+1
Наше все: гид по пушкинским местам и другим достопримечательностям Старицы Наше все: гид по пушкинским местам и другим достопримечательностям Старицы

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

Forbes
Чтение-путешествие на выходные: спонтанный гид по городам из книги Никиты Алексеева «Аахен-Яхрома» Чтение-путешествие на выходные: спонтанный гид по городам из книги Никиты Алексеева «Аахен-Яхрома»

Главы из «Аахен-Яхрома», которые можно использовать как идеи для путешествий

Правила жизни
«Месье поправляет пенсне» «Месье поправляет пенсне»

История очков, настоящий исторический детектив

Зеркало Мира
Супер фреш! Супер фреш!

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

Собака.ru
Фавориты ювелирного мира Фавориты ювелирного мира

Гранат – история драгоценного камня

Зеркало Мира
Согласование времен Согласование времен

Как в средневековой Европе измеряли и воспринимали время

Вокруг света
Вопрос века Вопрос века

Как правильно ухаживать за кожей вокруг глаз, чтобы не было «вековых» проблем?

Лиза
Что делать, если вы считаете себя абьюзером: 4 совета Что делать, если вы считаете себя абьюзером: 4 совета

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

Psychologies
Худеем по науке Худеем по науке

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

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

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

ТехИнсайдер
Что не продать — переработать Что не продать — переработать

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

Агроинвестор
Перегрелись: зачем останавливать глобальное потепление, если оно уже наступило Перегрелись: зачем останавливать глобальное потепление, если оно уже наступило

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

Forbes
Баклуши бить Баклуши бить

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

КАНТРИ Русская азбука
Морская граница на замке Морская граница на замке

Почему Береговая охрана Пограничной службы ФСБ должна стать резервом для флота

Обозрение армии и флота
Как измерить силу своих чувств: шкала Клода Штайнера Как измерить силу своих чувств: шкала Клода Штайнера

Можете ли вы описать, что вы чувствуете прямо сейчас?

Psychologies
Почему для женщин наличие секса важнее, чем для мужчин: необычное исследование ученых Почему для женщин наличие секса важнее, чем для мужчин: необычное исследование ученых

Как секс влияет на здоровье женщин?

Psychologies
Мысли вслух Мысли вслух

Антон Лапенко: из социальных сетей в большое кино

Men Today
Что читают в книжном клубе Сары Джессики Паркер Что читают в книжном клубе Сары Джессики Паркер

Топ-7 книг из списка актрисы Сары Джессики Паркер

СНОБ
Андрей Финягин: «Я научился не расстраиваться, когда меня не утверждают в кино» Андрей Финягин: «Я научился не расстраиваться, когда меня не утверждают в кино»

То, что показывают сейчас по ТВ, — это не сказочки, а пошлые анекдотики

Коллекция. Караван историй
Дофамин и его предшественник леводопа усилили деградацию бета-амилоида в префронтальной коре мышей Дофамин и его предшественник леводопа усилили деградацию бета-амилоида в префронтальной коре мышей

Дофамин и леводопа индуцируют деградацию бета-амилоида в мозге мышей

N+1
В древнем горшке из Китая нашли остатки пищи эпохи неолита В древнем горшке из Китая нашли остатки пищи эпохи неолита

Ученые проанализировали пищевую корку в керамическом горшке из памятника Хэмуду

N+1
Эти рыбы должны создать красивые круги из песка, чтобы привлечь самок! Интересные факты Эти рыбы должны создать красивые круги из песка, чтобы привлечь самок! Интересные факты

Самцы японской рыбы-фугу принимают необычный вызов в брачный период

ТехИнсайдер
8 удивительных парадоксов, о которых должен знать каждый, кто увлекается психологией 8 удивительных парадоксов, о которых должен знать каждый, кто увлекается психологией

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

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