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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

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

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

ТехИнсайдер
Коллекционер Антон Козлов: На картине можно изображать любую крамолу Коллекционер Антон Козлов: На картине можно изображать любую крамолу

Коллекционер Антон Козлов — про табу в современном искусстве и страхе перед ним

СНОБ
Лайфстайл в локальном исполнении Лайфстайл в локальном исполнении

Lamoda делает акцент на уникальный ассортимент и строгий отбор брендов

Монокль
«Талантливый писатель, но сволочь»: каким был Андрей Платонов «Талантливый писатель, но сволочь»: каким был Андрей Платонов

Как Платонов призывал к расправам и террору и почему раскаивался перед Сталиным

СНОБ
Овощ в мундире Овощ в мундире

Молодой картофель – какой лучше выбрать и как приготовить?

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

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

N+1
Не подходи ко мне! Не подходи ко мне!

Если муж раздражает: почему так происходит и что с этим делать

Лиза
Мамина диета Мамина диета

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

Лиза
Переводим с манипулятивного Переводим с манипулятивного

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

Psychologies
«Архипелаг 2024»: главные инновации «Архипелаг 2024»: главные инновации

В Сахалинской области прошел проектно-образовательный интенсив «Архипелаг 2024»

ФедералПресс
Лоскутное одеяло: в стиле пэтчворк Лоскутное одеяло: в стиле пэтчворк

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

КАНТРИ Русская азбука
Как избавиться от чувства вины и стыда? Объясняет психолог Как избавиться от чувства вины и стыда? Объясняет психолог

Что скрывают за собой стыд и вина? Стоит ли избавляться от этих чувств?

VOICE
Новая жизнь Новая жизнь

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

SALON-Interior
Вперед и вверх: как начать заниматься скалолазанием и куда пойти Вперед и вверх: как начать заниматься скалолазанием и куда пойти

Быстрый гид по скалолазанию для начинающих

Правила жизни
Как быть: почему творческие профессии становятся востребованнее технических? Как быть: почему творческие профессии становятся востребованнее технических?

На кого идти учиться сейчас, чтобы быть востребованным в творческой индустрии?

Правила жизни
Моя попытка номер… Моя попытка номер…

Актеры, которые поступили в театральный вуз не с первого раза

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

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

ТехИнсайдер
«Гуслица»: творческая усадьба на территории мануфактуры «Гуслица»: творческая усадьба на территории мануфактуры

Вдали мегаполиса энтузиасты развивают на историческом месте новую арт-резиденцию

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

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

Караван историй
Самые интересные фэнтези-романы, основанные на мифах и легендах Самые интересные фэнтези-романы, основанные на мифах и легендах

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

Maxim
Держись подальше. 7 признаков токсичного партнера Держись подальше. 7 признаков токсичного партнера

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

Лиза
«Экспотехностраж-2024» с прицелом на перспективу «Экспотехностраж-2024» с прицелом на перспективу

Крупнейшее мероприятие в сфере обеспечения безопасности, «Экспотехностраж»

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

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

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

О механизме инвалидизации — о том, что неуместная помощь может приносить вред

Psychologies
Жостово: вaм букетик! Жостово: вaм букетик!

Жостовский расписной поднос — ровесник восстания декабристов

КАНТРИ Русская азбука
Как на Дальнем Востоке решают  проблемы кадрового дефицита Как на Дальнем Востоке решают  проблемы кадрового дефицита

Российская экономика активизировалась на азиатском рынке

РБК
Однажды в Белом море Однажды в Белом море

Соловки – фантастической красоты природа и наблюдение за белухами

2Xplore
Пять минут позора: как подготовиться к интервью на английском и перестать бояться Пять минут позора: как подготовиться к интервью на английском и перестать бояться

Как успешно пройти интервью, даже если ваш английский пока далек от идеала?

Forbes
Крым: как устроить человеческое житьё Крым: как устроить человеческое житьё

Летом 1920 года в Крыму царил осторожный оптимизм

Дилетант
5 секретов для достижения любой цели 5 секретов для достижения любой цели

Успех начинания, каким бы оно ни было, зависит от пяти элементов благополучия

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