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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

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

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

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

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

Forbes
Людмила Вебер: Нажимается кнопочка «выкл» — и ты оказываешься в полной темноте, в которой надо как-то учиться жить Людмила Вебер: Нажимается кнопочка «выкл» — и ты оказываешься в полной темноте, в которой надо как-то учиться жить

Художница Людмила Вебер — о том, что она пережила по ту сторону решетки

СНОБ
Чем съемка Игр в Париже отличалась от съемки Олимпиады в Сочи — рассказывает Андрей Болтенко Чем съемка Игр в Париже отличалась от съемки Олимпиады в Сочи — рассказывает Андрей Болтенко

Почему парижское открытие Игр и революционное, и «жульническое» одновременно

СНОБ
Энергия на любой вкус Энергия на любой вкус

Всем по зарядке! — бросил клерк, обводя руками свою компанию. — Я угощаю!

Наука и жизнь
Тетёрки: насукали и жуём Тетёрки: насукали и жуём

Приготовление весенних тетерок — это всегда импровизация

КАНТРИ Русская азбука
Ученый Горелов рассказал, как найти утечки тепла в доме Ученый Горелов рассказал, как найти утечки тепла в доме

Есть ли польза от бесконтактного термометра, где искать «мостики холода»?

ТехИнсайдер
Как преодолеть финансовые конфликты в семье: практическое руководство Как преодолеть финансовые конфликты в семье: практическое руководство

Как разрешить финансовые трудности в семье и при этом укрепить свои отношения?

VOICE
Что такое датчик Холла и как его проверить: инструкция Что такое датчик Холла и как его проверить: инструкция

Все о датчике Холла: насколько он важен в автомобиле и как его проверить

РБК
Задержите дыхание! Ученые рассказали, почему запах после дождя опасен для жизни Задержите дыхание! Ученые рассказали, почему запах после дождя опасен для жизни

Знали ли вы, что вздох в дождливую погоду может оказаться последним?

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

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

ТехИнсайдер
Люди перестали пить? Вот что такое «трезвые бары»: интересный факт! Люди перестали пить? Вот что такое «трезвые бары»: интересный факт!

Почему «трезвые бары» становятся всё популярнее? О чем говорит эта тенденция?

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

О том, как создаются транспортные модели и как они работают

ТехИнсайдер
Заполнить униформу Заполнить униформу

Как армейские куртки стали инструментом борьбы с системой

Правила жизни
В России представили новый кроссовер «Москвич 8»: все подробности В России представили новый кроссовер «Москвич 8»: все подробности

Кроссовер «Москвич 8»: все подробности об этом автомобиле

РБК
Избавиться от травмы: как, зачем и что будет после? Избавиться от травмы: как, зачем и что будет после?

Что делать, чтобы преодолеть травму и начать двигаться вперед?

Psychologies
А как у них? А как у них?

9 самых странных школьных правил со всего мира

Лиза
Пристрастие родителей к алкоголю может привести к ускоренному старению их детей Пристрастие родителей к алкоголю может привести к ускоренному старению их детей

Что сильнее влияет на способность бороться с болезнями — природа или воспитание?

ТехИнсайдер
Фонотека Фонотека

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

Правила жизни
Марат Калайджян: «Людям нужна простота» Марат Калайджян: «Людям нужна простота»

Марат Калайджян — вкус во плоти, учит всех нас правильному отношению к продуктам

Bones
Дорогие и грязные: почему в Москве-реке, Ганге и Темзе нельзя купаться Дорогие и грязные: почему в Москве-реке, Ганге и Темзе нельзя купаться

В каком состоянии находятся главные водные артерии мира?

Forbes
Исповедь рэп-звезды: как фильм «Телец» показывает взлеты и падения Machine Gun Kelly Исповедь рэп-звезды: как фильм «Телец» показывает взлеты и падения Machine Gun Kelly

«Телец» — тягучая музыкальная история рэпера Колсона Бэйкера

Forbes
Нанимать мигрантов станут по-новому: как изменится рынок труда в России Нанимать мигрантов станут по-новому: как изменится рынок труда в России

Процедура найма мигрантов может измениться в сторону ужесточения

ФедералПресс
Ученые доказали, что мыслительная деятельность может приносить боль Ученые доказали, что мыслительная деятельность может приносить боль

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

ТехИнсайдер
Нежеланные попутчики Нежеланные попутчики

Даже если все вас бросят, а мир повернется к вам спиной – они останутся с вами

Зеркало Мира
У кого больше шансов на успешные знакомства и отношения — у собачников или кошатников? У кого больше шансов на успешные знакомства и отношения — у собачников или кошатников?

Кто больше помогает при знакомстве и отношениях — собака или кошка?

Maxim
Нужно ли рассказывать всю правду о себе партнеру: 3 истории Нужно ли рассказывать всю правду о себе партнеру: 3 истории

Три истории, которые доказывают: иногда не стоит раскрывать всю правду партнеру

Psychologies
Урал, любовь моя Урал, любовь моя

5 абсолютно разных граней Большой уральской тропы

2Xplore
И без Netflix хорошо И без Netflix хорошо

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

ЖАРА Magazine
«Вам звонят из…» «Вам звонят из…»

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

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