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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

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

Исследователи сообщили об успешном лечении тяжелой системной склеродермии

N+1
10 фактов, которые нужно знать мужчинам о женщинам 10 фактов, которые нужно знать мужчинам о женщинам

Семейный психотерапевт напоминает о нескольких особенностях женской психики

Psychologies
5 причин образования жира на животе 5 причин образования жира на животе

Привычки, которые способствуют образованию жира на животе и висцерального жира

ТехИнсайдер
Жилища обтекаемой формы: зачем в СССР строили дома в виде бочек Жилища обтекаемой формы: зачем в СССР строили дома в виде бочек

Дома-бочки в СССР: для кого строили эти дома и почему они были такой формы?

ТехИнсайдер
Какое пиво лучше с оливье, борщом, окрошкой: ответ специалиста Какое пиво лучше с оливье, борщом, окрошкой: ответ специалиста

Крайне необычный варианты гастрономической пары к пиву

Maxim
Контракт и досуг: какой экономический эффект дают промышленные выставки Контракт и досуг: какой экономический эффект дают промышленные выставки

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

РБК
43% российских студентов подрабатывают летом 43% российских студентов подрабатывают летом

Почти каждый второй российский студент подрабатывает этим летом, показал опрос

Forbes
Строго по записи Строго по записи

Контролировать свой рацион полезно всем без исключения

Лиза
Сергей Катырин: Проблема трансграничных платежей по-прежнему актуальна Сергей Катырин: Проблема трансграничных платежей по-прежнему актуальна

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

ФедералПресс
Как готовят будущих «айтишников» в столичных школах Как готовят будущих «айтишников» в столичных школах

Как помочь будущему айтишнику найти свое призвание

Наука и техника
Автоэксперт Пономарев рассказал, как проверить наличие фреона в автокондиционере Автоэксперт Пономарев рассказал, как проверить наличие фреона в автокондиционере

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

ТехИнсайдер
Фридрих великий Фридрих великий

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

Weekend
Виталий Коваленко: «Самое опасное в моей жизни — это съемки» Виталий Коваленко: «Самое опасное в моей жизни — это съемки»

Я прошел по краю: оказалось заряженным то оружие, которое не должно было

Караван историй
Светлана Волкова: Надо прочитать пару погонных метров исторической литературы, чтобы создать одну страничку Светлана Волкова: Надо прочитать пару погонных метров исторической литературы, чтобы создать одну страничку

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

СНОБ
Точка роста Точка роста

Регина Тодоренко: лучшее лекарство от хейта — безразличие

VOICE
Анна на кастинге Анна на кастинге

«Тайны Карениной»: документальный сериал о киногеничности романа Льва

Weekend
Время собирать камни Время собирать камни

Топ мест в России, где можно увидеть самые захватывающие валуны

2Xplore
Недетская анимация: какие реальные психические процессы показаны в мультфильме «Головоломка-2» Недетская анимация: какие реальные психические процессы показаны в мультфильме «Головоломка-2»

Какие научные доводы легли в основу «Головоломки-2»?

ТехИнсайдер
Стоит ли смотреть распиаренный «Собиратель душ» с Николасом Кейджем? Честная рецензия MAXIM Стоит ли смотреть распиаренный «Собиратель душ» с Николасом Кейджем? Честная рецензия MAXIM

Что не так с фильмом «Собиратель душ» с Николасом Кейджем?

Maxim
Один на острове Один на острове

25 вещей, которые непременно нужно сделать на Сахалине

2Xplore
Всё по минимуму Всё по минимуму

Минимализм в интерьере: как добиться лаконичности и сохранить ощущение уюта

Лиза
Город без плана Город без плана

Новосибирск: конторы, фавелы и оперный театр

Weekend
Продуманный подход вместо запретов Продуманный подход вместо запретов

Собравшиеся на форум ученые и врачи обсуждали проблематику табакокурения

Наука
Обмен любезностями Обмен любезностями

Противостояние Сталина и Троцкого в их в выступлениях и публицистических работах

Дилетант
Бабушка знала толк! Вот почему полезно есть супы: интересные факты Бабушка знала толк! Вот почему полезно есть супы: интересные факты

Супы — это не просто согревающее в холодную погоду блюдо

ТехИнсайдер
На высоте На высоте

Катерина Шпица о репутационных рисках и ощущении себя в роли «звезды»

OK!
Наша прекрасная Анастасия Заворотнюк Наша прекрасная Анастасия Заворотнюк

Карьера, обретение личного счастья и роковая болезнь Анастасии Заворотнюк

Лиза
Как выбрать лучший парашют? Как выбрать лучший парашют?

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

Наука и техника
Александр Клюквин: «Никто не работает ради зрителя. Я не работаю ради зрителя» Александр Клюквин: «Никто не работает ради зрителя. Я не работаю ради зрителя»

Пауза — это хлеб с мясом у актера

Коллекция. Караван историй
Статус или свобода: как разные поколения зарабатывают и тратят деньги Статус или свобода: как разные поколения зарабатывают и тратят деньги

Чем отличаются представления о ценности денег у разных поколений?

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