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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

Терраформирование Марса уже не фантастика Терраформирование Марса уже не фантастика

Для терраформирования Марса необходимо увеличить его температуру на 10°C

ТехИнсайдер
«У меня лучше!»: почему некоторые люди так любят хвастаться? «У меня лучше!»: почему некоторые люди так любят хвастаться?

Почему люди любят хвастаться? Это норма или патология?

Psychologies
Зловещие пятна на теле планеты Зловещие пятна на теле планеты

16 июля 1945 года человечество, само еще не подозревая, вступило в атомную эру

Наука и техника
Полина Оганичева Полина Оганичева

Звезда международных съемок и показов трижды становилась героиней обложек

Grazia
Сталкер, топор и подземные боги: Игорь Яковенкo выпустил языческий альбом «Пантеон» Сталкер, топор и подземные боги: Игорь Яковенкo выпустил языческий альбом «Пантеон»

Композитор Игорь Яковенко и барабанщик Петр Ившин выпускают альбом «Пантеон»

СНОБ
Исследование: женщины должны начинать ежегодную маммографию в возрасте 40 лет Исследование: женщины должны начинать ежегодную маммографию в возрасте 40 лет

Когда женщинам следует начинать делать маммографию? Ответ есть!

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

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

Maxim
Подо льдами Подо льдами

Плавание подводных лодок подо льдами теперь стало обыденным явлением

Наука и техника
Наличники (или шоу «Окна») Наличники (или шоу «Окна»)

Почему резные наличники получили распространение именно в России?

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

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

ТехИнсайдер
Единственно правильная закуска к виски Единственно правильная закуска к виски

Кто сказал, что виски не закусывают?

Maxim
Держали в секрете 20 лет! Американцы нашли руины корабля пиратов с Варварийского берега Держали в секрете 20 лет! Американцы нашли руины корабля пиратов с Варварийского берега

Обнаруженный затонувший пиратский корабль — первый в своем роде

ТехИнсайдер
Японский бот тебе товарищ Японский бот тебе товарищ

«Санни»: сериал-инструкция по мирному сосуществованию с роботами

Weekend
Кто такой Тим Уолц и как учитель с военным прошлым стал кандидатом в вице-президенты Кто такой Тим Уолц и как учитель с военным прошлым стал кандидатом в вице-президенты

Как губернатор штата Миннесота Тим Уолц смог сколотить состояние

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

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

ТехИнсайдер
Триколор и Булочка: 39 текстов про тело в одной книге Триколор и Булочка: 39 текстов про тело в одной книге

Тема телесности раскрывается в тридцати девяти текстах «Тело: у каждого свое»

СНОБ
Жизнь на Земле была сложной уже 2 миллиарда лет назад Жизнь на Земле была сложной уже 2 миллиарда лет назад

Сложные организмы появились не позднее 2,1 миллиарда лет назад

ТехИнсайдер
Мамина диета Мамина диета

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

Лиза
Как себе помочь, если нет денег на психолога? Как себе помочь, если нет денег на психолога?

Как помочь себе самостоятельно, развивая осознанность?

VOICE
Что такое «фанфляция», или почему у вас так мало денег на банковской карте Что такое «фанфляция», или почему у вас так мало денег на банковской карте

«Фанфляция» — на чем строится современная культура потребления

Psychologies
От полосатой робы до красных галифе: изломы судьбы Мишки Япончика От полосатой робы до красных галифе: изломы судьбы Мишки Япончика

Как главарь одесских уголовников Мишка Япончик оказался в Красной армии?

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

Несколько денежных типов личности, которые определяют подход людей к деньгам

ТехИнсайдер
Хайп против сатиры: по-прежнему ли работы Бэнкси стоят внимания Хайп против сатиры: по-прежнему ли работы Бэнкси стоят внимания

Как Бэнкси превращается в Кэти Пэрри в мире стрит-арта

СНОБ
Искусство керамики Искусство керамики

Как найти творческое хобби, которое в то же время будет полезно для ресторана

Bones
Уильям Гершель и музыка небесных сфер Уильям Гершель и музыка небесных сфер

Уильям Гершель, великий астроном, раздвинувший для нас границы Солнечной системы

Наука и техника
Сколько зарабатывает дальнобойщик и как им стать Сколько зарабатывает дальнобойщик и как им стать

Как стать дальнобойщиком и сколько он зарабатывает, выяснил Autonews.ru

РБК
15 модных словечек и фраз, которые стоит позаимствовать из словаря зумеров 15 модных словечек и фраз, которые стоит позаимствовать из словаря зумеров

Разбираем зумерский сленг, чтобы найти с ними общий язык

Psychologies
Не только привлечение внимания: 9 причин, почему взрослые устраивают истерики Не только привлечение внимания: 9 причин, почему взрослые устраивают истерики

Почему взрослые устраивают истерики и как правильно на это реагировать?

Psychologies
Психолог о демографической проблеме: «Мы подсели на иглу комфорта» Психолог о демографической проблеме: «Мы подсели на иглу комфорта»

Почему молодые люди не стремятся заводить семьи

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

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

ТехИнсайдер
Открыть в приложении