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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

Мозг людей, рожденных слепыми, обладает уникальной пластичностью Мозг людей, рожденных слепыми, обладает уникальной пластичностью

Нейронные паттерны визуальной коры у слепых уникальны и не меняются со временем

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

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

ТехИнсайдер
Наш человек! Наш человек!

11 звезд Голливуда с русскими корнями

Лиза
Уголок школьника Уголок школьника

5 вещей и предметов мебели, которые нужно выбросить из детской комнаты

Лиза
Что такое Часы Судного дня Что такое Часы Судного дня

Кто придумал часы геополитической тревоги, что они показывают?

Maxim
Как установить приложения на телевизор со Smart TV Как установить приложения на телевизор со Smart TV

Как правильно установить стороннюю программу на телевизор?

CHIP
«Что делать женщине, если…» «Что делать женщине, если…»

Совсем скоро в Okko стартует новый сезон сериала «Что делать женщине, если…»

OK!
Моя попытка номер… Моя попытка номер…

Актеры, которые поступили в театральный вуз не с первого раза

Лиза
Перестаньте добавлять сахар в кофе! Вот как это вредит здоровью Перестаньте добавлять сахар в кофе! Вот как это вредит здоровью

Смешивание сахара с кофе может иметь неожиданные последствия для здоровья

ТехИнсайдер
Овощ в мундире Овощ в мундире

Молодой картофель – какой лучше выбрать и как приготовить?

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

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

N+1
Николай Бобров: «Перу — это севиче и чича морада» Николай Бобров: «Перу — это севиче и чича морада»

Николай Бобров о стажировке в Перу, колорите и четырех тысячах видов картошки

Bones
«Нимб и крест: как читать русские иконы» «Нимб и крест: как читать русские иконы»

Как хорошо средневековый человек ориентировался в иконографии

N+1
Русская альтернатива Русская альтернатива

Почему Запад против нас ополчился и как его победить

Монокль
Вкус ностальгии: блюда, которые были в каждой советской школьной столовой Вкус ностальгии: блюда, которые были в каждой советской школьной столовой

Вспоминаем, какие блюда подавали в каждой школе СССР

ТехИнсайдер
«У нас нет хороших решений» «У нас нет хороших решений»

Денис Соловьев — о ситуации на валютном рынке и проблемах с внешними платежами

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

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

ТехИнсайдер
«Участие бизнеса необходимо  на каждом этапе формирования  кадрового резерва» «Участие бизнеса необходимо  на каждом этапе формирования  кадрового резерва»

О роли бизнеса в создании кадрового потенциала для развития нефтегазовой отрасли

РБК
Древнего дюгоня покусали акулы и крокодил Древнего дюгоня покусали акулы и крокодил

Палеонтологи описали остатки вымершего дюгоня из рода Culebratherium

N+1
Как устроить ролевую игру, если ты не знаешь, с чего начать: 8 полезных советов Как устроить ролевую игру, если ты не знаешь, с чего начать: 8 полезных советов

Итак, вы решили попробовать ролевые игры — с чего начать?

VOICE
Крафтсмены Крафтсмены

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

Bones
«Вам звонят из…» «Вам звонят из…»

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

Psychologies
Ярких летучих мышей из Азии начали истреблять ради изготовления украшений Ярких летучих мышей из Азии начали истреблять ради изготовления украшений

На онлайн-площадках в большом количестве торгуют украшенными гладконосами

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

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

Forbes
10 сложностей в отношениях, о которых молчат мужчины 10 сложностей в отношениях, о которых молчат мужчины

Какие сложности испытывают мужчины в отношениях и как с ними справиться?

Psychologies
Зеленая скульптура Зеленая скульптура

Учимся создавать топиари с помощью фигурной стрижки растений

Лиза
Смерть самурая Смерть самурая

Лучший фильм, чтобы проститься с Аленом Делоном

Weekend
Старость – не данность Старость – не данность

Можно ли на самом деле хотя бы замедлить старение?

Вокруг света
Нейроинтерфейс позволил пациенту с БАС общаться с точностью почти 98 процентов Нейроинтерфейс позволил пациенту с БАС общаться с точностью почти 98 процентов

Точность декодирования у нейроинтерфейса составляет 97,5 процента

N+1
Гендиректор ТМК ЭТЕРНО Денис Макиенко: «Мы строим новую компанию» Гендиректор ТМК ЭТЕРНО Денис Макиенко: «Мы строим новую компанию»

О том, почему ТМК ЭТЕРНО решила перестроить отлаженный бизнес

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