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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

Есть ли способы меньше потеть? Есть ли способы меньше потеть?

Как уменьшить избыточное потоотделение и начать жить?

Maxim
Синдром Адели: что это простыми словами Синдром Адели: что это простыми словами

Иногда симпатия может перерастать в одержимость: что такое синдром Адели

Psychologies
Шестое чувство Шестое чувство

Не отвлекают ли от главного приемы мультисенсорного маркетинга?

Bones
Многоразовый космический корабль Многоразовый космический корабль

Как космический корабль «Буран» опередил свое время

Наука и техника
Хроника отравления Хроника отравления

Что раскручивает маховик школьной агрессии и как его затормозить?

Psychologies
Наличники (или шоу «Окна») Наличники (или шоу «Окна»)

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

КАНТРИ Русская азбука
Медиатор: кто это и чем занимается Медиатор: кто это и чем занимается

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

Psychologies
Кто предупрежден, тот вооружен Кто предупрежден, тот вооружен

Что делать, если родители или друзья пытаются давить на нас в своих интересах?

Psychologies
Лето в активе Лето в активе

Если лежать на пляже скучновато, почему бы не попробовать другие виды отдыха?

Лиза
Не те хромосомы, много тестостерона: почему на Олимпиадах так много гендерных скандалов Не те хромосомы, много тестостерона: почему на Олимпиадах так много гендерных скандалов

Кто такие интерсекс-люди и почему из-за них возникают скандалы на Олимпиаде?

Psychologies
Помнить все! Помнить все!

7 привычек, которые помогут снизить риск деменции

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

Вы плачете и ищете у него утешения, а он только злится?

Psychologies
Нобелевские премии по физике в контексте истории Нобелевские премии по физике в контексте истории

Как Карл Озеен сделал все, чтобы Эйнштейн получил заслуженную Нобелевскую премию

Наука и жизнь
Что заставляет нас заводить отношения: 3 ложных мотива Что заставляет нас заводить отношения: 3 ложных мотива

Какие мотивы вступить в отношения можно назвать истинными, а какие ложными?

Psychologies
Муж приковал ее на 40 дней к дереву! Как американка пережила домашнее насилие Муж приковал ее на 40 дней к дереву! Как американка пережила домашнее насилие

История женщины, которую бывший муж оставил в джунглях умирать

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

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

ТехИнсайдер
Что такое дроссельная заслонка, за что она отвечает и как работает Что такое дроссельная заслонка, за что она отвечает и как работает

Дроссельный узел – один из важнейших элементов управления двигателя

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

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

СНОБ
«Звездная болезнь»: плюсы, минусы, последствия для «больного» и окружающих «Звездная болезнь»: плюсы, минусы, последствия для «больного» и окружающих

Как распознать в себе и близких симптомы «звездной болезни» и спастись от них?

Psychologies
Молнии над водой Молнии над водой

Как выглядят гонки Formula E1 на электрических лодках с подводным крылом?

ТехИнсайдер
Как художница Луиз Буржуа осмысляла травматичное детство и материнский опыт Как художница Луиз Буржуа осмысляла травматичное детство и материнский опыт

Каково это — быть способной создать новую жизнь, но ощущать себя несвободной?

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

Кто и как изобрел первый компактный аналоговый информационный носитель

Правила жизни
Чистота душевная, любовь нелицемерная Чистота душевная, любовь нелицемерная

Сергий Радонежский – один из самых почитаемых православных святых

Зеркало Мира
Ингибирование гистондеацетилазы 3 улучшило реконсолидацию памяти у старых мышей Ингибирование гистондеацетилазы 3 улучшило реконсолидацию памяти у старых мышей

Фермент гистондеацетилаза 3 участвует в реконсолидации памяти

N+1
7 практик для замедления и осознанности на каждый день 7 практик для замедления и осознанности на каждый день

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

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

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

Наука и техника
Что будет, если молния попадет в автомобиль? Что будет, если молния попадет в автомобиль?

Чем грозит разряд электричества небесной канцелярии машине и водителю.

Maxim
Природа Черногории и гастрономия Адриатики: что делать в Будве и окрестностях Природа Черногории и гастрономия Адриатики: что делать в Будве и окрестностях

Чем заняться в Будве и окрестностях во время путешествия

Forbes
С того цвета С того цвета

«Правила жизни» разбираются в истории цвета

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

Какие виды царапин бывают на автомобиле и как их убрать

РБК
Открыть в приложении