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

N+1Наука

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

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

Егор Конюхов

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

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

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

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

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

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

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

Как погибли и воскресли реки Европы – и при чем здесь Олимпийские игры 2024 Как погибли и воскресли реки Европы – и при чем здесь Олимпийские игры 2024

Какой вода была раньше в Сене и других реках Европы

ТехИнсайдер
Из кожуры арбуза сделали ион-селективные мембраны Из кожуры арбуза сделали ион-селективные мембраны

Китайские материаловеды изготовили ион-селективные мембраны из кожуры арбуза

N+1
Лариса Долина отдала мошенникам миллионы — почему она и тысячи россиян доверяют им? Лариса Долина отдала мошенникам миллионы — почему она и тысячи россиян доверяют им?

Почему десятки тысяч россиян готовы отдавать деньги и квартиры мошенникам?

Psychologies
Как установить приложения на телевизор со Smart TV Как установить приложения на телевизор со Smart TV

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

CHIP
10 способов ментальной самообороны 10 способов ментальной самообороны

Хотите инструкцию, какие конкретно принять меры против манипуляций?

Psychologies
Фьюзинг: дедовский метод Фьюзинг: дедовский метод

Процесс создания красоты, «фьюзинг», — давняя и довольно традиционная технология

КАНТРИ Русская азбука
Пчелы учат дроны летать роем Пчелы учат дроны летать роем

Как дроны перенимают у пчел манеру полета

ТехИнсайдер
Кого поставить в угол Кого поставить в угол

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

Лиза
Что будет, если молния попадет в автомобиль? Что будет, если молния попадет в автомобиль?

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

Maxim
Дети и новый муж Дети и новый муж

Cоветы по сближению детей с новым партнером и основные промахи

Лиза
Как работает автопилот и чем он отличается от круиз-контроля Как работает автопилот и чем он отличается от круиз-контроля

Насколько различаются возможности автопилота и круиз-контроля в автомобиле

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

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

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

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

Правила жизни
Графомания или смерть Графомания или смерть

Что вынуждает ученых публиковать так много статей

N+1
«Чёрный бор» «Чёрный бор»

«Чёрный бор» — спорный налог для Новгородского княжества, введенный Калитой

Дилетант
Нанимать мигрантов станут по-новому: как изменится рынок труда в России Нанимать мигрантов станут по-новому: как изменится рынок труда в России

Процедура найма мигрантов может измениться в сторону ужесточения

ФедералПресс
Бесчеловечный флот Америки Бесчеловечный флот Америки

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

Обозрение армии и флота
Мир готовят к новой пандемии Мир готовят к новой пандемии

ВОЗ обновила список патогенов, способных вызвать очередную эпидемию

Монокль
Эксперт рассказал, как меньше пьянеть! Факты о толерантности к алкоголю Эксперт рассказал, как меньше пьянеть! Факты о толерантности к алкоголю

Почему одни люди могут выпить больше других?

ТехИнсайдер
Исабель Альенде «Дочь фортуны». Фрагмент из приквела романа «Дочь духов» Исабель Альенде «Дочь фортуны». Фрагмент из приквела романа «Дочь духов»

Объемная, насыщенная приключенческая история от Исабель Альенде, «Дочь фортуны»

СНОБ
Поворот в сторону профессионалов: обучение в колледжах вновь востребовано Поворот в сторону профессионалов: обучение в колледжах вновь востребовано

Как будет развиваться среднее профессиональное образование в России

ФедералПресс
Предметный разговор Предметный разговор

Искусствовед Софья Симакова рассказывает о феномене коллекционного дизайна

Правила жизни
Без перегрузок Без перегрузок

Как правильно выбрать кружок или секцию для ребенка

Лиза
С чистого листа С чистого листа

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

Лиза
Ощущение вкуса Ощущение вкуса

На что мы смотрим, когда выбираем блюдо или напиток?

Bones
Трезвые разговоры в баре: Екатерина Манойло и Михаил Турбин Трезвые разговоры в баре: Екатерина Манойло и Михаил Турбин

Что обсуждают писатели, когда встречаются в баре рано утром?

СНОБ
Письмена доколумбовой Америки Письмена доколумбовой Америки

Системы письма у майя, ацтеков, мештеков и инков

Знание – сила
50 cent, Леди Гага и другие звезды отказываются от секса: почему они это делают? 50 cent, Леди Гага и другие звезды отказываются от секса: почему они это делают?

Может ли отказ от секса изменить вашу жизнь к лучшему?

Psychologies
Мёд всему голова Мёд всему голова

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

КАНТРИ Русская азбука
Любовь наперекор Любовь наперекор

Haval H3 просто обречен на любовь – и плевать на законы физики

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