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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

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

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

Psychologies
Женские секреты. Неудобные вопросы гинекологу, которые многие стесняются задать Женские секреты. Неудобные вопросы гинекологу, которые многие стесняются задать

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

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

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

Psychologies
Главное — сохранять спокойствие: каковы действия пилота, если перед посадкой отказали шасси Главное — сохранять спокойствие: каковы действия пилота, если перед посадкой отказали шасси

Что может произойти в случае, если шасси перед посадкой самолета не выпускаются

ТехИнсайдер
Красавицы и чудовище. Почему Хичкок был одержим блондинками Красавицы и чудовище. Почему Хичкок был одержим блондинками

В чем загадка «хичкоковских блондинок»

СНОБ
Защита краснокнижных растений и животных: один из национальных приоритетов Защита краснокнижных растений и животных: один из национальных приоритетов

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

ФедералПресс
Дом из дерева Дом из дерева

Деревянный дом — это целый мир со своими правилами, устоями и обычаями

КАНТРИ Русская азбука
«Всюду одно растление и разврат» «Всюду одно растление и разврат»

Андрей Платонов о том, как он не стал советским писателем

Weekend
Культовые кроссовки, выпуск 19: Nike Air Max 95 — самая популярная модель в Японии Культовые кроссовки, выпуск 19: Nike Air Max 95 — самая популярная модель в Японии

Nike Air Max 95 во многом определила траекторию движения Nike

Правила жизни
Новая жизнь Новая жизнь

Вилла в Сочи с интерьером вне времени

SALON-Interior
Наш человек! Наш человек!

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

Лиза
Точно в срок: 7 советов любителям опозданий Точно в срок: 7 советов любителям опозданий

Вы изо всех сил стараетесь приходить вовремя, но постоянно опаздываете?

Psychologies
Грифонаж, страпонтен, глабелла, нёрдл: необычные названия привычных вещей Грифонаж, страпонтен, глабелла, нёрдл: необычные названия привычных вещей

Грифонаж, страпонтен, петрикор: вы точно знаете эти вещи

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

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

N+1
Тандыр Тандыр

Тандыры и еду из них можно встретить на всем протяжении Великого шелкового пути

Bones
Николай Горинович: изуродованный революционер, ставший праведником Николай Горинович: изуродованный революционер, ставший праведником

Николай Горинович был революционером, которого пытались убить его же соратники

СНОБ
Вредные советы из СССР Вредные советы из СССР

8 кулинарных лайфхаков, которым не стоит следовать

Лиза
Не морем единым Не морем единым

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

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

Как создать комфортную и поддерживающую среду для ребенка с РАС

Psychologies
«Я не люблю своего ребенка»: что делать, если это про вас «Я не люблю своего ребенка»: что делать, если это про вас

Нелюбовь: что делать, если ваш ребенок не вызывает у вас эмоций?

Psychologies
Бесчеловечный флот Америки Бесчеловечный флот Америки

Основные программы в области создания надводных роботизированных систем ВМС США

Обозрение армии и флота
«Главный вызов — создание нового уровня жизни» «Главный вызов — создание нового уровня жизни»

Алексей Чекунков о том, как решается кадровый дефицит на Востоке

РБК
Химики использовали иодид самария как катализатор Химики использовали иодид самария как катализатор

Как химики научились применять иодид самария в каталитических количествах

N+1
Как пустышка становится лекарством: что общего у гомеопатии и психотерапии Как пустышка становится лекарством: что общего у гомеопатии и психотерапии

Почему плацебо помогает при болезни Паркинсона?

Forbes
«Как я разденусь?»: 8 неочевидных причин, которые мешают достичь оргазма «Как я разденусь?»: 8 неочевидных причин, которые мешают достичь оргазма

Что мешает вам получать удовольствие от близости с любимым человеком?

Psychologies
Заполнить униформу Заполнить униформу

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

Правила жизни
Вопрос века Вопрос века

Как правильно ухаживать за кожей вокруг глаз, чтобы не было «вековых» проблем?

Лиза
Щи: вoт она, скрепа! Щи: вoт она, скрепа!

Щи случались на столах наших предков чаще, чем что-либо еще

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

Халатное отношение к собственному здоровью способно сильно укоротить вашу жизнь

Psychologies
Еръ: читaем вывески Еръ: читaем вывески

Ер твою направо! — не ругательство, а стремление придать бренду основательности

КАНТРИ Русская азбука
Открыть в приложении