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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

У пиренейского кроманьонца выявили инвагинацию зуба У пиренейского кроманьонца выявили инвагинацию зуба

Ученые исследовали 17 зубов, которые археологи нашли в слоях верхнего палеолита

N+1
Большая маленькая Риз Уизерспун Большая маленькая Риз Уизерспун

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

Караван историй
Заполнить униформу Заполнить униформу

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

Правила жизни
Да, анальный секс без проникновения существует — и вот как им заняться! Да, анальный секс без проникновения существует — и вот как им заняться!

Как насчет того, чтобы поэкспериментировать с концепцией анального секса?

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

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

РБК
«Славянская нечисть. От природных духов и вредоносных сущностей до гостей с того света» «Славянская нечисть. От природных духов и вредоносных сущностей до гостей с того света»

«Славянская нечисть»: чем опасна полудница

N+1
«Месье поправляет пенсне» «Месье поправляет пенсне»

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

Зеркало Мира
«Тренд – опасное слово» «Тренд – опасное слово»

Дизайнер Наталья Белоногова — о том, как превратить ресторан в театральную сцену

Правила жизни
Вы невнимательны, и это совершенно нормально. Почему? Вы невнимательны, и это совершенно нормально. Почему?

С возрастом мы теряем способность к концентрации внимания. В чем же причина?

Psychologies
Почему лениться полезно Почему лениться полезно

5 неожиданных фактов о лени от врача

Лиза
Топ-5 лучших фанатских версий сериальных концовок аниме Топ-5 лучших фанатских версий сериальных концовок аниме

Поклонники аниме считают, что они смогли бы лучше закончить некоторые истории

Maxim
Что вытворяют тарантулы во время стресса и какой вид смертельно опасен для человека: 50 шокирующих фактов о пауках Что вытворяют тарантулы во время стресса и какой вид смертельно опасен для человека: 50 шокирующих фактов о пауках

Пауки не только устрашающе выглядят, но и полны загадок

ТехИнсайдер
Ученый Горелов рассказал, как найти утечки тепла в доме Ученый Горелов рассказал, как найти утечки тепла в доме

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

ТехИнсайдер
Футбол уже не тот Футбол уже не тот

Может ли самый популярный вид спорта стать еще более массовым?

Men Today
Благородный винтаж и вещи «первой руки»: почему все охотятся за антикварной мебелью Благородный винтаж и вещи «первой руки»: почему все охотятся за антикварной мебелью

Галеристы фиксируют: на рынке антикварной мебели уже третий год идет оживление

Forbes
Сад против времени. В поисках рая для всех Сад против времени. В поисках рая для всех

Глава из сборника Оливии Лэнг «Сад против времени. В поисках рая для всех»

Правила жизни
Pro bono: что такое социальная адвокатура и как получить бесплатную помощь юриста Pro bono: что такое социальная адвокатура и как получить бесплатную помощь юриста

Как в России устроена социальная адвокатура и как работает принцип pro bono

Forbes
Глава компании «Полипласт Северо-запад» — о высоких технологиях и импортозамещении Глава компании «Полипласт Северо-запад» — о высоких технологиях и импортозамещении

О важности следовать принципам бережливого производства и ESG-повестке

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

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

Bones
Гендиректор РЭО: «Необходимо создать современную инфраструктуру по утилизации отходов» Гендиректор РЭО: «Необходимо создать современную инфраструктуру по утилизации отходов»

В России с нуля создается отрасль обращения с твердыми коммунальными отходами

ФедералПресс
3 факта об истребителе F-16 3 факта об истребителе F-16

Странное название и наследие подводных лодок: что надо знать про самолет F-16.

Maxim
Солнечный нуар Солнечный нуар

«Плохая обезьяна»: новый сериал создателя «Теда Лассо»

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

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

OK!
Шитьё: нaряд вне очереди Шитьё: нaряд вне очереди

Вышивка — один из верных способов сделать внешний вид более ярким, праздничным

КАНТРИ Русская азбука
10 отличных фильмов о мотоциклах, которые должен посмотреть каждый 10 отличных фильмов о мотоциклах, которые должен посмотреть каждый

Да-да, «Криминальное чтиво» тоже вошло, детка...

Maxim
«Я встретила любовь, когда шла покупать швабру»: 14 историй о любви «Я встретила любовь, когда шла покупать швабру»: 14 историй о любви

Истории людей, которые романтично встретили по-настоящему близкого человека

Psychologies
Приручить внутренних драконов: советы для любителей спорить и бездумно говорить «да» Приручить внутренних драконов: советы для любителей спорить и бездумно говорить «да»

Проверенные стратегии для укрощения «драконов» — вредных ментальных привычек

Forbes
Энтузиазм и отвага Энтузиазм и отвага

Секрет петербургского ресторанного феномена — это энтузиазм его создателей

Монокль
Женский взгляд: 10 красных флагов в дейтинг-приложениях Женский взгляд: 10 красных флагов в дейтинг-приложениях

Десять стоп-сигналов, которые говорят женщинам: «Не стоит ему отвечать»

Psychologies
Финтех, крипта, долларизация: как Латинская Америка справляется с валютным хаосом Финтех, крипта, долларизация: как Латинская Америка справляется с валютным хаосом

В Латинской Америке появилась россыпь стартапов-«единорогов» в финтех-сфере

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