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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

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

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

ТехИнсайдер
Логотип личности Логотип личности

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

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

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

ТехИнсайдер
«Дашь сиську потрогать?»: таксист снимал на видео, как домогался к клиенткам «Дашь сиську потрогать?»: таксист снимал на видео, как домогался к клиенткам

Что можно сделать в ситуации, если вас домогаются?

Psychologies
«В начале было кофе. Лингвомифы, речевые „ошибки“ и другие поводы поломать копья в спорах о русском языке» Почему некоторые слова перестают склоняться «В начале было кофе. Лингвомифы, речевые „ошибки“ и другие поводы поломать копья в спорах о русском языке» Почему некоторые слова перестают склоняться

О том, почему некоторые слова в русском языке теряют возможность склоняться

N+1
Чай по всем канонам Чай по всем канонам

Как приготовить правильный чай и что при этом важно не упустить из виду

КАНТРИ Русская азбука
Постотпускной синдром Постотпускной синдром

Почему можно впасть в депрессию после отдыха и что с этим делать

Лиза
«Ваш диагноз — сибирская язва»: свердловская эпидемия 1979 года, которая до сих пор остается засекреченной «Ваш диагноз — сибирская язва»: свердловская эпидемия 1979 года, которая до сих пор остается засекреченной

Ровно 45 лет назад в Свердловске произошла эпидемия смертельной сибирской язвы

ТехИнсайдер
Изотопный анализ показал, как питались элита и низшие классы во Франции 1000 лет назад Изотопный анализ показал, как питались элита и низшие классы во Франции 1000 лет назад

​​​​​​​Археологи узнали средневековые диетические практики Франции

ТехИнсайдер
Вино из Воронежа Вино из Воронежа

В мир вина я попал очень просто — мама была большой ценительницей

Bones
Собрание автомобильных редкостей Собрание автомобильных редкостей

Об уникальных автомобилях, вошедших в историю

Зеркало Мира
В Кении нашли древнейшего австралопитека В Кении нашли древнейшего австралопитека

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

N+1
Стоматолог Блюмкин рассказал, какие гаджеты для зубов нужно приобрести каждому Стоматолог Блюмкин рассказал, какие гаджеты для зубов нужно приобрести каждому

Актуальные гаджеты для гигиены полости рта — советует стоматолог

ТехИнсайдер
Рескиллинг как новая норма Рескиллинг как новая норма

Почему набирает обороты тренд на переобучение сотрудников

РБК
«Чудовищный эксперимент» Уэнделла Джонсона: как психолог провел жестокий опыт с заиканием на детях-сиротах «Чудовищный эксперимент» Уэнделла Джонсона: как психолог провел жестокий опыт с заиканием на детях-сиротах

История о том, как детская обида и эгоизм покалечили психику сирот

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

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

ТехИнсайдер
Триколор и Булочка: 39 текстов про тело в одной книге Триколор и Булочка: 39 текстов про тело в одной книге

Тема телесности раскрывается в тридцати девяти текстах «Тело: у каждого свое»

СНОБ
Светятся в темноте и разрушают сперматозоиды! Вот какие бывают презервативы: интересные факты Светятся в темноте и разрушают сперматозоиды! Вот какие бывают презервативы: интересные факты

Существует множество видов презерватива, у каждого типа есть свои плюсы и минусы

ТехИнсайдер
Чем полезна куриная печень для организма: 6 свойств Чем полезна куриная печень для организма: 6 свойств

Куриную печень готовят и едят гораздо реже самой курятины, но это зря

РБК
«Глаза и уши режима: государственный политический контроль в Советской России, 1917–1928» «Глаза и уши режима: государственный политический контроль в Советской России, 1917–1928»

Кто собирал информацию о настроениях населения

N+1
Маленькие трагедии Маленькие трагедии

Что определяет детскую моду? В первую очередь то, кем взрослые видят детей

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

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

Правила жизни
Екатерина Гусева: «Чем больше отдаю душевных сил, тем больше получаю солнечной энергии!» Екатерина Гусева: «Чем больше отдаю душевных сил, тем больше получаю солнечной энергии!»

Я чувствую, что наполнена зрительской благодарностью и любовью

Караван историй
Думать — больно? Западные эксперты рассказали, как сознательно снизить уровень стресса Думать — больно? Западные эксперты рассказали, как сознательно снизить уровень стресса

Мышление может причинять боль? Вот как это объясняют специалисты!

ТехИнсайдер
Почему нам нравится сериал «Эмили в Париже» и чего ожидать от выхода 4-го сезона Почему нам нравится сериал «Эмили в Париже» и чего ожидать от выхода 4-го сезона

Как «Эмили в Париже» приковывает нас к экрану?

Psychologies
«Уже и китайские бренды заменяются отечественными» «Уже и китайские бренды заменяются отечественными»

О растущей локализации производств и госпрограммах поддержки промышленности

РБК
От помощника в обучении до будущей профессии От помощника в обучении до будущей профессии

Как меняются школы и вузы под влиянием искусственного интеллекта

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

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

ТехИнсайдер
Хайп против сатиры: по-прежнему ли работы Бэнкси стоят внимания Хайп против сатиры: по-прежнему ли работы Бэнкси стоят внимания

Как Бэнкси превращается в Кэти Пэрри в мире стрит-арта

СНОБ
Замечали лицемерие? Посмотрите на 7 видов улыбок и узнайте их значение! Замечали лицемерие? Посмотрите на 7 видов улыбок и узнайте их значение!

Что улыбка может рассказать о человеке?

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